Hardware Security (CY-801) - Unit 5 Short Notes

UNIT 5: Hardware Security – Short Notes

I. Finite Fields and Algebraic Foundations

Galois Field (GF) Construction

• Definition: A finite field (Galois Field) with $$\displaystyle q = p^n $$ elements, denoted GF($$\displaystyle p^n $$), where $p$ is prime and $n \geq 1$.

• Construction of GF($$\displaystyle 2^n $$):

  1. Start with base field $$\displaystyle \mathbb{F}_2 = \{0, 1\} $$.

  2. Choose an irreducible polynomial $f(x)$ of degree $n$ over $$\displaystyle \mathbb{F}_2[x] $$.

  3. Field elements are polynomials of degree $$\displaystyle < n $$ with coefficients in $$\displaystyle \mathbb{F}_2 $$.

  4. Arithmetic operations are performed modulo $f(x)$.

• Example: GF(4)

  • Irreducible polynomial: $$\displaystyle f(x) = x^2 + x + 1 $$ over $$\displaystyle \mathbb{F}_2 $$.

  • Elements: $\{0, 1, x, x+1\}$.

  • Addition: coefficient-wise XOR (e.g., $$\displaystyle x + (x+1) = 1 $$).

  • Multiplication: polynomial multiplication then reduce modulo $f(x)$ (e.g., $$\displaystyle x \cdot x = x^2 \equiv x+1 \pmod{f(x)} $$).

• Properties:

  • Additive inverse: $$\displaystyle a + a = 0 $$ (characteristic 2).

  • Multiplicative inverse: For non-zero $a$, find $b$ such that $a \cdot b \equiv 1 \pmod{f(x)}$.

  • Primitive element: A generator $\alpha$ such that $$\displaystyle \{\alpha^0, \alpha^1, ..., \alpha^{q-2}\} $$ yields all non-zero field elements.

Polynomial Arithmetic in Finite Fields

• Representation: Field element $$\displaystyle a = a_{n-1}x^{n-1} + \dots + a_1 x + a_0 $$, where $$\displaystyle a_i \in \{0,1\} $$.

• Operations:

  • Addition: XOR of corresponding coefficients (bitwise XOR).

  • Multiplication:

    1. Multiply polynomials (like binary multiplication).

    2. Reduce result modulo irreducible polynomial $f(x)$ using polynomial division.

  • Reduction: If $m(x)$ is product, compute $m(x) \bmod f(x)$ by repeatedly substituting $$\displaystyle x^n \equiv $$ lower-degree terms from $$\displaystyle f(x)=0 $$.

• Complexity: Multiplication is $$\displaystyle O(n^2) $$ for schoolbook; optimized to $O(n \log n)$ with Karatsuba/FFT-like methods.

Algebraic Verification Techniques

• Goal: Check if an arithmetic circuit $C$ over field $F$ computes the zero polynomial identically.

• Polynomial Identity Testing (PIT):

  • Schwartz-Zippel Lemma: For a non-zero polynomial $$\displaystyle p(x_1,...,x_m) $$ of total degree $d$, random evaluation yields $$\displaystyle p=0 $$ with probability $\leq d/|S|$ over domain $S$.

  • Algorithm:

    1. Pick random values $$\displaystyle r_i \in R $$ (large enough subset of $F$).

    2. Evaluate circuit $C$ on $\mathbf{r}$.

    3. If $C(\mathbf{r}) \neq 0$, then $C \not\equiv 0$.

    4. If $$\displaystyle C(\mathbf{r}) = 0 $$, repeat $k$ times to reduce error.

  • Application: Verify correctness of finite-field arithmetic circuits (e.g., multipliers, AES S-box) without symbolic expansion.

Domain-Specific Hardware for Finite Fields

• Finite Field Multipliers:

  • Montgomery Multiplication: Optimized for repeated multiplications (e.g., ECC). Avoids explicit reduction step.

  • Normal Basis Multiplication: Efficient for GF($$\displaystyle 2^n $$) using Frobenius map; good for hardware with low logic depth.

  • Basis Choice:

    | Basis | Pros | Cons | |-------|------|------| | Polynomial | Simple addition (XOR) | Complex reduction | | Normal | Cheap squaring ($$\displaystyle x \to x^2 $$) | Multiplication more complex |

• Optimization for Cryptography:

  • AES (GF($$\displaystyle 2^8 $$): Uses polynomial basis with irreducible $$\displaystyle x^8 + x^4 + x^3 + x + 1 $$. Implement via lookup tables or combinational logic.

  • ECC (GF($p$) or GF($$\displaystyle 2^n $$): Requires fast modular reduction; Montgomery for prime fields, normal basis for binary fields.

  • Hardware focus: Pipeline, parallelism, resource sharing (e.g., shared multipliers for multiple operations).

[!TIP] Exam Focus

• Be ready to construct GF(4) step-by-step.

• Know Schwartz-Zippel for polynomial identity testing.

• Contrast Montgomery vs. Normal basis multipliers.

II. FPGA Implementation Challenges and Techniques

Accuracy Issues in FPGA

• Timing Inaccuracies:

  • Place-and-route delays not perfectly predictable.

  • Clock skew, routing delays cause setup/hold violations.

  • Impact: Timing failures in security-critical circuits (e.g., fault attacks via clock glitching).

• Resource Estimation Errors:

  • Synthesis/place-and-route tools may over/underestimate LUTs, FFs, DSP blocks.

  • Impact: Design may not fit or meet timing, leading to insecure fallback (e.g., reduced security parameters).

• Power Estimation Errors:

  • Dynamic power depends on real switching activity; tools use statistical models.

  • Impact: Side-channel leakage may be worse than predicted.

Precision Enhancement

• Fixed-point vs. Floating-point:

  • Fixed-point: Deterministic, lower resource use, but requires careful scaling to avoid overflow/underflow.

  • Floating-point: Larger dynamic range, but higher area/power, rounding errors.

  • Trade-off: Cryptographic algorithms often use fixed-point for predictability.

• Bit-width Optimization:

  • Quantization: Reducing bit-widths to save resources.

  • Effect on Security: Too few bits may cause overflow attacks or weaken masking (e.g., in lattice-based crypto).

  • Method: Simulate worst-case signal ranges; add guard bits.

Domain-Specific Design on FPGA

• Custom Hardware for Finite Field Arithmetic:

  • Implement GF($$\displaystyle 2^n $$) multipliers with optimized reduction (e.g., using precomputed reduction matrices).

  • Use distributed arithmetic for S-boxes (AES) to reduce ROM usage.

• Resource & Performance Optimization:

  • Pipelining: Increase throughput for high-speed crypto (e.g., AES-GCM).

  • Resource Sharing: Time-multiplex expensive operations (e.g., modular exponentiation in RSA).

  • Security-Performance Trade-off: More parallelism → better performance but larger area → more side-channel leakage.

[!TIP] Exam Focus

• Link timing inaccuracies to fault attacks.

• Explain why fixed-point is preferred in crypto hardware.

• Give example: AES S-box implementation on FPGA using LUTs vs. combinational logic.

III. Physically Unclonable Functions (PUFs)

PUF Fundamentals

• Definition: A Physical Unclonable Function is a hardware structure that maps a challenge $C$ to a response $R$ such that:

  • The mapping is easy to evaluate but hard to predict.

  • It derives from inherent manufacturing variations (e.g., transistor threshold mismatch).

• Core Principle: Physical entropy source – each chip’s microscopic variations produce unique, noisy responses.

• Common Types:

  | PUF Type | Principle | Pros | Cons | |----------|-----------|------|------| | SRAM PUF | Power-up state of SRAM cells | No extra hardware, high entropy | Requires stable power-up, temperature sensitive | | Arbiter PUF | Race between two paths through switch network | Simple, small | Vulnerable to ML attacks | | Ring Oscillator PUF | Frequency differences due to process variation | Good randomness, stable | Large area, sensitive to voltage/temp | | Optical PUF | Speckle pattern from laser on material | Extremely high entropy, unclonable | Expensive, not CMOS-compatible |

Security Parameters of PUFs

• Uniqueness: Responses from different chips should be uncorrelated.

  • Metric: Inter-chip Hamming Distance (HD). For $N$-bit response:

$$\text{HD}_{\text{inter}} = \frac{1}{\binom{M}{2}} \sum_{i<j} \frac{\text{HD}(R_i, R_j)}{N}$$

  Ideal: 50% (random).

• Randomness: Responses should be uniformly random.

• Reliability: Same challenge yields same response across conditions (temp, voltage, aging).

  • Metric: Intra-chip Hamming Distance (HD). For same chip over multiple reads:

$$\text{HD}_{\text{intra}} = \frac{1}{M} \sum_{k=1}^{M} \frac{\text{HD}(R, R_k)}{N}$$

  Ideal: 0% (but noise → small %).

• Other Metrics: Uniformity (balance of 0s/1s), min-entropy.

PUF Attacks

• Model-building Attacks:

  • Goal: Learn a predictive model of PUF behavior from challenge-response pairs (CRPs).

  • Example: Arbiter PUF vulnerable to Logistic Regression or SVM due to linear structure.

  • Counter: Use non-linear PUFs (e.g., XOR of multiple arbiter PUFs) or lightweight PUFs with limited CRPs.

• Invasive Attacks:

  • Reverse engineering: Extract circuit layout to model delays.

  • Probing: Directly measure internal nodes (difficult due to small feature sizes).

• Non-invasive Attacks:

  • Side-channel on PUF operation: Monitor power/EM during response generation to learn internal state.

  • Fault injection: Glitch power/clock to force errors and deduce structure.

  • Example: SRAM PUF – temperature variations increase noise; attacker may exploit thermal imaging.

Design for Response Quality

• Circuit-level Techniques:

  • Balanced design: Ensure symmetric path delays (e.g., in arbiter PUF).

  • Noise reduction: Use larger ring oscillator stages, filter jitter.

  • Temperature/voltage compensation: Calibration circuits.

• Error Correction:

  • BCH codes: Correct up to $t$ bit errors in noisy PUF response. Requires helper data (public).

  • Fuzzy extractors: Combine error correction (e.g., code-offset) with privacy amplification to generate uniform key from noisy measurement.

• Post-processing:

  • Privacy amplification: Hash noisy response to shorten, uniform key.

  • Key generation: Use PUF as root of trust for key derivation.

Hardware Piracy Prevention

• PUF-based Device Authentication:

  • Device enrolls by measuring CRPs; later proves possession by responding to challenge.

• IP Protection & Overbuilding Prevention:

  • IC metering: Each chip has unique PUF key; manufacturer cannot clone without knowing responses.

  • Secure key storage: No non-volatile memory; keys reconstructed on-demand from PUF.

  • Licensing: Challenge-response used to activate features.

• PUF-based Metering:

  • Track production count via unique IDs derived from PUFs.

[!TIP] Exam Focus

• Calculate inter/intra-chip HD for given response sets.

• Contrast model-building (ML) vs. invasive attacks.

• Explain BCH error correction for SRAM PUF.

• Describe PUF-based metering workflow.

IV. Side-Channel Attacks

Introduction and Taxonomy

• Definition: Attacks that exploit physical leakage from a device during computation (power, time, EM, acoustic, cache).

• Categories:

  • Passive vs. Active: Passive (eavesdrop leakage) vs. active (inject faults, manipulate environment).

  • Invasive vs. Non-invasive: Invasive (depackaging, probing) vs. non-invasive (external measurement).

  • Single vs. Multi-trace: One execution vs. many traces for statistical analysis.

Specific Attack Types

• Cache Attacks (shared hardware):

  • Prime+Probe: Attacker fills cache set (Prime), waits, then probes to see if victim evicted lines.

  • Flush+Reload: Attacker flushes shared cache line, then measures reload time (fast if victim accessed).

  • Target: Cryptographic keys in software (e.g., AES T-table indices).

• Power Analysis:

  • SPA (Simple Power Analysis): Visual inspection of power trace (e.g., RSA exponentiation bits).

  • DPA (Differential Power Analysis): Statistical test (e.g., difference of means) across many traces to correlate with intermediate value.

  • CPA (Correlation Power Analysis): Use hypothesized power model (e.g., Hamming weight of intermediate byte) and compute Pearson correlation.

• Timing Attacks: Measure execution time variations (e.g., RSA CRT, AES table lookup).

• Electromagnetic (EM) Analysis: Similar to power but with spatial resolution; can probe specific chip regions.

Case Study: DES and Side-Channel

• DES Structure Leakage:

  • SPA: Initial/final permutation visible; rounds may show pattern.

  • DPA on S-boxes: Each round’s S-box output depends on 6-bit input and 4-bit output. Attacker guesses 6-bit subkey, computes S-box output, correlates with power trace.

  • Improved Attacks:

    • Use chosen plaintexts to control inputs to S-boxes.

    • Multi-trace DPA across many plaintexts to average noise.

    • Target first/last round where input/output known (plaintext/ciphertext).

• Result: Extract 48-bit key with ~1000 traces.

Countermeasures

• Masking:

  • Principle: Secret sharing – split sensitive variable $x$ into $d+1$ shares $$\displaystyle x_1, ..., x_{d+1} $$ such that $$\displaystyle x = x_1 \oplus ... \oplus x_{d+1} $$.

  • Implementation:

    • Gate-level masking: AND gate with masked inputs requires extra gates (e.g., ISW).

    • Instruction-level: Software masks (e.g., masked AES lookup tables).

  • Security: $d$-th order masking resists up to $d$-th order attacks.

• Hiding:

  • Random Delays: Insert dummy operations to desynchronize traces.

  • Noise Injection: Add random power consumption (e.g., dummy circuits).

  • Constant-time Logic: Ensure power independent of data (e.g., dual-rail precharge, sense amplifiers).

• Layout Techniques:

  • Shielding: Add metal layers to reduce EM/power leakage.

  • Balanced Routing: Match capacitive load for data lines.

• Algorithmic Countermeasures:

  • Shuffling: Randomize operation order (e.g., AES rounds).

  • Dummy Operations: Insert fake operations to flatten profile.

[!TIP] Exam Focus

• Describe Prime+Probe vs. Flush+Reload.

• CPA formula: $$\displaystyle \rho(HW(s), T) = \frac{\text{cov}(HW, T)}{\sigma_{HW} \sigma_T} $$.

• Explain DES DPA step-by-step (guess subkey → compute S-box output → correlate).

• Contrast masking (divide secret) vs. hiding (mask leakage).

V. Fault Attacks and Fault Tolerance

Fault Attack Models

• Fault Injection Methods:

  • Voltage Glitching: Drop supply voltage to cause timing violations.

  • Clock Glitching: Shorten clock period to skip operations.

  • Laser/Flash: Localized ionizing radiation to flip bits.

  • Temperature: Extreme temps cause malfunctions.

• Goals:

  • Bypass authentication (e.g., skip password check).

  • Extract keys (e.g., Differential Fault Analysis on RSA/ECC).

  • Indroduce errors for cryptanalysis (e.g., DES fault attacks reveal S-box differences).

• Examples:

  • RSA-CRT Fault: Glitch during CRT recombination → reveal $p$ or $q$.

  • ECC Fault: Fault on scalar multiplication point → solve discrete log.

  • DES Fault: Single fault in round → compare faulty vs. correct ciphertext to deduce key bits.

Fault-Tolerant Cryptographic Architectures

• Redundancy:

  • Duplication: Compute twice, compare results.

  • Triple Modular Redundancy (TMR): Three copies, majority vote. Common in space/avionics.

• Detection Circuits:

  • Parity checks on registers/buses.

  • Checksums (CRC) on computed values.

  • Temporal redundancy: Recompute and compare at different times.

• Error Correction in PUFs:

  • BCH codes correct bit flips in PUF response.

  • Fuzzy extractors combine error correction with privacy amplification.

Design Techniques for Resilience

• Secure Fault Detection:

  • Control-flow checking: Duplicate program counter, compare.

  • Data integrity: MACs on critical variables.

• Recovery:

  • Rollback: Revert to known good state on fault detection.

  • Graceful degradation: Switch to less secure but functional mode.

• Combining with Side-Channel:

  • Use masking + duplication (masked duplication) to resist both.

  • Cost: Area/power overhead 2×–5×.

[!TIP] Exam Focus

• Sketch TMR architecture (three modules + voter).

• Differential Fault Analysis on RSA-CRT: Show equation $$\displaystyle S^2 \equiv m \pmod{N} $$ vs. faulty $S'$ → $$\displaystyle \gcd(S^2 - S'^2, N) $$ reveals factor.

• Explain BCH correction for PUF: encode response, decode with error correction.

VI. Advanced Topics and Integration

Formal Verification in Hardware Security

• Goal: Mathematically prove security properties (e.g., absence of leakage, correctness).

• Algebraic Methods:

  • Polynomial checking: Represent circuit as polynomial; verify identities (e.g., masking correctness).

  • Example: Prove that a masked AND gate computes $$\displaystyle z = (x_1 \oplus r) \cdot (y_1 \oplus r) \oplus \text{ correction} $$ and that $z \oplus$ shares reconstruct $x \cdot y$.

• Tools: SAT/SMT solvers for equivalence checking; formal models for side-channel resistance (e.g., masking verification).

Cross-Cutting Countermeasures

• Integration of Techniques:

  • PUF + Masking: PUF provides key; masked implementation uses it.

  • Fault tolerance + Side-channel: TMR with masked modules.

• Trade-offs:

  | Countermeasure | Area | Power | Performance | Security Level | |----------------|------|-------|-------------|----------------| | Masking (1st order) | +50% | +30% | -10% | Resists 1st-order DPA | | TMR | +200% | +150% | -30% | Resists faults, some SCA | | PUF (RO array) | +10% | +5% | - | Provides key, no runtime cost |

• Design Flow:

  1. Identify threat model (SPA? DPA? Faults?).

  2. Select countermeasures (masking + duplication).

  3. Optimize for target platform (FPGA vs. ASIC).

  4. Verify formally and via evaluation (e.g., TVLA for SCA).

[!TIP] Exam Focus

• Formal verification example: Show how to check that a masked addition is correct ($$\displaystyle x_1 \oplus x_2 = x $$).

• Trade-off analysis: Why TMR is costly but effective for space applications.

• Integration example: PUF-generated key fed into masked AES core.

Final Note: Always connect theory to real implementations (AES, RSA, ECC) and past paper questions. Practice derivations (GF construction, HD calculation) and attack steps (DES DPA, RSA-CRT DFA).