Secure Hash Algorithm (SHA)

Pre-image resistance is the fundamental property that a hash function is computationally infeasible to reverse. Given an output digest h, it should be impossible to find any input m such that hash(m) = h. This ensures that the original data cannot be derived from its fingerprint, protecting passwords stored as hashes and commitment schemes.

• Example: Given the SHA-256 digest a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146, finding the original input "Hello World" is intractable without brute-forcing all possible inputs.

Second pre-image resistance guarantees that for a given input m1 and its hash h1 = hash(m1), it is computationally infeasible to find a different input m2 (where m2 ≠ m1) that produces the same hash hash(m2) = h1. This protects against forgery in data integrity checks.

• Critical for: File integrity verification. An attacker cannot substitute a malicious file that hashes to the same value as a legitimate file, ensuring the detected digest uniquely identifies the original, unaltered data.

Collision resistance means it is computationally infeasible to find any two distinct inputs m1 and m2 (where m1 ≠ m2) that produce the same hash output, i.e., hash(m1) = hash(m2). This is a stronger guarantee than second pre-image resistance and is vital for digital signatures.

• Why it matters: In a digital signature, you sign the hash of a document. If collisions can be found, an attacker could create a fraudulent document that hashes to the same value as a legitimate one, forging a valid signature. SHA-256 and SHA-3 are designed to be collision-resistant against all known practical attacks.

The avalanche effect describes the property where a small change in the input—even flipping a single bit—produces a drastic, unpredictable change in the output digest. On average, approximately 50% of the output bits should change. This ensures the hash output appears random and uncorrelated to the input.

• Demonstration:
  • SHA256("hello") starts with: 2cf24dba5fb0a30e26e83b2ac5b9e29e...
  • SHA256("hellp") starts with: 099d6c7f2f3a6b7c9457e2b3a2f3c6d9... The change of one character results in a completely different, seemingly random hash.

A cryptographic hash function is deterministic: the same input will always produce the identical hash output. It also produces a fixed-length output regardless of the size of the input data. SHA-256 always produces a 256-bit (32-byte) digest, whether hashing a single character or a terabyte file.

• Key implications:
  • Determinism enables consistency for verification (e.g., checksums).
  • Fixed-length output provides efficiency for storage and comparison, and is essential for the security proofs of many cryptographic protocols.

A practical hash function must be computationally efficient to calculate from any given input. While reversing the hash is designed to be hard, the forward computation must be fast for legitimate use cases like TLS handshakes, blockchain mining, or real-time data authentication on embedded devices.

• TinyML Consideration: For resource-constrained microcontrollers, the computational and memory footprint of a hash function is critical. This has led to the development and standardization of lightweight cryptography algorithms, such as those in the NIST Lightweight Cryptography project (e.g., Ascon, winner of the NIST LWC competition), which provide SHA-3-like security with a much smaller code size and lower energy consumption.

SHA-256 is a member of the SHA-2 family that produces a 256-bit (32-byte) hash digest. It is the most widely adopted cryptographic hash function, forming the backbone of modern security protocols and systems.

• Core Properties: It is deterministic, pre-image resistant, and exhibits a strong avalanche effect.
• Critical Applications: It secures blockchain transactions (e.g., Bitcoin), TLS/SSL certificates, and software update integrity checks.
• TinyML Relevance: While computationally intensive, SHA-256 is essential for secure boot and firmware attestation in high-assurance embedded systems, often accelerated by hardware cryptographic co-processors.

SHA-3 (Keccak) represents a radical architectural departure from previous SHA families, based on a sponge function rather than the Merkle–Damgård construction. This makes it inherently resistant to length-extension attacks.

• Internal State: It uses a large internal permutation state (e.g., 1600 bits) for absorbing input and squeezing output.
• Flexibility: The same core permutation can be configured for hashing, authenticated encryption (KMAC), and extendable-output functions (XOFs).
• Embedded Use: Its simple logic and low gate count make it a candidate for lightweight cryptography in silicon-constrained devices, though adoption is still growing.

SHA-1 produces a 160-bit hash and was widely used for digital signatures and certificate authorities. Published in 1995, it is now considered cryptographically broken.

• Security Status: Practical collision attacks were demonstrated in 2017, leading to its deprecation for all security-sensitive purposes.
• Legacy Risk: It remains in some legacy systems and is a prime target for downgrade attacks. Modern systems must enforce migration to SHA-2 or SHA-3.
• Lesson for TinyML: Highlights the necessity of cryptographic agility in device firmware to allow for algorithm updates as standards evolve.

SHA functions are foundational building blocks for Key Derivation Functions (KDFs) and secure password storage mechanisms. They transform secrets into cryptographically strong keys.

• PBKDF2: A widely used KDF that applies a pseudorandom function (like HMAC-SHA256) thousands of times to a password and salt, increasing the computational cost for brute-force attacks.
• HKDF: A simpler, hash-based KDF designed to extract and expand key material from a high-entropy source.
• TinyML Context: KDFs are crucial for deriving device-unique encryption keys from a hardware root of trust or for securing wireless provisioning credentials on microcontrollers.

A Hash-based Message Authentication Code (HMAC) combines a cryptographic hash function (like SHA-256) with a secret key to verify both the data integrity and the authenticity of a message.

• Mechanism: HMAC(K, m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)). This nested structure protects against certain cryptographic weaknesses.
• Primary Use: It is the standard method for authenticating API requests, software update packages, and communication between IoT devices and cloud services.
• Implementation Note: For TinyML devices, HMAC provides a computationally efficient alternative to digital signatures for verifying commands from a trusted server.

For severely constrained microcontrollers, standard SHA algorithms can be prohibitive. This drives the development and use of optimized or alternative constructs.

• SHA-256/224: Truncated variants that offer slightly reduced security for a smaller digest size.
• Hardware Acceleration: Many modern microcontrollers (e.g., with ARM CryptoCell) include dedicated silicon for SHA operations, reducing power consumption and execution time by orders of magnitude.
• Lightweight Alternatives: In some threat models, lightweight cryptography standards like SHAKE (from SHA-3) or Ascon may be evaluated for hashing needs where traditional SHA is too heavy.

A Secure Hash Algorithm (SHA) deterministically transforms input data of any size into a fixed-size cryptographic hash or digest. In TinyML, this is used to verify the integrity of critical assets:

• Model Binaries: Ensure a deployed neural network file hasn't been corrupted or tampered with.
• Sensor Data: Create a checksum for data batches before processing to detect transmission errors.
• Firmware Updates: The digest of a new firmware image is calculated and compared against a signed value during a Secure OTA Update. Any alteration to the input, even a single bit, produces a completely different, unpredictable hash, making tampering evident.

The SHA family includes algorithms with different security strengths and computational demands, critical for selecting the right fit for a microcontroller.

• SHA-256: The current standard. Produces a 256-bit (32-byte) digest. Offers 128-bit collision resistance. Common in Secure Boot and code signing. Requires ~2-4KB of ROM and significant RAM for context.
• SHA-512: Stronger (512-bit digest), but more computationally intensive. Rarely used on ultra-constrained MCUs.
• SHA-3 (Keccak): NIST's newest standard, based on a different sponge construction. Offers similar security to SHA-2 but with a different performance profile and potentially better resistance to some side-channel attacks.
• SHA-1 (Deprecated): Considered cryptographically broken. Must not be used for new security designs, though may be found in legacy systems.

SHA is rarely used alone. It's a core component in constructing a chain of trust from a Hardware Root of Trust.

1. The boot ROM (immutable) contains a public key and uses SHA-256 to verify the signature of the first-stage bootloader.
2. The verified bootloader then hashes the application firmware (using SHA-256) and compares it to a stored, signed digest.
3. The application can, in turn, verify the integrity of its TinyML model in flash by comparing its computed SHA-256 hash against a trusted value stored in a protected area. This cascading verification, built on cryptographic hashing, ensures only authentic and unmodified code and models execute.

Running SHA on microcontrollers presents unique challenges:

• Memory Footprint: A typical SHA-256 software implementation may require 2-4KB of ROM/Flash for code and ~200 bytes of RAM for the context and working buffer. This is significant for devices with only 32KB of total flash.
• Compute Time: Hashing a 1MB firmware image on a 80MHz Cortex-M4 can take hundreds of milliseconds, impacting boot time and power consumption.
• Mitigation Strategies:
  • Use hardware acceleration (crypto coprocessors) if available (e.g., some STM32, NXP LPC, and ESP32 chips).
  • Hash critical sections only (e.g., headers and code, excluding padding).
  • Use Lightweight Cryptography standards like SHAKE (from SHA-3) if appropriate for the protocol.

Beyond static integrity checks, SHA enables dynamic security protocols for TinyML devices.

• Message Authentication Codes (HMAC): SHA-256 is used as the underlying hash for HMAC, providing data authenticity and integrity for messages between a sensor and a gateway.
• Firmware Attestation: A device proves its software state to a remote server. The server sends a nonce (random number), the device hashes its firmware with the nonce (using SHA-256), and signs the result with a device-specific key. The server verifies the signature and hash.
• Key Derivation: SHA-256 is often the core of Key Derivation Functions (KDFs) like HKDF, which derive secure session keys from a master secret.

SHA is a building block used in conjunction with other embedded security concepts.

• Digital Signatures (ECDSA/RSA): These algorithms sign the SHA-256 hash of a message, not the message itself, for efficiency.
• Secure Boot & TEE: The Trusted Firmware-M (TF-M) reference implementation, part of the Platform Security Architecture (PSA), uses SHA-256 for all integrity measurements during secure boot and secure partition management.
• Post-Quantum Cryptography (PQC): Several NIST-standardized PQC algorithms (e.g., Dilithium for signatures) internally use SHA-3 or SHA-2 for hashing and expansion, making efficient SHA implementation a prerequisite for future quantum-resistant security on embedded devices.

A Cryptographic Nonce (number used once) is an arbitrary number that can be used just once in a cryptographic communication. It is critical for preventing replay attacks.

• Properties: Must be unique and unpredictable within a given context. Often a random or sequential number.
• Interaction with SHA: Nonces are frequently included as part of the data input to hash functions in protocols. For example, in challenge-response authentication, a server sends a nonce that the client must hash with a secret key to prove identity.
• TinyML Use Case: Used in secure communication sessions between a sensor node and a gateway to ensure that an old, recorded transmission cannot be replayed maliciously.

A Merkle Tree (or hash tree) is a data structure in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the hash of the labels of its child nodes.

• Efficient Verification: Allows efficient and secure verification of the contents of large data structures. You can prove a single leaf is part of the tree without transmitting the entire tree.
• SHA's Role: The hash function (e.g., SHA-256) is used to compute all the node labels.
• TinyML Use Case: Verifying the integrity of individual layers or parameters within a large machine learning model stored in external flash, without needing to hash the entire multi-megabyte model on the constrained MCU.