Defending cryptographic code against side-channel attacks

Cryptographic algorithms are mathematically secure, but their implementations can leak secrets through timing variations, cache access patterns and power consumption. Side-channel attacks exploit these leaks to extract keys from otherwise secure systems. The defenses below are the ones we use in OpenCrypt.

Timing attacks

Early-exit comparison

This comparison function is vulnerable:

// VULNERABLE: Early exit leaks information
fn compare_tags(a: &[u8], b: &[u8]) -> bool {
    if a.len() != b.len() {
        return false;
    }
    for i in 0..a.len() {
        if a[i] != b[i] {
            return false;  // Early exit!
        }
    }
    true
}

An attacker can time the responses: a correct first byte continues to the second comparison, a wrong one returns immediately. By trying all 256 values for each position, the attacker recovers the secret tag byte by byte.

Constant-time comparison

The fix examines every byte, even after it finds a mismatch:

// SECURE: Always examines all bytes
fn constant_time_compare(a: &[u8], b: &[u8]) -> bool {
    if a.len() != b.len() {
        return false;
    }

    let mut result = 0u8;
    for i in 0..a.len() {
        result |= a[i] ^ b[i];  // Accumulate differences
    }

    result == 0  // Single comparison at end
}

Cache timing attacks

Table lookups

Table-driven AES implementations are vulnerable:

// VULNERABLE: Memory access depends on secret
const SBOX: [u8; 256] = [/* ... */];

fn sub_bytes(state: &mut [u8; 16]) {
    for byte in state.iter_mut() {
        *byte = SBOX[*byte as usize];  // Secret-dependent index!
    }
}

The secret byte determines which cache line is accessed. An attacker sharing the CPU can:

1. Flush all cache lines containing SBOX
2. Wait for the victim to perform an encryption
3. Probe which cache lines were loaded
4. Deduce the secret byte from the access pattern

Bitsliced S-box

Eliminate secret-dependent memory access entirely:

// SECURE: No memory lookups
fn sbox_bitsliced(x: u8) -> u8 {
    // Decompose into bits
    let mut bits = [0u8; 8];
    for i in 0..8 {
        bits[i] = (x >> i) & 1;
    }

    // Compute S-box using boolean operations only
    // (algebraic decomposition of the AES S-box)
    let t1 = bits[0] ^ bits[3];
    let t2 = bits[0] ^ bits[5];
    // ... many more boolean operations
    let s7 = /* final computation */;

    // Recompose into byte
    (s7 << 7) | (s6 << 6) | /* ... */
}

Boolean operations execute in constant time regardless of operand values.

Hardware AES

The best defense is hardware AES (AES-NI on x86, Cryptography Extensions on ARM):

#[target_feature(enable = "aes")]
unsafe fn aes_round(state: uint8x16_t, round_key: uint8x16_t) -> uint8x16_t {
    // Single instruction: SubBytes, ShiftRows, MixColumns, AddRoundKey
    vaeseq_u8(state, round_key)
}

Hardware implementations are inherently constant-time, and orders of magnitude faster.

Conditional branching attacks

Square-and-multiply

// VULNERABLE: Branch depends on secret
fn modular_exp(base: &BigInt, exp: &BigInt, modulus: &BigInt) -> BigInt {
    let mut result = BigInt::one();

    for i in (0..exp.bit_length()).rev() {
        result = (&result * &result) % modulus;  // Always square

        if exp.bit(i) {                          // Secret-dependent branch!
            result = (&result * base) % modulus;
        }
    }
    result
}

Branch prediction and the instruction cache reveal which bits of the exponent are set.

Constant-time selection

// SECURE: Always perform both operations
fn modular_exp_ct(base: &BigInt, exp: &BigInt, modulus: &BigInt) -> BigInt {
    let mut result = BigInt::one();

    for i in (0..exp.bit_length()).rev() {
        result = (&result * &result) % modulus;

        // Always compute the multiplication
        let multiplied = (&result * base) % modulus;

        // Select result based on bit, without branching
        result = constant_time_select(
            exp.bit(i),
            &multiplied,  // if bit is 1
            &result       // if bit is 0
        );
    }
    result
}

fn constant_time_select<T: Copy>(condition: bool, a: &T, b: &T) -> T {
    let mask = -(condition as isize) as usize;  // All 1s or all 0s
    // Bitwise selection without branching
    // Implementation depends on type T
}

Power analysis attacks

Simple power analysis (SPA)

Power consumption varies with instruction type and operand values:

Square operation:   ████████░░░░
Multiply operation: ████████████░░░░

An attacker with physical access can trace power consumption during RSA and read the private exponent directly.

Differential power analysis (DPA)

Statistical analysis of many power traces can extract keys even with noise:

1. Collect thousands of power traces during encryption
2. Partition the traces by hypothesized key bits
3. Compute the difference of means between partitions
4. The correct hypothesis shows a statistically significant difference

Software defenses

Hardware countermeasures (noise generators, power smoothing) are the most effective, but software can help:

// Randomized projective coordinates (for ECC)
fn randomize_point(p: &AffinePoint, rng: &mut Rng) -> ProjectivePoint {
    let lambda = rng.random_nonzero_field_element();
    ProjectivePoint {
        x: p.x * lambda,
        y: p.y * lambda,
        z: lambda,
    }
}

// Exponent blinding (for RSA)
fn blind_exponent(d: &BigInt, phi: &BigInt, rng: &mut Rng) -> BigInt {
    let r = rng.random_in_range(1, 2.pow(64));
    d + r * phi  // d' ≡ d (mod φ(n))
}

Testing for timing leaks

We use dudect-style statistical testing:

fn test_constant_time<F: Fn(&[u8]) -> Vec<u8>>(func: F) -> bool {
    let mut measurements_class_0 = Vec::new();
    let mut measurements_class_1 = Vec::new();

    for _ in 0..10_000 {
        // Class 0: random input
        let input_0 = random_bytes(32);
        let time_0 = measure(|| func(&input_0));
        measurements_class_0.push(time_0);

        // Class 1: fixed input
        let input_1 = [0u8; 32];
        let time_1 = measure(|| func(&input_1));
        measurements_class_1.push(time_1);
    }

    // Welch's t-test
    let t = welch_t_test(&measurements_class_0, &measurements_class_1);
    t.abs() < 4.5  // No statistically significant difference
}

OpenCrypt's CI pipeline includes dudect (statistical timing analysis), ctgrind (Valgrind-based taint tracking) and timecop (instruction-level timing verification).

Constant-time guarantees in OpenCrypt

All OpenCrypt operations are constant-time with respect to their secret data:

Constant-time checklist

1. Never branch on secrets; use constant-time selection primitives.
2. Never index arrays with secrets; use bitsliced or hardware implementations.
3. Never use variable-time arithmetic; avoid BigInt libraries without constant-time support.
4. Always compare in constant time, with the subtle crate or an equivalent.
5. Test with statistical tools. Timing leaks are subtle, and testing catches them.
6. Prefer hardware crypto: AES-NI and similar are inherently constant-time.
7. Audit the generated assembly. Compilers can introduce non-constant-time code.

We built OpenCrypt with side channels in mind from the start, and every function, operation and conditional in it is analyzed for timing leaks.