International Association
for Cryptologic Research

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.

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.

No abstract

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.

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).

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.

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/.

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.

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.

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.

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.

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.

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)

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.

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.

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.

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.

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.

No abstract

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.

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.

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.

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.

No abstract

No abstract

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.

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.

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.

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).

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.

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.

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.

No abstract

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.

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.

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.

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.

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

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.

No abstract

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.