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

UNIT 3: Hardware Security

I. Finite Field Arithmetic & Algebraic Foundations

Construction of Finite Fields (Galois Fields)

• Prime fields GF(p): Constructed using integers modulo a prime p. Arithmetic is performed mod p.

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

  • Addition/Subtraction: (a ± b) mod p

  • Multiplication: (a * b) mod p

  • Inverse: a⁻¹ such that (a * a⁻¹) mod p = 1 (computed via Extended Euclidean Algorithm).

• Extension fields GF(2^m): Constructed using irreducible polynomials of degree m over GF(2).

  • Elements: All polynomials of degree < m with coefficients in {0,1}. There are 2^m elements.

  • Arithmetic: Polynomial addition (XOR) and multiplication (followed by reduction modulo the irreducible polynomial f(x)).

• Exam Focus: Explicit construction of GF(4) using f(x) = x² + x + 1 over F₂

  1. Irreducible Polynomial: f(x) = x² + x + 1 is irreducible over GF(2) (no roots in {0,1}).

  2. Elements: All polynomials of degree < 2: {0, 1, x, x+1}. Represent as {0, 1, α, α+1} where α is a root of f(x), so α² + α + 1 = 0 → α² = α + 1 (in GF(4)).

  3. Addition Table (XOR):

     | + | 0 | 1 | α | α+1 | |---|---|---|---|-----| | 0 | 0 | 1 | α | α+1 | | 1 | 1 | 0 | α+1| α | | α | α | α+1| 0 | 1 | | α+1|α+1| α | 1 | 0 |

  4. Multiplication Table (using α² = α+1):

     | * | 0 | 1 | α | α+1 | |---|---|---|---|-----| | 0 | 0 | 0 | 0 | 0 | | 1 | 0 | 1 | α | α+1 | | α | 0 | α | α+1| 1 | | α+1|0 | α+1| 1 | α |

     Inverse: 1⁻¹=1, α⁻¹ = α+1 (since α*(α+1)=α²+α=(α+1)+α=1), (α+1)⁻¹ = α.

Finite Field Arithmetic Circuits

• Adder: In GF(2^m), addition is simply bitwise XOR of the m-bit polynomials.

• Multiplier:

  • Combinational: Direct implementation of polynomial multiplication followed by reduction modulo f(x).

  • Sequential: Uses shift-and-add algorithm, similar to standard binary multiplication but with polynomial arithmetic and reduction steps.

  • Domain-Specific Implementation: Optimizations depend on the field basis (polynomial, normal, dual) and irreducible polynomial structure (e.g., trinomials, pentanomials allow efficient reduction).

• Inverse: Computationally intensive. Often uses exponentiation (a⁻¹ = a^(2^m - 2)) via repeated squaring and multiplication, or lookup tables for small m.

Polynomial Identity Testing for Arithmetic Circuits

• Problem: Given an arithmetic circuit C with inputs a₁...aₙ and constants from field F, does it compute the identically zero polynomial?

• Deterministic Approach: Symbolic expansion (exponential cost).

• Randomized Approach (Schwartz-Zippel Lemma):

  If a non-zero n-variate polynomial of degree d is evaluated at a random point r from a set S, the probability of getting zero is ≤ d/|S|.

  • Algorithm:

    1. Pick random values r₁, r₂, ..., rₙ from a large enough subset S ⊆ F.

    2. Evaluate circuit C on (r₁, ..., rₙ).

    3. If output ≠ 0, polynomial is not identically zero.

    4. If output = 0, polynomial is zero with high probability (error ≤ d/|S|).

  • Exam Focus: For circuit C with inputs a₁...aₙ and constants from F, use randomization. Choose random r_i ∈ F. Compute C(r₁,...,rₙ). If non-zero → not identically zero. If zero → likely zero with bounded error.

II. Reconfigurable Hardware Security (FPGA)

FPGA Architecture & Basic Security Implications

• Basic Structure:

  • Configurable Logic Blocks (CLBs): Primary logic resources (LUTs, flip-flops).

  • Interconnects: Programmable routing switches and wires.

  • Configuration Memory: SRAM-based (volatile) or Flash-based (non-volatile) cells storing the bitstream that defines the circuit.

• Security Implications: The programmable nature and external configuration make FPGAs susceptible to:

  • Bitstream theft/cloning: Copying the configuration data.

  • Reverse engineering: Extracting the design from the bitstream or hardware.

  • Trojan insertion: Malicious modification of the bitstream or configuration logic.

  • Side-channel leakage: Power/EM analysis during reconfiguration or operation.

Accuracy and Precision Issues in FPGA Implementations

• Sources of Error:

  • Quantization & Finite Precision: Fixed-point arithmetic vs. floating-point; rounding errors.

  • Routing Delays: Unpredictable interconnect delays affect timing, especially in high-frequency or parallel designs.

  • Process Variation: Manufacturing variations cause Vt mismatch, affecting transistor switching speeds and leakage.

  • Clock Skew & Jitter: Distribution network imperfections.

• Impact on Security: Errors in cryptographic computations (e.g., modular exponentiation, finite field ops) can lead to:

  • Incorrect results, causing protocol failures.

  • Side-channel leakage: Data-dependent timing/power variations due to glitches or unbalanced routing.

  • Fault vulnerability: Designs operating at marginal timing are more susceptible to clock/voltage glitch attacks.

• Precision Enhancement Techniques:

  • Fixed-point design: Careful selection of word-length and scaling factors.

  • Pipelining: Breaks combinational paths to meet timing, reduces glitches.

  • Floorplanning & Constraints: Manually place critical modules, set timing constraints to control routing.

  • Using dedicated hardware blocks: DSP slices, block RAM for predictable performance.

  • Dynamic Reconfiguration: Partially reconfigure to adapt to conditions.

FPGA-Specific Security Threats

• Bitstream Theft & Cloning:

  • Attack: Read back the configuration memory (if supported) or intercept the bitstream during download.

  • Impact: Intellectual Property (IP) theft, device cloning for overproduction.

• Reverse Engineering:

  • Attack: Decapsulation, microscopy, and probing of the configuration memory cells or routing fabric to reconstruct the netlist/design.

  • Impact: Complete design recovery, identification of security vulnerabilities.

III. Physical Unclonable Functions (PUFs)

PUF Fundamentals & Classification

• Definition: A physical entity that embodies a challenge-response behavior that is:

  • Unique: Responses differ significantly across devices for the same challenge.

  • Unclonable: Physically impossible to duplicate the exact challenge-response mapping.

  • Reliable: Responses are repeatable for the same challenge under nominal conditions.

• Classification:

  • Strong PUF: Large challenge space (e.g., 2^80). Used for authentication. Example: Arbiter PUF, SRAM PUF.

  • Weak PUF: Small, fixed challenge set (e.g., 128-bit key). Used for key storage. Example: SRAM PUF (used as a key), Ring Oscillator PUF (for device ID).

• Common Types:

  • SRAM PUF: Leverages random startup state of SRAM cells due to transistor mismatch.

  • Ring Oscillator (RO) PUF: Measures frequency differences between identically designed RO pairs; process variations cause unique patterns.

  • Arbiter PUF: A chain of multiplexers; the race condition outcome between two paths depends on gate delays.

  • Optical PUF: Uses scattering of laser light through a transparent material with random inhomogeneities.

High-Priority: PUF Attacks

• Model Building Attacks (Machine Learning Attacks):

  • Goal: Learn a compact predictive model f: Challenge → Response from a limited set of challenge-response pairs (CRPs).

  • Why possible? Many PUFs (especially lightweight ones like Arbiter PUF) have a linear or near-linear response model in the transformed challenge space.

  • Examples:

    • Arbiter PUF: Response is essentially the sign of a weighted sum of challenge bits (sign(∑ w_i * c_i)). Attacks use:

      • Logistic Regression: Simple linear classifier.

      • CMA-ES (Covariance Matrix Adaptation Evolution Strategy): Powerful evolutionary algorithm to find weights w_i.

    • XOR Arbiter PUF: Multiple Arbiter PUFs whose outputs are XORed. Increases resistance but not immunity; attacks use divide-and-conquer or enhanced ML.

  • Exam Focus: Discuss model building attacks on PUFs with examples. For an n-stage Arbiter PUF, the response is r = sign(∑_{i=1}^n δ_i * c_i) where δ_i are delay differences. An attacker collects k CRPs {(C_j, r_j)} and solves for δ_i using linear regression (minimizing ∑ (r_j - sign(∑ δ_i c_{j,i}))²). Success requires k >> n but is feasible for large n if model is linear.

• Other Attack Vectors:

  • Invasive Attacks: Physical probing (e.g., with focused ion beam) to measure internal delays or modify circuit. Can clone the PUF structure.

  • Side-Channel Attacks: Monitor power/EM during PUF operation to correlate with internal states or responses.

  • Replay & Man-in-the-Middle: In authentication protocols, intercept and replay valid CRPs if the protocol lacks freshness.

  • Environmental Exploitation: Exploit reliability issues (temperature, voltage) to cause errors and infer information.

High-Priority: Enhancing PUF Response Quality

Design techniques to improve the four main metrics:

1. Uniqueness: Inter-chip Hamming Distance (HD) should be ~50%. Achieved by ensuring sufficient process variation sensitivity. Use larger silicon area per PUF cell.

2. Reliability: Intra-chip HD should be near 0% under nominal conditions. Reduced by:

   • Circuit Design: Use symmetric layout (e.g., differential pairs for RO), increase RO stages, use voting circuits (e.g., 3-out-of-5 for each bit).

   • Temperature/Voltage Compensation: On-chip sensors to adjust sampling.

3. Uniformity: Response bits should be 50% ones/zeros. Achieved by balanced design (e.g., using XOR of multiple ROs).

4. Bit Aliasing Reduction: Minimize number of "stuck" bits (always 0/1). Use post-processing (e.g., XOR with a secret mask) or selective cell usage.

• Error Correction & Helper Data:

  • Problem: PUF responses are noisy; need a stable "key" for cryptographic use.

  • Solution: Use Error-Correcting Codes (ECC) like BCH or repetition codes. The Helper Data Algorithm (HDA):

    1. Enroll: Measure noisy response R_noisy. Apply ECC encoder to get codeword C and syndrome S. Store S (helper data) publicly. The secret key is C.

    2. Reconstruct: Measure new response R'_noisy. Use S and R'_noisy with ECC decoder to correct errors and recover C.

  • Key: Helper data must not leak information about C (information-theoretic security).

PUF Security Parameters & Evaluation Metrics

• Inter-chip Hamming Distance (HD): Average Hamming distance between responses from different devices for the same challenge. Measures uniqueness. Target: ~50% for m-bit response → m/2 ± √(m/4).

• Intra-chip Hamming Distance: Hamming distance between responses from the same device under different conditions (temp, voltage). Measures reliability. Target: ~0%.

• Uniformity: Percentage of '1' bits in the response. Target: 50%.

• Randomness: Passes statistical tests (NIST SP 800-22) for randomness.

• Uniqueness Formula: For N devices, UID = (2/(N(N-1))) * ∑_{i<j} HD(R_i, R_j). Should be 0.5.

Hardware Piracy Prevention using PUFs

• IP Protection (Binding):

  • Procedure: The IP core (e.g., AES engine) is encrypted with a key K. K is derived from the PUF response of the target device.

  • Prevents: Cloning: A cloned device has a different PUF → cannot derive correct K → cannot decrypt/run IP.

• Overbuilding Prevention (Authentication):

  • Procedure: Manufacturer enrolls each device's PUF (stores a set of valid CRPs or a derived secret in a secure database). During field operation, the device is challenged by the verifier (e.g., server). Only genuine devices with the correct PUF can respond correctly.

  • Prevents: Unauthorized manufacturing of extra copies beyond the licensed quantity.

• Other Procedures:

  • PUF-Based Key Generation: Replace non-volatile memory for key storage. Key is regenerated on-demand from PUF.

  • Secure Boot: Bootloader uses PUF-derived key to decrypt/authenticate the OS image.

IV. Side-Channel Attacks (SCA)

Core Concept: What is a Side-Channel Attack?

• Exploits physical leakage from a device performing a secret operation (e.g., encryption) to extract the secret key.

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

• Fundamental Principle: The physical implementation's behavior depends on the secret data and the algorithm's intermediate values.

High-Priority: Types of Side-Channel Attacks

• Simple Power Analysis (SPA):

  • Method: Visual inspection of a single power trace.

  • What to look for: Distinct patterns for different operations (e.g., square vs. multiply in RSA, S-box lookups in AES). Can directly read key bits if operations are data-dependent and not masked.

  • Example: In a naive RSA square-and-multiply, the presence/absence of a multiplication indicates a key bit.

• Differential Power Analysis (DPA):

  • Method: Statistical analysis over many traces (100s-1000s). Uses a hypothesis about an intermediate value V (e.g., output of an S-box).

  • Steps:

    1. Collect N power traces P_i(t) for N random inputs X_i (with known plaintext/ciphertext).

    2. For each possible key guess k, compute the hypothetical intermediate value V_i = f(X_i, k) (e.g., S-box output).

    3. Model leakage: Assume power consumption correlates with the Hamming weight (HW) or Hamming distance (HD) of V_i. Compute HW(V_i).

    4. Correlate: For each time sample t, compute correlation coefficient ρ(t, k) between P_i(t) and HW(V_i) across all i.

    5. Result: The correct k will show a peak in ρ(t, k) at the time when V is computed.

  • Exam Focus: Improved side-channel attack by using DES algorithm

    • Target: First round key K₁ (6 bits for one S-box).

    • Hypothesis: After initial permutation, 48-bit right half R₀ is XORed with round key K₁. The 6-bit input to S-box S_j is S_in = (R₀[bits] ⊕ K₁[bits]).

    • Attack:

      1. Collect traces for many plaintexts P.

      2. For each of the 8 S-boxes, focus on one. For a 6-bit key guess k for that S-box:

         • Compute S_in = (R₀(P) ⊕ k) for each trace.

         • Look up S-box output S_out = S_j(S_in).

         • Use HW(S_out) as power model.

      3. Compute correlation of this model with power traces at the expected S-box computation time.

      4. The correct 6-bit k for that S-box yields the highest correlation peak.

      5. Repeat for all 8 S-boxes to recover full 48-bit K₁. Repeat for subsequent rounds or use known key schedule to get full 56-bit key.

• Timing Attacks:

  • Measure execution time variations that depend on secret data.

  • Example: RSA with Chinese Remainder Theorem (CRT) has different computation paths for p and q. Timing can reveal which path was taken, leading to p or q.

• Cache Attacks:

  • Cache-Timing: Observe cache hit/miss patterns via timing. Example: In AES, T-table lookups cause cache misses for uncached addresses, revealing accessed table indices → key bits.

  • Prime+Probe:

    1. Prime: Attacker fills the cache with its own data.

    2. Wait: Victim executes cryptographic operation, evicting some of attacker's cache lines.

    3. Probe: Attacker re-accesses its data and measures access times. Slow access → cache line was evicted → victim accessed that memory region → reveals secret-dependent memory access pattern.

  • Flush+Reload:

    1. Flush: Attacker flushes a shared memory page (e.g., a library function) from cache.

    2. Wait: Victim executes, potentially loading parts of that page back.

    3. Reload: Attacker accesses the page and times each access. Fast access → victim loaded that line → reveals execution path.

  • Exam Focus: Cache Attacks. They exploit shared hardware resources (last-level cache) in multi-tenant systems (cloud, multi-core). They are non-invasive and work across VMs/containers.

• Electromagnetic (EM) Attacks: Similar to power analysis but probe EM radiation. Can have higher spatial resolution.

• Acoustic Cryptanalysis: Very high-frequency sound emitted by capacitors/ceramic packages varies with power consumption → can be used like a cheap power probe.

High-Priority: Countermeasures against SCA

• Hiding: Make the physical leakage independent of the secret data.

  • Random Delays: Insert random, secret-independent delays to desynchronize traces.

  • Constant-Time Logic: Design circuits where power consumption is data-independent (e.g., use dual-rail precharge logic, balanced logic styles like WDDL).

  • Shielding: Use on-chip metal layers or dedicated shields to attenuate EM/power signals.

• Masking: Secret sharing of intermediate values. A d-th order masking scheme protects against attacks using up to d leakage points.

  • Boolean Masking: Split a secret x into d+1 shares x₁ ⊕ x₂ ⊕ ... ⊕ x_{d+1} = x. Operations are performed on shares.

  • Arithmetic Masking: Split x as x = x₁ + x₂ + ... + x_{d+1} (mod p). Used in finite field arithmetic.

  • Challenge: Masking increases area/cost. Requires secure composition (each operation must be masked to the same order).

• Redundancy & Detection:

  • Duplication: Compute operation twice and compare. If mismatch → fault/attack detected → invalidate output.

  • Sensors: On-chip voltage, temperature, light sensors to detect physical tampering.

  • Active Shielding: Detect physical intrusion and zeroize secrets.

• Algorithmic:

  • Threshold Implementations: A formal masking method that guarantees security against d-th order attacks at the algorithm level, using uniform and non-complete sharing.

  • Use SCA-Resistant Algorithms: Some algorithms are inherently more resistant (e.g., masking-friendly designs like AES with specific S-box implementations).

V. Fault Attacks & Fault-Tolerant Cryptography

Core Concept: What is a Fault Attack?

• Attack: Intentionally induce a physical fault (transient or permanent) in a cryptographic device during operation to cause an erroneous output.

• Goal: The faulty output, combined with a correct output, can leak secret information.

• Common Fault Injection Methods:

  • Voltage Glitch: Over/under-voltage to cause timing violations or logic upsets.

  • Clock Glitch: Shorten clock period to skip cycles or cause setup/hold violations.

  • Laser/Flashlight: Focused light to induce charge in transistors (local bit flips).

  • Temperature Extremes: Increase leakage or slow down circuits.

  • Electromagnetic Pulse: Induce currents in wires.

Common Fault Models

• Bit Flip (Transient): A single bit in memory or register flips temporarily.

• Bit Flip (Permanent): A bit is stuck at 0 or 1 (e.g., from laser damage).

• Instruction Skip: A specific instruction is skipped (e.g., by clock glitch).

• Instruction Replace: An instruction is replaced by another (e.g., ADD → SUB).

High-Priority: Fault-Tolerant Cryptographic Architecture

• Design Goals:

  1. Detect the presence of a fault.

  2. Prevent leakage of secret information from the faulty output (e.g., by invalidating it).

  3. Optionally correct the fault to maintain availability.

• Techniques:

  • Redundant Computation:

    • Dual Modular Redundancy (DMR): Two identical units compute in parallel. Outputs are compared. Mismatch → fault detected → output discarded.

    • Triple Modular Redundancy (TMR): Three units, majority voting. Can correct single fault.

  • Error Detection Codes (EDC): Attach parity, checksum, or CRC to intermediate values (registers, bus data). Check before use.

  • Verification & Comparison Units: Dedicated hardware to compare results from redundant units or check EDCs.

• Exam Focus: Explain architecture of fault tolerance of cryptography with a neat sketch.

  • Sketch Description: A typical DMR-based architecture for a cryptographic core (e.g., AES):

    1. Input: Secret key K and plaintext P fed into two identical, independent cryptographic engines (Engine A and Engine B). They must be physically separated to avoid common-mode faults.

    2. Computation: Both engines perform the same sequence of operations (rounds).

    3. Comparison: After each round (or at the end), a comparator circuit checks if the intermediate state (or final ciphertext) from Engine A equals that from Engine B.

    4. Output: If match, the output (e.g., ciphertext) is valid and sent out. If mismatch, a fault flag is raised, the output is invalidated (e.g., all zeros or error signal), and the operation may be retried or the device may enter a secure state.

    5. Optional: Use TMR with a voter for higher reliability. EDCs can be added on internal buses.

Countermeasures Against Fault Attacks

• Detection:

  • Checksums/Parity: On critical registers (e.g., round keys, state).

  • Verification of Intermediate States: Re-compute or check consistency (e.g., in RSA, verify m = (m^d mod n)^e mod n after decryption).

  • Sensor-Based: Detect abnormal voltage/temperature that could cause faults.

• Correction: Use Error-Correcting Codes (ECC) like Hamming codes on stored data. Less common for active computation due to overhead.

• Algorithmic:

  • Invalidation: Upon any fault detection (DMR mismatch, EDC error), immediately discard the output and do not release it. This prevents the attacker from obtaining a valid faulty ciphertext for differential fault analysis (DFA).

  • Fault-Aware Algorithms: Design algorithms where a single fault corrupts the entire output (e.g., by adding final checksum that depends on all operations).

  • Randomized Execution: Randomize operation order or use random masks to make fault propagation unpredictable.

VI. Hardware Security Verification & Testing

Methods for Verifying Security Properties

• Formal Verification:

  • Use mathematical methods (theorem proving, model checking) to prove that a hardware design satisfies a security property (e.g., non-interference: secret inputs do not affect public outputs).

  • Challenges: Modeling physical leakage (power, timing) is difficult. Often focuses on logical correctness and information flow at RTL/gate level.

• Simulation-Based Verification with Models:

  • Simulate the design with power/EM models (e.g., using tools like Synopsys PrimePower, Cadence Joules).

  • Perform statistical analysis on simulated power traces to check for data-dependent leakage (pre-silicon SCA evaluation).

  • Use fault injection simulation to test fault tolerance.

Testing for Physical Vulnerabilities

• Side-Channel Evaluation Setups:

  • Equipment: High-bandwidth oscilloscope (for power), near-field probe (for EM), controlled environment (temperature, voltage).

  • Procedure: Capture thousands of traces for known inputs (plaintexts) under fixed conditions. Perform DPA/CPA analysis using tools like ChipWhisperer.

• Fault Injection Setups:

  • Equipment: Laser fault injection (LFI) system, voltage/clock glitch generators, temperature chambers.

  • Procedure: Apply controlled faults while the device performs crypto operation. Monitor output for errors or use differential fault analysis (DFA) tools to extract keys from faulty ciphertexts.

\boxed{\text{End of Unit 3 Notes}}