International Association
for Cryptologic Research

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

No abstract

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.

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.

No abstract

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.

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.

No abstract

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.

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.