constant-time-testing

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 in 1996. Since then, researchers have demonstrated practical attacks on RSA (Schindler), OpenSSL (Brumley and Boneh), AES implementations, and even post-quantum algorithms like Kyber.

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.

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

When patterns cannot be avoided, employ masking techniques 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	No root cause, noise sensitivity

1. Formal Tools

Formal verification mathematically proves timing properties on an abstraction (model) of code. Tools create a model from source/binary and verify it satisfies specified properties (e.g., variables annotated as secret).

Popular tools:

• SideTrail
• ct-verif
• FaCT

Strengths: Proof of absence, language-agnostic (LLVM bytecode) Weaknesses: Requires expertise, modeling assumptions may miss real-world issues

2. Symbolic Tools

Symbolic execution analyzes how paths and memory accesses depend on symbolic variables (secrets). Provides concrete counterexamples. Focus on cache-timing attacks.

Popular tools:

• Binsec
• pitchfork

Strengths: Concrete counterexamples aid debugging Weaknesses: Path explosion leads to long execution times

3. Dynamic Tools

Dynamic analysis marks sensitive memory regions and traces execution to detect timing-dependent operations.

Popular tools:

• Memsan: Tutorial
• Timecop (see below)

Strengths: Granular control, targeted analysis Weaknesses: Coverage limited to executed paths

Detailed Guidance: See the timecop skill for setup and usage.

4. Statistical Tools

Execute code with various inputs, measure elapsed time, and detect inconsistencies. Tests actual implementation including compiler optimizations and architecture.

Popular tools:

• dudect (see below)
• tlsfuzzer

Strengths: Simple setup, practical real-world results Weaknesses: No root cause info, noise obscures weak signals

Detailed Guidance: See the dudect skill for setup and usage.

Testing Workflow

Phase 1: Static Analysis        Phase 2: Statistical Testing
┌─────────────────┐            ┌─────────────────┐
│ Identify secret │      →     │ Detect timing   │
│ data flow       │            │ differences     │
│ Tool: ct-verif  │            │ Tool: dudect    │
└─────────────────┘            └─────────────────┘
         ↓                              ↓
Phase 4: Root Cause             Phase 3: Dynamic Tracing
┌─────────────────┐            ┌─────────────────┐
│ Pinpoint leak   │      ←     │ Track secret    │
│ location        │            │ propagation     │
│ Tool: Timecop   │            │ Tool: Timecop   │
└─────────────────┘            └─────────────────┘

Recommended approach:

1. Start with dudect - Quick statistical check for timing differences
2. If leaks found - Use Timecop to pinpoint root cause
3. For high-assurance - Apply formal verification (ct-verif, SideTrail)
4. Continuous monitoring - Integrate dudect into CI pipeline

Tools and Approaches

Dudect - Statistical Analysis

Dudect measures execution time for two input classes (fixed vs random) and uses Welch's t-test to detect statistically significant differences.

Detailed Guidance: See the dudect skill for complete setup, usage patterns, and CI integration.

Quick Start for Constant-Time Analysis

#define DUDECT_IMPLEMENTATION
#include "dudect.h"

uint8_t do_one_computation(uint8_t *data) {
    // Code to measure goes here
}

void prepare_inputs(dudect_config_t *c, uint8_t *input_data, uint8_t *classes) {
    for (size_t i = 0; i < c->number_measurements; i++) {
        classes[i] = randombit();
        uint8_t *input = input_data + (size_t)i * c->chunk_size;
        if (classes[i] == 0) {
            // Fixed input class
        } else {
            // Random input class
        }
    }
}

Key advantages:

• Simple C header-only integration
• Statistical rigor via Welch's t-test
• Works with compiled binaries (real-world conditions)

Key limitations:

• No root cause information when leak detected
• Sensitive to measurement noise
• Cannot guarantee absence of leaks (statistical confidence only)

Timecop - Dynamic Tracing

Timecop wraps Valgrind to detect runtime operations dependent on secret memory regions.

Detailed Guidance: See the timecop skill for installation, examples, and debugging.

Quick Start for Constant-Time Analysis

#include

---

*Content truncated.*