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

UNIT 1: Hardware Security – Short Notes

I. Mathematical Foundations for Hardware Security

Finite Fields (Galois Fields)

A finite field (or 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.

Construction of GF(pⁿ):

• Built from a prime field GF(p) (where p is prime) using an irreducible polynomial f(x) of degree n over GF(p).

• Elements are polynomials of degree < n with coefficients in GF(p), i.e., $$\displaystyle a_{n-1}x^{n-1} + \ldots + a_1 x + a_0 $$, where $$\displaystyle a_i \in \text{GF}(p) $$.

• Arithmetic is performed modulo f(x) and coefficients modulo p.

Example: Constructing GF(4) = GF(2²)

• Prime field: GF(2) = {0, 1} with modulo-2 arithmetic.

• Irreducible polynomial: $$\displaystyle f(x) = x^2 + x + 1 $$ over GF(2)[x] (no roots in GF(2)).

• Elements: {0, 1, x, x+1}. Represent as {0, 1, 2, 3} where 2 ≡ x, 3 ≡ x+1.

• Addition: Polynomial addition mod 2 (XOR). E.g., 2 + 3 = x + (x+1) = 1.

• Multiplication: Polynomial multiplication mod f(x) and mod 2. E.g., 2 × 2 = x·x = x² ≡ x+1 (since x² ≡ x+1 mod f(x)) = 3.

Key Properties:

• Closure: Operations stay within the field.

• Associativity/Commutativity: For + and ×.

• Identity: 0 for +, 1 for ×.

• Inverses: Every a ≠ 0 has additive inverse (−a) and multiplicative inverse (a⁻¹).

• Characteristic: Smallest p such that p·1 = 0. For GF(pⁿ), characteristic = p.

Applications: AES (GF(2⁸)), ECC (GF(p) or GF(2ᵐ)), error-correcting codes.

Polynomial Identity Testing in Hardware Context

Problem: Given an arithmetic circuit C over field F with inputs $$\displaystyle a_1, ..., a_n $$ and constants, does it compute the zero polynomial (i.e., identically zero for all inputs)?

Hardware Relevance:

• Circuits represent polynomials; testing equivalence of two circuits reduces to testing if their difference computes zero.

• Used in formal verification to prove circuit correctness (e.g., two designs compute same function).

Method: Schwartz-Zippel Lemma

• Randomly assign values from a large enough subset S ⊆ F to inputs.

• If C is non-zero polynomial, probability it evaluates to 0 is ≤ deg(C)/|S|.

• Algorithm:

  1. Pick random $$\displaystyle r_1, ..., r_n \in S $$.

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

  3. If result ≠ 0 → C is not identically zero.

  4. If result = 0 → C likely zero (with bounded error probability).

Exam Tip: This is a probabilistic test. For deterministic testing, polynomial interpolation or symbolic manipulation is needed but often infeasible for large circuits.

II. Hardware Implementation Platforms

Field-Programmable Gate Arrays (FPGA)

Basic Architecture:

• Configurable Logic Blocks (CLBs): Look-up tables (LUTs), flip-flops, multiplexers for combinational/sequential logic.

• Interconnects: Programmable routing resources (switches, wires).

• I/O Blocks: Interface with external pins.

• Configuration Memory: SRAM-based (volatile) or flash-based (non-volatile) storing bitstream.

Accuracy Issues in FPGA Implementations

Precision Enhancement Techniques

• Dynamic Reconfiguration: Partial reconfiguration to correct errors on-the-fly.

• Design-Time Calibration: Static timing analysis (STA), constraint-driven placement/routing, use of timing constraints (SDC files).

• Hardened IP Blocks: Vendor-provided pre-verified modules (e.g., transceivers, memory controllers) with guaranteed performance.

• Redundancy & Voting: Triple modular redundancy (TMR) for critical paths.

Common Pitfall: FPGA timing models are estimations; actual silicon may vary. Always verify with in-system timing analysis.

III. Physical Unclonable Functions (PUFs)

PUF Fundamentals

Definition: A Physical Unclonable Function is a hardware security primitive that maps challenges C to responses R based on inherent, uncontrollable manufacturing variations (e.g., transistor threshold voltage mismatch).

Core Principle: Each device has a unique "silicon fingerprint" that is easy to evaluate but hard to clone or predict.

Common Types:

Challenge-Response Pair (CRP) Generation:

• Challenge: Input stimulus (e.g., enable signals for RO pairs, selection bits for multiplexers in delay chains).

• Response: Measured physical property (e.g., which RO faster, arbiter output).

• CRP Database: Stored on server for authentication; should be large enough to prevent exhaustive attacks.

PUF Security Parameters

1. Reliability: Consistency of responses under environmental variations (temperature, voltage, aging).

   • Measured by intra-device Hamming distance (HD) across multiple measurements.

   • Ideal: intra-HD ≈ 0%.

2. Uniqueness: Distinguishability between different devices.

   • Measured by inter-device Hamming distance between responses of different devices to same challenge.

   • Ideal: inter-HD = 50% (for random n-bit responses).

3. Randomness: Statistical properties of responses (pass NIST tests).

4. Unpredictability: Hard to predict response to new challenge even with known CRPs (resistance to modeling attacks).

Metrics:

• Inter-Hamming Distance (inter-HD): Average HD between responses of different PUFs to same challenge.

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

• Intra-Hamming Distance (intra-HD): Average HD between responses of same PUF under different conditions.

$$\text{intra-HD} = \frac{1}{M} \sum_{k=1}^{M} \text{HD}(R, R'_k)$$

Design Techniques for High-Quality PUF Responses

• Circuit-Level Optimizations:

  • Balanced Delay Chains: Symmetric layout for Arbiter PUF to minimize systematic bias.

  • Temperature/Voltage Compensation: Use dummy circuits, biasing, or calibration loops.

  • XOR of Multiple PUFs: Combine outputs of k independent Arbiter PUFs to increase non-linearity (but may reduce reliability).

• Environmental Compensation:

  • On-chip sensors (temp, voltage) to apply digital correction (e.g., majority voting, error correction).

• Error Correction & Privacy Amplification:

  • ECC (e.g., BCH codes) to correct noisy responses.

  • Privacy amplification (hashing) to reduce entropy loss from helper data.

• Post-Processing:

  • Response Smoothing: Apply digital filters or thresholding to reduce noise.

  • Helper Data Generation: Public data for error correction without revealing secret.

PUF Attacks and Threat Models

Model Building Attacks on PUFs

Goal: Learn a predictive model f(C) ≈ R from observed CRPs, then predict responses to new challenges.

Machine Learning Frameworks:

• Logistic Regression: For linear PUFs (e.g., single Arbiter PUF).

• CMA-ES (Covariance Matrix Adaptation Evolution Strategy): For non-linear XOR Arbiter PUFs.

• Neural Networks: Deep learning for complex PUFs.

Attack Scenario:

1. Attacker collects N CRPs (challenges Cᵢ, responses Rᵢ).

2. Trains model on dataset.

3. Tests model on hold-out challenges; if accuracy > random, model successful.

Case Study: XOR Arbiter PUF

• Output = XOR of k Arbiter PUF outputs.

• Increases security against linear ML but introduces noise.

• Attack: Use divide-and-conquer or CMA-ES to model each stage individually.

Exam Tip: Reliability (noise) is main obstacle for ML attacks. Use error-correcting codes to limit usable CRPs.

Hardware Piracy Prevention Using PUFs

Problem: Overproduction, cloning, counterfeiting of ICs.

PUF-Based Solutions:

1. IP Protection: Bind design to unique PUF response. Only devices with correct PUF response can activate functionality.

2. Anti-Counterfeiting: Each device's PUF response acts as unique ID; verify via remote server.

3. Overbuilding Prevention: Manufacturer cannot produce extra working clones without knowing secret CRP mapping.

4. Secure Key Generation & Storage:

   • Key Generation: Use PUF response as secret key (after error correction and privacy amplification).

   • No Non-Volatile Memory Needed: Keys reconstructed on-demand from PUF; no storage of key bits.

Procedure:

• Enrollment: Device generates PUF response R, applies ECC to produce key K and helper data H.

• H is public; K is never stored.

• Authentication: Device re-generates R', uses H to correct errors, derives K'. Server verifies K'.

IV. Hardware Attack Vectors

Side-Channel Attacks (SCA)

Fundamental Principle: Secrets (e.g., cryptographic keys) leak through physical emanations (power, EM, time) correlated with processed data.

Types of Side-Channel Attacks:

Case Study: DES-based Side-Channel Attack (DPA)

Target: DES implementation with S-boxes. Assumption: Power consumption depends on Hamming weight of intermediate values (e.g., S-box output). Steps:

1. Capture many power traces Tᵢ for different plaintexts Pᵢ (with same secret key K).

2. For each possible subkey k (6 bits for one S-box):

   • Compute intermediate value v = S-box(Pᵢ[bits], k).

   • Predict power model (e.g., Hamming weight of v).

   • Compute correlation between predicted power and actual trace at time t.

3. Correct subkey k will show peak correlation at S-box output time.

4. Repeat for all 8 S-boxes → recover full 56-bit key.

Key Insight: DPA exploits data-dependent leakage; countermeasures must mask or randomize intermediate values.

Cache Attacks

Principle: Exploit shared hardware resources (CPU caches) in multi-core/cloud environments to infer secrets.

Common Techniques:

• Prime+Probe:

  1. Prime: Attacker fills cache with its data.

  2. Victim executes cryptographic code (evicts some cache lines).

  3. Probe: Attacker measures access time to its data; slow access → victim accessed that line.

• Flush+Reload:

  1. Flush: Attacker flushes shared memory page from cache.

  2. Victim executes (may load page).

  3. Reload: Attacker accesses page; fast → victim loaded it.

• Evict+Time: Measure overall execution time after evicting specific cache lines.

Targets: AES T-table lookups, RSA sliding windows, isolation breaches (e.g., between VMs).

Fault Attacks

Fault Injection: Deliberately induce transient faults to disrupt computation and leak secrets.

Techniques:

• Clock Glitching: Shorten clock period → setup violations.

• Voltage Glitching: Drop supply voltage → timing errors.

• Laser Fault Injection: Focused laser beam to damage/perturb transistors.

Effects on Cryptography:

• Bypass rounds: Fault in AES round 9 → last round key exposed.

• Differential Fault Analysis (DFA): Compare correct vs. faulty ciphertexts to derive key.

  • Example on AES: Inject fault before last round; equations relate fault in ciphertext to last round key.

Practical Setup: Low-cost equipment (e.g., voltage glitcher on Raspberry Pi) can break unprotected implementations.

V. Countermeasures and Defense Mechanisms

Countermeasures Against Side-Channel Attacks

Hiding Techniques

• Masking: Split secret s into shares s₁, s₂, ..., sₙ such that s = s₁ ⊕ ... ⊕ sₙ. Each share processed independently.

  • First-order masking: Resists first-order DPA.

  • Higher-order masking: Needed against higher-order attacks (more shares → more overhead).

• Shuffling: Randomize order of operations (e.g., S-box lookups).

• Random Delays: Insert variable wait states.

• Constant-Time: Ensure execution path/time independent of secret data (avoid data-dependent branches/memory accesses).

Design-Level Protections

• Balanced Circuit Design: Dual-rail logic (each bit represented by two wires; transitions balanced).

• Masked Logic Styles: Hardware gates that inherently process masked data (e.g., masked AND gate).

• Noise Injection: Add random current/EM noise to mask leakage.

• Power Flattening: Use current mirrors, larger capacitors to smooth power spikes.

Countermeasures Against Fault Attacks

• Detection Mechanisms:

  • Parity Checks: On registers, buses.

  • Checksums/CRC: On memory/data.

  • Control Flow Monitoring: Check program counters, sequence counters.

• Error-Correcting Codes (ECC): Single-error correction, double-error detection (SECDED) in memory and datapaths.

• Redundancy:

  • Temporal: Execute operation twice, compare.

  • Spatial: Duplicate computation units, vote on results.

Fault-Tolerant Cryptographic Architectures

Goal: Detect/correct faults without leaking secrets.

Typical Architecture:

Input → [Duplication Unit] → [Voter] → Output

          |               |

          ↓               ↓

     [Computation A]  [Computation B]

• Two/Three modules compute same operation in parallel.

• Voter outputs majority result; if mismatch → raise error/fail.

• Trade-offs: Area ×2–3, performance overhead (critical path of voter), power increase.

Design Tip: Protect key schedule and non-linear operations (S-boxes) most aggressively.

VI. Specialized Hardware Security Techniques

Domain-Specific Implementation for Finite Field Multipliers

Target: Efficient GF(2⁸) multiplication for AES (bytes are elements in GF(2⁸)).

Standard AES Field: GF(2⁸) with irreducible polynomial $$\displaystyle m(x) = x^8 + x^4 + x^3 + x + 1 $$.

Hardware Architectures:

1. Serial Multiplier:

   • Shift-and-add: For each bit of multiplier, conditionally add multiplicand.

   • Area: Small; Speed: Slow (8 cycles per multiply).

2. Parallel (Combinational) Multiplier:

   • Generate all partial products (AND gates) → reduce via XOR trees.

   • Area: Large; Speed: 1 cycle.

3. Montgomery Multiplier:

   • Avoids division by irreducible polynomial during reduction.

   • Efficient for repeated multiplications (e.g., exponentiation).

4. Normal Basis Multiplier:

   • Uses normal basis representation; squaring is simple (cyclic shift).

   • Good for squaring-heavy operations.

Side-Channel Considerations:

• Masked Multipliers: Process shares in parallel; avoid glitches.

• Constant-Time: Fixed latency regardless of input bits.

Trade-offs:

Reference: See rpgvonline.com for VHDL/Verilog examples of GF(2⁸) multipliers.

Hardware Verification for Security

Goal: Prove hardware design meets security specifications (e.g., no leakage, correct PUF behavior).

Formal Methods:

• Model Checking: Exhaustively verify finite-state circuits (e.g., control logic).

• Theorem Proving: Interactive proofs for complex properties.

• Equivalence Checking: Prove two circuits compute same function (uses polynomial identity testing).

Polynomial Identity Testing in Verification:

• Represent circuit as polynomial P(x₁, ..., xₙ) over GF(2).

• To check if P ≡ 0, use random testing (Schwartz-Zippel) or symbolic simulation.

• Application: Verify that a masked circuit computes f(s) correctly even with shares.

Example: Verify that masked S-box output = S-box(s) where s = s₁ ⊕ s₂.

Final Summary for Exam:

• PUFs are central: Know types, security parameters (inter/intra-HD), attacks (especially modeling with ML), and piracy prevention.

• Side-Channel Attacks: DPA on DES is a classic case study; cache attacks are modern.

• Fault Attacks: Glitching + DFA; countermeasures with redundancy.

• Finite Fields: Construction (GF(4) example), AES GF(2⁸) multipliers.

• Polynomial Identity Testing: Probabilistic method for circuit equivalence.

• FPGA: Accuracy issues (timing, signal integrity) and precision fixes.

Exam Strategy: For 7-mark questions, structure answer as: Definition → Mechanism/Construction → Example → Applications/Implications. Use diagrams where possible (e.g., PUF architecture, DPA flow).