PRNG Security Checklist for Masked Cryptographic Schemes - Commerce Security Authority

If your team is deploying masking countermeasures to protect cryptographic operations in hardware security modules or payment processors, you may assume your pseudorandom number generator (PRNG) produces uniform, independent randomness. However, this assumption might not hold when using a linear feedback shift register (LFSR) or similar PRNG in constrained hardware. This checklist helps you evaluate whether your PRNG choice undermines the masking scheme it's supposed to protect.

Purpose of This Checklist

This guide assists security architects and cryptographic engineers in systematically evaluating PRNG implementations used in masked cryptographic schemes. Use it when:

Designing or auditing hardware security modules with masking countermeasures
Evaluating FPGA-based cryptographic implementations for payment processing systems
Assessing if your existing masking scheme maintains its security properties with your chosen PRNG
Responding to penetration test findings related to side-channel vulnerabilities

The checklist addresses a gap in formal security proofs: most masking security analyses assume perfect randomness without validating the actual PRNG implementation. Deploying an LFSR or other lightweight PRNG in resource-constrained hardware introduces dependencies and non-uniformity that can compromise your masking scheme's security.

Prerequisites

Before using this checklist, ensure you have:

Technical documentation:

Complete specification of your masking scheme, including the number of shares (d+1 for d-probing security)
PRNG implementation details: polynomial, seed length, output transformation
Target cryptographic primitive specifications (S-box dimensions, operation sequence)

Access and tools:

Source code or hardware description language files for both PRNG and masking implementation
Verification tools capable of Walsh-Hadamard transform analysis or equivalent linear cryptanalysis techniques
Test environment: either an FPGA evaluation board or cycle-accurate simulator

Team knowledge:

Understanding of the d-probing security model and its implications for your implementation
Familiarity with side-channel attack vectors relevant to your deployment environment
Ability to interpret correlation measurements from practical side-channel evaluations

The Security Evaluation Checklist

Phase 1: PRNG Characterization

☐ Document PRNG type and parameters

Record generator type (LFSR, LFSR variant, other)
Note polynomial degree and feedback taps
Identify output bit width and extraction method
Document seed initialization procedure

☐ Analyze output properties

Calculate period length
Verify claimed uniformity across output range
Test for short-cycle states or degenerate seeds
Measure autocorrelation in generated sequences

☐ Check independence assumptions

Determine if consecutive outputs share internal state bits
Identify any output transformation that introduces correlation
Document refresh rate: how often does the PRNG state update relative to masking operations?

Phase 2: Joint PRNG-Masking Analysis

☐ Map randomness consumption

Count random bits required per masked operation
Trace which PRNG outputs feed which shares
Identify any PRNG output reuse across multiple masking operations
Document timing: does PRNG output generation overlap with sensitive computation?

☐ Apply formal verification

Define your security target (d-probing model with specific d value)
Select verification approach: Walsh-Hadamard transform for linear analysis, or alternative method for non-linear schemes
Run joint analysis of PRNG and masking scheme together (not separately)
Document which probe combinations the analysis covers

☐ Interpret verification results

Identify any probe combinations that reveal information
Determine if violations stem from PRNG properties or masking scheme design
Calculate security margin: how close are you to the theoretical d-probing threshold?
Flag any unexpected correlations between shares

Phase 3: Practical Validation

☐ Prepare test environment

Deploy implementation to target hardware (FPGA or ASIC testbed)
Set up side-channel measurement apparatus (oscilloscope, current probe)
Configure known-plaintext or chosen-plaintext test scenarios
Establish baseline: measure unmasked implementation for comparison

☐ Execute side-channel evaluation

Collect power or electromagnetic traces during cryptographic operations
Apply correlation analysis targeting intermediate values
Test with multiple PRNG seeds to verify consistency
Measure leakage for different S-box inputs (4-bit and 8-bit test cases are standard)

☐ Correlate formal and empirical findings

Do practical measurements confirm vulnerabilities identified in formal analysis?
Are there practical leakages not predicted by the formal model?
Quantify attack complexity: how many traces would an attacker need?

Phase 4: Risk Assessment and Remediation

☐ Evaluate operational risk

Consider your threat model: physical access requirements, attacker sophistication
Assess whether identified weaknesses are exploitable in your deployment scenario
Review compliance requirements (FIPS 140-3 Level 3+ for hardware modules handling payment keys)
Document risk acceptance or mitigation plan

☐ Implement corrections if needed

Option 1: Replace PRNG with higher-quality generator (trade-off: resource cost)
Option 2: Modify masking scheme to compensate for PRNG limitations
Option 3: Add post-processing to PRNG output (verify this doesn't introduce new issues)
Option 4: Accept risk with compensating controls (environmental shielding, tamper detection)

☐ Document findings

Record PRNG-masking combination and security level achieved
Note any deviations from theoretical security guarantees
Update threat model and security claims
Schedule re-evaluation trigger: implementation changes, new attack research, compliance updates

Customizing This Checklist

For different cryptographic primitives: The checklist references S-box implementations because that's where masking is commonly applied. If you're protecting a different operation (field multiplication, key scheduling), adjust Phase 2 to map randomness consumption for your specific primitive. The analysis methodology remains the same.

For resource-constrained environments: If you're working with severe area or power constraints, you may need to accept lower security margins. Document your trade-off explicitly: "Achieved d=2 probing security with LFSR-based PRNG instead of theoretical d=3, accepted based on physical access controls."

For different security models: This checklist assumes the d-probing model. If you're working under the robust probing model or a noisy leakage model, adjust the formal verification step in Phase 2 to use appropriate analysis techniques. The Walsh-Hadamard transform extends to robust probing, but you'll need to account for physical defaults in your verification.

For certification requirements: If you're pursuing FIPS 140-3 certification, add explicit checks for approved random number generators (SP 800-90A/B/C) and document why your PRNG choice meets or exceeds those requirements. Certification bodies increasingly scrutinize the randomness source for masking implementations.

Validation Steps

After completing the checklist:

Verify completeness: Every checkbox should be either checked or explicitly marked as not applicable with justification.
Cross-check formal and empirical results: If your formal analysis claims d-probing security but practical measurements show exploitable leakage, your formal model is missing something. Don't ship until you resolve the discrepancy.
Conduct peer review: Have a second cryptographic engineer review your PRNG characterization and verification results. PRNG analysis is subtle; confirmation bias is real.
Test edge cases: Run the practical validation with degenerate inputs (all-zero plaintexts, maximum-value plaintexts) and weak PRNG seeds. Attackers will.
Schedule periodic reassessment: New side-channel attack techniques emerge regularly. Plan to re-run Phase 3 annually or when you update either the PRNG or masking implementation.

The goal isn't perfect randomness, that's unattainable in hardware. The goal is knowing exactly what security properties your PRNG-masking combination actually provides, so you can make informed risk decisions and set realistic security claims.