Lightweight Cryptography (CY-802 (C)) - Unit 1 Short Notes

UNIT 1: Lightweight Cryptography Fundamentals & Primitives

I. Introduction to Lightweight Cryptography

Definition: A subfield of cryptography focused on designing cryptographic primitives (ciphers, hashes) that are optimized for severely resource-constrained environments.

Primary Need: Traditional cryptography (AES, RSA, SHA-2) is often prohibitively expensive for devices with limited:

• Energy/Power: Battery-operated or energy-harvesting devices (e.g., IoT sensors).

• Area/Footprint: Minimal silicon die size (RFID tags, smart dust).

• Memory: Tiny RAM/ROM (often < 1 KB).

• Computational Throughput: Low clock speeds, simple processors.

"Operation" in Computing Context:

The fundamental unit of cost measurement. Not a single CPU instruction, but often translated to:

• Gate Equivalents (GE): Area cost in standard CMOS cell libraries. 1 GE ≈ area of a 2-input NAND gate.

• CPU Cycles: Time cost on a specific processor (e.g., ARM Cortex-M0).

• Energy per Bit: Joules required to encrypt/process one bit of data.

[!TIP] Exam Focus: Be prepared to list at least 3 specific constraints (Energy, Area, Memory) and explain why AES (128-bit block, 10+ rounds) is unsuitable for a 1KB RAM sensor node.

II. Core Symmetric Primitives: Block Ciphers

Design Philosophies & Strategies

Analysis of Specific Lightweight Block Ciphers

1. PRESENT

• Design Rationale: Designed for hardware efficiency. Uses a 64-bit block size (for RFID) and 80/128-bit keys.

• Structure: 31-round Substitution-Permutation Network (SPN).

• S-Box: 4-bit S-Box (16 entries). Designed for minimal area (13 GE in hardware) while providing good non-linearity.

• Permutation Layer: Simple bit permutation across 64-bit state. Very cheap in hardware (just wiring).

• Key Schedule: Simple, but criticized for potential weaknesses.

2. DESL / DESXL

• Design Rationale: Optimized legacy DES. Aims for compatibility with existing DES infrastructure while reducing cost.

• Structure: Based on Feistel network (like DES), but with reduced rounds (DESL: 12 rounds vs. DES 16) and larger key (DESXL: 184-bit key).

• Comparison: DESL/DESXL have larger state (64-bit) than some newer ciphers but benefit from Feistel structure's inherent decryption (same as encryption). PRESENT's SPN requires separate decryption logic.

[!TIP] Exam Focus: Know one cipher in detail (PRESENT is most common). Be ready to contrast SPN (PRESENT) vs. Feistel (DESL) structures and their implications for area/decryption cost.

Modes of Operation for Lightweight Block Ciphers

• Purpose: Extend a block cipher to encrypt data longer than its block size.

• Lightweight-Suitable Modes:

  • CTR (Counter) Mode: Highly parallel, requires only encryption. Excellent for sensors streaming data. No padding needed.

  • ECB (Electronic Codebook): Simple but insecure for repeated data. Used only in extremely constrained, single-block scenarios (e.g., encrypting a 64-bit ID in an RFID tag).

  • Lightweight AEAD Modes: e.g., CTR + MAC (like CMAC) or specialized modes (e.g., from the CAESAR competition) for combined confidentiality & integrity.

Example - CTR Mode for Sensors:

1. Device shares a secret key K and an initial counter/nonce IV.

2. For each block i, compute Keystream_i = E_K(IV || i).

3. Ciphertext block C_i = P_i XOR Keystream_i.

4. Advantage: Encryption/decryption are identical. Sensor can generate keystream on-the-fly without storing entire message.

The Substitution Box (S-Box)

• Fundamental Role: The primary non-linear component in a block cipher. Provides confusion (Shannon), hiding relationship between key and ciphertext.

• Design Criteria for Lightweight S-Boxes:

  1. Low Area: Small lookup table (4-bit or 8-bit).

  2. Good Cryptographic Properties: High non-linearity, low differential uniformity, balanced output.

  3. Efficient Implementation: Simple logic or small ROM.

• Example - PRESENT 4-bit S-Box:

  Input: 0x0, 0x1, ..., 0xF

  Output: 0xC, 0x5, 0x6, 0xB, 0x9, 0x0, 0xA, 0xD, 0x3, 0xE, 0xF, 0x8, 0x4, 0x7, 0x1, 0x2

  (Can be implemented with minimal combinatorial logic).

III. Core Symmetric Primitives: Stream Ciphers

Design Principles:

• Generate a pseudo-random keystream from a secret internal state.

• State Size vs. Security: Larger internal state generally resists state recovery attacks but costs more memory.

• Update Function: Must be fast and secure (often based on LFSRs or NLFSRs).

Common Constructions:

• LFSR-based: Use one or more Linear Feedback Shift Registers for good period & randomness, combined with a non-linear filtering function.

• Filter Generators: A single large LFSR filtered by a non-linear Boolean function.

• Clock-Controlled: Irregular clocking of one LFSR by another (e.g., A5/1 for GSM, now broken).

Security Considerations & Attacks:

• Birthday Attack on State: If the internal state is n bits, after about 2^(n/2) keystream bits, collisions in the state become likely, potentially leading to state recovery.

  • Design Optimization: Use a large internal state (e.g., > 128 bits) to make 2^(n/2) infeasible.

• State Compromise Extensions (SCE): If an attacker learns the internal state at time t, can they compute past/future keystream?

  • Design Optimization: Ensure the state update function is one-way and sensitive to all state bits.

• Trade-off: Larger state → more memory & potentially slower update. Design must balance security level (state size), speed (bits/cycle), and size (GE).

[!TIP] Exam Focus: Link the birthday paradox (2^(n/2)) directly to the required minimum internal state size for a given security level (e.g., 128-bit security needs > 256-bit state).

IV. Cryptographic Hash Functions

Purpose & Security Requirements:

• Purpose: Map arbitrary-length input to fixed-length output (digest). Used for integrity, digital signatures, key derivation.

• Requirements:

  1. Pre-image Resistance: Given hash h, hard to find m s.t. H(m)=h.

  2. Second Pre-image Resistance: Given m1, hard to find m2≠m1 s.t. H(m1)=H(m2).

  3. Collision Resistance: Hard to find any m1, m2 with H(m1)=H(m2).

Lightweight Hash Function Design:

• Often based on the Sponge Construction (used in SHA-3, but lightweight variants).

• Sponge Principle: Absorb input into a state, then squeeze output. State size b = r + c (rate r, capacity c).

  • Security: Collision resistance ≈ 2^(c/2), pre-image ≈ 2^(c).

  • Lightweight Tweak: Use smaller state b (e.g., 256 bits) and smaller rate r to reduce area/energy.

• Examples:

  • PHOTON: Sponge-based, uses AES-like permutations. Offers 80-256 bit digests.

  • SPONGENT: Very small state (88-256 bits), optimized for hardware.

  • QUARK: Focus on ultra-low power, uses a lightweight permutation.

Real-World Applications of Lightweight Hashing:

• Message Authentication Codes (MACs): e.g., CBC-MAC or HMAC using a lightweight hash for IoT packet authentication.

• Integrity Checking: Verifying firmware updates on sensor nodes.

• Key Derivation Functions (KDFs): Deriving session keys from a master secret in a low-power device.

V. Key Management for Lightweight Cryptography

Fundamental Concepts & Challenges:

• Challenges in Constrained Devices:

  • Secure Storage: No secure element; keys stored in vulnerable memory.

  • Secure Distribution: No computational power for complex asymmetric protocols (e.g., Diffie-Hellman).

  • Scalability: Millions of devices; manual key provisioning impossible.

  • Energy Cost: Frequent key updates drain battery.

Centralized vs. Distributed Key Management:

Integration with Standard Protocols (IPSec/TLS):

• Problem: Standard TLS/IPSec use RSA/ECDH for key exchange, AES for encryption—too heavy.

• Adaptations:

  1. Cipher Suite Negotiation: Offer lightweight suites (e.g., TLS_ECDHE_PSK_WITH_AES_CCM_8 using pre-shared keys).

  2. Session Resumption: Use PSK (Pre-Shared Key) mode to avoid expensive public-key ops.

  3. Compression & Header Optimization: Use lightweight record layers, minimal headers.

  4. Hardware Offload: If available, use dedicated crypto engines.

Group Key Management for IoT:

• Requirements:

  • Scalability: Support thousands of nodes.

  • Dynamic Membership: Efficient join/leave (forward/backward secrecy).

  • Low Communication Overhead: Minimize messages for key updates.

  • Resilience: Tolerate node capture.

• Symmetric Key Techniques: Use Logical Key Hierarchy (LKH).

  • Each node holds a individual key and keys for a binary tree path to the root (group key).

  • Join/Leave: Only update keys on the path from affected nodes to root (O(log n) messages).

• Evaluation Criteria for New Protocols:

  1. Group Size: Small (sensor field) vs. Large (smart city).

  2. Mobility: Static vs. highly mobile nodes.

  3. Hardware Constraints: CPU, memory, radio energy cost.

  4. Security Properties: Forward secrecy, compromise resilience.

  5. Application Needs: Real-time vs. batch updates.

[!TIP] Exam Focus: Contrast Centralized (KDC) and Distributed (PSK) for key management. For group key management, explain LKH briefly (tree structure, O(log n) update cost).

VI. Security Evaluation & Design Principles

Importance of Open Design and Public Scrutiny:

• Kerckhoffs's Principle: Security should rely only on the key, not algorithm secrecy.

• Peer Review & Community Cryptanalysis: Public scrutiny finds flaws faster (e.g., attacks on KeeLoq, DESXL). Long-term viability depends on years of analysis.

• Security Through Obscurity: Dangerous for widespread deployment; once reverse-engineered, system fails.

Cryptanalysis as a Design Driver:

• Attacks Inform Design: Knowledge of linear/differential cryptanalysis leads to better S-boxes and diffusion layers. Algebraic attacks influence nonlinearity.

• Security Margin: Designers target a security margin (e.g., rounds > minimum required to resist known attacks). Lightweight ciphers often have smaller margins due to constraints.

• Balance: Trade-off between performance (area, energy) and estimated security.

Threat Model for Tiny Devices:

• Physical Attacks (More Relevant):

  • Side-Channel: Power analysis (SPA/DPA), electromagnetic leaks.

  • Fault Injection: Laser/clock glitching to induce errors.

  • Probing/Tampering: Physical access to read memory or buses.

• Network Attacks:

  • Eavesdropping, replay, node capture (steal key), Sybil attacks.

• Difference from Traditional: Physical proximity is often assumed. Attacker can capture and reverse-engineer the device. Traditional threat models often assume only network access.

VII. Foundational Comparisons & Context

Symmetric vs. Asymmetric Cryptography:

Broader Lightweight Cryptography Landscape:

• Primitives: Lightweight block ciphers, stream ciphers, hash functions, MACs.

• Protocols: Lightweight versions of TLS, IPSec, CoAP security.

• Implementations: Hardware (ASIC/FPGA) vs. software (8-bit AVR, ARM Cortex-M) optimizations. Bit-serial implementations save area.

• Standardization: NIST Lightweight Cryptography Project (selecting ASCON as standard in 2022) is a key driver.

[!TIP] Final Exam Strategy: For any question, first identify the constraint (energy, area, memory). Then, explain how a lightweight design choice (smaller S-box, SPN structure, LKH) addresses that constraint while maintaining acceptable security. Always mention trade-offs.