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

UNIT 2: Hardware Security

1. Finite Field Arithmetic & Algebraic Foundations

Finite Fields (Galois Fields)

A finite field (Galois Field, GF) is a set with a finite number of elements where addition, subtraction, multiplication, and division (except by zero) are defined and satisfy field axioms.

• Prime Fields (F_p):

  • Constructed using integers modulo a prime number p.

  • Elements: {0, 1, 2, ..., p-1}.

  • Arithmetic: Standard integer operations followed by modulo p.

  • Example: F_5 = {0,1,2,3,4}. 3 + 4 = 7 mod 5 = 2.

• Binary Extension Fields (F_{2^m}):

  • Constructed as polynomials of degree < m with coefficients in F_2.

  • Polynomial Basis Representation: An element a ∈ F_{2^m} is represented as a polynomial: a(x) = a_{m-1}x^{m-1} + ... + a_1 x + a_0, where a_i ∈ {0,1}.

  • Irreducible Polynomial f(x): A polynomial of degree m that cannot be factored into polynomials of lower degree over F_2. It acts as the modulus.

  • Primitive Polynomial: An irreducible polynomial whose root α is a generator (primitive element) of the multiplicative group F_{2^m}^*. All non-zero field elements are powers of α.

Example: Constructing F_4

Let m=2, so field has 2^2 = 4 elements. Use irreducible polynomial f(x) = x^2 + x + 1 over F_2.

1. Elements (Polynomial Basis): All degree <2 polynomials: {0, 1, x, x+1}.

2. Addition/Subtraction: Coefficient-wise XOR.

*   `x + (x+1) = 1` (since `x+x=0` in `F_2`).

3. Multiplication: Multiply polynomials, then reduce modulo f(x).

*   `x * x = x^2`. Since `x^2 ≡ x + 1 (mod x^2+x+1)`, result is `x+1`.

4. Multiplicative Inverses: Use Extended Euclidean Algorithm on polynomials.

*   Inverse of `x`: `x * (x+1) = x^2+x ≡ 1 (mod f(x))`, so `x^{-1} = x+1`.

Finite Field Arithmetic

• Addition/Subtraction: For F_{2^m}, it is bitwise XOR of the polynomial coefficients. a + b = a ⊕ b.

• Multiplication:

  1. Perform polynomial multiplication of the two operands.

  2. Apply modular reduction using the chosen irreducible polynomial f(x).

  • Key for Hardware: This step is the bottleneck. Optimized circuits (e.g., using Montgomery Multiplication or Normal Basis) are used to speed it up.

• Multiplicative Inverse: Computed using the Extended Euclidean Algorithm (EEA) for polynomials. For a(x), find b(x) such that a(x)*b(x) ≡ 1 mod f(x).

Domain-Specific Implementation

• Goal: Speed up GF(2^m) multiplication/inversion for cryptographic primitives (AES, ECC).

• Optimized Multipliers:

  • Montgomery Multiplication: Avoids costly division in reduction. Uses a transformation.

  • Normal Basis Representation: Squaring is a simple cyclic shift, very efficient. Multiplication is more complex.

  • Composite Field Arithmetic: Break F_{2^m} into F_{2^k} subfields for smaller, faster multipliers.

• Hardware Architectures: Use lookup tables (LUTs), shift-and-add sequences, or fully parallel combinatorial multipliers. Trade-off between area (gate count) and time (latency).

Formal Verification & Polynomial Identity Testing

• Problem: Given an arithmetic circuit C with inputs a_1..a_n and constants from field F, does it compute the zero polynomial? (i.e., C(a_1..a_n) = 0 for all inputs).

• Schwartz-Zippel Lemma (Randomized Algorithm):

  If C is not identically zero, then for a random point r chosen from a large enough subset S ⊆ F, Pr[C(r)=0] ≤ deg(C)/|S|.

  • Procedure: Pick random r_i ∈ S for each input. Evaluate C(r_1..r_n). If result ≠ 0, circuit is not zero polynomial. If result = 0, circuit is likely zero polynomial (with high probability).

  • Application: Verifying secure multi-party computation, checking equivalence of hardware/software implementations, proving circuit correctness.

[!TIP] Exam Focus: Be ready to construct F_4 step-by-step and state Schwartz-Zippel with its probability bound.

2. Hardware Platforms & Implementation Challenges

Field-Programmable Gate Arrays (FPGA)

• Basic Architecture:

  • Configurable Logic Blocks (CLBs): The basic logic unit (Look-Up Tables - LUTs, flip-flops).

  • Interconnects: Programmable routing switches and wires.

  • Memory Blocks: Embedded RAM/ROM.

  • I/O Blocks: Interface with external pins.

• Accuracy Issues:

  • Timing Errors: Signal propagation delays vary due to process variation (manufacturing differences), voltage, and temperature (PVT). Can cause setup/hold violations.

  • Signal Integrity: Crosstalk, ringing, and ground bounce distort signals.

• Precision Enhancement Techniques:

  • Dynamic/Partial Reconfiguration: Change parts of the FPGA configuration on-the-fly to adapt to conditions or implement redundancy.

  • Error Correction: Use ECC on configuration memory (SRAM-based FPGAs are susceptible to radiation-induced upsets).

  • Design Margining: Design with conservative timing constraints (slack) to account for worst-case PVT.

• Security Implications: FPGA's reconfigurability is a double-edged sword: enables rapid prototyping but also allows hardware trojans or bitstream theft/cloning.

[!TIP] Common Pitfall: Do not confuse FPGA accuracy issues (timing, signal integrity) with security vulnerabilities (bitstream encryption, cloning). They are related but distinct.

3. Physical Unclonable Functions (PUFs) - Core Topic

PUF Fundamentals

• Definition: A Physical Unclonable Function is a physical entity that, given a challenge C, produces a response R that is:

  1. Unique: Different devices produce different responses to the same challenge.

  2. Unpredictable: Response cannot be predicted even with knowledge of other CRPs.

  3. Reliable: Same challenge on same device produces same response (within tolerance) across environmental variations.

• Challenge-Response Pair (CRP): The fundamental input-output behavior. A PUF is characterized by a large set of CRPs.

• Taxonomy:

  • Silicon PUFs: Exploit manufacturing variations in ICs.

    • SRAM PUF: Power-up state of SRAM cells (due to transistor mismatch).

    • Ring Oscillator (RO) PUF: Frequency difference between identically designed ROs (due to delay variation).

    • Arbiter PUF: A chain of delay elements; a race between two signals decided by an arbiter. Susceptible to ML attacks.

  • Optical/Non-Silicon PUFs: Use scattering patterns of opaque materials (e.g., Optical PUF).

PUF Design for Quality

• Enhancing Reliability:

  • Error Correction Codes (ECC): Encode the noisy PUF response to correct errors. Requires Helper Data (public, non-secret).

  • Helper Data Algorithms (HDAs): Like Fuzzy Extractor protocols. Use privacy amplification to generate a stable, uniform key from noisy PUF output.

  • Temporal Majority Voting: Take multiple measurements and vote.

• Enhancing Uniqueness & Randomness:

  • Use balanced circuit designs (e.g., differential pairs in RO PUF).

  • Careful layout techniques to maximize process variation impact and minimize spatial correlation.

• Trade-offs: Higher reliability often requires more helper data (storage overhead) or slower operation. High uniqueness might increase area.

Security Parameters (Measured Quantitatively)

PUF Attacks & Vulnerabilities

• Model Building Attacks (Machine Learning):

  • Goal: Learn a predictive model of the PUF's challenge-response behavior.

  • Target: Arbiter PUF (linear model), XOR PUFs (resistant if XOR count is high).

  • Reliability Attacks: Exploit noisy responses to improve model accuracy (e.g., SVM with multiple noisy measurements).

• Exploitative Attacks:

  • Side-Channel: Monitor power/EM during PUF operation to extract internal states.

  • Invasive/Cloning: Reverse-engineer the physical structure to create a clone. Very difficult for silicon PUFs due to nanometer-scale variations.

• Environmental Attacks:

  • Voltage/Temperature Variation: Intentionally change operating conditions to increase error rate, potentially forcing error correction to reveal helper data or cause denial-of-service.

PUF Applications for Hardware Security

• Hardware Piracy Prevention:

  • IP Authentication: Manufacturer embeds a secret key derived from PUF. Device must prove it has the genuine PUF to activate.

  • IP Watermarking/Fingerprinting: Unique PUF response acts as a fingerprint for each manufactured IC.

  • IC Overbuilding Prevention: Each chip has unique, unclonable ID. Activate only sold units; detect unauthorized surplus.

• Secure Key Generation & Storage: PUF generates a stable, unique seed. Combined with ECC/HDAs, it produces a cryptographic key without needing non-volatile memory (which can be read).

• Device Authentication & Secure Boot: Device proves its identity (via PUF-derived key) to a verifier. Can also authenticate bootloader code.

[!TIP] Exam Focus: Contrast Reliability (same device, same CRP) vs Uniqueness (different devices). Know Helper Data is public but must not leak info about the PUF output.

4. Implementation Attacks & Countermeasures - Core Topic

Side-Channel Attacks (SCA)

• Definition: Extracting secret information by analyzing physical leakage from a device performing a cryptographic operation.

• Leakage Sources: Power consumption, electromagnetic (EM) radiation, timing, acoustic, cache behavior.

• Types:

  | Attack | Principle | Required Traces | Complexity | | :--- | :--- | :--- | :--- | | SPA | Visual inspection of a single trace to see operations (e.g., square vs multiply). | 1 | Low | | DPA | Statistical correlation between power trace and hypothesized intermediate value (e.g., S-Box output). | Thousands | Medium | | CPA | Uses a power model (e.g., Hamming Weight of intermediate value) for correlation. More efficient than DPA. | Hundreds | Medium-High | | Timing | Measures execution time variations (e.g., RSA square-and-multiply). | Many | Low-Medium | | Cache Attacks | Prime+Probe: Fill cache, wait, probe to see if lines were evicted. Flush+Reload: Flush shared cache line, measure reload time. | Many | High | | EM Attacks | Probe near-chip EM radiation; often has better spatial resolution than power. | Similar to power | Similar to power |

• Case Study: Improved SPA/DPA on DES

  • SPA: DES's Feistel structure and permutations cause distinct power patterns for each round. An attacker can identify round boundaries and potentially the final permutation.

  • DPA: Target the S-Box output of the last round. Hypothesis: S-Box(input ⊕ subkey). For each possible subkey byte, compute intermediate value, model its power (e.g., Hamming Weight), and correlate with traces. Correct subkey will show a spike in correlation.

Fault Attacks

• Definition: Intentionally inducing a fault (transient error) in the cryptographic computation to cause an erroneous output. Analyzing the faulty output reveals secret information.

• Fault Induction Methods: Clock/voltage glitching, laser/ion beam injection, temperature extremes.

• Types:

  • Safe-Error Attack: Induce a fault in a redundant operation. If output is correct, the fault was in a non-critical part; if incorrect, it was in a critical part. Reveals secret bits.

  • Differential Fault Analysis (DFA):

    1. Collect many correct ciphertexts (or one known plaintext-ciphertext pair).

    2. Induce faults at a specific point (e.g., during last round of AES).

    3. Collect faulty ciphertexts.

    4. Differencing: (Correct ⊕ Faulty) often cancels unknown values and reveals equations involving the secret key.

  • Examples: DFA on RSA-CRT (fault in one of the two exponentiations reveals p or q). DFA on AES (fault in last round's AddRoundKey reveals key byte).

Countermeasures Against Implementation Attacks

• Design-Level (Hardware/Logic):

  • Masking (First & Higher-Order):

    • Boolean Masking: Split secret d into d = d_1 ⊕ d_2 ⊕ ... ⊕ d_n. All intermediate computations done on shares. Requires non-linear operations (S-Boxes) to be masked securely.

    • Algebraic Masking: Work in a different algebraic domain (e.g., GF(2^8) for AES).

    • Higher-Order: Protects against attacks combining leakage from multiple shares/points. Very costly.

  • Hiding:

    • Constant Power/Time: Design so power/time is independent of data (e.g., use dual-rail logic, balanced logic trees).

    • Randomized Clock: Jitter clock frequency.

    • Noise Injection: Add random operations or dummy cycles.

  • Redundancy & Verification:

    • Duplicate & Compare: Compute twice, compare results (detects faults, some SCA if comparison is secure).

    • Error Detection Codes: Parity, CRC on internal buses.

• Algorithmic/Protocol-Level:

  • Randomization: Shuffle order of operations (e.g., AES round keys).

  • Secret Sharing: Used in masking.

• Specific to Fault Attacks:

  • Redundant Execution: Triple Modular Redundancy (TMR) with voter.

  • Fault Detection Sensors: Monitor voltage, clock, light (laser detection).

  • Checksums/Integrity Checks: Verify intermediate results (e.g., AES MixColumns is linear; check InvMixColumns result).

[!TIP] Exam Focus: Distinguish Masking (breaks correlation between leakage and secret) from Hiding (makes leakage independent of secret). Know DFA on RSA-CRT is a classic example.

5. Fault-Tolerant Cryptographic Architectures

Motivation

• Harsh Environments: Space (radiation), automotive (temperature extremes), industrial control.

• Malicious Attacks: Resistance to Fault Attacks (as above).

• Goal: Ensure correct operation or detect errors even when faults occur.

Architectural Techniques

• Duplication with Comparison:

  • Duplication with Compare (DWC): Two identical modules compute in parallel; comparator checks for mismatch. Detects single fault.

  • Triple Modular Redundancy (TMR): Three modules, majority voter. Can correct a single fault and detect double faults. High area overhead (3x).

• Error Detection Codes (EDC):

  • Apply codes like Parity, CRC, or Hamming Code to internal data paths and registers.

  • Detects single-bit (or multi-bit) errors during storage/transfer.

• Residue Number Systems (RNS):

  • Represent a number by its residues modulo several pairwise-coprime moduli.

  • Fault Detection: If a computation error occurs in one modulus channel, the overall result's residue check will fail.

• Concurrent Error Detection (CED):

  • Error detection logic runs in parallel with the main computation.

  • Example: In AES, compute InvMixColumns in parallel and check if MixColumns(InvMixColumns(State)) == State.

Sketched Architecture: Fault-Tolerant AES Core

[Plaintext] --> [Round 0 (AddRoundKey)] --> [Round 1 (SubBytes, ShiftRows, MixColumns, AddRoundKey)] --> ... --> [Final Round (SubBytes, ShiftRows, AddRoundKey)] --> [Ciphertext]

                                                                        |

                                                                        V

                                                            [Parallel Duplicate AES Core]

                                                                        |

                                                                        V

                                                            [Comparator / Voter]

                                                                        |

                                                                        V

                                                          [Error Signal / Corrected Output]

• Description: Two (or three) complete AES datapaths operate in parallel on the same input. A comparator (for DWC) or voter (for TMR) checks outputs. A mismatch triggers an error signal or selects the majority output.

• Trade-off: Area increases linearly (DWC) or triply (TMR). Performance may be slightly reduced due to voter delay. Power increases significantly.

[!TIP] Exam Focus: Be able to sketch a DWC/TMR architecture for a block cipher. Know RNS provides inherent fault detection in arithmetic. Understand CED is integrated into the datapath, not an afterthought.

UNIT 2 - High-Yield Exam Summary

1. Finite Fields: Know how to construct F_{2^m} with an irreducible polynomial. Addition is XOR. Multiplication is polynomial multiply mod f(x).

2. PUFs: Definition (physical fingerprint), Taxonomy (SRAM, RO, Arbiter), Security Parameters (Uniqueness, Reliability, Randomness), Attacks (ML on Arbiter PUF), Applications (Key generation, anti-piracy).

3. SCA: SPA vs DPA vs CPA. Cache Attacks (Prime+Probe). DES SPA/DPA case study (target S-Box).

4. Countermeasures: Masking (break correlation) vs Hiding (constant leakage). Redundancy for fault attacks.

5. Fault Tolerance: DWC (detect), TMR (correct). CED examples in AES.

6. FPGA: Accuracy Issues = PVT variations causing timing errors. Precision = reconfiguration, ECC, margining.

Remember: For 7-mark questions, provide definitions, key principles, a small example (like F_4), and a concise diagram if asked (like fault-tolerant architecture).