Research by DJ Bernstein et al. Cache-Timing Attacks on AES and related work on constant-time engineering

BY KEYHUNTER 03.09.2026

Research by DJ Bernstein et al. Cache-Timing Attacks on AES and related work on constant-time engineering

Abstract:  This article examines the foundations of cache-timing attacks, laid out in the classic works of Daniel J. Bernstein, as well as related research in the fields of fault attacks and constant-time engineering. It covers the microarchitectural mechanisms of AES T-table leaks, mathematical models of correlation and cache collisions, cryptographic signature attack techniques (RSA-CRT, ECDSA, Schnorr/Ed25519), and modern hardware and software methods for auditing and protecting key material.

1. Introduction and background of AES standardization

During the NIST open competition to select the AES standard (1997–2000), the Rijndael project was selected due to its high performance and compact programming model. However, during the FIPS 197 specification phase, NIST and the developers erroneously claimed that table lookups were immune to timing attacks. The reality of general-purpose processor microarchitecture (x86, ARM, SPARC) disproved this hypothesis: the physical latency of accessing a cache line directly depends on its current state (L1/L2 Cache Hit vs. Cache Miss).

Archival precedent:  In 1996, Paul Kocher published a seminal paper on timing attacks on RSA and Diffie-Hellman, where in section 11 he succinctly stated:  “RAM cache hits can produce timing characteristics .” Despite this caveat, the AES working group deemed table substitutions completely secure, leading to the widespread deployment of vulnerable T-table implementations in OpenSSL, Crypto++, LibTomCrypt, and other system libraries over the next decade.

2. Microarchitectural basis of leakage: T-tables and cache lines

An optimized software implementation of AES on 32-bit platforms combines linear and nonlinear round operations (SubBytes, ShiftRows, MixColumns) into four precomputed tables $T_0, T_1, T_2, T_3$ of size 1024 bytes (256 32-bit words):

$$T_0[b] = (S'[b], S[b], S[b], S[b] \oplus S'[b])$$ $$X_{i+1, 0} = T_0[x_{i,0}] \oplus T_1[x_{i,5}] \oplus T_2[x_{i,10}] \oplus T_3[x_{i,15}] \oplus K_{i,0}$$

In the first round, the fetch index is formed as $x_{0,j} = p_j \oplus k_j$. The processor loads data not byte by byte, but in blocks—cache lines of length $L$ (usually 64 bytes, which corresponds to $\delta = L / 4 = 16$ table entries). The fetch time $t$ depends on whether the cache line with address $T_0[\langle p_j \oplus k_j angle]$ is in L1/L2 or evicted to DRAM.

// Фрагмент уязвимого кода (OpenSSL 0.9.7 / классический T-Table lookup)
uint32_t s0 = *(uint32_t *)((uint8_t *)T0 + ((p[0] ^ k[0]) << 2));
uint32_t s1 = *(uint32_t *)((uint16_t *)T1 + ((p[5] ^ k[5]) << 2));
// Секретный ключ k[i] непосредственно формирует адрес в памяти!

3. Statistical Cryptanalysis by D. J. Bernstein (2005)

Daniel Bernstein demonstrated the complete remote extraction of a 128-bit AES key over a network using a profiled correlation attack. The method is divided into the following phases:

  1. Study Phase:  On an identical test system with a known key $K_{ref}$, millions of random packets are sent, collecting timing profiles $t(j)$ for each possible plaintext byte $j \in [0, 255]$:$$t(j) = rac{1}{N_j} \sum_{m=1}^{N_j} ext{cycles}(p_b = j)$$
  2. Attack Phase:  Collect noisy timings $u(j)$ on the target server with an unknown key $K_{target}$.
  3. Correlation filtering:  Calculating the cross-correlation function:$$C(i) = \sum_{j=0}^{255} t(j) \cdot u(i \oplus j)$$The peak of the correlation $C(i)$ directly indicates the value of the key byte $k_b = i$.

Historical fact:  Bernstein’s experiment was conducted on a Pentium III server running FreeBSD and OpenSSL 0.9.7a. Although the measurements were conducted via UDP network packets, the statistical accumulation of $ pprox 2^{25}$ measurements allowed for complete network jitter cancellation and key recovery in a few hours.

4. Evolution of Cache Attacks: Collisions, Prime+Probe, Flush+Reload

Subsequent work by Bonneau & Mironov (CHES 2006) and Osvik, Shamir, and Tromer (2006) took cash cryptanalysis to the level of rigorous analytical models:

  • Cache-Collision Attacks (Final Round):  In round 10 of AES  MixColumns, the $T_4$-box table is omitted and the $S$-box table $T_4$ is used. The collision $S^{-1}[c_i \oplus k_{10,i}] = S^{-1}[c_j \oplus k_{10,j}]$ reduces the overall execution time. This reduced the required number of probes from $2^{27.5}$ to $2^{13}$.
  • Prime+Probe:  The attacker fills the cache sets with their data (Prime), lets the victim perform the operation, and then measures the re-read time (Probe).
  • Flush+Reload:  In the presence of shared memory (shared libraries), the instruction  clflush resets a specific line, and the subsequent access measurement detects the victim’s activity down to the machine instruction.

5. Related Vectors: Leak Diversification and Fault Attacks (ePrint 2011/388)

Besides cache timings, key leaks are closely related to induced faults.  Brier, Naccache, Nguyen, and Tibouchi (IACR ePrint 2011/388)  investigated modulus fault attacks on RSA-CRT signatures. Unlike the classical Boneh-DeMillo-Lipton attack (1997), the fault is injected into the public modulus N before CRT interpolation:

$$S \equiv s_p \pmod p, \quad S \equiv s_q \pmod q$$ $$\widetilde{S} = ext{CRT}(s_p, s_q) \pmod{\widetilde{N}}, \quad \widetilde{N} = N + \Delta$$

The authors showed that using orthogonal lattice techniques, the factorization of the module $N = p \cdot q$ can be restored using only 5–45 corrupted signatures, bypassing standard CRT integrity checks.

Practical Cryptanalysis:  This class of attacks has been hardware-verified by the authors using fault injection laser techniques on smart cards, proving the critical importance of end-to-end verification of the entire computational graph.

6. Vulnerabilities in signature algorithms: ECDSA, Ed25519, and hidden nonce bits

In asymmetric signature algorithms (ECDSA, Schnorr, Ed25519), any dependence of the scalar multiplication time $k \cdot G$ on the value of the random number (nonce $k$) leads to a catastrophic compromise of the private key $d$:

$$s \equiv k^{-1} (H(m) + r \cdot d) \pmod n \implies k \equiv s^{-1} H(m) + s^{-1} r \cdot d \pmod n$$

If, as a result of a cache leak in the Montgomery or wNAF algorithms, an attacker discovers even $\ell \ge 2..4$ bits of each nonce $k_i$, the problem reduces to the Hidden Number Problem (HNP). Using LLL/BKZ lattice basis reduction, the private key can be recovered in seconds:

$$L = egin{pmatrix} 2^{\ell} n & 0 & \dots & 0 \ 0 & 2^{\ell} n & \dots & 0 \t_1 & t_2 & \dots & \epsilon \end{pmatrix}$$

7. Constant-Time Engineering: Principles and Implementation Patterns

Modern cryptographic engineering is based on strict rules for the design of constant-time code:

  1. No branching by secret:  No conditional jumps  if (secret), ternary operators, or jump tables.
  2. Disable memory addressing on secret:  No table substitutions of $T[secret]$.
  3. Using Bit Multiplexers (CT Select):
// Безопасный условный выбор значения (Constant-Time Multiplexer)
uint32_t ct_select_u32(uint32_t mask, uint32_t a, uint32_t b) {
    // mask = 0xFFFFFFFF (если условие true) или 0x00000000 (если false)
    return (mask & a) | (~mask & b);
}

// Постоянное по времени сравнение буферов (Constant-Time memcmp)
int ct_memcmp(const void *a, const void *b, size_t len) {
    const uint8_t *p1 = (const uint8_t *)a;
    const uint8_t *p2 = (const uint8_t *)b;
    uint8_t diff = 0;
    for (size_t i = 0; i < len; ++i) {
        diff |= (p1[i] ^ p2[i]);
    }
    return (1 & ((diff | -diff) >> 7)); // 0 если равны, 1 если отличны
}

8. Comparative analysis of approaches to the implementation of primitives

Implementation approachCache-Timing VulnerabilityPerformance (cycles/byte)Complexity of auditExamples in production
Classic T-ChartsCritical (L1/L2 hits)Very high (8–12 cpb)Low (code is simple but vulnerable)OpenSSL < 0.9.8, old LibTomCrypt
Bitsliced ​​AESCompletely absentMedium/High (parallel)High (complex logical graph)NaCl, libsodium, BearSSL
Hardware instructions (AES-NI / ARM Crypto)Completely absentMaximum (0.6–1.2 cpb)Minimum (hardware level)Modern OpenSSL, Linux Kernel, BoringSSL
CSwap/Montgomery Ladder (ECC)Absent in CT multiplexersOptimal for curvesMedium (requires compiler control)libsecp256k1, Curve25519 (TweetNaCl)

9. Audit methodology and instrumental control

To guarantee constant-time properties, specialized static and dynamic verifiers are used:

  • Dudect:  Dynamic analysis based on the nonparametric statistical Student’s t-test / Kolmogorov-Smirnov test (t-test leakage detection).
  • Valgrind + Memcheck (ctgrind):  Marks private keys with  VALGRIND_MAKE_MEM_UNDEFINED() and then generates errors when attempting to use undefined data as branch or memory addresses.
  • Compiler invariants:  Limit unwanted compiler optimizations ( opt-barrier, inline-assembly wrappers).
// Пример аннотации ctgrind для аудита закрытого ключа
#include <valgrind/memcheck.h>

void audit_scalar_mult(const uint8_t *secret_scalar, size_t len) {
    VALGRIND_MAKE_MEM_UNDEFINED(secret_scalar, len);
    // Выполнение алгоритма (CSwap + point add)
    // Любое ветвление по secret_scalar вызовет аварию Memcheck
    VALGRIND_MAKE_MEM_DEFINED(secret_scalar, len);
}

Sources

A study by DJ Bernstein et al. Cache-Timing Attacks on AES and Constant-Time Engineering:  https://cryptrade.ru/a-study-by-dj-bernstein-et-al-cache-timing-attacks-on-aes-and-constant-time-engineering/

  1. A. Chow.  BIP-174: Partially Signed Bitcoin Transaction Format , status Final, created 2017-07-12. GitHub bitcoin/bips.
  2. Bitcoin BIP-32: Hierarchical Deterministic Wallets.
  3. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA).
  4. Bitcoin BIP-127: Proof of Reserves; BIP-370: PSBT Version 2; BIP-141: Segregated Witness.