January 06, 2021 Anonymous Communication from Multiparty Shuffling Protocols
Speaker: Saba Eskandarian
Abstract: This paper studies the role of multiparty shuffling protocols in enabling more efficient metadata-hiding communication. We show that the process of shuffling messages can be expedited by having servers collaboratively shuffle and verify secret-shares of messages instead of using a conventional mixnet approach where servers take turns performing independent verifiable shuffles of user messages. We apply this technique to achieve both practical and asymptotic improvements in anonymous broadcast and messaging systems. We first show how to build a three server anonymous broadcast scheme, secure against one malicious server, that relies only on symmetric cryptography and has optimal asymptotic performance. Next, we show how this scheme can be used to significantly improve the performance of the MCMix anonymous messaging system. Finally, we adapt our three server broadcast scheme to a k-server scheme secure against k-1 malicious servers, at the cost of a more expensive per-shuffle preprocessing phase.
We implement our shuffling protocol and find that it outperforms mixnets by 9.2x for broadcasting small messages and outperforms the MCMix conversation protocol by 11.8x.Joint work with: Dan Boneh
January 13, 2021 Differentially private learning needs better features
Speaker: Florian Tramèr
Abstract: In the first part of this talk, I'll motivate the need for training machine learning models with differential privacy guarantees, by drawing on recent examples of privacy failures. In the second part, I'll demonstrate that differentially private machine learning still has a long way to go to become practical. For many canonical vision tasks, I'll show that "old-school" computer vision algorithms with handcrafted features significantly outperform end-to-end deep neural networks for moderate privacy budgets.
February 03, 2021 Protecting Cryptography Against Compelled Self-Incrimination
Speaker: Sarah Scheffler (Boston University)
Abstract: The information security community has devoted substantial effort to the design, development, and universal deployment of strong encryption schemes that withstand search and seizure by computationally-powerful nation-state adversaries. In response, governments are increasingly turning to a different tactic: issuing subpoenas that compel people to decrypt devices themselves, under the penalty of contempt of court if they do not comply. Compelled decryption subpoenas sidestep questions around government search powers that have dominated the Crypto Wars and instead touch upon a different (and still unsettled) area of the law: how encryption relates to a person's right to silence and against self-incrimination.
In this work, we provide a rigorous, composable definition of a critical piece of the law that determines whether cryptosystems are vulnerable to government compelled disclosure in the United States. We justify our definition by showing that it is consistent with prior court cases. We prove that decryption is often not compellable by the government under our definition. Conversely, we show that many techniques that bolster security overall can leave one more vulnerable to compelled disclosure.As a result, we initiate the study of protecting cryptographic protocols against the threat of future compelled disclosure. We find that secure multi-party computation is particularly vulnerable to this threat, and we design and implement new schemes that are provably resilient in the face of government compelled disclosure. We believe this work should influence the design of future cryptographic primitives and contribute toward the legal debates over the constitutionality of compelled decryption.Joint work with: Mayank Varia
February 10, 2021 Raccoon Attack: Finding and Exploiting Most-Significant-Bit-Oracles in TLS-DH(E)
Speaker: Robert Merget & Markus Brinkmann (Ruhr-Universität Bochum)
Abstract: Diffie-Hellman key exchange (DHKE) is a widely adopted method for exchanging cryptographic key material in real-world protocols like TLS-DH(E). Past attacks on TLS-DH(E) focused on weak parameter choices or missing parameter validation. The confidentiality of the computed DH share, the premaster secret, was never questioned; DHKE is used as a generic method to avoid the security pitfalls of TLS-RSA.
We show that due to a subtle issue in the key derivation of all TLS-DH(E) cipher suites in versions up to TLS 1.2, the premaster secret of a TLS-DH(E) session may, under certain circumstances, be leaked to an adversary. Our main result is a novel side-channel attack, named Raccoon attack, which exploits a timing vulnerability in TLS-DH(E), leaking the most significant bits of the shared Diffie-Hellman secret. The root cause for this side channel is that the TLS standard encourages non-constant-time processing of the DH secret. If the server reuses ephemeral keys, this side channel may allow an attacker to recover the premaster secret by solving an instance of the Hidden Number Problem. The Raccoon attack takes advantage of uncommon DH modulus sizes, which depend on the properties of the used hash functions. We describe a fully feasible remote attack against an otherwise-secure TLS configuration: OpenSSL with a 1032-bit DH modulus. Fortunately, such moduli are not commonly used on the Internet.Furthermore, with our large-scale scans we have identified implementation-level issues in production-grade TLS implementations that allow for executing the same attack by directly observing the contents of server responses, without resorting to timing measurements.Paper: USENIX Security '21
February 17, 2021 Unifying Compilers for SNARKs, SMT, and More
Speaker: Alex Ozdemir
Abstract: The programming languages community, the cryptography community, and others rely on translating programs in high-level source languages (e.g., C) to logical constraint representations. Unfortunately, building compilers for this task is difficult and time consuming. In this work, we present CirC, an infrastructure for building compilers for SNARKs that builds upon a common abstraction: stateless, non-deterministic computations called existentially quantified circuits, or EQCs. Circ support multiple inputs languages and multiple target circuit representations. We use is to easily build an alternate compiler for the ZoKrates language which outperforms the language's reference compiler. We also use CirC to combine the applications of SNARKs and SMT: we do basic SMT-assisted optimization and find & prove knowledge of program vulnerabilities, in zero-knowledge.
Joint work with: Fraser Brown & Riad S. Wahby
Paper: ePrint 2020/1586
February 24, 2021 JAW: Studying Client-side CSRF with Hybrid Property Graphs and Declarative Traversals
Speaker: Soheil Khodayari (CISPA)
Abstract: Client-side CSRF is a new type of CSRF vulnerability where the adversary can trick the client-side JavaScript program to send a forged HTTP request to a vulnerable target site by modifying the program’s input parameters. We have little to-no knowledge of this new vulnerability, and exploratory security evaluations of JavaScript-based web applications are impeded by the scarcity of reliable and scalable testing techniques. This paper presents JAW, a framework that enables the analysis of modern web applications against client-side CSRF leveraging declarative traversals on hybrid property graphs, a canonical, hybrid model for JavaScript programs. We use JAW to evaluate the prevalence of client-side CSRF vulnerabilities among all (i.e., 106) web applications from the Bitnami catalog, covering over 228M lines of JavaScript code. Our approach uncovers 12,701 forgeable client-side requests affecting 87 web applications in total. For 203 forgeable requests, we successfully created client-side CSRF exploits against seven web applications that can execute arbitrary server-side state-changing operations or enable cross-site scripting and SQL injection, that are not reachable via the classical attack vectors. Finally, we analyzed the forgeable requests and identified 25 request templates, highlighting the fields that can be manipulated and the type of manipulation.
March 03, 2021 Proof-Carrying Data without Succinct Arguments
Speaker: Benedikt Bünz
Abstract: Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Prior approaches to construct PCD are based on recursive applications of succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this talk I will describe how to obtain PCD without relying on SNARKs. In particular, we construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. We then exploit this new framework to achieve a more efficient PCD construction, by giving an accumulation scheme for a non-interactive argument of knowledge for R1CS with constant verification time. Concretely the recursive circuit can be as small as 3 exponentiations in a group with hard discrete logarithm. We also avoid the use of FFTs and other structure in the cryptographic group. Our results are supported by a modular and efficient implementation.
Paper: ePrint 2020/1618
March 10, 2021 Halo Infinite: Proof-carrying data from any additive polynomial commitment
Speaker: Ben Fisch
Abstract: Polynomial commitment schemes (PCS) have recently been in the spotlight for their key role in building SNARKs. A PCS provides the ability to commit to a polynomial over a finite field and prove its evaluation at points. Proof-carrying data (PCD) enables a set of parties to carry out an indefinitely long distributed computation where every step along the way is accompanied by a proof of correctness. It generalizes incrementally verifiable computation and can even be used to construct SNARKs. Until recently, however, the only known method for constructing PCD required expensive SNARK recursion. A system called Halo first demonstrated a new methodology for building PCD without SNARKs, exploiting an aggregation property of the Bulletproofs polynomial commitment scheme. We expand upon this methodology to show that PCD can be (heuristically) built from any homomorphic PCS, even if the PCS evaluation proofs are neither succinct nor efficient. In fact, the Halo methodology extends to any PCS that has an even more general property, namely the ability to aggregate linear combinations of commitments into a new succinct commitment that can later be opened to this linear combination. Our results thus imply new constructions of SNARKs and PCD that were not previously described in the literature and serve as a blueprint for future constructions as well.
Paper: ePrint 2020/1536
March 17, 2021 RSA Signatures Under Hardware Restrictions
Speaker: Yan Michalevsky
Abstract: We would like to compute RSA signatures with the help of a Hardware Security Module (HSM). But what can we do when we want to use a certain public exponent that the HSM does not allow or support? Surprisingly, this scenario comes up in real-world settings such as code-signing of Intel SGX enclaves. Intel SGX enclaves have to be signed in order to execute in release mode, using 3072-bit RSA signature scheme with a particular public exponent. However, we encountered commercial hardware security modules that do not support storing RSA keys corresponding to this exponent. We ask whether it is possible to overcome such a limitation of an HSM and answer it in the affirmative (under stated assumptions). We show how to convert RSA signatures corresponding to one public exponent, to valid RSA signatures corresponding to another exponent. We define security and show that it is not compromised by the additional public knowledge available to an adversary in this setting.