AES-CTR HMAC Streaming AEAD

This document formally defines the mathematical function represented by AES-CTR HMAC Streaming keys (encoded in proto format as type.googleapis.com/google.crypto.tink.AesCtrHmacStreamingKey).

This encryption is loosely based on [HRRV15]¹. For an analysis of the security we refer to [HS20]². Note also that the Tink cross language tests have a test aes_ctr_hmac_streaming_key_test.py which contains test_manually_created_test_vector with a complete walkthrough on how to get a ciphertext.

Key and parameters

Keys are described by the following parts (all sizes in this document are in bytes):

$\mathrm{InitialKeyMaterial}$, a byte string: the initial key material.
$\mathrm{CiphertextSegmentSize} \in \{1, 2, \ldots, 2^{31}-1\}$.
$\mathrm{DerivedKeySize} \in \{16, 32\}$.
$\mathrm{HkdfHashType} \in \{\mathrm{SHA1}, \mathrm{SHA256}, \mathrm{SHA512}\}$.
$\mathrm{HmacHashType} \in \{\mathrm{SHA1}, \mathrm{SHA256}, \mathrm{SHA512}\}$.
$\mathrm{HmacTagSize} \in \mathbb{N}$.

Valid keys additionally satisfy the following properties:

$\mathrm{len}(\mathrm{InitialKeyMaterial}) \geq \mathrm{DerivedKeySize}$.
If $\mathrm{HmacHashType} = \mathrm{SHA1}$ then $\mathrm{HmacTagSize} \in \{10, \ldots, 20\}$.
If $\mathrm{HmacHashType} = \mathrm{SHA256}$ then $\mathrm{HmacTagSize} \in \{10, \ldots, 32\}$.
If $\mathrm{HmacHashType} = \mathrm{SHA512}$ then $\mathrm{HmacTagSize} \in \{10, \ldots, 64\}$.
$\mathrm{CiphertextSegmentSize} > \mathrm{DerivedKeySize} + \mathrm{HmacTagSize} + 8$ (This equals $\mathrm{len}(\mathrm{Header}) + \mathrm{HmacTagSize}$ as explained later).

Keys which do not satisfy any of these properties are rejected by Tink (either when the key is parsed or when the corresponding primitive is created).

Encryption function

To encrypt a message $\mathrm{Msg}$ with associated data $\mathrm{AssociatedData}$, we create a header, split the message into segments, encrypt each segment, and concatenate the segments. We explain these steps in the following.

Creating the header

To create the header, we first pick a uniform random string $\mathrm{Salt}$ of length $\mathrm{DerivedKeySize}$. We next pick a uniform random string $\mathrm{NoncePrefix}$ of length 7.

We then set $\mathrm{Header} := \mathrm{len}(\mathrm{Header}) \| \mathrm{Salt} \| \mathrm{NoncePrefix}$, where the length of the header is encoded as a single byte. We note that $\mathrm{len}(\mathrm{Header}) \in \{24, 40\}$.

Next, we use HKDF³ with hash-function $\mathrm{HkdfHashType}$ to compute key material of length $\mathrm{DerivedKeySize} + 32$ for this message: $k := \mathrm{HKDF}(\mathrm{InitialKeyMaterial}, \mathrm{Salt}, \mathrm{AssociatedData})$. The inputs are used in the corresponding respective inputs of $\mathrm{HKDF}$: $\mathrm{InitialKeyMaterial}$ is $\mathrm{ikm}$, $\mathrm{Salt}$ is the salt, and $\mathrm{AssociatedData}$ is used as $\mathrm{info}$.

The string $k$ is then split into two parts $k_1 \| k_2 := k$, such that $\mathrm{len}(k_1) = \mathrm{DerivedKeySize}$ and $\mathrm{len}(k_2) = 32$.

Splitting the message

The message $M$ is next split into parts: $M = M_0 \| M_1 \| \cdots \| M_{n-1}$.

Their lengths are chosen so that they satisfy:

$\mathrm{len}(M_0) \in \{0,\ldots, \mathrm{CiphertextSegmentSize} - \mathrm{len}(\mathrm{Header}) - \mathrm{HmacTagSize}\}$.
If $n > 1$, then $\mathrm{len}(M_1), \ldots, \mathrm{len}(M_{n-1}) \in \{1,\ldots, \mathrm{CiphertextSegmentSize} - \mathrm{HmacTagSize}\}$.
If $n > 1$, then $M_{0}, \ldots, M_{n-2}$ must have maximal length according to the above to constraints.

In this splitting, $n$ may at most be $2^{32}$. Otherwise, encryption fails.

Encrypting the blocks

To encrypt segment $M_i$, we first compute $\mathrm{IV}_i := \mathrm{NoncePrefix} \| \mathrm{i} \| b \| 0x00000000$, where we encode $\mathrm{i}$ in 4 bytes using big-endian encoding, and set the byte $b$ to be 0x00 if $i < n-1$ and 0x01 otherwise.

We then encrypt $M_i$ using AES CTR key $k_1$, and initialization vector $\mathrm{IV}_i$. In other words, the inputs to the invocations of AES are $\mathrm{IV}_i, \mathrm{IV}_i + 1, \mathrm{IV}_i + 2, \ldots$ where $\mathrm{IV}_i$ is interpreted as big-endian integer. This yields $C'_i$.

We compute the tag using HMAC with the hash function given by $\mathrm{HmacHashType}$ and with key $k_2$ over the concatenation $\mathrm{IV}_i \| C'_i$.

We then concatenate the ciphertext followed by the tag to get $C_i$.

Concatenate the segments

Finally, all segments are concatenated as $\mathrm{Header} \| C_0 \| \cdots \| C_{n-1}$, which is the final ciphertext.

Decryption function

Decryption simply inverts the encryption. We use the header to obtain the nonce, and decrypt each segment of ciphertext individually.

APIs may (and typically do) allow random access, or access to the beginning of a file without inspecting the end of the file. This is intentional, since it is possible to decrypt $M_i$ from $C_i$, without decrypting all previous and remaining ciphertext blocks.

However, APIs should be careful to not allow users to confuse end-of-file and decryption errors: in both cases the API probably has to return an error, and ignoring the difference can lead to an adversary being able to effectively truncate files.

Serialization and parsing of keys

To serialize a key in the "Tink Proto" format, we first map the parameters in the obvious way into the proto given at aes_ctr_hmac_streaming.proto. The field version needs to be set to 0. We then serialize this using normal proto serialization, and embed the resulting string in the value of field of a KeyData proto. We set the type_url field to type.googleapis.com/google.crypto.tink.AesCtrHmacStreamingKey. We then set key_material_type to SYMMETRIC, and embed this into a keyset. We usually set the output_prefix_type to RAW. The exception is that if the key was parsed with a different value set for output_prefix_type, Tink may either write RAW or the previous value.

To parse a key, we reverse the above process (in the usual way when parsing protos). The field key_material_type is ignored. The value of output_prefix_type can either be ignored, or keys which have output_prefix_type different from RAW can be rejected. Keys which have a version different from 0 are be rejected.

References

[HRRV15] Hoang, Reyhanitabar, Rogaway, Vizar. Online authenticated-encryption and its nonce-reuse misuse-resistance. CRYPTO 2015. https://eprint.iacr.org/2015/189 ↩
[HS20] Security of Streaming Encryption in Google's Tink Library. Hoang, Shen, 2020. https://eprint.iacr.org/2020/1019 ↩
[HKDF] HMAC-based Extract-and-Expand Key Derivation Function (HKDF), RFC 5869. https://www.rfc-editor.org/rfc/rfc5869 ↩