365 Architect

05 — Side-Channel Risks

The Unique Problem: Floating-Point Arithmetic

FN-DSA is the only NIST PQC standard that requires floating-point arithmetic during signing. This creates unique security risks:

Algorithm Arithmetic type Side-channel risk
ML-DSA Integer (ℤ) Moderate (timing on rejection)
SLH-DSA Integer hash operations Low (hash functions are naturally constant-time)
FN-DSA Floating-point (ℝ) High (FP timing varies with input)
ECDSA Integer (elliptic curves) High (scalar multiplication timing)

Why Floating-Point Is Dangerous

Timing Variations

Floating-point operations have input-dependent timing:

  • Multiplication of very small numbers: fast (subnormal handling)
  • Multiplication of very large numbers: fast (infinity handling)
  • Multiplication of "normal" numbers: varies with exponent alignment
  • Division: significantly slower than multiplication
  • Square root: even slower

An attacker measuring signing time can infer:

  • Which coefficients are large vs. small
  • The approximate magnitude of secret values
  • Over many signatures, enough information to recover the trapdoor

Cache Behaviour

Floating-point unit (FPU) state affects CPU caches:

  • FPU register file is separate from integer registers
  • Saving/restoring FPU state affects cache lines
  • Different code paths (NaN handling, denormals) access different memory

Power Analysis

FPUs consume different power depending on operation:

  • Subnormal arithmetic: high power (special handling)
  • Normal arithmetic: moderate power
  • Idle: low power

On devices without power analysis protection, this leaks information.

The Specific Risks in FN-DSA

1. Gaussian Sampling Timing

The core of FN-DSA signing is discrete Gaussian sampling. The reference implementation uses:

  • Floating-point exponentials: exp(-x² / (2σ²))
  • Floating-point comparisons: accept/reject based on random value

Timing leak: The number of rejections depends on the secret trapdoor. An attacker counting rejections via timing learns about the secret basis.

2. FFT/NTT Precision

The NTT uses exact integer arithmetic, but the trapdoor sampling uses floating-point:

  • Convert integer coefficients to floating-point
  • Perform Gaussian sampling in FP
  • Convert back to integers

Precision leak: Rounding errors in the conversion depend on the secret values. Different secrets produce different rounding patterns.

3. Basis Reduction

During key generation, the trapdoor basis is "reduced" to be as short as possible:

  • Uses floating-point Gram-Schmidt orthogonalisation
  • Iterative refinement with different precision levels
  • Convergence depends on initial basis quality

Leakage: The number of iterations and precision changes reveals information about the secret f and g.

Mitigations

1. Constant-Time Floating-Point (Best Effort)

The NIST reference implementation includes constant-time FP strategies:

  • Fixed-precision arithmetic: Use 64-bit doubles exclusively (no extended precision)
  • Branchless code: Replace if/else with bitwise masks
  • Uniform instruction sequences: Same operations regardless of input magnitude
  • Avoid subnormals: Scale inputs to prevent subnormal numbers
// Branchless comparison (constant-time)
int ct_compare(double a, double b) {
    int64_t ia = *(int64_t*)&a;
    int64_t ib = *(int64_t*)&b;
    return (ia > ib) - (ia < ib);  // -1, 0, or 1
}

2. Integer-Only Alternative (New)

Recent research proposes integer-only Gaussian sampling:

  • Approximate exp(-x²) using integer lookup tables
  • Use integer arithmetic for all comparisons
  • Slightly less efficient but completely constant-time

Trade-off: ~20% slower signing, but eliminates FP side channels entirely.

3. Masking (Higher-Order Protection)

Split the secret into multiple shares:

  • s = s₁ + s₂ + ... + sₖ (mod q)
  • Compute on each share independently
  • Combine results at the end

Benefit: Attacker must recover ALL shares simultaneously. Cost: k× computation time, k× memory.

4. Hardware Countermeasures

Countermeasure What it does Effectiveness
Jitter Random delays between operations Hides timing, but doesn't prevent statistical analysis
Power balancing Duplicate operations to even out power Moderate; doesn't address data-dependent power
Shielding Physical Faraday cage around device Prevents electromagnetic analysis
Noise generator Inject random noise into power Makes power analysis harder but not impossible
Threat model Recommended approach
Standard server (datacenter) Reference implementation + basic constant-time
High-security server (HSM) Integer-only sampling + masking
Embedded device (IoT) Integer-only sampling (if performance acceptable)
Smart card Masking + hardware countermeasures
Side-channel lab testing Integer-only + third-party audit

Testing for Side Channels

Tools

Tool What it tests Method
dudect Timing differences Welch's t-test on execution times
deadpool Power analysis Differential power analysis (DPA)
CHIP.WHISPERER Power + electromagnetic Correlation power analysis (CPA)
VALGRIND/ctgrind Branch detection Detects branches on secret data

DUDECT Example

# Collect timing samples for two different secret inputs
dudect -i secret_A.bin -o secret_B.bin ./fndsa_sign

# Output: t-statistic (should be < 10 for "probably constant-time")

A t-statistic > 10 suggests statistically significant timing differences.

Comparison with ML-DSA Side Channels

Attack vector ML-DSA FN-DSA
Timing (rejection sampling) Leaks number of retries Leaks FP operation counts
Cache (secret-dependent access) Low (polynomials always accessed) Medium (FP state affects cache)
Power (data-dependent) Low (integer ops are uniform) High (FP ops vary with magnitude)
Fault injection Medium (fault on retry count) High (fault on FP rounding mode)

Resources

  • NIST FIPS 206, Section 8: Side-Channel Considerations
  • Prest et al., "Rounding Gaussian sampling for lattice trapdoors" (2020), AFRICACRYPT
  • dudect: github.com/oreparaz/dudect
  • Howe et al., "Tunable Gaussian sampling for lattice-based signatures" (2023), ASIACRYPT
★★★★★
Share on LinkedIn