Chunked encryption

This document specifies a mechanism to encrypt a large message of up to 4 PiB, allowing authenticated streaming encryption and decryption, and authenticated random access with predictable mapping of plaintext and ciphertext indices.

It has similar purpose to STREAM and FLOE, combining the TLS 1.3 record layer design with an HKDF-Expand key derivation step that includes key commitment.

It is secure if instantiated with any secure hash of at least 256 bits and a secure AEAD based on a block cipher of at least 128 bits, with a key size of at least 128 bits and a nonce size of at least 96 bits.

The recommended instantiation is named Cobblestone-128 and uses SHA-512 and AES-128-GCM. A compliance-oriented instantiation is named Cobblestone-256 and uses SHA-512 and AES-256-GCM.

The maximum number of messages that can be encrypted under a single input key depends on the maximum size of each message. The concrete values for the recommended instantiations are shown in the table below.

If instantiated with an AEAD having a tag length of 16 bytes, like AES-GCM in the recommended instantiation, this scheme has a fixed overhead of 56 bytes and a marginal overhead of approximately 0.1%.

Specification §

At a high level, for each message a single-use random key, base nonce, and commitment are generated with HKDF-Expand from an input key, salt, and context. The message is split into 16 KiB chunks, with the last chunk being always shorter. Each chunk is then encrypted with an AEAD, the key, and the base nonce XOR’d with a chunk counter.

Key derivation §

This scheme is instantiated with an HKDF-Expand hash function, and an AEAD which encrypts messages with a key of len(key) bytes and a nonce of len(nonce) bytes. Applications and protocols SHOULD select a single hash and a single AEAD for use with each high-level application or protocol version.

Absent other requirements, the use of SHA-512 and AES-128-GCM is RECOMMENDED.

For each message, a tuple of unique, uniformly random key, base nonce, and commitment are derived from an input key of len(key) bytes (i.e. the same key size as the underlying AEAD) with HKDF-Expand.

|| denotes concatenation. 0x followed by two hexadecimal characters denotes a byte value in the 0-255 range. A string surrounded by " is encoded as ASCII.

key || base nonce || commitment = HKDF-Expand(prk = input key, 
    info = "c2sp.org/chunked-encryption@v1+" || aead || 0x00 || salt || context)

The input key MUST be uniformly random, e.g. generated by a CSPRNG or output by a KDF.

aead is the name of the underlying AEAD, from the AEAD Algorithms IANA registry, like AEAD_AES_128_GCM.

salt is a sequence of 24 bytes that MUST NOT repeat for a certain input key, and that SHOULD be randomly generated. It MUST be prepended to the final message ciphertext, before the commitment.

context is application provided additional data, and it MAY be empty.

key and base nonce MUST be of len(key) and len(nonce) bytes respectively.

commitment MUST be of 32 bytes, and MUST be prepended to the ciphertext, after the salt. When decrypting, implementations MUST check the commitment matches the derived value before continuing.

Message chunking §

The message is split into chunks of 16 KiB, except the final chunk which MUST be shorter than 16 KiB, and MAY be empty. Note that there is only one correct chunking for each message length. For example:

• An empty message is encrypted as a single empty chunk.
• A message of 1 KiB is encrypted as a single chunk of 1 KiB.
• A message of 16 KiB is encrypted as two chunks, one of 16 KiB and one empty.
• A message of 20 KiB is encrypted as two chunks, one of 16 KiB and one of 4 KiB.

When decrypting, the implementation MUST check that the final chunk is shorter than 16 KiB, and consider the message truncated otherwise.

The chunks are numbered from zero, and the message MUST NOT exceed 2³⁸ chunks or 4 PiB - 1 byte. If the chunk counter reaches or exceeds 2³⁸ while encrypting or decrypting, implementations MUST abort. Implementations MAY limit the chunk count to a lower number, but SHOULD NOT apply a limit lower than 2³² (64 TiB).

AEAD usage §

Each chunk MUST be encrypted/decrypted with the AEAD using the key and a nonce derived as the XOR of the base nonce and the chunk number as a big-endian integer as wide as the base nonce. (Equivalently, the final 5 bytes of the base nonce are XOR’d with the chunk number as a big-endian 38-bit integer.)

The AEAD’s AAD is not used and MUST be empty.

The final ciphertext MUST be the concatenation of salt, commitment, and the AEAD ciphertexts.

Test vectors §

A full suite of test vectors is provided as part of Project Wycheproof.

Implementation notes §

A streaming encryption implementation needs only buffer 16 KiB of input and can flush that buffer into an encrypted chunk immediately once the buffer fills up. When the message terminates, the buffer must be flushed into a final short encrypted chunk, even if the buffer is empty.

After checking the commitment, a streaming decryption implementation needs to read multiples of 16 KiB + len(tag), where len(tag) is usually 16, and decrypt them and authenticate them before making the plaintext available to the application. Upon reaching the end of the ciphertext, it must decrypt the final chunk, which must have encrypted length between len(tag) and 16 KiB + len(tag) - 1. Otherwise, it must return a message truncation error.

A random access decryption implementation may choose to authenticate the message length at any point by calculating the offset of the last chunk, checking its encrypted length is between len(tag) and 16 KiB + len(tag) - 1, and decrypting it. This check must be performed if the application requests a seek offset relative to the end of the message. All decryption implementations must check the commitment before decrypting any chunk.

A plaintext index i can be found at index i % 16384 of chunk i // 16384. Chunk k can be found at ciphertext offset 56 + k * (16384 + len(tag)).

Note that not all message ciphertext lengths are valid, in particular any message of encrypted length 56 + k * (16 KiB + len(tag)) is truncated, and any message of encrypted length < 56, or > 56 + k * (16 KiB + len(tag)) and < 56 + k * (16 KiB + len(tag)) + len(tag) is invalid. Pay attention not to assume that the final encrypted chunk is always > len(tag), as that can cause panics or memory errors.

FIPS 140 compliance §

Two components of this scheme are in scope for FIPS 140-3 compliance: the key derivation and the AEAD.

The key derivation uses an Approved Feedback Mode KDF from NIST SP 800-108 Rev. 1 Upd. 1, as explained in The FIPS Compliance of HKDF.

A FIPS 140-3 compliant AEAD must be selected, such as AES-GCM. It can be shown that the key and nonce derivation employed by this scheme fully satisfies the SP 800-38D universal pair uniqueness requirement even if 2⁷⁷ full-length messages are encrypted. (See the birthday bound analysis below.) However, most FIPS 140-3 modules and NVLAP-accredited labs only accept schemes that comply with the relaxed requirements of Implementation Guidance C.H. This scheme can be used with a XOR’d counter-based nonce scheme complying with IG C.H Scenario 3, with a nonce scheme intended for use with TLS 1.3 complying with IG C.H Scenario 1.a, or with a nonce scheme intended for use with HPKE or with this specification complying with IG C.H Scenario 5. These are all equivalent and for example the FIPS 140-3 Go Cryptographic Module v1.26.0 provides all three as different APIs for the same implementation.

Security analysis §

At the AEAD level, we need to show that (key, nonce) pairs have a low chance of colliding. Even assuming a worst case scenario in which every message has length 4 PiB, exhausting the 38-bit counter space in the nonce, and the AEAD has a key size of 128 bits and nonce size of 96 bits, that leaves 128 + 96 - 38 = 186 bits of uniformly random space. Since the counter occupies at most the low-order 38 bits, the remaining 58 bits of the base nonce are invariant across chunks within a message and can’t collide unless the whole base nonce collides. That produces a birthday bound of 2⁷⁷ messages for a chance of collision of 2⁻³².

At the key derivation level, using random 192-bit salts has a birthday bound of 2⁸⁰ messages for a chance of collision of 2⁻³², which exceeds the derived key + base nonce birthday bound of 2⁷⁷. The HKDF internal state is sufficient not to be the bottleneck even if SHA-256 is in use. The commitment provides a verification oracle for the input key and salt, but since their combined space (128 + 192 = 320 bits in the worst case) exceeds the derived key and base nonce space (128 + 96 - 38 = 186 bits in the worst case), it does not become the bottleneck for multi-target security.

The 32-byte key commitment provides 128 bits of key commitment security.

The HKDF-Expand info field is encoded as a parseable sequence of a fixed-length prefix, a variable-length AEAD name terminated with a zero byte, a fixed-length salt, and a variable-length context. Using a c2sp.org prefix minimizes the risk of collision with other HKDF-Expand uses.

As for the truncation (and extension) protection, in order to forge a message length the attacker would need to produce a (nonce, ciphertext) tuple where the nonce encodes counter (length // 16 KiB), and the ciphertext has length (len(tag) + length % 16 KiB). Without violating ciphertext unforgeability (INT-CTXT), this is only possible if such a tuple was output by an honest encryption operation, meaning the message length is the correct one.

Aside from key derivation, key commitment, and truncation protection, the scheme is essentially identical to the TLS 1.3 record layer, and benefits from its extensive security analysis. In particular, we refer to ePrint 2024/051 (originally published in 2016) and ePrint 2018/993.

Using Equation (7) of ePrint 2024/051 we can calculate the attacker’s single-file advantage for a series of sizes.

Since each file is encrypted under an independent key (per the derivation analysis above) a standard hybrid argument bounds the advantage against k files by at most k × ϵ. Section 1.3 of ePrint 2024/051 and Section 1 of ePrint 2017/435 confirm there is no additional multi-key degradation for GCM as a mode. That means that if we want to bound the advantage at 2⁻³² we can encrypt at most 2⁻³² / ϵ files of that size, leading to the table of maximum file counts at the top.

ePrint 2018/993 provides a stricter and more comprehensive (but more complex) analysis, combining the missing birthday advantage with the forgery advantage and the offline bruteforce advantage.

We apply Theorem 4.3 with two scheme-specific refinements: the σB/2ⁿ birthday term ranges over encryption blocks only (Bad2/Bad3), and the forgery term charges each verification query its own length rather than B (Bad7/Bad8), since every AEAD invocation in this scheme is at most 2¹⁰ blocks. Assuming at most 2⁶⁰ forgery attempts, q is 2⁶⁰ + the number of encrypted chunks (total data / 16 KiB). σ is the number of encrypted blocks (total data / 128 bits). B is the number of encrypted blocks “per user” (file size / 128 bits). d is how many files share an effective nonce, 2⁷ at 2⁶⁵ files: the counter takes the low 38 bits, so files collide only in the 2⁵⁸ invariant base-nonce prefixes. p is a bound on offline work: for 128-bit keys we need to pick 2⁸⁰ or the generic key-guessing attack dominates (note that no 128-bit-key scheme can meet a 2⁻³² advantage target against attackers exceeding ~2⁹⁶ AES evaluations), for 256-bit keys it’s irrelevant.

Applying it to the numbers in the table yields advantage of 2⁻³⁰ for every row, dominated by the σB term, which represents the same missing-birthday distinguisher we analyzed above. (The factor 4 over Equation (7)’s 2⁻³² is proof bookkeeping in ePrint 2018/993, not a stronger attack: their Theorem 3.1 charges the within-key collision event twice across two bad-event cases and drops the birthday ½ that Equation (7) retains.)

Rationale §

The last chunk is required to be short, which implicitly acts as the end-of-message signal. The alternative, allowing a full final chunk and disallowing an empty final chunk, has multiple disadvantages: it requires an explicit final chunk flag in the nonce or AD; it forces a streaming decryption implementation to do trial decryptions or look-ahead to determine if a chunk is final or not; it requires extra buffering (push-based) or overread (pull-based) on the encryption side, even if the application makes inputs available in otherwise optimal chunk-sized spans; and finally it requires an exception to allow an empty chunk for empty messages. Moreover, the final chunk flag is a bit of in-band signaling, which requires handling cases like trailing chunks or garbage after the final chunk, and it can be a source of implementation errors. Similarly, with full final chunks a valid ciphertext length can be both a valid truncation and a valid message, while with short final chunks a valid ciphertext length can only be a single valid message.

Padding and variable chunk sizes are not supported, to allow random access decryption with a predictable mapping of plaintext indices.

The chunk size was chosen to match the TLS 1.3 record size. This has a few advantages: systems can be expected to be capable to decrypt chunks whole if they can do the same for TLS 1.3; we get to reuse more easily some security bound analysis; and implementations are likely to be tested and optimized at that size. The selected chunk size provides marginal overhead (< 0.1%) and a maximum message size that exceeds the key wearout limit of a 128-bit block cipher in CTR mode.

The maximum chunk count is selected such that the maximum size of a message is below the key wearout limit of a 128-bit block cipher in CTR mode, while protecting enough nonce space to make the birthday bound and multi-target security analysis of 128-bit keys straightforward.

The nonce is generated along with the key to extend the birthday and multi-target bounds of AEADs with 128-bit keys. The counter is XOR’d with the nonce instead of concatenated to provide additional practical multi-target security beyond the conservative analysis (which assumes the counter space is exhausted in every message), and to match the TLS 1.3 and HPKE designs, in order to reuse their security analysis such as ePrint 2018/993.

The AEAD’s AAD is not used because context can already be bound into the key derivation step. (This part may change in a future version if a strong reason presents itself. For example, this requires context to be known before encryption starts.)

The key derivation uses HKDF-Expand without the Extract step to comply with NIST SP 800-108, and because the input key for an encryption API can be presumed to be uniformly random already.

Using SHA-512 instead of SHA-256 in the recommended instantiation halves the HMAC calls in HKDF-Expand, and is anyway a better fit for modern 64-bit architectures.

Implementations §

• filippo.io/cobblestone (Go)

Appendix: raw mode §

If this scheme is used in the context of a higher-level protocol, the key and base nonce MAY be generated using its existing key derivation and domain separation facilities, instead of using the specified HKDF-Expand invocation.

The key and base nonce MUST be both uniformly random, not just non-repeating, so for example the base nonce MUST NOT be produced by directly encoding a counter. They MUST NOT be reused for multiple messages.

key and base nonce SHOULD be generated as one long key of length len(key) + len(nonce) and SHOULD be derived via a KDF from either a non-repeating message counter or from a random value of 192 bits or more.

If this mode is used, no salt or commitment is prepended to the final ciphertext, and no key commitment is provided by this layer.

Libraries SHOULD NOT expose this mode to applications: it should either be implemented internally by higher-level libraries as a component of the higher-level protocol, or exposed as a “hazmat” primitive meant for implementing protocols.

The ciphertext offset and validity formulas in the implementation notes must be adjusted to remove the 56-byte prefix when implementing raw mode.