International Association
for Cryptologic Research

The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols. A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is highly critical with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by McEliece implementations in the cryptographic libraries Classic McEliece and Botan.We propose a novel decoding algorithm to reconstruct a secret key from its public key with information from a Gaussian transformation leak. Even if the obtained side-channel leakage is extremely noisy, i.e., each bit is flipped with probability as high as r ≈ 0.4, we succeed to recover the secret key in a matter of minutes for all proposed (Classic) McEliece instantiations. Remarkably, for high-security McEliece parameters, our attack is more powerful in the sense that it can tolerate even larger r . We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor.Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage.

Speculative out-of-order execution is a strategy of masking execution latency by allowing younger instructions to execute before older instructions. While originally considered to be innocuous, speculative out-of-order execution was brought into the spotlight with the 2018 publication of the Spectre and Meltdown attacks. These attacks demonstrated that microarchitectural side channels can leak sensitive data accessed by speculatively executed instructions that are not part of the normal program execution. Since then, a significant effort has been vested in investigating how microarchitectural side channels can leak data from speculatively executed instructions and how to control this leakage. However, much less is known about how speculative out-of-order execution affects microarchitectural side-channel attacks.In this paper, we investigate how speculative out-of-order execution affects the Evict+Time cache attack. Evict+Time is based on the observation that cache misses are slower than cache hits, hence by measuring the execution time of code, an attacker can determine if a cache miss occurred during the execution. We demonstrate that, due to limited resources for tracking out-of-order execution, under certain conditions an attacker can gain more fine-grained information and determine whether a cache miss occurred in part of the executed code.Based on the observation, we design the Evict+Spec+Time attack, a variant of Evict+Time that can learn not only whether a cache miss occurred, but also in which part of the victim code it occurred. We demonstrate that Evict+Spec+Time is an order of magnitude more efficient than Evict+Time when attacking a T-tables-based implementation of AES. We further show an Evict+Spec+Time attack on an S-boxbased implementation of AES, recovering the key with as little as 14 815 decryptions. To the best of our knowledge, ours is the first successful Evict+Time attack on such a victim.

The scale and frequency of password database compromises has led to widespread and persistent credential stuffing attacks, in which attackers attempt to use credentials leaked from one service to compromise accounts with other services. In response, browser vendors have integrated password leakage detection tools, which automatically check the user’s credentials against a list of compromised accounts upon each login, warning the user to change their password if a match is found. In particular, Google Chrome uses a centralized leakage detection service designed by Thomas et al. (USENIX Security ’19) that aims to both preserve the user’s privacy and hide the server’s list of compromised credentials. In this paper, we show that Chrome’s implementation of this protocol is vulnerable to several microarchitectural side- channel attacks that violate its security properties. Specifically, we demonstrate attacks against Chrome’s use of the memory-hard hash function scrypt, its hash-to-elliptic curve function, and its modular inversion algorithm. While prior work discussed the theoretical possibility of side-channel attacks on scrypt, we develop new techniques that enable this attack in practice, allowing an attacker to recover the user’s password with a single guess when using a dictionary attack. For modular inversion, we present a novel cryptanalysis of the Binary Extended Euclidian Algorithm (BEEA) that extracts its inputs given a single, noisy trace, thereby allowing a malicious server to learn information about a client’s password. This paper was presented at USENIX Security 2023, and the full version can be found at https://www.usenix.org/system/files/usenixsecurity23-kwong.pdf

The microarchitectural behavior of modern CPUs is mostly hidden from developers and users of computer software. Due to a plethora of attacks exploiting microarchitectural behavior, developers of security-critical software must, e.g., ensure their code is constant-time, which is cumbersome and usually results in slower programs. In practice, small leakages which are deemed not exploitable still remain in the codebase. For example, sub-cache-line leakages have previously been investigated in the CacheBleed and MemJam attacks, which are deemed impractical on modern platforms.In this work, we revisit and carefully analyze the 4k-aliasing effect and discover that the measurable delay introduced by this microarchitectural effect is higher than found by previous work and described by Intel. By combining the rediscovered effect with a high temporal resolution possible when single-stepping an SGX enclave, we construct a very precise, yet widely applicable attack with sub-cache-line leakage resolution. o demonstrate the significance of our findings, we apply the new attack primitive to break a hardened AES T-Table implementation that features constant cache line access patterns. The attack is up to three orders of magnitude more efficient than previous sub-cache-line attacks on AES in SGX. Furthermore, we improve upon the recent work of Sieck et al. which showed partial exploitability of very faint leakages in a utility function loading base64-encoded RSA keys. With reliable sub-cache-line resolution, we build an end-to-end attack exploiting the faint leakage that can recover 4096-bit keys in minutes on a laptop. Finally, we extend the key recovery algorithm to also work for RSA keys following the standard that uses Carmichael’s totient function, while previous attacks were restricted to RSA keys using Euler’s totient function.

Intel's Software Guard Extensions (SGX) promises an isolated execution environment, protected from all software running on the machine. As such, numerous works have sought to leverage SGX to provide confidentiality and integrity guarantees for code running in adversarial environments. In the past few years however, SGX has come under heavy fire, threatened by numerous side channel attacks. With Intel repeatedly patching SGX to regain security, in this paper we set out to explore the effectiveness of SGX's update mechanisms to prevent attacks on real-world deployments. To that aim, we study two commercial SGX applications. First, we investigate the Secret network, an SGX-backed blockchain aiming to provide privacy preserving smart contracts. Next, we also consider PowerDVD, a UHD Blu-Ray Digital Rights Management (DRM) software licensed to play discs on general purpose computers. We show that in both cases vendors are unable to meet security goals originally envisioned for their products, presumably due to SGX's long mitigation timelines and a difficult manual update process. This in turn forces vendors into making difficult security/usability trade offs, resulting in severe security compromises.

Most software domains rely on compilers to translate high-level code to multiple different machine languages, with performance not too much worse than what developers would have the patience to write directly in assembly language. However, cryptography has been an exception, where many performance-critical routines have been written directly in assembly (sometimes through metaprogramming layers). Some past work has shown how to do formal verification of that assembly, and other work has shown how to generate C code automatically along with formal proof, but with consequent performance penalties vs. the best-known assembly. We present CryptOpt, the first compilation pipeline that specializes high-level cryptographic functional programs into assembly code significantly faster than what GCC or Clang produce, with mechanized proof (in Coq) whose final theorem statement mentions little beyond the input functional program and the operational semantics of x86-64 assembly. On the optimization side, we apply randomized search through the space of assembly programs, with repeated automatic benchmarking on target CPUs. On the formal-verification side, we connect to the Fiat Cryptography framework (which translates functional programs into C-like IR code) and extend it with a new formally verified program-equivalence checker, incorporating a modest subset of known features of SMT solvers and symbolic-execution engines. The overall prototype is practical, e.g. producing new fastest-known implementations for the relatively new Intel i9 12G, of finite-field arithmetic for both Curve25519 (part of the TLS standard) and the Bitcoin elliptic curve secp256k1.

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.

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.

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)

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

Over the past two decades, cache attacks have been identified as a threat to the security of cipher implementations. These attacks recover secret information by combining observations of the victim cache accesses with the knowledge of the internal structure of the cipher. So far, cache attacks have been applied to ciphers that have fixed state transformations, leaving open the question of whether using secret, key-dependent transformations enhances the security against such attacks. In this paper we investigate this question. We look at an implementation of the North Korean cipher Pilsung, as reverse-engineered by Kryptos Logic. Like AES, Pilsung is a permutation-substitution cipher, but unlike AES, both the substitution and the permutation steps in Pilsung depend on the key, and are not known to the attacker. We analyze Pilsung and design a cache-based attack. We improve the state of the art by developing techniques for reversing secret-dependent transformations. Our attack, which requires an average of eight minutes on a typical laptop computer, demonstrates that secret transformations do not necessarily protect ciphers against side channel attacks.

Intel Software Guard Extensions (SGX) allows users to perform secure computation on platforms that run untrusted software. To validate that the computation is correctly initialized and that it executes on trusted hardware, SGX supports attestation providers that can vouch for the user’s computation. Communication with these attestation providers is based on the Extended Privacy ID (EPID) protocol, which not only validates the computation but is also designed to maintain the user’s privacy. In particular, EPID is designed to ensure that the attestation provider is unable to identify the host on which the computation executes. In this work we investigate the security of the Intel implementation of the EPID protocol. We identify an implementation weakness that leaks information via a cache side channel. We show that a malicious attestation provider can use the leaked information to break the unlinkability guarantees of EPID. We analyze the leaked information using a lattice-based approach for solving the hidden number problem, which we adapt to the zero-knowledge proof in the EPID scheme, extending prior attacks on signature schemes.

It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits.In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024. For RSA-2048 our attack is efficient for 13% of keys.