International Association
for Cryptologic Research

We present STIR (Shift To Improve Rate), a concretely efficient interactive oracle proof of proximity (IOPP) for Reed--Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. Roughly, in order to achieve $\lambda$ bits of security, STIR has query complexity $O(\log d + \lambda \cdot \loglog d )$, while the popular FRI protocol (including variants based on conjectured security assumptions) has query complexity $O(\lambda \cdot \log d )$. STIR relies on a new technique for recursively reducing the degree of the function being tested while simultaneously improving the rate. We provide an implementation of STIR compiled to a SNARK. Compared to FRI, our implementation achieves an improvement in argument size that ranges from $1.25\times$ to $2.46\times$ depending on the chosen parameters. For example, in order to achieve 128 bits of security for degree $2^{26}$ and rate $1/4$, STIR has argument size $114$~KiB, compared to $211$~KiB for FRI.

Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class $\mathcal{SZK}$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $\mathcal{BPP}^{\mathcal{SZK}}$. This poses a barrier for building advanced cryptography from code-based assumptions such as Learning Parity with Noise (LPN), as LPN is only known to be in $\mathcal{BPP}^{\mathcal{SZK}}$ under an extremely low noise rate $\frac{\log^2 n}{n}$, for which it is broken in quasi-polynomial time. In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class $\mathcal{BPP}^{\mathcal{SZK}}$ and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece's cryptosystem and random $k\mbox{-}$XOR in average-case complexity. Roughly, the assumption states that \[(\mathbf{T}\, \mathbf{M}, \mathbf{s} \,\mathbf{T}\, \mathbf{M} + \mathbf{e}) \quad \text{is indistinguishable from}\quad (\mathbf{T} \,\mathbf{M}, \mathbf{u}),\] for a random (dense) matrix $\mathbf{T}$, random sparse matrix $\mathbf{M}$, and sparse noise vector $\mathbf{e}$ drawn from the Bernoulli distribution with inverse polynomial noise probability. We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate $\frac{\log^2 n}{n}$ that is only quasi-polynomially secure.

We provide two improvements to Regev's recent quantum factoring algorithm (arXiv:2308.06572), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $\approx \sqrt{n}$ times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling \emph{in-place} quantum-quantum modular multiplication. This implementation works with only black-box access to any quantum circuit for \emph{out-of-place} modular multiplication, which we believe is yet another result of potentially broader interest. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $\approx \sqrt{n}$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.

Since their introduction over two decades ago, physical side-channel attacks have presented a serious security threat. While many ciphers’ implementations employ masking techniques to protect against such attacks, they often leak secret information due to unintended interactions in the hardware. We present Rosita, a code rewrite engine that eliminates such leakage. Rosita uses a leakage emulator which we amended to correctly emulate leakage from the target system and then rewrites the code to eliminate that leakage. We use Rosita to automatically protect masked implementations of AES and Xoodoo and show the absence of observable leakage at only a 25% penalty to the performance.

The initial cryptographic instruction set extension of RISC-V is looking stable and is approaching a specification freeze. Implementations exist and evaluation is ongoing on multiple fronts. In this talk, we discuss lightweight, ``scalar crypto''' instructions that have been introduced to the specification during the past year. These instructions directly extend the base RV32 and RV64 instruction set, removing the requirement of implementing a vector or SIMD unit. We hope that this makes RISC-V even more attractive for embedded chip vendors. We describe how AES, SHA2/3, and GCM can be implemented and optimized with base 32/64-bit register file, and how Entropy Sources are accessed to build hardware TRNGs. We also give pointers on efficient asymmetric (ECC, RSA, PQC) implementations on such targets, and describe how tightly-coupled custom accelerators and side-channel mitigations can be integrated.

Intel’s Software Guard Extensions (SGX) promises an isolated execution environment, protected from all software running on the machine. However, a significant limitation of SGX is its lack of protection against side-channel attacks. In particular, Intel states that side channel attacks our outside of SGX’s threat model, stating that “it is the developer's responsibility to address side-channel attack concerns”. In this talk we will discuss CacheOut, a new transient execution attack that is capable of extracting data across virtually all hardware-backed security domains. Unlike previous Microarchitectural Data Sampling Attacks (MDS), which were limited to leaking structured data form internal CPU buffers, CacheOut is able to leak data from the CPU’s L1-D cache, while giving the attacker control of what address to leak from the victim’s address space. After presenting CacheOut’s ability to leak random-looking data such as encryption keys from OpenSSL across process and virtual machine boundaries, we will discuss CacheOut’s applicability to breach SGX’s confidentiality by leaking arbitrary data from SGX enclaves. Besides being able to extract arbitrary enclaved data from fully-patched machines, we will show that CacheOut can be leveraged to compromise the EPID attestation keys of machines properly configured to pass Intel’s remote attestation protocol. With production attestation keys at hand, we are able to pass fake enclaves as genuine, issue fake attestation quotes, or even allow AMD machines to pass as genuine Intel hardware. Next, we analyze the impact of SGX breaches on several emerging SGX applications such as Signal’s communication app and Town Crier, an SGX-based blockchain application. We will show how SGX-based systems often fail in the presence of side channels, despite explicit attempts by developers to provide resilience in case of SGX breaches. Finally, we will discuss disclosure timelines, showing how SGX’s microcode-based patching model prohibits rapid patching, forcing developers to trust machines using compromised microcode. The talk will be given by Daniel Genkin and Stephan van Schaik, be amid at a cryptographic audience and include demonstrations. https://cacheoutattack.com/.

At RWC 2019 we presented a black-box security evaluation of the the keyless entry system employed within the Tesla Model S [WMA+19]. Our analysis revealed that these high-end vehicles could be stolen in a matter of seconds, this was made possible by an inadequate proprietary cipher. Tesla released a second iteration of this key fob, upgrading to a newer version of the proprietary cipher. We later demonstrated that this new version was in fact vulnerable to a downgrade attack [WVdHG+20]. In response Tesla released an over-the-airsoftware update which allowed users to self service their key fob. In contrast, this presentation will cover a security evaluation of the keyless entry system used in the Tesla Model X. This modern-day system was developed in-house by Tesla. The key fob uses Bluetooth Low Energy to communicate with the car, and both the key fob and car use a Common Criteria EAL5+ certified secure element to perform security critical operations. Even though this system was clearly designed with security in mind we demonstrate how a pair of vulnerabilities can be combined to completely bypass the secure public-key and symmetric-key cryptograhpic primitives that are used within this system. Therefore,this talk could serve as a yearly reminder of Shamir’s third law of security which states that cryptography is typically bypassed, not penetrated. To demonstrate the practical impact of our findings we implement a proof-of-concept attack, demonstrating that we could gain interior access to, and drive off with a Tesla Model X in a matter of minutes. The only prerequisite for an attacker is to be within five meters of the legitimate key fob for a few seconds. We want to stress that this is not a classical relay attack, our findings result in permanent access to the vehicle similar to any legitimate key fob. During this talk we will describe our reverse engineering efforts covering both the keyfob as well as the body control module located inside the vehicle. We will uncover the identified vulnerabilities and will showcase a proof-of-concept attack allowing an adversary to drive off with the car in a matter of minutes. We will provide insight into the internal workings of this system from both the key fob and vehicle side as well as the procedure used by Tesla service centers to pair a key fob to the car. This research once again demonstrates the difficulties faced, even by experienced security professionals, to implement a real-world system securely. By doing so we also demonstrate the importance of security evaluation methods, secure building blocks that are impossible or difficult to implement incorrectly, and secure example code provided by silicon vendors.

Computer-aided cryptography is an active area of research that develops and applies formal, machine-checkable approaches to the design, analysis, and implementation of cryptography. We present a cross-cutting systematization of the computer-aided cryptography literature, focusing on three main areas: (i) design-level security (both symbolic security and computational security), (ii) functional correctness and efficiency, and (iii) implementation-level security (with a focus on digital side-channel resistance). In each area, we first clarify the role of computer-aided cryptography---how it can help and what the caveats are---in addressing current challenges. We next present a taxonomy of state-of-the-art tools, comparing their accuracy, scope, trustworthiness, and usability. Then, we highlight their main achievements, trade-offs, and research challenges. After covering the three main areas, we present two case studies. First, we study efforts in combining tools focused on different areas to consolidate the guarantees they can provide. Second, we distill the lessons learned from the computer-aided cryptography community's involvement in the TLS 1.3 standardization effort. Finally, we conclude with recommendations to paper authors, tool developers, and standardization bodies moving forward.

Verifpal is a new automated modeling framework and verifier for cryptographic protocols, optimized with heuristics for common-case protocol specifications, that aims to work better for real-world practitioners, students and engineers without sacrificing comprehensive formal verification features. In order to achieve this, Verifpal introduces a new, intuitive language for modeling protocols that is easier to write and understand than the languages employed by existing tools. Its formal verification paradigm is also designed explicitly to provide protocol modeling that avoids user error. Verifpal is able to model protocols under an active attacker with unbounded sessions and fresh values, and supports queries for advanced security properties such as forward secrecy or key compromise impersonation. Furthermore, Verifpal's semantics have been formalized within the Coq theorem prover, and Verifpal models can be automatically translated into Coq as well as into ProVerif models for further verification. Verifpal has already been used to verify security properties for Signal, Scuttlebutt, TLS 1.3 as well as the first formal model for the DP-3T pandemic-tracing protocol, which we present in this work. Through Verifpal, we show that advanced verification with formalized semantics and sound logic can exist without any expense towards the convenience of real-world practitioners.

No abstract

Threshold wallets leverage threshold signature schemes (TSS) to distribute signing rights across multiple parties when issuing blockchain transactions. These provide greater assurance against insider fraud, and are sometimes seen as an alternative to methods using a trusted execution environment to issue the signature. This new class of applications motivated researchers to discover better protocols, entrepreneurs to create start-up companies, and large organizations to deploy TSS-based solutions. For example, the leading cryptocurrency exchange (in transaction volume) adopted TSS to protect some of its wallets. Although the TSS concept is not new, this is the first time that so many TSS implementations are written and deployed in such a critical context, where all liquidity reserves could be lost in a minute if the crypto fails. Furthermore, TSS schemes are sometimes extended or tweaked to best adapt to their target use case---what could go wrong? This paper, based on the authors' experience with building and analyzing TSS technology, describes three different attacks on TSS implementations used by leading organizations. Unlike security analyses of on-paper protocols, this work targets TSS as deployed in real applications, and exploits logical vulnerabilities enabled by the extra layers of complexity added by TSS software. The attacks have concrete applications, and could for example have been exploited to empty an organization's cold wallet (typically worth at least an 8-digit dollar figure). Indeed, one of our targets is the cold wallet system of the biggest cryptocurrency exchange (which has been fixed after our disclosure).

Turning academic research into a reliable and safe product is a tremendous and challenging effort, requiring additional applications of ideas from many areas of computer science. In particular there is a substantial gap to be bridged between the high level cryptographic research papers specifying a protocol and its real-world implementation. In this talk, we discuss the involved challenges and lessons learned from implementing the consensus layer for Cardano.

Distributed randomness beacons allow a number of parties to periodically obtain fresh random outputs in such a way that they can verify these outputs are correctly generated while being able to prove to any third party that a given random output was previously obtained at a certain period. These schemes find a number of real world applications towards achieving anonymity and privacy in many scenarios as well as being central building blocks of consensus protocols. The emergence of provably secure Proof-of-Stake blockchains and other decentralized applications has sparked a renewed interest in constructing more efficient and robust randomness beacons, yielding a multitude of constructions based on different techniques, ranging from traditional secret sharing to timing based primitives such as verifiable delay functions. In this talk, we survey recent results on randomness beacons, focusing on our results covering a wide range of building blocks and their respective assumptions: Publicly Verifiable Secret Sharing (e.g. ALBATROSS), Verifiable Random Functions (e.g. Ouroboros Praos) and Time-lock Puzzles (e.g. CRAFT). We classify distributed randomness beacon protocols in terms of their security guarantees, their bias (or lack of thereof) and their complexity. We cover randomness beacons based on traditional techniques such as threshold schemes (i.e. secret sharing and threshold signatures) and verifiable random functions, as well as protocols based on timed primitives such as verifiable delay functions (e.g. Boneh et al.) and time-lock puzzles. We present basic constructions of randomness beacons based on each of these primitives, pointing out the scenarios where each has a (dis)advantage. Moreover, we discuss the communication channel synchronicity assumptions (and consensus guarantees) under which these beacons can be proven secure. We aim at informing the real world cryptography community of the scenarios where each beacon may perform better, as well as potential pitfalls in employing each of them. Towards this goal, we also discuss the necessary setup assumptions and procedures needed for each construction and how these fit into threat models considered in practical applications such as different flavors of Proof-of-Stake blockchain protocols, which crucially rely on randomness beacons for their security. We also strive to describe the optimistic randomness beacon constructions in our recent works (ALBATROSS and CRAFT), which achieve much better concrete performance than current approaches in case parties behave honestly, only falling back to more expensive procedures/techniques in case it is necessary to recover from cheating. Finally, we identify directions for future work on real world randomness beacons aiming at improving their efficiency and/or providing novel useful features.

This talk introduces a new direction of research for searchable symmetric encryption (SSE). In contrast to previous research in SSE which focussed only on leakage from the encrypted index component of SSE, we consider the system-wide security of SSE schemes, encompassing both encrypted indices and encrypted documents. The SWiSSSE scheme that we present provably meets a strong, system-side security definition; our proof is complemented by cryptanalysis showing that the residual leakage does not render SWiSSSE vulnerable to known attacks. We believe that by taking a system-wide view of security for SSE, we can provide greater confidence to practitioners considering deployment of SSE schemes.

In order to evaluate a privileged cryptographic primitive, say decrypt a ciphertext or check a signature, an endpoint needs to know the raw key material, the algorithm including all parameters, and the ciphertext/signature. For example, JWT contains an algorithm field that dictates how it should be verified. This seemingly innocuous design has led to countless broken implementations and vulnerabilities, including the infamous "alg: None". While the security community likes to pick on JWT, we show that JWT is not the only system that succumbs to what we call in-band protocol negotiation attacks. We display a showcase of old and new attacks in widely deployed standards and systems, including AWS S3 Crypto SDK (CVE-2020-8912), AWS Encryption SDK and AWS KMS (under embargo). We show that not only the algorithm field can cause problems, but even a mundane detail such as the ciphertext format can also lead to weaknesses. We found that the root cause of these vulnerabilities is a failure to answer this basic question: what is a key? Many systems, standards, or libraries consider a key consisting of only the raw secret material. A secret key material, however, is usually not enough to instantiate a protocol, forcing people to store other parameters in the ciphertext, i.e., doing in-band protocol negotiation. We present how Google uses Tink to ensure that even software that has not been reviewed by cryptography engineers will not be vulnerable to this class of attack.

In this talk I will present the design, analysis, and implementation of Pancake, the first system to protect key-value stores from access pattern leakage attacks with small constant factor bandwidth overhead. First, I will outline our new formal security model, and explain why it captures realistic attacks. Then, I will describe our frequency smoothing mechanism, which provably transforms plaintext accesses into uniformly-distributed encrypted accesses. Finally, I will explain the implementation and evaluation of the Pancake system itself. We integrated Pancake into three key-value stores used in production clusters, and demonstrated its practicality: on standard benchmarks, PANCAKE achieves 229× better throughput than non-recursive Path ORAM - within 3-6× of insecure baselines for these key-value stores.

No abstract

Logging infrastructure is a crucial component of WhatsApp and other modern services. It helps us understand the performance and reliability of our mobile apps and improve them. There are different reasons that data is logged, but in many cases we only need to compute aggregate statistics, and do not need to know the specific user’s identity. A redesign of the logging framework to upload logs anonymously from our apps, provides a defense-in-depth, and mitigates risks such as accidental logging or misuse of user identifiers. However, this opens up the opportunity for attackers to corrupt or spam logs and bias the collected metrics through this unauthenticated channel. In this talk, we present PrivateStats, an anonymous, fraud resistant logging system we have built, using Verifiable Oblivious Pseudorandom Functions (VOPRFs), and are deploying in WhatsApp. We discuss a number of requirements that informed our choice of algorithms and design, and report on the first deployment of such a service at scale. We further discuss new cryptographic techniques that enable a more transparent and verifiable key rotation and distribution strategy, which is of independent interest. We believe that these lessons in scaling are useful for other organizations and motivate further research into anonymization at scale.

We present CanDID, a platform for practical, user-friendly realization of {\em decentralized identity}, the idea of empowering end users with management of their own credentials. While decentralized identity promises to give users greater control over their private data, it burdens users with management of private keys, creating a significant risk of key loss. Existing and proposed approaches also presume the spontaneous availability of a credential-issuance ecosystem, creating a bootstrapping problem. They also omit essential functionality, like resistance to Sybil attacks and the ability to detect misbehaving or sanctioned users while preserving user privacy. CanDID addresses these challenges by issuing credentials in a user-friendly way that draws securely and privately on data from existing, unmodified web service providers. Such legacy compatibility similarly enables CanDID users to leverage their existing online accounts for recovery of lost keys. Using a decentralized committee of nodes, CanDID provides strong confidentiality for user's keys, real-world identities, and data, yet prevents users from spawning multiple identities and allows identification (and blacklisting) of sanctioned users. We present the CanDID architecture and its technical innovations and report on experiments demonstrating its practical performance.

We propose a talk based on a recent project to design and implement a new system to privately manage groups in the Signal messenger application. The system is in testing and is expected to be deployed by RWC 2021. There is an associated research paper, to appear at CCS 2020. (The first ten pages of that paper are attached, and an earlier version of the complete paper is online as ePrint 2019/1416). The talk will select content from the paper, implementation and deployment experience that are expected to be of interest to the RWC audience. Paper abstract: In this paper we present a system for maintaining a membership list of users in a group, designed for use in the Signal Messenger secure messaging app. The goal is to support {\em private groups} where membership information is readily available to all group members but hidden from the service provider or anyone outside the group. In the proposed solution, a central server stores the group membership in the form of encrypted entries. Members of the group authenticate to the server in a way that reveals only that they correspond to some encrypted entry, then read and write the encrypted entries. Authentication in our design uses a primitive called a keyed-verification anonymous credential~(KVAC), and we construct a new KVAC scheme based on an algebraic MAC, instantiated in a group G of prime order. The benefit of the new KVAC is that attributes may be elements in G whereas previous schemes could only support attributes that were integers modulo the order of G. This enables us to encrypt group data using an efficient Elgamal-like encryption scheme, and to prove in zero-knowledge that the encrypted data is certified by a credential. Because encryption, authentication, and the associated proofs of knowledge are all instantiated in G the system is efficient, even for large groups.

Secure channel protocols like QUIC and DTLS 1.3 run over unreliable-transport networks like UDP. They have to carefully catch effects arising naturally in those networks while protecting against malicious interference. In this talk, we introduce the notion of robustness for cryptographic channels, generically capturing this behavior. Our robustness notion guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We establish that QUIC and DTLS 1.3 achieve the desired level of robustness. Notably though, their robust behavior translates to a practically relevant security degradation (when compared to, e.g., TLS 1.3) which we will highlight in this talk. The security bounds we establish have led the responsible IETF working groups to mandate concrete forgery limits in recent updates to both protocol drafts.

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, we have identified an implementation-level issue in production-grade TLS implementations that allows executing the same attack by directly observing the contents of server responses, without resorting to timing measurements.

In this talk we introduce partitioning oracles, a new class of decryption error oracles which, conceptually, take a ciphertext as input, and output whether the decryption key belongs to some known subset of keys. These can arise when encryption schemes are not committing with respect to their keys, and lead to vulnerabilities when keys are lower entropy, such as human-chosen passwords. We detail adaptive chosen ciphertext attacks that exploit partitioning oracles to efficiently recover passwords. The attacks utilize efficient key multi-collision algorithms --- a cryptanalytic goal that we define --- against the widely used authenticated encryption with associated data (AEAD) schemes, including AES-GCM, XSalsa20/Poly1305, and ChaCha20/Poly1305. Finally, we discuss why these findings point to the need to develop and standardize efficient committing AEAD schemes for widespread deployment.

We present KEMTLS, an alternative to the TLS 1.3 handshake that uses key-encapsulation mechanisms (KEMs) instead of signatures for server authentication. Among existing post-quantum candidates, signature schemes generally have larger public key/signature sizes compared to the public key/ciphertext sizes of KEMs: by using an IND-CCA-secure KEM for server authentication in post-quantum TLS, we obtain multiple benefits. A size-optimized post-quantum instantiation of KEMTLS requires less than half the bandwidth of a size-optimized post-quantum instantiation of TLS 1.3. In a speed-optimized instantiation, KEMTLS reduces the amount of server CPU cycles by almost 90% compared to TLS 1.3, while at the same time reducing communication size, reducing the time until the client can start sending encrypted application data, and eliminating code for signatures from the server's trusted code base.

Mesh messaging applications allow users in relative proximity to communicate without the Internet. The most viable offering in this space, Bridgefy, has recently seen increased uptake in areas experiencing large-scale protests (Hong Kong, India, Iran, US, Zimbabwe, Belarus, Thailand), suggesting its use in these protests. It is also being promoted as a communication tool for use in such situations by its developers and others. In this work, we perform a security analysis of Bridgefy. Our results show that Bridgefy permits its users to be tracked, offers no authenticity, no effective confidentiality protections and lacks resilience against adversarially crafted messages. We verify these vulnerabilities by demonstrating a series of practical attacks on Bridgefy. Thus, if protesters rely on Bridgefy, an adversary can produce social graphs about them, read their messages, impersonate anyone to anyone and shut down the entire network with a single maliciously crafted message. As a result, we conclude that participants of protests should avoid relying on Bridgefy until these vulnerabilities are addressed and highlight the resulting gap in the design space for secure messaging applications.

Zoom’s platform provides video conferencing services for hundreds of millions of daily meeting participants. They use Zoom to conduct business, learn among classmates scattered by recent events, connect with friends and family, collaborate with colleagues, and in some cases, discuss critical matters of state. Zoom is working hard to improve meeting security for its users. In May 2020, Zoom published an incrementally deployable proposal\footnote{\url{https://github.com/zoom/zoom-e2e-whitepaper}}, describing not only a design for its improved end-to-end encryption (E2EE), but also a plan to build an auditable and persistent notion of identity for all Zoom users, which will provide additional security even against active attacks from a compromised Zoom server. In this talk, I will first describe our improved end-to-end design, report on our progress deploying it, and comment on some lessons we learned along the way. Then, I will look to the future and present our vision for user identity protocols. I will argue why it matters, discuss the issues which make this problem hard, and how we plan to address them.

Post-Compromise Security, or PCS, refers to the ability of a given protocol to recover—by means of normal protocol operations—from the exposure of local states of its (otherwise honest) participants. Reaching PCS in group messaging protocols so far either bases on n parallel two-party messaging protocol executions between all pairs of group members in a group of n users (e.g., in the Signal messenger), or on so-called tree based group ratcheting protocols (e.g., developed in the context of the IETF Message Layer Security initiative). Both approaches have great restrictions: Parallel pairwise executions induce for each state update a communication overhead of O(n). While tree-based protocols reduce this overhead to O(log n), they cannot handle concurrent state updates. For resolving such inevitably occurring concurrent updates, these protocols delay reaching PCS up to n communication time slots (potentially more in asynchronous settings such as messaging). Furthermore, a consensus mechanism (such as a central server) is needed in practice. In this talk we discuss the trade-off between PCS, concurrency, and communication overhead in the context of group ratcheting. In particular, we will explain why state updates, concurrently initiated by t group members for reaching PCS immediately, necessarily induce a communication overhead of Ω(t) per message. This result is based on an analysis of generic group ratcheting constructions in a symbolic execution model. Secondly, we will present a new group ratcheting construction that resolves the aforementioned problems with concurrency but reaches a communication overhead of only O(t∙(1+log(n/t))), which smoothly increases from O(log n) with no concurrency, to O(n) with unbounded concurrency. Thus, we present a protocol in which each group member can (nearly) immediately recover from exposures independent of concurrency in the group with almost minimal communication overhead. We believe that this result, beyond its applicability to the IETF Message Layer Security (MLS) standardization effort, more generally and more importantly is of interest for (distributed) messaging environments where concurrency is unavoidable. Although all three considered properties (fast recovery from exposures, little induced communication, and handling of concurrency) are indeed desired by practical messengers, our short review of current real-world protocols and academic proposals at the beginning of this talk reveals (that and) where these approaches fail. Hence, our results, if being deployed, can enhance messaging for a large audience. While the formal execution of our results is theoretic and partially complex, the high-level ideas and concepts, summarized in this talk, are simple and intuitive. We think that our plain results are interesting for practitioners and the combination of different theoretic approaches to derive these results are insightful to real-world crypto researchers. Our primary submission are the presentation slides. For further details and background information, imparted in the talk but maybe not entirely clear from only the slides, we provide a short extended abstract (see the second slide for the URL).

In academic MPC papers, protocols are typically optimized for a certain environment. Thus, one may consider very powerful machines connected via a very fast and high bandwidth network, or one may consider mobile phones communicating, and so on. However, in some cases, the environment is not known and tradeoffs need to be made. In this talk, we will describe some of the challenges encountered in building a product based on MPC that is deployed in very different environments by different customers. For a test case, we will consider specific challenges that arose for two-party RSA key generation, and how the "best academic protocol" needed to be modified for generic deployment, and in particular in settings with very poor bandwidth. The talk will present what changes were made to the protocol and why, together with general lessons learned that we believe are of importance to the research community.

This talk aims to present the systematic process in reviewing the Diogenes paper and code, advancing it to a production-ready state. we will first provide background for the project and important details on its inner workings. We will describe our approach and framework to review crypto-systems and describe the attacks we found and what lessons we can learn from them. We intend to highlight the following topics: • Consistency between paper, specification, and code • Real world adversaries • Collaboration between cryptographers and engineers • Dangers of optimizations

Many organizations stand to benefit from pooling their data together in order to draw mutually beneficial insights -- e.g., for fraud detection across banks, better medical studies across hospitals, etc. However, such organizations are often prevented from sharing their data with each other by privacy concerns, regulatory hurdles, or business competition.

We present Senate, a system that allows multiple parties to collaboratively run analytical SQL queries without revealing their individual data to each other. Unlike prior works on secure multi-party computation (MPC) that assume that all parties are semi-honest, Senate protects the data even in the presence of malicious adversaries. At the heart of Senate lies a new MPC decomposition protocol that decomposes the cryptographic MPC computation into smaller units, some of which can be executed by subsets of parties and in parallel, while preserving its security guarantees. Senate then provides a new query planning algorithm that decomposes and plans the cryptographic computation effectively, achieving a performance of up to 145x faster than the state-of-the-art.

No abstract

Although it is one of the most popular signature schemes today, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated as part of the signing algorithm. It is known that any small amount of nonce exposure or nonce bias can in principle lead to a full key recovery: the key recovery is then a particular instance of Boneh and Venkatesan's hidden number problem (HNP). That observation has been practically exploited in many attacks in the literature, taking advantage of implementation defects or side-channel vulnerabilities in various concrete ECDSA implementations. However, most of the attacks so far have relied on at least 2 bits of nonce bias (except for the special case of curves at the 80-bit security level, for which attacks against 1-bit biases are known, albeit with a very high number of required signatures). In this paper, we uncover LadderLeak, a novel class of side-channel vulnerabilities in implementations of the Montgomery ladder used in ECDSA scalar multiplication. The vulnerability is in particular present in several recent versions of OpenSSL. However, it leaks less than 1 bit of information about the nonce, in the sense that it reveals the most significant bit of the nonce, but with probability <1. Exploiting such a mild leakage would be intractable using techniques present in the literature so far. However, we present a number of theoretical improvements of the Fourier analysis approach to solving the HNP (an approach originally due to Bleichenbacher), and this lets us practically break LadderLeak-vulnerable ECDSA implementations instantiated over the sect163r1 and NIST P-192 elliptic curves. In so doing, we achieve several significant computational records in practical attacks against the HNP. We submitted a short Abstract summarizing the work, but a long version was accepted to CCS'20 and a full paper is available on ePrint [1]. The work was already presented at the Crypto & Privacy Village at DEFCON [2] and the Workshop on Attacks in Cryptography [3,4] affiliated to CRYPTO 2020. [1] https://eprint.iacr.org/2020/615 [2] https://cryptovillage.org/dc28/ [3] https://www.youtube.com/watch?v=UbjOKMTVMWQ (long) [4] http://www.youtube.com/watch?v=1ddvx2TgPF8&t=22m09s (short)

Multi-signatures enable a group of signers to produce a single signature on a given message. Recently, Drijvers et al. (S&P'19, RWC'19) showed that all thus far proposed two-round multi-signature schemes in the DL setting (without pairings) are insecure under parallel sessions, i.e., if a single signer participates in multiple signing sessions concurrently. While Drijvers et al. improve the situation by constructing a secure two-round scheme, saving a round comes with the price of having less compact signatures. In particular, the signatures produced by their scheme are more than twice as large as Schnorr signatures, which arguably are the most natural and compact among all practical DL signatures and are therefore becoming popular in cryptographic applications, e.g., support for Schnorr signature verification has been proposed to be included in Bitcoin. If one needs a multi-signature scheme that can be used as a drop-in replacement for Schnorr signatures, then one is either forced to resort to a three-round scheme such as MuSig (Maxwell et al., DCC 2019) or MDSL-pop (Boneh, Drijvers, and Neven, ASIACRYPT 2018), or to accept that signing sessions are only secure when run sequentially, which may be hard to enforce in practice, e.g., when the same signing key is used by multiple devices. In this work, we propose MuSig2, a novel and simple two-round multi-signature scheme variant of the MuSig scheme. Our scheme is the first natural and simple multi-signature scheme that simultaneously i) is secure under parallel signing sessions, ii) supports key aggregation, iii) outputs ordinary Schnorr signatures, and iv) needs only two communication rounds. Furthermore, our scheme is the first multi-signature scheme in the DL setting that supports preprocessing of all but one rounds, effectively enabling a non-interactive signing process, without forgoing security under parallel sessions. The combination of all these features makes MuSig2 highly practical. We prove the security of MuSig2 under the One-More Discrete Logarithm (OMDL) assumption in the random oracle model, and the security of a slightly optimized variant in the combination of random oracle model and algebraic group model.

WebAuthn, forming part of FIDO2, is a W3C standard for strong authentication, which employs digital signatures to authenticate web users whilst preserving their privacy. Owned by users, WebAuthn authenticators generate attested and unlinkable public-key credentials for each web service to authenticate users. Since the loss of authenticators prevents users from accessing web services, usable recovery solutions preserving the original WebAuthn design choices and security objectives are urgently needed. We examine Yubico's recent proposal for recovering from the loss of a WebAuthn authenticator by using a secondary backup authenticator. We analyse the cryptographic core of their proposal by modelling a new primitive, called Asynchronous Remote Key Generation (ARKG), which allows some primary authenticator to generate unlinkable public keys for which the backup authenticator may later recover corresponding private keys. Both processes occur asynchronously without the need for authenticators to export or share secrets, adhering to WebAuthn's attestation requirements. We prove that Yubico's proposal achieves our ARKG security properties under the discrete logarithm and PRF-ODH assumptions in the random oracle model. To prove that recovered private keys can be used securely by other cryptographic schemes, such as digital signatures or encryption schemes, we model compositional security of ARKG using composable games by Brzuska et al. (ACM CCS 2011), extended to the case of arbitrary public-key protocols. As well as being more general, our results show that private keys generated by ARKG may be used securely to produce unforgeable signatures for challenge-response protocols, as used in WebAuthn. We conclude our analysis by discussing concrete instantiations behind Yubico's ARKG protocol, its integration with the WebAuthn standard, performance, and usability aspects.

Recent user studies on the complex relationship between humans and security technology conclude that even knowledgeable users are often incapable of making technically-sound security decisions when interacting with cryptographic tools and protocols. In this talk, I will discuss how user \textit{mental models}\footnote{A mental model is a representation of someone's perceptions of how something works in the real world.} of such protocols diverge from the technical reality. I will also discuss how mental models are shaped by design, how they influence security decisions, and how researchers can elicit such mental models using qualitative methods. I will briefly present our interdisciplinary work on mental models of HTTPS and cryptocurrencies. In this line of work, we focused on different user populations, such as end users and administrators. Especially our work on administrators' mental models of HTTPS revealed root causes for poor configurations that have a negative impact on security. We have also shown that administrators are often incapable of making informed-decisions when configuring HTTPS and therefore heavily rely on the quality of online resources. Based on these findings, I will discuss the complex interdependence of mental models, design and security. My talk will conclude with considerations on how to incorporate the human component in the design process of novel security and privacy technology. I will discuss how current user interface components of complex cryptographic protocols could be adapted to better support decision-making in favor of security. Such improvements should focus on 1) creating (functional) mental models that correspond to the technical reality, and 2) provide interaction techniques that allow users to make the right security-decisions regardless of whether their understanding of the cryptographic fundamentals is correct. The overarching goals of this talk are to raise awareness for the impact of design on mental models, and to establish a fruitful interdisciplinary discourse.

This talk explores a small yet crucial part of the U.S. Fifth Amendment privilege against self-incrimination called the "foregone conclusion doctrine." This doctrine concerns a new chapter of the Crypto Wars, in which the government issues subpoenas that compel people to decrypt their own devices, under the penalty of contempt of court if they do not comply. This talk will survey the use of compelled decryption by courts, provide a legal and technical description of the doctrine, and use a simulation-based definition to analyze the compellability of various cryptographic systems.

No abstract

With the beginning of the third round of NIST's Post-Quantum Cryptography standardization project recently announced, one of the major contributing factors for selection will be side-channel analysis and attacks in general. NIST state, in their most recent (NISTIR 8309) Status Report document that ``NIST hopes to see more and better data for performance in the third round. This performance data will hopefully include implementations that protect against side-channel attacks, such as timing attacks, power monitoring attacks, fault attacks, etc''. This clearly requires actually performing these attacks on reference, optimizied, and even side-channel resistant implementations of the candidates. Moreover, it is also prudent to know which attacks have and have not been done. We fill this gap by presenting a comprehensive overview and survey of the state-of-the-art on attacks for these post-quantum schemes, which range from classical cryptanalysis, static timing analysis, fault attacks, simple power analysis, correlation and differential power analysis, electromagnetic attacks, template attacks, cold-boot attacks, and then also highlight countermeasures. The talk will contribute a full list of all attacks found to-date but will primarily (for brevity) discuss a selection of the more interest and/or important attacks found.

Much of public key cryptography is designed in the Random Oracle Model, which assumes parties have access to one or more independent random functions. Implementing these random functions securely, usually via a cryptographic hash function, critically requires a technique called domain separation. This talk is about how spectacularly wrong things can go when domain separation is not done right, and simple ways to do it right. We begin with a case study on random oracle implementation in the NIST PQC KEM standardization effort, giving attacks arising from poor domain separation on some submissions, and classifying the remaining submissions from dubious to good. We then give a library of proof-validated domain separations that are secure, easy to implement, and usable in any type of cryptographic protocol, not just PQC KEMs.

Post-quantum crypto standards are coming: it doesn’t matter if you believe in quantum computers or not. What is the impact on the billions of embedded devices? Using some typical embedded use-cases we outline the challenges and show some recent solutions in this area.

No abstract

No abstract

Exposure Notification is a system designed by Google and Apple for notifying individuals when they have been exposed to SARS-CoV-2 by coming in contact with someone who has tested positive for the virus. Within GAEN, no user-identifying data is ever uploaded to the central server; users establish their proximity exclusively peer-to-peer and anonymously, with the sole purpose of knowing whether they have been in contact with an individual who may later be deemed to have been infected. The design choices of the protocols in question, which makes them robust against data collection attacks, unfortunately also make them particularly susceptible to data injection by malicious parties. In particular, these protocols allow for a determined attacker to generate false exposure notifications on a mass scale in an undetectable and unpreventable manner. In this paper we highlight how these data injections attacks can be used to implement voter suppression in political elections and to compromise the integrity of the democratic process.

In recent months multiple proposals for contact tracing schemes for combating the spread of COVID-19 have been published. Many of those proposals try to implement this functionality in a decentralized and privacy-preserving manner using Bluetooth Low Energy (BLE). The different schemes provide different trade-offs between privacy, security, and explainability. We claim that different countries, with different needs and cultural norms, may require different trade-offs. We present ``Hashomer'', a contact tracing scheme that has been tailored to needs and cultural norms in Israel. In this talk, we will explain the specific trade-offs we made and the different challenges we faced. Our scheme was adopted by the Israeli Ministry of Health's (MoH) and released as part of the national contact tracing application --- ``Hamagen''. The design is fully decentralized and has the following properties: Message Unlinkability --- Different BLE messages sent by the same user cannot be linked to each other (except for messages sent by COVID-19 positive users who {\em give consent} to tracing their contacts, and only for messages sent within a short time period). Explainability --- To convince users that they were exposed to a COVID-19 positive person, we let them learn the approximate time of contact. This also implies that users can potentially learn, using the phone's GPS information, the location of the exposure. Partial Disclosure and Coercion Prevention --- Users and the MoH are able to redact tracing information and exposure notifications for specific time intervals. Prevention of Relay Attacks -- The design prevents attacks where a malicious receiver relays BLE transmissions from one location to other locations. Proof of exposure to a COVID-19 positive person --- To prevent false reports about exposure, we allow users who are notified by the application about exposure to a COVID-19 positive person, to prove this fact to the server. Identity Commitment --- To prevent malicious changing or replacing keys, we bind the BLE messages to a unique ID in a privacy-preserving way. Performance --- BLE payload size is limited to 16 bytes. The application uses only symmetric key cryptography (AES and HMAC). To reduce bandwidth, contact updates from the MoH are of limited size.

Human mobility is undisputedly one of the critical factors in infectious disease dynamics. Until a few years ago, researchers had to rely on static data to model human mobility, which was then combined with a transmission model of a particular disease resulting in an epidemiological model. Recent works have consistently been showing that substituting the static mobility data with mobile phone data leads to significantly more accurate models. While prior studies have exclusively relied on a mobile operator’s subscribers’ aggregated data, it may be preferable to contemplate aggregated mobility data of infected individuals only. Clearly, naively linking mobile phone data with infected individuals would massively intrude privacy. This research aims to develop a software solution that reports the aggregated mobile phone location data of infected individuals while still maintaining compliance with privacy expectations. To achieve privacy, we use homomorphic encryption, zero-knowledge proof techniques, and differential privacy. Our protocol’s open-source implementation can process eight million subscribers in one hour.

zkSNARKs are an exciting avenue for enhancing the privacy and scalability of decentralized systems. Indeed, researchers and practitioners are implementing and deploying decentralized applications atop zkSNARKs at breakneck speed. However, existing zkSNARK implementations live in their own “walled gardens”: optimizations and improvements in one implementation cannot easily be shared with other projects, leading to either inefficiency, or wasted effort due to reimplementation. In this talk, I will introduce *arkworks*: a set of Rust libraries that resolves the foregoing problem by providing all of the components required for zkSNARK programming, packaged into generic, efficient, and easy-to-use modules, such as the following: * Generic implementations of finite fields, elliptic curves, and pairings, as well as instantiations of widely-used curves. * State-of-the-art zkSNARKs such as Groth16, Groth-Maller17, Marlin. * Ergonomic libraries for writing constraints, along with implementations of many commonly-used constraint “gadgets”. * Recursive composition of arbitrary SNARKs, including recursion from accumulation schemes. * Libraries for aggregating proofs and signatures. The modular design of our libraries means that improvements in one component (such as finite field arithmetic) are inherited for free by downstream components (such as zkSNARK implementations). We achieve this composability without sacrificing performance: our generic libraries are competitive with the best application-specific libraries. As a result, our libraries have been deployed in existing industry products such as Celo, MINA, and Aleo.

No abstract

Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short and efficiently verifiable proofs that do not reveal anything more than the correctness of the statement. zk-SNARKs are widely used in decentralised systems to address privacy and scalability concerns. A major drawback of such proof systems in practice is the requirement to run a trusted setup for the public parameters. Moreover, these parameters set an upper bound to the size of the computations or statement to be proven, which results in new scalability problems. We design and implement SnarkPack, a new argument that further reduces the size of SNARK proofs by means of aggregation. Our goal is to provide an off-the-shelf solution that is practical in the following sense: (1) it is compatible with existing deployed SNARK systems, (2) it does not require any extra trusted setup. SnarkPack is designed to work with Groth16 scheme and has logarithmic size proofs and a verifier that runs in logarithmic time in the number of proofs to be aggregated. Most importantly, SnarkPack reuses the public parameters from Groth16 system. SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 163ms, yielding a verification mechanism that is exponentially faster than batching and previous solutions in the field. SnarkPack can be deployed in blockchain applications that rely on many SNARK proofs such as Proof-of-Space or roll-up solutions.

This talk will discuss a novel application of cryptography, the zero-knowledge middlebox. There is an inherent tension between ubiquitous encryption of network traffic and the ability of middleboxes to enforce network usage restrictions. An emerging battleground that epitomizes this tension is DNS filtering. Encrypted DNS (DNS-over-HTTPS and DNS-over-TLS) was recently rolled out by default in Firefox, with Google, Cloudflare, Quad9 and others running encrypted DNS resolvers. This is a major privacy win, protecting users from local network administrators observing which domains they are communicating with. However, administrators have traditionally filtered DNS to enforce network usage policies (e.g. blocking access to adult websites). Such filtering is legally required in many networks, such as US schools up to grade 12. As a result, Mozilla was forced to compromise, building a special flag for local administrators to instruct Firefox not to use Encrypted DNS. This example points to an open question of general importance, namely: can we resolve such tensions, enabling network policy enforcement while giving users the maximum possible privacy? Prior work has attempted to balance these goals by either revealing client traffic to trusted hardware run by the middlebox (e.g. Endbox) or using special searchable encryption protocols which enable some policy enforcement on encrypted traffic (e.g. Blindbox, Embark) by leaking information to the middlebox. Instead, we propose utilizing zero-knowledge proofs for clients to prove to middleboxes that their encrypted traffic is policy-compliant, without revealing any other additional information. Critically, such zero-knowledge middleboxes don’t require trusted hardware or any modifications to existing TLS servers. We implemented a prototype of our protocol using Groth16 proofs which can prove statements about an encrypted TLS 1.3 connection such as “the domain being queried in this encrypted DNS packet is not a member of the specified blocklist.” With current tools, our prototype takes on the order of ten seconds to produce one proof. While this is too slow for use with interactive web-browsing, it is close enough that we consider it a tantalizing target for future optimization. This talk will cover the tension between encryption and policy-enforcing middleboxes, including recent developments in Encrypted DNS and the necessity of DNS filtering. It will briefly survey existing solutions before presenting and arguing for the new zero-knowledge middlebox paradigm. Finally, the talk will describe our prototype implementation and several optimizations developed for it, as well as future avenues for improvement and open research questions.

Forward security is an essential design goal of modern cryptographic protocols with a long body of literature in several application domains such as interactive key-exchange protocols (prominently in TLS 1.3 & Double Ratcheting), digital signatures, search on encrypted data, updatable cryptography, mobile Cloud backups, decentralized contact tracing, new approaches to Tor, and even novel decentralized protocols such as the Dfinity's Internet Computer or Algorand's consensus multi-signatures, among others. The well-known benefit of forward security is the mitigation of key leakage by evolving secret keys over epochs and thereby revoking access to prior-epoch ciphertexts or signing capabilities. Such a strong security guarantee is highly recognized by industry to be included into security products (e.g., by companies such as Google, Apple, Facebook, Microsoft, and Cloudflare), particularly resulting in over 99% of Internet sites surveyed by Qualys SSL Labs (https://www.ssllabs.com/ssl-pulse/) support at least some form of forward security at the time of writing. Green and Miers (S&P 2015) initiated the studies of puncturable encryption (PE) as a new cryptographic primitive towards the strong form of asynchronous forward-secure encryption (in particular, without the need of any pre-shared key material). Already several follow-up works showed the versatility of such a concept yielding a rich abstraction of forward security investigated in a variety of (data-in-transit and data-at-rest) application domains such as 0-RTT key exchange for TLS (Eurocrypt'17, Eurocrypt'18, Asiacrypt'20, JoC'21), Google's QUIC (Cans'20), searchable encryption (CCS'17), mobile Cloud backups (OSDI'20), Cloudflare's Geo Key Manager (Financial Crypto'21), Tor (PoPETS'20), and updatable encryption (ePrint'21). Loosely speaking, PE is a promising variant of public-key encryption that allows realizing the property of fine-grained and non-interactive forward security with several useful applications. This talk provides an exhausting overview to the concept of PE, presents state-of-the-art research on PE schemes and discusses cryptographic deployment challenges in several aspects, e.g., parameter choices, applications (such as 0-RTT key exchange using Bloom-Filter Encryption, forward security for Cloudflare's Geo Key Manager, and mobile Cloud backups using SafetyPin) as well as open problems and challenges towards real-world deployment. The overall goal is to make PE more accessible to the general audience and industry in a developer-friendly way and also presenting new insights and results. The presentation builds on an existing blog post with the same title (https://profet.at/blog/pe_part1/).

At RWC 2020, Carruth gave an overview of what Spectre attacks mean for the development for cryptographic software. One central message of his talk was that while certain Spectre-related attacks are considered CPU bugs that should (and are being) fixed in hardware, “Spectre v1 is here for decades. . . ” Among other coding guidelines, he recommends protecting against such Spectre v1 attacks by: * moving operations involving long-term keys to a separate agent process; and * hardening this agent process with speculative load hardening (SHL), if it is affordable. In this presentation we will show that SLH is insufficient as a protection against Spectre v1, in particular when applied to cryptographic software. While this observation may seem like it contradicts earlier analyses, it is a result of taking declassification of data into account, which is a very common, albeit often implicit, construct in cryptographic software. On the positive side we show that two small modifications to SLH yield a countermeasure that provably protects against Spectre v1 attacks. What is even more positive is that this countermeasure is—in particular for cryptographic software—expected to be much cheaper than SLH. In order to widely deploy this countermeasure it is necessary to augment type systems of mainstream programming languages and compilers to distinguish between secret and public data. Such modifications to type systems are already being discussed to systematically protect against traditional timing attacks.

Timing attacks are among the most devastating side-channel attacks, allowing remote attackers to retrieve secret material, including cryptographic keys, with relative ease. In principle, "these attacks are not that hard to mitigate": the basic intuition, captured by the constant-time criterion, is that control-flow and memory accesses should be independent from secrets. Furthermore, there is a broad range of tools for automatically checking adherence to this intuition. Yet, these attacks still plague popular crypto libraries twenty-five years after their discovery, reflecting a dangerous gap between academic research and crypto engineering. This gap can potentially undermine the emerging shift towards high-assurance, formally verified crypto libraries. However, the causes for this gap remain uninvestigated. To understand the causes of this gap, we conducted a survey with 44 developers of 27 prominent open source cryptographic libraries. The goal of the survey was to analyze if and how the developers ensure that their code executes in constant time. Our main findings are that developers are aware of timing attacks and of their potentially dramatic consequences and yet often prioritize other issues over the perceived huge investment of time and resources currently needed to make their code resistant to timing attacks. Based on the survey, we identify several shortcomings in existing analysis tools for constant-time, and issue recommendations that can make writing constant-time libraries less difficult. Our recommendations can inform future development of analysis tools, security-aware compilers, and crypto libraries, not only for constant-timeness, but in the broader context of side-channel attacks, in particular for micro-architectural side-channel attacks.

In today's world, Voice-over-IP calls from personal computers have become ubiquitous. We study the question of what information is leaked over these channels, beyond the obvious audio content. As it turns out, the built-in microphones in commodity PCs inadvertently capture electromagnetic side-channel leakage from ongoing computation. Moreover, this information is often conveyed by supposedly-benign channels such as audio recordings and common Voice-over-IP applications, even after lossy compression. Thus, as we will demonstrate in this talk, that it is possible to conduct physical side-channel attacks on computation by remote and purely passive analysis of commonly-shared channels. These attacks require neither physical proximity (which could be mitigated by distance and shielding), nor the ability to run code on the target or configure its hardware. Consequently, we argue, physical side channels on PCs can no longer be excluded from remote-attack threat models. We analyze the computation-dependent leakage captured by internal microphones, and empirically demonstrate its efficacy for attacks. In one scenario, an attacker steals the secret ECDSA signing keys of the counterparty in a voice call. In another, the attacker detects what web page their counterparty is loading. In a final scenario, a player in the Counter-Strike multiplayer game can detect a hidden opponent waiting in ambush, by analyzing how the 3D rendering done by the opponent's computer induces faint but detectable signals into the opponent's audio feed.

No abstract

This talk relates to two ongoing works where we introduce a new security notion that lies right in between pseudorandom permutations (PRPs) and strong pseudorandom permutations (SPRPs). We refer to this new security notion and any (tweakable) cipher that satisfies it, as a rugged pseudorandom permutation (RPRP). Rugged pseudorandom permutations lend themselves to some interesting applications, have practical benefits, and lead to novel cryptographic constructions. Analogous to the encode-then-encipher paradigm first proposed by Bellare and Rogaway and later extended by Shrimpton and Terashima, we can transform a variable-length tweakable RPRP into an AEAD scheme. However, we can construct RPRPs more efficiently as they are weaker primitives than SPRPs (the notion traditionally required by the encode-then-encipher paradigm). We can construct RPRPs using two-pass schemes, whereas SPRPs typically require three passes over the input data. We also identify new transformations that yield nonce-hiding AEAD schemes with more compact ciphertexts than previously known. Further extending this approach, we arrive at a new generalised notion of authenticated encryption and matching constructions, which we refer to as nonce-set AEAD. Nonce-set AEAD is particularly well-suited to realise modern secure channels, such as those used in QUIC and DTLS, which employ a windowing mechanism at the receiver end of the channel. Finally, we show how to use tweakable RPRPs to construct an efficient onion encryption scheme for Tor with significantly improved security and good performance.

No abstract

Motivated by calls for privacy and data breaches of cloud services, efforts to broadly deploy Encrypted Search Algorithms (ESAs) are moving forward. ESAs allow search on encrypted data and can be found in research as well as industry. As all practical solutions leak some information, cryptanalysis plays an important role in the area of encrypted search. Many attacks have been proposed that exploit different leakage profiles under various assumptions. While leakage attacks aim to improve our common understanding of leakage, it is difficult to draw definite conclusions about their practical risk. This uncertainty stems from many limitations including a lack of reproducibility due to closed-source implementations, empirical evaluations conducted on small and/or unrealistic data, and reliance on very strong assumptions that can significantly affect accuracy. Particularly, assumptions made about the query distribution do not have any empirical basis because datasets containing users' queries are hard to find. In this talk, we present results from our extensive re-evaluation of leakage attacks on many new datasets in a variety of use cases that - for the first time - include query data. We show that in many of these cases the practical risk of leakage is not as expected. Moreover, the evaluations and conclusions of our work are far from final and still suffer from the fact that for increasingly practical studies of attacks more (especially query) data is desperately needed, which is largely unavailable to researchers. We therefore also cover the remaining challenges from both a research and an industry perspective towards practically assessing the security of ESAs to enable adequate deployments.

The SwissPost e-voting system is currently proposed under the scrutiny of the community, before being deployed in 2022 for political elections in several Swiss cantons. We explain how real world constraints led to shortcomings that allowed a privacy attack to be mounted. More precisely, dishonest authorities can learn the vote of several voters of their choice, without being detected, even when the requested threshold of honest authorities act as prescribed.

This talk will provide an overview of the Exposure Notifications Private Analytics (ENPA) system developed by Apple, Google, ISRG, MITRE and NCI in conjunction with the Exposure Notifications System (ENS) provided by Apple and Google. The goal of ENPA is to enable health authorities to obtain key epidemiology metrics about the ENS deployment and corresponding indicators about the pandemic. We will motivate the need for the private analytics system in the context of Exposure Notification, describe its functionality and privacy properties, and discuss the practical challenges we encountered in the process of deployment. Finally, we will give examples of uses of the data generated by the ENPA system.

Operating a large, complex, Internet-based application usually requires measuring the behavior of the application's users. Often the purpose of these measurements is not to build profiles about individual users, but to shed light on overall trends that might point to performance bottlenecks, user-experience issues, bugs, or attack vectors. Recent advances in cryptography, e.g., Prio (NSDI 2017), have made it possible to compute these aggregates without revealing individual measurements to the service provider. This talk will describe the IETF's initial effort to standardize some of these techniques.

Anonymous message delivery systems, such as private messaging services and privacy-preserving payment systems, need a mechanism for recipient to retrieve the messages addressed to them, without leaking metadata and or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale. We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. Servers operate obliviously, and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding (unlike in prior schemes), and are post-quantum secure. Our starting point is an asymptotically-efficient scheme using Fully Homomorphic Encryption and batch-code-like techniques. We then address concrete performance with a bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned, with a total receiver computation of a under 20ms. The detector's cost is a couple of USD per million messages scanned. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.

Established security bounds for the TLS 1.3 full (1-RTT) and pre-shared key (PSK) handshake protocols grow quadratically with the total number of handshakes across all users. Due to the pervasive use of TLS, these bounds are so loose that they give no guarantees for the standardized parameters used in practice. We give new proofs and concrete bounds that justify the use of these parameters both in principle and in practice. We also discuss the pitfalls that arise when trying to capture the TLS 1.3 key schedule within the random oracle model.

TLS is widely used to add confidentiality, authenticity and integrity to application layer protocols such as HTTP, SMTP, IMAP, POP3, and FTP. However, TLS does not bind a TCP connection to the intended application layer protocol. This allows a man-in-the-middle attacker to redirect TLS traffic to a different TLS service endpoint on another IP address and/or port. For example, if subdomains share a wildcard certificate, an attacker can redirect traffic from one subdomain to another, resulting in a valid TLS session. This breaks the authentication of TLS and cross-protocol attacks may be possible where the behavior of one service may compromise the security of the other at the application layer. In this talk, we investigate cross-protocol attacks on TLS in general and conduct a systematic case study on web servers, redirecting HTTPS requests from a victim's web browser to SMTP, IMAP, POP3, and FTP servers. We show that in realistic scenarios, the attacker can extract session cookies and other private user data or execute arbitrary JavaScript in the context of the vulnerable web server, therefore bypassing TLS and web application security. We evaluate the real-world attack surface of web browsers and widely-deployed email and FTP servers in lab experiments and with internet-wide scans. We find that 1.4M web servers are generally vulnerable to cross-protocol attacks, i.e., TLS application data confusion is possible. Of these, 114k web servers can be attacked using an exploitable application server. Finally, we discuss the effectiveness of TLS extensions such as Application Layer Protocol Negotiation (ALPN) and Server Name Indiciation (SNI) in mitigating these and other cross-protocol attacks.

To revoke certificates in a public-key infrastructure, relying parties need to learn that the certificate is revoked. In a web protocol such as TLS, OCSP stapling may be an acceptable way to do this, but for other use cases OCSP has unacceptable performance, reliability and privacy costs. Certificate revocation lists have acceptable privacy, but are impractically large. CRLite implements certificate revocation by aggregating compressing certificate revocation lists (CRLs) and compressing them using a special-purpose compression technology — this is necessary because otherwise CRLs are impractically large. This talk covers CRLite's compression technique, other state-of-the-art approaches, and several improvements on these. Specifically, we discuss encoding databases as structured linear functions, and how to accommodate non-uniform data — for example, in the common case when only 1% of certificates are revoked. These improvements could give a ~40% reduction in compressed CRL size, and are independently useful.

Steganography is often dismissed as the outcast of cryptographic research topics: after extensive research in the 1990’s and 2000’s, work on steganography has largely ground to a halt and work on encrypted systems took precedence. Unfortunately, encrypted system are now under threat, by censorship in authoritarian countries and legal constraints in liberal countries. While steganographic systems might offer a remedy to these threats, the long history of theoretical steganographic research has resulted in no practical steganographic systems capable of embedding messages into realistic communication distributions, such as human-readable text. In our recent work at CCS21, we took first steps towards remedying this shortfall, identifying several important research directions that must be studied in order to instantiate such systems. In our talk, we hope to reinvigorate community’s excitement over steganographic research by describing the promise of steganographic systems, demonstrating our system, and highlighting the interesting problems left to solve.

Recent advances in password-based key exchange (PAKE) protocols can offer stronger security guarantees for globally deployed security protocols. Notably, the OPAQUE protocol realizes saPAKE [Eurocrypt2018], strengthening the protection offered by aPAKE to compromised servers: after compromising an saPAKE server, the adversary still has to perform a full brute-force search to recover any passwords or impersonate users. However, (s)aPAKEs do not protect client storage, and can only be applied in the so-called asymmetric setting, in which some parties, such as servers, do not communicate with each other. Nonetheless, passwords are also widely used in symmetric settings, where a group of parties share a password and can all communicate (e.g., Wi-Fi with client devices, routers, and mesh nodes; or industrial IoT scenarios). In these settings, the (s)aPAKE techniques cannot be applied, and the state-of-the-art still involves handling plaintext passwords. We propose the notions of (strong) identity-binding PAKEs that improve this situation in two dimensions: they protect all parties from compromise, and can also be applied in the symmetric setting. We propose stronger counterparts to state-of-the-art security notions from the asymmetric setting in the UC model, and construct protocols that provably realize them. Our constructions bind the local storage of all parties to abstract identities, building on ideas from identity-based key exchange, but without requiring a third party. Our first protocol, CHIP, generalizes the security of aPAKE protocols to all parties, forcing the adversary to perform a brute-force search to recover passwords or impersonate others. Our second protocol, CRISP, additionally renders any adversarial pre-computation useless, thereby offering saPAKE-like guarantees for all parties, instead of only the server. We aim to work towards standardization of CHIP and CRISP, for example through IETF. Exposure through Real World Crypto will not only help people find our solutions, but also help to connect us with people who might be interested in working with us towards standardization.

No abstract

Current messaging protocols are incapable of detecting active man-in-the-middle threats after a state compromise. Even strongly-secure protocols such as Signal, which offers forward secrecy and post-compromise security, are dependent on the adversary being passive immediately following state compromise, and healing guarantees are lost if the attacker is not. In addition, despite a great deal of research analyzing the confidentiality properties of secure messaging, entity authentication has largely been abstracted away. Modern messaging applications often rely on out-of-band communication to achieve entity authentication, with human users actively engaging with the protocol, verifying and attesting to long-term public keys. This is done primarily to reduce reliance on trusted third parties (by replacing that role with the user), but this implies that an accurate picture such messaging application's security must take this interaction into account. In this presentation, we examine these gaps by formalizing user-mediated entity authentication, introducing a security model for capturing user authentication in real-world ratcheted messaging protocols. We further demonstrate that the Signal application’s user-mediated authentication protocol cannot be proven secure in this strong model and suggest a new solution that allows the detection of an active state-compromising adversary. Our solution – the MoDUSA protocol – achieves active post-compromise entity authentication security, under certain assumptions on the out-of-band communication channel. These results have direct implications for existing and future ratcheted secure messaging applications.

Messaging schemes such as the Signal protocol rely on out-of-band channels to guarantee the authenticity of long-running communication. However those out-of-band checks may rarely be performed in practice. In this talk, we propose a method for performing continuous authentication during the communication, without needing an out-of-band channel. Leveraging the users' long-term secrets, our Authentication Steps extension guarantees authenticity as long as long-term secrets are not compromised, strengthening Signal's post-compromise security, and further allows to detect a potential compromise of long-term secrets after the fact via an out-of-band channel. Our protocol comes with a formal definition for continuous authentication and security proof, as well as a prototype implementation which seamlessly integrates on top of the official Signal Java library, together with bandwidth and storage overhead benchmarks.

In 2019, US Attorney General William Barr authored an open letter to Facebook, requesting the company delay its plans to deploy additional end-to-end encryption technology. A key objection raised by the Barr memo was that end-to-end encryption technologies “[put] our citizens and societies at risk by severely eroding a company’s ability to detect and respond to illegal content and activity, such as child sexual exploitation and abuse, terrorism, and foreign adversaries’ attempts to undermine democratic values and institutions.” In addition to reiterating a previous law-enforcement position regarding “exceptional access” to encrypted records, the Barr letter outlined a new request: for technology providers to “​embed the safety of the public in system designs, thereby enabling you to continue to act against illegal content effectively with no reduction to safety, and facilitating the prosecution of offenders and safeguarding of victims.” In the two years since Barr’s letter, the scientific, policy and industrial communities have grappled with the implications of this request. A major topic of concern is whether existing server-side media scanning technologies — used to detect the presence of known child sexual abuse material (CSAM) — can be adapted to work in end-to-end encrypted systems. This work is largely referred to by the term “client-side scanning.” (We use this designation to refer to any system that performs scanning on plaintext at the client, even if some realizations may use two-party protocols.) This debate came to a head in August 2021 when Apple announced the inclusion of a new on-device CSAM scanning technology that is slated for inclusion in iOS 15. In this presentation the authors propose to discuss the background and provide a taxonomy of security and privacy risks related to client-side scanning systems.

We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram's equivalent of the TLS record protocol. We give positive and negative results. On the positive side, we formally and in detail model a slight variant of Telegram's ``record protocol'' and prove that it achieves security in a suitable secure channel model, albeit under unstudied assumptions. In this abstract we focus on the negative results. First, we motivate our modelling deviation from MTProto by giving two attacks -- one of practical, one of theoretical interest -- against MTProto without our modifications. We then also give a third attack exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of salt and id fields that are established by Telegram's key exchange protocol. To recover these, we chain the third attack with a fourth one against the implementation of the key exchange protocol on Telegram's servers. Our results provide the first comprehensive study of MTProto's use of symmetric cryptography.

The Signal protocol for end-to-end encrypted messaging provides a range of desirable security properties: asynchronicity, offline deniability, mutual implicit authentication, forward secrecy, and post-compromise security. Transitioning Signal to a post-quantum secure version with the same guarantees proves tricky, however. This is due to the fact that post-quantum key encapsulation mechanisms cannot be used as a drop-in replacement for the clever use of the Diffie--Hellman protocol in Signal's initial key exchange X3DH. In this talk, we elaborate on this obstacle, which may arise in further high-level protocols with subtle security guarantees, and show how to achieve asynchronous deniable key exchange from key encapsulation mechanisms and designated verifier signatures. In particular, we present a provably-secure construction for the post-quantum Signal initial key agreement which achieves the same security guarantees as the currently used X3DH.

ARM-based Android smartphones rely on the TrustZone Trusted Execution Environment to implement security-sensitive functions. The TrustZone runs a separate, isolated, OS (the TZOS), in parallel to Android. The implementation of the cryptographic functions within the TZOS is left to the device vendors, who create proprietary undocumented designs. In this work, we examine the cryptographic design and implementation of Android's Hardware-Backed Keystore in Samsung's Galaxy S8, S9, S10, S20, and S21 flagship devices. We provide a detailed description of the cryptographic design and code structure, and we unveil severe design flaws. We identify an IV reuse attack on AES-GCM that allows an attacker to extract hardware-protected key material, and a downgrade attack that makes even the latest Samsung devices vulnerable to the IV reuse attack. We demonstrate working key extraction attacks on the latest devices. We also show the implications of our attacks on two higher-level cryptographic protocols between the TrustZone and a remote server: we demonstrate a working FIDO2 WebAuthn login bypass and a compromise of Google’s Secure Key Import. We discuss multiple flaws in the design flow of TrustZone based protocols. Although our specific attacks only apply to the ~100 million devices made by Samsung, it raises the much more general requirement for open and proven standards for critical cryptographic and security designs.

We present our recent cryptanalytical results concerning the OpenPGP standard and a number of its most popular implementations. Our corresponding research paper was accepted to CCS'21 and was presented last November. As the OpenPGP encryption standard is widely adopted in practice and has millions of users that critically depend on it, and we found its most used implementations, prominently including \texttt{gnupg}, crucially flawed, we believe our results are of relevance and interest for the RWC'22 audience. In a nutshell, our attacks exploit that different OpenPGP implementations assume different interpretations of ElGamal encryption (group structure, generators, etc).

In January 2020, Chrome published a blog post detailing our strategy for removing third party cookies from the web. It's a two-pronged approach. First, we need to prevent other covert types of tracking that might replace cookies. But also, we need to provide a well-lit path to a new way to do things, so that web developers who use third-party cookies today — including the online advertising ecosystem — have other ways to accomplish their goals, with better privacy properties built in. Solutions here are both difficult and complex, as we try to squeeze out the maximum amount of utility with the minimum amount of trust in parties other than the client. In this talk we’ll outline specific challenges we’ve faced in designing APIs for ads targeting and ads measurement, as well as various cryptographic technologies we have explored.

As the Internet of Things (IoT) rolls out today to devices whose lifetime may well exceed a decade, conservative threat models should consider attackers with access to quantum computing power.The IETF SUIT standard defines a security architecture for IoT software updates, standardizing metadata and cryptographic tools---namely, digital signatures and hash functions---to guarantee the legitimacy of software updates. SUIT's performance has previously been evaluated in pre-quantum contexts, but not in a post-quantum context. Taking the open-source implementation of SUIT available in RIOT as a case study, we survey post-quantum considerations, focusing on low-power, microcontroller-based IoT devices with stringent constraints on memory, CPU, and energy consumption. We benchmark a selection of proposed post-quantum signature schemes (LMS, Falcon, and Dilithium) and compare them with current pre-quantum signature schemes (Ed25519 and ECDSA) on a variety of IoT hardware including ARM Cortex-M, RISC-V, and Espressif (ESP32), which form the bulk of modern 32-bit microcontroller architectures. Interpreting the results in the context of SUIT, we estimate the real-world impact of post-quantum alternatives for a range of typical software update categories.

V2V technology has the potential to prevent 615,000 collisions per year in the US, reduce congestion by up to 30%, and support efforts in slowing climate change by eliminating 5% of vehicle CO2 emissions. However, the security of V2V technology is often an afterthought, much less the threat of quantum computing on this security. With experts estimating that RSA-2048 will be broken by quantum computers with a probability of 50-99% by 2051, and cars manufactured today having an expected lifespan of 30 years, time is running out. This research is the first full-scale study into how post-quantum cryptography (PQC) will interact with current standards for vehicle-to-vehicle (V2V) communications. Connected vehicles use V2V technology to exchange safety messages that allow them to avoid colliding with each other, improving roadway safety and proximity awareness. These communications must be secured against malicious attacks to ensure an adversary cannot abuse V2V to cause a collision, traffic jam, or other unsafe and/or disruptive situation. The IEEE 1609.2 standard (2016) specifies authentication mechanisms for V2V communication. However, it relies on the Elliptic Curve Digital Signature Algorithm (ECDSA), which is not quantum-secure. It is therefore imperative that this standard be updated to support quantum-secure algorithms in line with current PQ standardisation efforts by NIST (2016). To the best of our knowledge, ours is among the first works to consider PQC in conjunction with the 1609.2 standard from the perspective of digital signatures, and the first to do so with consideration for the unique constraints imposed by the complex, wireless environment of V2V communications. In this talk, we consider how the three NIST digital signature finalists would integrate with the IEEE 1609.2 standard and, using these observations, we propose several practical designs for consideration during migration to PQC. Specifically, we conclude that Falcon-512 is the most suitable NIST PQC finalist for V2V and illustrate how Falcon can be incorporated into pure PQC, hybrid classical-PQC, backwards-compatible and ``partially quantum-secure'' designs to leverage PQ security while accounting for its large public key sizes. Through experimental evaluation of these designs using a software-defined radio testbed, we show that a partially quantum-secure hybrid scheme, using post-quantum certificates to support classical ECDSA signatures, achieves the best compromise between PQ security and little impact on V2V system performance during the transition phase.

Solely functionally-correct cryptographic implementations are often not sufficient in many real-world use-cases. For example, many payment, transit and identity use-cases require protection against advanced side-channel attacks, using certified implementations to protect the users and their data. In this presentation, we demonstrate that realizing this for post-quantum cryptography (PQC) is significantly more complex and computationally expensive compared to its classical public-key counterparts (RSA and ECC). The core of the issue is the Fujisaki-Okamoto (FO) transform, used in many key-exchange finalists considered for standardization, which allows for very powerful chosen-ciphertext side-channel attacks. While this attack vector is known in academia and used to break unprotected and protected implementations of PQC with very few traces, it is our impression that the practical impact has not yet been fully grasped by the applied cryptographic community. In this talk, we highlight the problems that arise with variants of the FO transformation regarding side-channel analysis, quantify the impact, and show that first order masking alone is not sufficient for many practical use-cases. Through a case study of Kyber, we demonstrate that achieving the same level of protection we are used to in hardened RSA and ECC implementations is much more costly and involved for PQC algorithms that are based on the FO transform. This increased overhead comes on top of the already larger and more computationally expensive PQC algorithms. As the targeted embedded devices for these hardened implementations are often very restricted, it is not trivial to find a balance in practice between sufficient security and acceptable performance. To conclude the talk, we discuss the overarching impact of our results on industry and provide potential directions forward to overcome this threat.

Cryptographic agility frameworks enable the transition from one cryptographic algorithm or implementation to another in a computing system or application. As quantum safe algorithms (PQC) steadily progress through the NIST-led standardization process, we ask whether the research community has done enough to map and expand cryptographic deployment paradigms, most developed decades ago, to modern compute infrastructures. The problem is acutely felt by the operators of such infrastructures where applications and systems are highly distributed, involve many software and hardware components, bring together multiple stakeholders, and require policy-driven control. Since the security, performance, and manageability of cryptography matters, we contend that these are not extraneous concerns that lack connection to the applied research community.

In this talk, we will describe the design and implementation of a threshold ECDSA signing protocol. This protocol is currently being developed and integrated in the Internet Computer (IC) so as to allow Bitcoin and Ethereum transactions to be performed on the IC itself. We also report on vulnerabilities in ECDSA when combined with commonly used optimizations (such as key derivation and presignatures), as well as new techniques to mitigate against these vulnerabilties.

Modern trends such as the outsourcing of computation to the cloud and recent advances in decentralized applications, particularly in the area of blockchains, are presenting new motivation and necessity to deploy threshold cryptography. While these techniques have been traditionally considered for a small set of parties, in this paper we are interested in larger deployments. Our focus is on a setting where a large distributed system or a set of servers provides cryptographic services to other applications by operating cryptographic functions in a shared way, and with threshold security. We develop efficient and scalable building blocks for Threshold Cryptography as a Service, that enable central tasks such as distributed key generation, threshold signatures and encryption, proactive refreshing of key shares, custodial services, etc. Our solutions apply both in a traditional setting with dedicated servers, as well as in a fully decentralized architecture such as a public blockchain. The underlying design is for a functionality we call MultiVSS, which runs multiple concurrent Verifiable Secret Sharing (VSS) executions on a multiplicity of secrets input by the different protocol participants. Using batching and other techniques we achieve a reduction in the cost of processing multiple secrets by a factor of $n$, the number of parties in the system. Even for a moderate number of servers the performance gain is significant and it becomes crucial for operations involving a large number of servers as in some of our applications. Consequently, we achieve scalability to large sets of participants which, in the case of blockchains, can rise to hundreds or even thousands of nodes with each node sharing a large number of secrets in tandem. We implement and show the practicality of the system for possibly millions of clients, as in the case of custodial services, and any number (small or large) of servers. Our solution supports additional features such as packing of secrets, dynamic server allocation and dishonest majorities. We further apply these constructions to the newly introduced YOSO model.

No abstract

Investigative journalists collect large numbers of digital documents during their investigations. These documents can greatly benefit other journalists' work. However, many of these documents contain sensitive information. Hence, possessing such documents can endanger reporters, their stories, and their sources. Consequently, many documents are used only for single, local, investigations. We presented DatashareNetwork, a decentralized and privacy-preserving search system that enables journalists worldwide to find documents via a dedicated network of peers, as the first search engine designed by journalists for journalists in 2020 to address this problem. We start the talk by introducing real-world problems that investigative journalists face and describe DatashareNetwork as a possible solution. Then, we discuss the practical challenges of moving forward from an academic prototype to deploying DatashareNetwork for the International Consortium of Investigative (ICIJ). This talk covers (1) our joint requirement gathering and (2) design with journalists, (3) a user study to help ICIJ with presenting the privacy property of our system to journalists and making utility/privacy trade-off decisions, (4) deployment challenges to integrate DatashareNetwork into ICIJ's IT infrastructure, and finally (5) open problems that require more attention from the community.

Verifying where and when a digital image was taken has become increasingly difficult; this issue of image provenance is especially concerning in the realm of news media. While fact-checking services can identify misinformation, enabling individuals to personally verify the provenance of photos would prevent them from having to rely on third-parties and empower them to protect themselves. The Coalition for Content Provenance and Authenticity (C2PA) has developed a standard to verify image provenance that relies on digital signatures produced by cameras; however, photos are often edited (cropped, resized, converted to grayscale, etc.) before being included in a news story, and the public cannot validate signatures on the original photo given only the published image. The C2PA standard addresses this issue by having C2PA-enabled editing applications sign the edits that have taken place, but this solution requires trusting the C2PA applications. In contrast, we propose using zk-SNARKs to prove which edits have been applied to a given photo. The completeness and soundness of these proofs mean that the verifier need not trust the prover, which solves the trust problem posed by the C2PA standard. We implemented Circom programs to generate proofs for various common photo edits, and we demonstrate the practicality of these proofs through timing experiments. Witness and proof generation take only a few minutes for realistically sized pictures; verification time is around 10 ms; and proof sizes are around 800 bytes.

The US Defense Advanced Research Project Agency (DARPA) has been investing in cryptographic technologies for the last 10+ years, starting with the PROCEED program in fully homomorphic encryption. This talk will be about new, late-breaking results and insights gleaned by leading and managing DARPA’s cryptography and privacy programs over the last five years, with particular focus on our many applications. Specific technical highlights will be on recent RACE (secure, anonymous messaging) and SIEVE (zero knowledge) program results, especially those that have broad applications, instead of defense-only.

At RWC in 2019, Gregory Neven presented seminal work on a range of two-round multisignature schemes, all of which proved to be insecure against ROS attacks. At that time, it appeared doubtful if concurrently secure two-round multi-party Schnorr signatures could exist. In 2020, this research question was answered in the affirmative, and we saw the emergence of several two-round multi-party Schnorr signature scheme secure under concurrent sessions, namely FROST on the threshold side, MuSig2 (presented at RWC 2021) and DWMS on the multisignature side. Three years have passed since these schemes were first published, and we have learned a lot in their transition from theory to practical use. In this talk, we will review these lessons learned, and how the field has since progressed. We will then introduce a range of open research questions that, if solved, would dramatically improve the practicality and applicability of these schemes in real-world systems.

Since the publication of the initial 2018 paper, the DKLs protocols [Doerner et al., IEEE S&P 2018 and 2019] have been deployed to secure cryptocurrency assets at considerable scale. In this time, much has changed in our understanding of industry needs, perspectives on protocol design, as well as the theory underlying our protocols. There is not at present an academic venue to announce such changes to the broader community as they do not constitute technical novelty, but they are important to communicate nonetheless. Until this point, we have communicated updates of this nature privately to developers on an ad-hoc basis. While this has been effective in supporting---and learning from---the developers with whom we have interacted directly, a more systematic approach is required for a dialogue with the broader community. We have therefore synthesized the information that is relevant to developers who wish to deploy and maintain our protocols today, and made the necessary resources available on a dedicated website. In this talk, we will give a summary of the resources that developers can expect to find on our site. Highlights include 1. Conservative Design Principles: We discuss standard vs non-standard functionalities for ECDSA, and what it takes to realize them. In response to criticism of our non-standard ideal functionality in our two-party paper, we provide a three-round version of our signing protocol that realizes the standard F_ECDSA functionality, along with recommendations for modes of operation. We additionally discuss the marginal cost of achieving UC security; in particular the efficiency of signing remains the same even with this improved security guarantee, due to an approach that avoids the use of zero-knowledge proofs. 2. Security of primitives: We make important recommendations for the instantiation of underlying primitives including Oblivious Transfer, and Secure Multiplication. Such recommendations include crucial non-obvious implementation details such as enforcing sequentiality of statistical checks on shared state, and random oracle tagging, as well as higher level advice in choice of protocols for building blocks. 3. Efficiency: We compare and contrast the efficiency profiles of homomorphic encryption based approaches to ECDSA, and OT based ones such as ours. Through benchmarks on diverse hardware and points of comparison in broadly relatable terms, we make the case that OT based threshold ECDSA achieves the best tradeoffs in many scenarios. Additionally, we present optimizations to our protocol that provide noticeable improvements in bandwidth. 4. Modes of operation: We discuss how to achieve proactive security---an industry best practice today---when using our protocols. Additionally, we discuss non-interactive signing in the preprocessing model, which is a mode of operation that has received much interest in the industry recently. 5. We discuss our experiences in helping several companies that have implemented, tested internally, and ultimately deployed our protocol to their users.

We propose a new cryptographic primitive called verifiably encrypted threshold key derivation (VETKD) that extends identity-based encryption with a decentralized way of deriving decryption keys. We show how VETKD can be leveraged on modern blockchains to build scalable decentralized applications (or dapps) for a variety of purposes, including preventing front-running attacks on decentralized finance (DeFi) platforms, end-to-end encryption for decentralized messaging and social networks (SocialFi), cross-chain bridges, as well as advanced cryptographic primitives such as witness encryption and one-time programs that previously could only be built from secure hardware or using a trusted third party. And all of that by secret-sharing just a single secret key...

We present a practical method to achieve timelock encryption, where a ciphertext is guaranteed to be decrypted only after a specified amount of time has passed or a date has been reached. We use an existing threshold network implementing the BLS signature scheme and use it in the context of Boneh and Franklin's identity-based encryption (IBE) scheme. The threshold network acts as a decentralised Private Key Generator in the IBE scheme where identities are the round numbers and secret keys are the randomness associated with this round output by the beacon. Therefore anyone can encrypt a message towards a specific round, which can be only be decrypted when the threshold network releases the associated randomness. A noticeable advantage of this scheme is that only users (senders and recipients) are required to perform additional cryptographic operations; the threshold network does not need to be aware of any encryption happening and does not require any change to support this scheme. We also release an open-source implementation of our scheme and a live web page that can be used in production now relying on the existing League of Entropy (LoE) network acting as a distributed public randomness beacon service using threshold BLS signatures. The LoE is a threshold BLS network producing random beacons at a frequency of 30 seconds and has been running in production without missing a single beacon for the past two years, ensuring very high availability to any user of our timelock solution.

This talk presents Portunus, a global system used by Cloudflare to restrict where in the world a customer's TLS private keys can be accessed based on some policy. It is an RBAC system built using ciphertext-policy attribute-based encryption, a variant of public-key cryptography introduced in 2005, that enables access control to be enforced with minimal dependence on a central authority. Using Portunus as an example, we discuss the benefits of employing attribute-based encryption (ABE) to construct access control systems for distributed settings. Portunus evolved from an earlier system, Geo Key Manager, previously presented at RWC 2018. Prompted by a question from the audience, we attacked the inflexible policies and vulnerability to collusion by replacing a home-grown simulation of an ABE-like scheme using Identity Based Encryption and Broadcast Encryption, with an established ABE scheme by TKN. This shortcoming was validated when customers demanded richer data restriction policies to reflect the increasing balkanization of the Internet in response to regulations such as GDPR. However, it is not enough to drop in a new scheme: real-world systems have to deal with attribute changes, key rotation, performance needs, and high loads. It also needs to address the needs of real users. This talk will discuss the translation of a ciphertext-policy ABE scheme from theory to practice and the hurdles along the way, as well as show how successful application of an imperfect cryptographic solution paved the way for adoption of a theoretically more satisfying and more capable solution.

This talk will make the case, on behalf of a group of authors of many of the recent results on commitment in AEAD, that the community should prioritize and standardize AEAD designs that achieve commitment to the key, associated data, and nonce. We call this context commitment. The main benefit of such schemes is that they preclude practitioners from having to make choices about what parts of the context should be committing. While context commitment has not yet seen the same kind of attacks in practice as key commitment, we expect them to be discovered and, to get ahead of attackers, standardization efforts should therefore target context commitment. We will start our presentation by defining context commitment [BH22], highlighting in particular how it is not formally implied by key commitment. We next discuss new attacks that exploit this gap, including showing context-commitment attacks on recently proposed key commitment-secure schemes [Kra19, §3.1.1], [ADG+22, §5.3], and [D+22]. These hint at a rich landscape of possible attacks, and we briefly discuss frameworks that explore this landscape [BH22,CR22,MLGR22]. Finally, we provide an overview of recent proposals for new AEAD schemes that achieve context commitment, and discuss avenues for future work.

Wi-Fi devices routinely queue frames at various layers of the network stack before transmitting, for instance, when the receiver is in sleep mode. In this work, we investigate how Wi-Fi access points manage the security context of queued frames. By exploiting power-save features, we show how to trick access points into leaking frames in plaintext, or encrypted using the group or an all-zero key. We demonstrate resulting attacks against several open-source network stacks. We attribute our findings to the lack of explicit guidance in managing security contexts of buffered frames in the 802.11 standards. The unprotected nature of the power-save bit in a frame’s header, which our work reveals to be a fundamental design flaw, also allows an adversary to force queue frames intended for a specific client resulting in its disconnection and trivially executing a denial-of-service attack. Furthermore, we demonstrate how an attacker can override and control the security context of frames that are yet to be queued. This exploits a design flaw in hotspot-like networks and allows the attacker to force an access point to encrypt yet-to-be-queued frames using an adversary-chosen key, thereby bypassing Wi-Fi encryption entirely. Our attacks have a widespread impact as they affect various devices and operating systems (Linux, FreeBSD, iOS, and Android) and because they can be used to hijack TCP connections or intercept client and web traffic. Overall, we highlight the need for transparency in handling security context across the network stack layers and the challenges in doing so.

Historically, the cryptographic algorithms used for ciphering and integrity-protection between mobile phones and cell towers intended to protect SMS, voice calls, etc ... have been shrouded in mystery. Additionally, there is a history of mobile phones accepting cellular connections with no or improperly configured cryptography (the “null cipher” problem, as it’s called in the field of cellular security) with users having little control over this. In an upcoming Android release, users will be able to choose to disable connecting to cell towers with no ciphering and integrity protection. This will be a talk about the history of null ciphers in cellular standards, their real life use in the field, how this problem space overlaps with fake base stations (aka “IMSI-catchers” or “Stingrays”), and an overview of how we’ve addressed these issues in an upcoming Android release, and some of the engineering challenges we faced.

Although the newest versions of TLS are considered secure, flawed implementations may undermine the promised security properties. Such implementation flaws result from the TLS specifications’ complexity, with exponentially many possible parameter combinations. Combinatorial Testing (CT) is a technique to tame this complexity, but it is hard to apply to TLS due to semantic dependencies between the parameters and thus leaves the developers with a major challenge referred to as the test oracle problem: Determining if the observed behavior of software is correct for a given test input. In this work, we present TLS-Anvil, a test suite based on CT that can efficiently and systematically test parameter value combinations and overcome the oracle problem by dynamically extracting an implementation-specific input parameter model (IPM) that we constrained based on TLS specific parameter value interactions. Our approach thus carefully restricts the available input space, which in return allows us to reliably solve the oracle problem for any combination of values generated by the CT algorithm. We evaluated TLS-Anvil with 13 well known TLS implementations, including OpenSSL, BoringSSL, and NSS. Our evaluation revealed two new exploits in MatrixSSL, five issues directly influencing the cryptographic operations of a session, as well as 15 interoperability issues, 116 problems related to incorrect alert handling, and 100 other issues across all tested libraries.

EDHOC is a lightweight authenticated key exchange protocol for IoT communication, currently being standardized by the IETF. Its design is a trimmed-down version of similar protocols like TLS 1.3, building on the SIGn-then-MAc (SIGMA) rationale. In its trimming, however, EDHOC notably deviates from the SIGMA design by sending only short, non-unique credential identifiers, and letting recipients perform trial verification to determine the correct communication partner. Done naively, this can lead to identity misbinding attacks when an attacker can control some of the user keys, invalidating the original SIGMA security analysis and contesting the security of EDHOC. In this talk we present a computational analysis capturing the potential attack vectors introduced by non-unique credential identifiers. We show that EDHOC, in its latest draft version 17, indeed achieves the intended key exchange security with user authentication even in a strong model where the adversary can register malicious keys with colliding identifiers, given that the employed signature scheme provides so-called exclusive ownership. Through our security result, we confirm cryptographic improvements integrated by the IETF working group in recent draft versions of EDHOC based on recommendations from our and others' analysis. We will comment on these fruitful interactions with the IETF LAKE working group in the talk, as an encouraging example of how proactive security analyses accompanying standardization efforts benefit real-world cryptography.

No abstract

As privacy-awareness rises, demand for end-to-end encrypted (E2EE) services is increasing. However, not all systems live up to their advertised security guarantees. MEGA—the largest provider of E2EE cloud storage with over 260 million users—failed to protect the confidentiality and integrity of their customers’ data, as our recent paper “MEGA: Malleable Encryption Goes Awry” showed. In this talk, we take a step back and discuss why it is surprisingly challenging to design a privacy-preserving cloud storage protocol that is secure even when the cloud provider is actively malicious. Recent academic effort focused on building file sharing systems which hide metadata. However, systems in practice still face much more fundamental challenges including key management, asynchronously coalescing updates stemming from collaboration on shared E2EE files, and cryptographic agility. We briefly discuss the approach of MEGA and how it was susceptible to a key recovery attack that allowed a malicious cloud provider to decrypt user files, among other vulnerabilities. Based on the attacks on MEGA, we suggest best practices for designing secure E2EE cloud storage systems. Unfortunately, it is infeasible for MEGA to completely redesign their system due to scale and backward compatibility. Even if a redesign was possible, the security they currently aim to provide still falls short of offering desirable properties like post-compromise security, forward security, and key rotation. With this in mind, we point out open questions for future work and advocate for a standardization process for a cloud storage design.

We conduct a security analysis of the e-voting protocol used for the largest political election using e-voting in the world, the 2022 French legislative election for the citizens overseas. Due to a lack of system and threat model specifications, we built and contributed such specifications by studying the French legal framework and by reverse-engineering the code base accessible to the voters. Our analysis reveals that this protocol is affected by two design-level and implementation-level vulnerabilities. We show how those allow a standard voting server attacker and even more so a channel attacker to defeat the election integrity and ballot privacy due to 6 attack variants. We propose and discuss 5 fixes to prevent those attacks. Our specifications, the attacks, and the fixes were acknowledged by the relevant stakeholders during our responsible disclosure. Our attacks are in the process of being prevented with our fixes for future elections. Beyond this specific protocol, we draw general conclusions and lessons from this instructive experience where an e-voting protocol meets the real-world constraints of a large-scale and political election.

No abstract

Grassroots organizers are people who work from within communities to effect economic, environmental, social, or political change. Engagement, communication, and trust between community members are vital to the success of grassroots movements. Grassroots organizers have therefore developed long-standing community-based trust and communication protocols that are grounded in physical community spaces such as schools, libraries, town halls, community centers, places of worship, parks, and streets. Digital networking tools afford organizers the ability to engage more people, quickly disseminate important information, and decentralize movements for change. However, they also increase the level of personal risk that communities face by organizing, since the visibility of personal information and communication on social media facilitates surveillance, disinformation, infiltration, and ultimately physical violence from law enforcement, hate groups, and foreign governments. In this talk, we will explore the question: How might we use cryptographic tools to adapt the existing trust and communication protocols of grassroots organizers from physical to digital spaces, without increasing the risk of surveillance, disinformation, and infiltration of grassroots movements?