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]1. For an analysis of the
security we refer to [HS20]2. 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 HKDF3 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 ↩