/constant-time-testing

name: constant-time-testing
type: domain
description: "Measures timing side channels in cryptographic implementations by running them, using dudect for statistical analysis and Timecop over Valgrind for dynamic tracing. Covers the formal, symbolic, dynamic, and statistical tool categories and how to read a result. Use when testing whether a running implementation is constant-time, measuring timing variance on a compiled binary, or investigating a suspected timing attack. Not for statically inspecting compiler output — the constant-time-analysis plugin covers that."

Constant-Time Testing

Timing attacks exploit variations in execution time to extract secret information from cryptographic implementations. Unlike cryptanalysis that targets theoretical weaknesses, timing attacks leverage implementation flaws - and they can affect any cryptographic code.

Background

Timing attacks were introduced by [Kocher](https://paulkocher.com/doc/TimingAttacks.pdf) in 1996. Since then, researchers have demonstrated practical attacks on RSA ([Schindler](https://link.springer.com/content/pdf/10.1007/3-540-44499-8_8.pdf)), OpenSSL ([Brumley and Boneh](https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf)), AES implementations, and even post-quantum algorithms like [Kyber](https://eprint.iacr.org/2024/1049.pdf).

Key Concepts

| Concept | Description | |---------|-------------| | Constant-time | Code path and memory accesses independent of secret data | | Timing leakage | Observable execution time differences correlated with secrets | | Side channel | Information extracted from implementation rather than algorithm | | Microarchitecture | CPU-level timing differences (cache, division, shifts) |

Why This Matters

Timing vulnerabilities can:

• **Expose private keys** - Extract secret exponents in RSA/ECDH
• **Enable remote attacks** - Network-observable timing differences
• **Bypass cryptographic security** - Undermine theoretical guarantees
• **Persist silently** - Often undetected without specialized analysis

Two prerequisites enable exploitation: 1. **Access to oracle** - Sufficient queries to the vulnerable implementation 2. **Timing dependency** - Correlation between execution time and secret data

Common Constant-Time Violation Patterns

Four patterns account for most timing vulnerabilities:

// 1. Conditional jumps - most severe timing differences
if(secret == 1) { ... }
while(secret > 0) { ... }

// 2. Array access - cache-timing attacks
lookup_table[secret];

// 3. Integer division (processor dependent)
data = secret / m;

// 4. Shift operation (processor dependent)
data = a << secret;

**Conditional jumps** cause different code paths, leading to vast timing differences.

**Array access** dependent on secrets enables cache-timing attacks, as shown in [AES cache-timing research](https://cr.yp.to/antiforgery/cachetiming-20050414.pdf).

**Integer division and shift operations** leak secrets on certain CPU architectures and compiler configurations.

When patterns cannot be avoided, employ [masking techniques](https://link.springer.com/chapter/10.1007/978-3-642-38348-9_9) to remove correlation between timing and secrets.

Example: Modular Exponentiation Timing Attacks

Modular exponentiation (used in RSA and Diffie-Hellman) is susceptible to timing attacks. RSA decryption computes:

$$ct^{d} \mod{N}$$

where $d$ is the secret exponent. The *exponentiation by squaring* optimization reduces multiplications to $\log{d}$:

$$ \begin{align*} & \textbf{Input: } \text{base }y,\text{exponent } d=\{d_n,\cdots,d_0\}_2,\text{modulus } N \\ & r = 1 \\ & \textbf{for } i=|n| \text{ downto } 0: \\ & \quad\textbf{if } d_i == 1: \\ & \quad\quad r = r * y \mod{N} \\ & \quad y = y * y \mod{N} \\ & \textbf{return }r \end{align*} $$

The code branches on exponent bit $d_i$, violating constant-time principles. When $d_i = 1$, an additional multiplication occurs, increasing execution time and leaking bit information.

Montgomery multiplication (commonly used for modular arithmetic) also leaks timing: when intermediate values exceed modulus $N$, an additional reduction step is required. An attacker constructs inputs $y$ and $y'$ such that:

$$ \begin{align*} y^2 < y^3 < N \\ y'^2 < N \leq y'^3 \end{align*} $$

For $y$, both multiplications take time $t_1+t_1$. For $y'$, the second multiplication requires reduction, taking time $t_1+t_2$. This timing difference reveals whether $d_i$ is 0 or 1.

When to Use

**Apply constant-time analysis when:**

• Auditing cryptographic implementations (primitives, protocols)
• Code handles secret keys, passwords, or sensitive cryptographic material
• Implementing crypto algorithms from scratch
• Reviewing PRs that touch crypto code
• Investigating potential timing vulnerabilities

**Consider alternatives when:**

• Code does not process secret data
• Public algorithms with no secret inputs
• Non-cryptographic timing requirements (performance optimization)

Quick Reference

| Scenario | Recommended Approach | Skill | |----------|---------------------|-------| | Prove absence of leaks | Formal verification | SideTrail, ct-verif, FaCT | | Detect statistical timing differences | Statistical testing | **dudect** | | Track secret data flow at runtime | Dynamic analysis | **timecop** | | Find cache-timing vulnerabilities | Symbolic execution | Binsec, pitchfork |

Constant-Time Tooling Categories

The cryptographic community has developed four categories of timing analysis tools:

| Category | Approach | Pros | Cons | |----------|----------|------|------| | **Formal** | Mathematical proof on model | Guarantees absence of leaks | Complexity, modeling assumptions | | **Symbolic** | Symbolic execution paths | Concrete counterexamples | Time-intensive path exploration | | **Dynamic** | Runtime tracing with marked secrets | Granular, flexible | Limited coverage to executed paths | | **Statistical** | Measure real execution timing | Practical, simple setup |