Side-Channel Attacks on Cryptographic Implementations: Detection and Prevention

The Hidden Threat

Cryptographic algorithms are mathematically secure, but their implementations can leak secrets through unintended channels. Side-channel attacks exploit these leaks—timing variations, cache access patterns, power consumption—to extract keys from otherwise secure systems.

This article examines the major classes of side-channel attacks and presents practical defenses used in HPCrypt.

Timing Attacks

The Problem

Consider this vulnerable comparison function:

// 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 measure response times:

• Correct first byte: continues to second comparison
• Wrong first byte: returns immediately

By trying all 256 values for each position and timing responses, the attacker recovers the secret tag byte by byte.

The Defense: Constant-Time Comparison

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

This examines every byte regardless of whether a mismatch was found.

Cache Timing Attacks

The Attack

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 victim to perform encryption
3. Probe which cache lines were loaded
4. Deduce the secret byte from the access pattern

The Defense: Bitsliced Implementation

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

Modern processors provide AES-NI (x86) or Cryptography Extensions (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

The Problem

// 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 instruction cache reveal which bits of the exponent are set.

The Defense: 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 directly read the private exponent.

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 traces by hypothesized key bits
3. Compute difference of means between partitions
4. Correct hypothesis shows statistically significant difference

Software Defenses

While hardware countermeasures (noise generators, power smoothing) are most effective, 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

Statistical Testing

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
}

Tooling

HPCrypt's CI pipeline includes:

• dudect: Statistical timing analysis
• ctgrind: Valgrind-based taint tracking
• timecop: Instruction-level timing verification

HPCrypt's Constant-Time Guarantees

All HPCrypt operations are constant-time with respect to:

Best Practices Summary

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 CT support

4. Always compare in constant time: Use subtle crate or equivalent

5. Test with statistical tools: Timing leaks are subtle; testing catches them

6. Prefer hardware crypto: AES-NI and similar are inherently constant-time

7. Audit generated assembly: Compilers can introduce non-constant-time code

Conclusion

Side-channel attacks transform theoretical security into practical vulnerability. Every cryptographic implementation must defend against them, not as an afterthought but as a fundamental design requirement.

HPCrypt is built from the ground up with side-channel resistance. Every function, every operation, every conditional is analyzed for timing leaks. This is the standard modern cryptographic libraries must meet.