Research by PC Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems (CRYPTO 1996)

Abstract. In 1996, Paul C. Kocher presented a fundamental paper at the CRYPTO ’96 conference that laid the foundations for practical side-channel cryptanalysis. The study demonstrated that microarchitectural and software timing variations in the computation of cryptographic primitives allow for the complete recovery of secret keys. The paper analyzes the mathematical model of the attack, factorization and decryption algorithms, measurement error limits, and a retrospective of real-world incidents, ranging from OpenSSL vulnerabilities to attacks on symmetric and post-quantum ciphers.

1. Introduction and genesis of the side channel problem

Before Paul Kocher’s publication, cryptographic algorithms (RSA, Diffie-Hellman, DSA/DSS) were assessed primarily through the lens of classical computational complexity (“black box”): security was determined by the difficulty of factoring large integers or solving the discrete logarithm problem in a finite field. Kocher made a conceptual shift (“gray box”) by showing that the physical implementation of an algorithm inevitably generates information leaks over the execution time $T$.

The sources of time variability are:

Conditional jumps and branches ( if/else) that depend on bits of the secret key or intermediate data.
Performance optimizations (skipping multiplications by zero/one, normalization).
Processor instruction delays (e.g. integer division with floating point clock).
RAM cache misses/hits.

Historical context and cryptanalytic precedent: In early hardware security modules (HSMs) and smart cards of the mid-1990s, code optimization for low computing power resulted in calls to multiplication routines being skipped for zero bits. This allowed terminal operators to recover private keys using a simple timer.

2. Mathematical model of attack on basic modular exponentiation

In Diffie-Hellman and RSA schemes, the closed operation reduces to the calculation $R = y^x \pmod n$, where the modulus $n$ and the input value $y$ are known to the cryptanalyst, and the exponent $x = (x_0, x_1, \dots, x_{w-1})_2$ is a secret $w$-bit key.

Square-and-Multiply (left to right / right to left) algorithm

In Kocher’s basic version, the classical cycle is considered:

Input: Base y, modulus n, secret key x of length w bits.
Output: R = y^x mod n

1. s_0 = 1
2. For k = 0 to w - 1:
3. If (bit k of x) == 1:
4. R_k = (s_k * y) mod n
5. Else:
6. R_k = s_k
7. s_{k+1} = (R_k)^2 mod n
8. Return R_{w-1}

The cryptanalyst recovers the key bit by bit, starting with the least significant/most significant known bit. Suppose the bits $x_0, \dots, x_{b-1}$ have already been found. Then the attacker can accurately simulate the state $s_b$.

If bit $x_b = 1$, the loop performs the operation $R_b = (s_b \cdot y) \pmod n$.
If $x_b = 0$, this operation is skipped.

If among all $y$ there are specific values for which modular multiplication is abnormally slow (e.g., an extra reduction step is required), the observed total time $T$ will be strictly correlated with the hypothesis $x_b = 1$.

3. Statistical formalism: signal-to-noise ratio and analysis of variance

The total execution time of an operation on the $i$-th message $y_i$ is formalized as the sum of elementary delays:

$$T_i = e_i + \sum_{k=0}^{w-1} t_{i, k}$$

where $t_{i, k}$ is the time spent on the $k$-th step of exponentiation for message $y_i$, and $e_i$ is a random additive measurement error (network jitter, OS interrupts, timer quantization).

Estimation via variance reduction

For a hypothesis about the first $b$ bits of the exponent, the cryptanalyst simulates the computation and subtracts the estimated time:

$$T’_i(x_b) = T_i — \sum_{k=0}^{b-1} t_{i, k}(y_i, x_b)$$

If the prefix $x_b$ is guessed absolutely correctly, the residual random variable is $e_i + \sum_{k=b}^{w-1} t_{i, k}$, and its theoretical variance is:

$$\mathrm{Var}\left(T’ \mid ext{the hypothesis is correct} ight) = \mathrm{Var}(e) + (w – b)\,\mathrm{Var}(t)$$

If an error occurs on a bit $c < b$, the intermediate values become pseudorandom, decorrelating the model with reality. The variance increases:

$$\mathrm{Var}\left(T’ \mid ext{hypothesis false} ight) = \mathrm{Var}(e) + (w – b + 2c)\,\mathrm{Var}(t)$$

Theoretical probability of success and the required number of measurements

Using the central limit theorem, Kocher derived a formula for the probability of correctly distinguishing a bit with a sample size of $j$ measurements:

$$P( ext{Correct}) = \Phi\left( \sqrt{ rac{j \cdot (b – c)}{2(w – b)}} ight)$$

where $\Phi(z)$ is the cumulative function of the standard normal distribution. The required number of measurements $j$ is directly proportional to the key width $w$ and inversely proportional to the variance of the elementary multiplication $\mathrm{Var}(t)$.

4. Features of attacks on CRT-RSA, Montgomery and DSS

4.1 RSA with Chinese Remainder Theorem (CRT)

In optimized implementations, $y_p = y \pmod p$ and $y_q = y \pmod q$ are calculated. If a cryptanalyst selects ciphertexts $y pprox p$, then division is not required for $y < p$, and a subtraction cycle is started for $y > p$. Kocher recorded a difference in the RSAREF library: an average of 42.1 μs for $y < p$ versus 73.0 μs for $y > p$, which made it possible to calculate the most significant digits of the divisors of the modulus $n$.

4.2. Montgomery Multiplication

The Montgomery algorithm eliminates classical division, but ultimately requires a conditional reduction subtraction: if (R >= n) R = R - n;. The presence or absence of this step (“Montgomery extra reduction”) generates a sufficient leakage signal to recover the private key.

4.3. Digital Signature Standard (DSS/DSA)

The computation of the signature $s = (k^{-1}(H(m) + x \cdot r)) \pmod q$ involves the secret key $x$. Variations in the length of the modular reduction of the product $x \cdot r \pmod q$ given $r$ reveal the high-order bits of the private key $x$.

Cryptanalysis Fact: Brumley-Boneh Attack (2003): David Brumley and Dan Boneh implemented a practical network timing attack against an OpenSSL 0.9.6 server, exploiting the Montgomery reduction and Karatsuba multiplication steps of CRT-RSA over a local network, extracting an RSA-1024 private key in a few hours.

5. Comparative analysis of counteraction methods

Method of protection	Principle of implementation	Advantages	Weaknesses and vulnerabilities
Randomization (Blinding) of the base	$y’ = y \cdot v_i \pmod n$; $R’ = (y’)^x \pmod n$; $R = R’ \cdot v_f \pmod n$	High speed, low overhead (~2-5%)	Does not protect against power profile attacks (SPA/DPA) without key randomization
Randomization of the indicator	$x’ = x + k \cdot \phi(n)$ or $x’ = x + k \cdot \mathrm{ord}(G)$	Masks the Hamming weight of the key	Requires caution when generating random $k$
Constant-Time Logic	Eliminating conditional branches, Montgomery Ladder, cswap	Complete isolation from input data variations	Reduced overall performance, difficulty of compiler-level verification
Noise injection	Adding random beats `sleep(rand())`	Ease of software integration	Inefficient: the number of required measurements grows quadratically $O(\sigma_{noise}^2)$, the attack is mitigated by averaging

6. Practical Implementation: Vulnerable Code vs. Constant-Time & Blinding

Vulnerable implementation (C-style)

// VULNERABLE: Running time is linear in the Hamming weight of the private key d
BIGNUM *rsa_mod_exp_vulnerable(const BIGNUM *y, const BIGNUM *d, const BIGNUM *n) {
    BIGNUM *r = BN_new();
    BN_one(r);
    int bits = BN_num_bits(d);

    for (int i = bits - 1; i >= 0; i--) {
        BN_mod_sqr(r, r, n, ctx); // r = r^2 mod n
        if (BN_is_bit_set(d, i)) {
            BN_mod_mul(r, r, y, n, ctx); // Only executed for 1! Time leak!
        }
    }
    return r;
}

Secure Implementation: Blinding by Kocher/Schnorr

// PROTECTED: Input Ciphertext Randomization (Base Blinding)
int rsa_mod_exp_blinded(BIGNUM *r, const BIGNUM *y, RSA_KEY *key, BN_CTX *ctx) {
    BIGNUM *v_f = BN_new();
    BIGNUM *v_i = BN_new();
    BIGNUM *y_blind = BN_new();

    // 1. Choose a random v_f that is relatively prime to n
    BN_rand_range(v_f, key->n);

    // 2. Calculate v_i = (v_f^-1)^e mod n (where e is the open exponent)
    BN_mod_inverse(v_i, v_f, key->n, ctx);
    BN_mod_exp(v_i, v_i, key->e, key->n, ctx);

    // 3. Blinding the input message: y_blind = (y * v_i) mod n
    BN_mod_mul(y_blind, y, v_i, key->n, ctx);

    // 4. Closed operation on a pseudo-random value
    BN_mod_exp(r, y_blind, key->d, key->n, ctx);

    // 5. Recovering the original result: r = (r * v_f) mod n
    BN_mod_mul(r, r, v_f, key->n, ctx);

    BN_free(v_f); BN_free(v_i); BN_free(y_blind);
    return 1;
}

7. Archived incidents and the evolution of side-channel attacks

2003 (OpenSSL 0.9.6 CRT Leak): Brumley and Boneh demonstrated practical interception of HTTPS server private keys over a local network due to the lack of default blinding.
2013 (Lucky Thirteen): AlFardan and Paterson discovered a timing leak in the CBC padding check in TLS 1.2 (the difference in processing time between a valid and invalid HMAC when computing PKCS#7 padding), which allowed session cookies to be decrypted.
2018–2020 (Minerva & TPM-FAIL): Research into ECDSA/EdDSA (secp256k1, P-256) cryptographic libraries revealed scalar multiplication duration leaks that allowed hardware token private keys to be recovered through analysis of the least significant bits of the nonce $k$.
Modern (Kyber / Dilithium / ML-KEM): In post-quantum algorithms, notch sampling and modular reduction in polynomial rings are tested for susceptibility to timing attacks within the NIST FIPS 203/204 standard.

8. Scientific and practical heritage

Paul Kocher’s 1996 paper transformed the methodology of cryptographic engineering. It proved that the abstract mathematical security of an algorithm is insufficient to ensure confidentiality. In modern cryptography, constant-time design (absence of branching on secret data, key-based table lookups, and variable-cycle instructions) coupled with blinding techniques is a mandatory industry standard.

Normative sources

Study by PC Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS (CRYPTO 1996): https://cryptco.ru/issledovanie-pc-kocher-timing-attacks-on-implementations-of-diffie-hellman-rsa-dss-crypto-1996/

A. Chow. BIP 370: PSBT Version 2 . Bitcoin Improvement Proposals, Final status, 2021. GitHub .
A. Chow. BIP 174: Partially Signed Bitcoin Transaction Format . Bitcoin Improvement Proposals, 2017. GitHub .
Bitcoin Core. PSBT Howto ; description of workflow Creator—Updater—Signer—Finalizer—Extractor. GitHub .
Bitcoin Core PR #21283. Implement BIP 370 PSBTv2 . GitHub .

Original source: Kocher, P. C. (1996). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems . In Advances in Cryptology—CRYPTO ’96 (pp. 104–113). Springer, Berlin, Heidelberg.