Key Derivation Function (KDF)

A secure KDF must be deterministic: given the same input (secret, salt, and other parameters), it must always produce the same output key. This property is essential for systems where multiple parties or processes need to derive the same key independently, such as in secure communication sessions or for decrypting stored data. However, determinism alone is dangerous for password-based keys, which is why a salt is a critical additional input to ensure uniqueness.

The output of a KDF must be pseudorandom and preimage-resistant. This means the derived key should be indistinguishable from a random bit string, and it should be computationally infeasible to reverse the function to find the original input secret. This property protects the source secret (e.g., a low-entropy password) even if the derived key is exposed. It is achieved by building the KDF upon a cryptographically secure pseudorandom function (PRF), such as HMAC-SHA256.

A secure KDF must be collision-resistant. It should be computationally infeasible to find two different input sets (e.g., two different passwords) that produce the same output key. While related to the properties of the underlying hash function, a well-designed KDF structure amplifies this resistance. Collision resistance prevents an attacker from substituting one secret for another, which is vital for authentication and integrity purposes in embedded systems.

To defend against brute-force attacks, especially on low-entropy inputs like passwords, a secure KDF incorporates a deliberate computational cost or work factor. This is typically implemented as a high iteration count (or CPU/memory cost in modern KDFs like Argon2 or scrypt). Each iteration applies the core PRF again, linearly increasing the time and energy required for an attack. For TinyML, this parameter must be carefully tuned to balance security with the device's limited power budget and latency requirements.

A cryptographic salt is a non-secret, random value that is a mandatory input to a secure KDF. Its primary purposes are:

• Preventing Rainbow Table Attacks: By making each key derivation unique, a salt forces attackers to precompute tables for each salt value, rendering bulk precomputation impractical.
• Ensuring Key Uniqueness: Even if the same master secret is used across multiple devices or contexts, a unique salt ensures different keys are generated, preventing systemic compromise.
• For embedded devices, salts must be stored securely alongside the derived key or regenerated deterministically.

Algorithm agility is the property that allows a system to seamlessly transition to a stronger KDF or hash function if the underlying primitive is compromised. A well-designed KDF specification includes an identifier for the algorithm used. Domain separation ensures keys derived for different purposes (e.g., encryption vs. authentication) are cryptographically independent, even from the same source secret. This is often achieved by including a context or info field as a KDF input, a critical practice in TinyML for deriving multiple keys for different model protection functions from a single device root key.

NIST SP 800-108 specifies several KDFs in feedback modes, with the Counter Mode being a common, efficient choice for constrained environments. It is designed for use with a pre-shared secret key (KKM).

• Core Mechanism: K_i = HMAC(K_KDM, [i] || Label || 0x00 || Context || [L]) where i is a counter. Each iteration produces a block of key material.
• Key Features: Deterministic, efficient, and allows derivation of multiple keys for different contexts (identified by the Label and Context fields).
• Primary Use Case: Deriving multiple encryption and authentication keys from a single master key in standardized systems, such as storage encryption or network protocols. Its simplicity can be advantageous for TinyML implementations where a strong master key already exists.

The revision of NIST SP 800-108 adds KDFs based on CMAC (Cipher-based MAC) and KMAC (Keccak-based MAC, from SHA-3). These provide alternatives to HMAC-based constructions.

• CMAC-based KDF: Uses a block cipher (like AES) in CMAC mode. This can be highly efficient on hardware with AES acceleration.
• KMAC-based KDF: Built on the SHA-3 / Keccak sponge function, offering security properties distinct from SHA-2-based HMAC. KMAC itself can be used as a variable-length output PRF, making it naturally suitable for key derivation.
• Primary Use Case: Systems requiring diversification from SHA-2 or leveraging specific hardware accelerators (AES-NI, SHA-3 co-processors). KMAC is also a core component of post-quantum cryptography standards like ML-KEM, making its use in KDFs future-resistant.

A Cryptographic Hash Function is a deterministic algorithm that maps data of arbitrary size to a fixed-size output (a hash or digest). It is a core building block for a KDF. Key properties include:

• Pre-image resistance: Infeasible to reverse the hash to find the original input.
• Collision resistance: Infeasible to find two different inputs that produce the same hash.
• Avalanche effect: A small change in input produces a drastically different output.

Common hash functions like SHA-256 and SHA-3 are used within KDFs (e.g., HKDF, PBKDF2) to provide the necessary pseudorandomness and one-way properties for secure key derivation.

A Password-Based Key Derivation Function is a specific class of KDF designed to derive cryptographic keys from low-entropy, human-memorable passwords. It intentionally uses a computationally expensive process to slow down brute-force and dictionary attacks.

Core Components:

• Password: The weak secret input.
• Salt: A random value added to each password to prevent precomputed rainbow table attacks.
• Iteration Count: The number of times the underlying hash function is repeated, increasing the work factor for an attacker.

PBKDF2 is the most widely deployed standard, though modern alternatives like Argon2 (the winner of the Password Hashing Competition) provide better resistance against GPU/ASIC attacks.

HKDF is a Key Derivation Function standardized in RFC 5869, built using the HMAC (Hash-based Message Authentication Code) construct. It is designed for use where the input keying material (IKM) already has sufficient entropy, such as a Diffie-Hellman shared secret or a hardware-generated random key.

HKDF operates in two stages:

1. Extract: Uses HMAC with a salt to 'concentrate' the possibly non-uniform IKM into a fixed-length, cryptographically strong pseudorandom key.
2. Expand: Uses HMAC to generate multiple output keys of the required length from the extracted key material.

HKDF is efficient and is the recommended KDF for deriving keys from established secrets in protocols like TLS 1.3 and for securing IoT device communications.

A Salt is a random, non-secret value used as an additional input to a KDF or one-way function. Its primary security functions are:

• Uniqueness: Ensures that identical passwords or inputs produce different derived keys. This defeats rainbow table attacks where an attacker precomputes hashes for common passwords.
• Key Separation: Using a unique salt for each context (e.g., per user, per device) ensures derived keys are independent, preventing compromise in one context from affecting others.

In a KDF like PBKDF2, the salt is not a secret but must be stored and retrieved alongside the derived key or its verifier. For HKDF, the salt can serve as a 'key diversification' parameter.

Key Stretching is the technique of deliberately increasing the computational resources (time and/or memory) required to test each possible key or password candidate. It is a critical defense when the input secret has low entropy, such as a user password.

Implementation in KDFs:

• Iterative Hashing: As used in PBKDF2, where the core hash function is applied thousands or millions of times.
• Memory-Hard Functions: As used in scrypt and Argon2, which require large amounts of memory to compute, making hardware-accelerated attacks prohibitively expensive.

The goal is to make brute-force attacks computationally infeasible for the defender, who performs the stretching once, while imposing the same high cost on an attacker for every guess.

A Cryptographic Key Hierarchy is a structured system for managing keys, where higher-level, long-lived keys are used to derive or protect lower-level, short-lived keys for specific operations. A KDF is the engine that enables this hierarchy.

Example for a TinyML Device:

1. Root Key: A unique device secret provisioned in hardware (e.g., from a PUF or Secure Element).
2. Identity Key: Derived via KDF from the Root Key + a fixed label. Used for device attestation.
3. Session Keys: Derived via KDF (e.g., HKDF) from an ephemeral shared secret (from ECDH) for encrypting a firmware update.

This practice limits the exposure and scope of any single key, contains damage from key compromise, and supports secure key rotation.