The AES-SIV Algorithm

The AES-SIV Algorithm

Introduction

Most authenticated encryption modes carry a rule that is easy to state and easy to break: never use the same nonce twice under one key. If you do, AES-GCM loses its security, and so does AES-CCM. Real systems break that rule by accident. A counter gets reset, a virtual machine is restored from a snapshot, or a random number generator is not as random as hoped.

AES-SIV takes a different approach. It does not need a nonce to stay secure. If you do give it one and then repeat it, the damage is small. An attacker learns only whether two messages were identical, and authenticity is not affected. This property is called nonce-misuse resistance.

Table of Contents

• History
• The Idea: a Synthetic IV
• CMAC and Doubling
• S2V
• Encryption with CTR
• Decryption
• Nonce-Based and Deterministic Use
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

Phillip Rogaway and Thomas Shrimpton specified SIV in their 2006 EUROCRYPT paper on deterministic authenticated encryption and the key-wrap problem. Dan Harkins turned it into an IETF document, RFC 5297, in October 2008. The RFC defines SIV with AES, using key lengths of 128, 192, or 256 bits for each of its two halves.

The original motivation was key wrapping. Protocols need to send cryptographic keys inside other keys, and older wrapping methods did not authenticate associated data or handled it poorly. SIV can replace those methods, and it accepts several separate associated data strings, up to 126.

The Idea: a Synthetic IV

In a normal mode like CCM, you choose a nonce and give it to the cipher. SIV works the other way round. It computes the initial value itself, from the message. That value is called the synthetic IV, or V.

V plays two roles. It is the authentication tag, because it is a keyed hash of the associated data and the plaintext. It is also the starting counter for AES in counter mode, which encrypts the plaintext. Because V depends on every byte of the input, two different messages almost certainly get two different counters, even if the caller supplies the same nonce for both.

The key is two AES keys joined together. The first half, K1, is used for the hash. The second half, K2, is used for encryption. For AES-128 the combined key is 256 bits, for AES-192 it is 384 bits, and for AES-256 it is 512 bits.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose the nonce-based mode or the deterministic mode. Enter a key made of two AES keys, associated data, and a message in hex. Several associated data strings are separated by colons. Encrypt shows each S2V step and each counter block. To decrypt, paste the synthetic IV and ciphertext into the message box and click Decrypt. Change one hex digit first, and the check fails.

CMAC and Doubling

SIV is built on AES-CMAC (RFC 4493), a MAC made from AES. CMAC needs an operation called doubling, which is multiplication by x in the field GF(2¹²⁸). To double a 16-byte value, shift it left by one bit, and if a one bit fell off the left end, XOR the result with the constant 0x87:

dbl(S) = (S << 1)                 if the top bit of S is 0
dbl(S) = (S << 1) xor 0x87        if the top bit of S is 1

CMAC uses doubling to make two subkeys from AES(0). SIV reuses the same operation inside its own function.

S2V

S2V takes a list of strings, the associated data followed by the plaintext, and turns them into one 16-byte value. It is a pseudorandom function built from CMAC. With the strings S1 to Sn, where Sn is the plaintext:

D = CMAC(K1, 16 zero bytes)
for i = 1 to n-1:
    D = dbl(D) xor CMAC(K1, Si)
if len(Sn) >= 16 bytes:
    T = Sn with D XORed onto its last 16 bytes
else:
    T = dbl(D) xor pad(Sn)
V = CMAC(K1, T)

The function pad appends a single one bit and then zero bits, up to 16 bytes. The RFC also defines S2V for an empty list, where the result is CMAC(K1, 0^127 || 1). SIV never reaches that case, because the plaintext is always in the list. The doubling in each step makes the order of the strings matter, so moving data from one string to another changes V. The RFC limits the input to 127 strings in total. Because the plaintext is one of them, that leaves at most 126 associated data strings.

The extra doubling for a short last string has a purpose. Without it, a short string Sn would give D xor pad(Sn). A 16-byte last string equal to pad(Sn) would give exactly the same value, so the two different inputs would collide. Doubling D keeps them apart.

Encryption with CTR

The synthetic IV is V. To make the first counter, SIV clears two bits of V, bit 31 and bit 63, counting from the right with the rightmost bit as bit 0. The result is Q. This lets implementations with only 32-bit or 64-bit adders increment the counter without worrying about carries across those bit positions.

Counter mode then runs under K2. For each 16-byte block i = 0, 1, 2, ... of plaintext, the keystream block is AES(K2, Q + i), with the counter treated as a 128-bit number. Unlike CCM, SIV does not reserve counter 0. The value V travels in the clear, so it needs no keystream block.

The ciphertext C is the plaintext XOR the keystream, so it has exactly the same length as the plaintext. The final output is V followed by C, which is 16 bytes longer than the plaintext.

Decryption

Decryption reverses the order, because V is both the tag and the counter:

1. Take V from the first 16 bytes of the input and make Q from it.
2. Decrypt C with counter mode to get a candidate plaintext.
3. Run S2V over the associated data and the candidate plaintext.
4. Compare the result with the received V. If they match, return the plaintext. If not, return an error and nothing else.

Because the tag is checked after decryption, SIV must never release the candidate plaintext before the check passes. Releasing it early is known as the release of unverified plaintext. The safe approach is to buffer the whole message and hand it over only after the check succeeds.

Nonce-Based and Deterministic Use

RFC 5297 describes two ways to use SIV.

Nonce-based. The nonce is one more associated data string, the last one before the plaintext. A random nonce should be at least 128 bits long. RFC 5297 says that the definition of a nonce precludes reuse, but SIV is resistant to nonce reuse. If a nonce does repeat, authenticity is unaffected and privacy is slightly reduced.

Deterministic. There is no nonce. The output depends only on the key, the associated data, and the plaintext, so the same input always gives the same output. This is the right mode for key wrapping, where the plaintext is a secret key that an attacker cannot predict. The RFC warns that it is not for ordinary data, because anyone can see when two plaintexts are equal.

A Worked Example

This is the deterministic example from RFC 5297, Appendix A.1. The key is fffefdfc fbfaf9f8 f7f6f5f4 f3f2f1f0 f0f1f2f3 f4f5f6f7 f8f9fafb fcfdfeff, so K1 is the first 16 bytes and K2 the last 16. The associated data is 10111213 14151617 18191a1b 1c1d1e1f 20212223 24252627, and the plaintext is the 14 bytes 11223344 55667788 99aabbcc ddee.

S2V. First CMAC(K1, 0^16) gives 0e04dfaf c1efbf04 01405828 59bf073a. Doubling it gives 1c09bf5f 83df7e08 0280b050 b37e0e74. The CMAC of the associated data is f1f922b7 f5193ce6 4ff80cb4 7d93f23b, and the XOR of the two is D = edf09de8 76c642ee 4d78bce4 ceedfc4f. The plaintext has fewer than 16 bytes, so S2V doubles D again, which gives dbe13bd0 ed8c85dc 9af179c9 9ddbf819. The padded plaintext is 11223344 55667788 99aabbcc ddee8000, and the XOR of the two is T = cac30894 b8eaf254 035bc205 40357819. The last CMAC gives the synthetic IV:

V = 85632d07 c6e8f37f 950acd32 0a2ecc93

The counter. Clearing bit 31 and bit 63 changes the low 64 bits of V from 950acd320a2ecc93 to 150acd320a2ecc93. Bit 63 was 1 and bit 31 was 0. The first counter is:

Q = 85632d07 c6e8f37f 150acd32 0a2ecc93

Encryption. AES(K2, Q) gives the keystream 51e218d2 c5a2ab8c 4345c4a6 23b2f08f. XORed with the 14-byte plaintext it gives the ciphertext 40c02b96 90c4dc04 daef7f6a fe5c. The complete output is V followed by C:

85632d07 c6e8f37f 950acd32 0a2ecc93 40c02b96 90c4dc04 daef7f6a fe5c

Every intermediate value above is the one printed in the RFC. For the nonce-based example in Appendix A.2, the synthetic IV is 7bdb6e3b432667eb06f4d14bff2fbd0f.

Nonce reuse. Encrypting transfer 100 to Alice and transfer 900 to Alice under the same key, associated data, and nonce gives two different synthetic IVs, 0effcb07a364470d6a60280a9e663569 and f5e253caa94de4d6da0baab0d23b3850. The messages differ by one character, so they are not related. Encrypting the first message again gives exactly the same output as before. That is the only thing nonce reuse reveals.

Python Implementation

This is a complete AES-SIV: CMAC, doubling, S2V, CTR, and encryption and decryption for a list of associated data strings. A single bytes object counts as one string. It uses the same small aes_core.py file as the AES-CCM guide, which has its source.

# siv.py
#
# AES-SIV, the deterministic authenticated encryption of RFC 5297.
# The tag, called the synthetic IV, is computed first from the associated data
# and the plaintext with a CMAC-based function named S2V. The same value then
# becomes the starting counter for AES-CTR encryption. Because the tag depends
# on the whole input, a repeated nonce reveals only that the same message was
# sent twice, which makes SIV "nonce-misuse resistant".
#
# The key is two AES keys joined together: K1 for S2V and K2 for CTR.

from aes_core import AES


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


def dbl(block):
    """Multiply by x in GF(2^128): shift left, and xor 0x87 if a one fell off the end."""
    value = int.from_bytes(block, "big")
    carry = value >> 127
    value = (value << 1) & ((1 << 128) - 1)
    if carry:
        value ^= 0x87
    return value.to_bytes(16, "big")


def pad(data):
    """Append a one bit and zero bits up to 16 bytes."""
    return data + b"\x80" + bytes(15 - len(data))


def cmac(key, message):
    """AES-CMAC (RFC 4493)."""
    aes = AES(key)
    k1 = dbl(aes.encrypt_block(bytes(16)))
    k2 = dbl(k1)
    blocks = [message[i:i + 16] for i in range(0, len(message), 16)] or [b""]
    last = blocks[-1]
    if len(message) and len(last) == 16:
        last = xor(last, k1)
    else:
        last = xor(pad(last), k2)
    state = bytes(16)
    for block in blocks[:-1]:
        state = aes.encrypt_block(xor(state, block))
    return aes.encrypt_block(xor(state, last))


def xorend(data, d):
    """XOR the 16-byte value d onto the last 16 bytes of data."""
    return data[:-16] + xor(data[-16:], d)


def s2v(key, strings):
    """The S2V function: a CMAC-based pseudorandom function over a list of strings."""
    if not strings:
        return cmac(key, bytes(15) + b"\x01")
    d = cmac(key, bytes(16))
    for s in strings[:-1]:
        d = xor(dbl(d), cmac(key, s))
    last = strings[-1]
    if len(last) >= 16:
        t = xorend(last, d)
    else:
        t = xor(dbl(d), pad(last))
    return cmac(key, t)


def split_key(key):
    if len(key) not in (32, 48, 64):
        raise ValueError("an SIV key is 32, 48 or 64 bytes: two AES keys of equal length")
    half = len(key) // 2
    return key[:half], key[half:]


def ctr_start(synthetic_iv):
    """Clear bit 31 and bit 63 (counting from the right) of the synthetic IV."""
    return (int.from_bytes(synthetic_iv, "big") & ~((1 << 31) | (1 << 63))).to_bytes(16, "big")


def ctr_crypt(key2, synthetic_iv, data):
    aes = AES(key2)
    counter = int.from_bytes(ctr_start(synthetic_iv), "big")
    out = bytearray()
    for i in range(0, len(data), 16):
        stream = aes.encrypt_block(((counter + i // 16) & ((1 << 128) - 1)).to_bytes(16, "big"))
        out += xor(data[i:i + 16], stream)
    return bytes(out)


def ad_strings(ad):
    """Accept a list of associated data strings. One bytes object counts as a single string."""
    return [bytes(ad)] if isinstance(ad, (bytes, bytearray)) else list(ad)


def encrypt(key, plaintext, ad_list=()):
    """Return the 16-byte synthetic IV followed by the ciphertext."""
    key1, key2 = split_key(key)
    v = s2v(key1, ad_strings(ad_list) + [plaintext])
    return v + ctr_crypt(key2, v, plaintext)


def decrypt(key, data, ad_list=()):
    """Return the plaintext, or raise ValueError if the synthetic IV does not match."""
    key1, key2 = split_key(key)
    if len(data) < 16:
        raise ValueError("the input is shorter than the synthetic IV")
    v, ciphertext = data[:16], data[16:]
    plaintext = ctr_crypt(key2, v, ciphertext)
    expected = s2v(key1, ad_strings(ad_list) + [plaintext])
    difference = 0
    for a, b in zip(expected, v):
        difference |= a ^ b
    if difference:
        raise ValueError("authentication failed")
    return plaintext


if __name__ == "__main__":
    key = bytes.fromhex("7f7e7d7c7b7a79787776757473727170" "404142434445464748494a4b4c4d4e4f")
    header = bytes.fromhex("00112233445566778899aabbccddeeff" "deaddadadeaddadaffeeddccbbaa9988" "77665544 33221100".replace(" ", ""))
    extra = bytes.fromhex("102030405060708090a0")
    nonce = bytes.fromhex("09f911029d74e35bd84156c5635688c0")
    plaintext = bytes.fromhex("7468697320697320736f6d6520706c61696e74657874" "20746f20656e6372797074207573696e6720534956" "2d414553")
    sealed = encrypt(key, plaintext, [header, extra, nonce])
    print("Key:        " + key.hex())
    print("Plaintext:  " + plaintext.hex())
    print("IV || C:    " + sealed.hex())
    print("Recovered:  " + decrypt(key, sealed, [header, extra, nonce]).hex())
    try:
        decrypt(key, bytes([sealed[0] ^ 1]) + sealed[1:], [header, extra, nonce])
    except ValueError as error:
        print("Tampered:   " + str(error))

Running it produces this output:

Key:        7f7e7d7c7b7a79787776757473727170404142434445464748494a4b4c4d4e4f
Plaintext:  7468697320697320736f6d6520706c61696e7465787420746f20656e6372797074207573696e67205349562d414553
IV || C:    7bdb6e3b432667eb06f4d14bff2fbd0fcb900f2fddbe404326601965c889bf17dba77ceb094fa663b7a3f748ba8af829ea64ad544a272e9c485b62a3fd5c0d
Recovered:  7468697320697320736f6d6520706c61696e7465787420746f20656e6372797074207573696e67205349562d414553
Tampered:   authentication failed

I checked this code against several independent sources before writing it up. The CMAC matches the four test vectors and the two subkeys of RFC 4493. The cipher reproduces both examples of RFC 5297, Appendix A, and every intermediate S2V value printed there. It also passes the Wycheproof test suites for AES-SIV-CMAC. The deterministic suite gave 118 valid and 324 invalid cases, and the nonce-based suite gave 252 valid and 648 invalid cases. Every valid vector was reproduced exactly and every invalid one was rejected. Changing any byte of the output makes decryption fail.

Limitations

This is a faithful teaching version of the mode, not a production one:

• Two passes over the data. SIV needs the whole plaintext before it can produce the first byte of output, and decryption needs the whole ciphertext, so SIV cannot stream. This is a limit of the goal, not only of this design. If the first output bytes depended only on the first input bytes, two messages sharing a prefix would share the start of their ciphertext, and an eavesdropper could see that. Misuse resistance allows only whole-message equality to leak, so the first output bytes must depend on the entire message.
• Not constant-time. The AES here uses table lookups on secret data, and Python is not suitable for real encryption.
• Deterministic mode leaks equality. Without a nonce, equal inputs give equal outputs. Use it only when that is acceptable, as in key wrapping.
• Slower than GCM. SIV runs CMAC over the data and then CTR over it again, so it costs about two AES calls per block.

Security Status

RFC 5297 says that SIV output is indistinguishable from random bits, and that an attacker cannot construct an input that decrypts to anything other than an error. Rogaway and Shrimpton give a proof for this in their paper. If a nonce is used correctly, SIV reaches the full level of security. If the nonce is reused, SIV keeps its authenticity guarantee, and only a slightly smaller amount of privacy remains.

The security proof for S2V holds only when the number of strings is less than the block size in bits, which is why the limit of 126 associated data strings exists. When S2V is used as a key derivation function, its secret input must be uniformly random. No practical attack on AES-SIV is known.

FAQ

What makes SIV nonce-misuse resistant?

The synthetic IV depends on the whole message, so the counter changes whenever the message changes. A repeated nonce therefore does not produce a repeated keystream for different messages.

Is AES-SIV the same as AES-GCM-SIV?

They are different modes. AES-GCM-SIV is a different mode, specified in RFC 8452. It also resists nonce misuse, but it uses a polynomial hash instead of CMAC. This guide covers the CMAC-based AES-SIV of RFC 5297.

Why is the key twice as long?

SIV uses two independent AES keys, one for the CMAC hash and one for counter mode. An AES-128 SIV key therefore has 256 bits, which is two 128-bit keys. RFC 5297 names its suites by the total key size. AEAD_AES_SIV_CMAC_256 uses two AES-128 keys, and AEAD_AES_SIV_CMAC_512 uses two AES-256 keys. It is easy to mistake the 256 for AES-256.

Can I stream data with SIV?

It is not possible, because SIV computes the tag first, from the entire plaintext, and the tag is also the counter. For streaming data, use a mode such as AES-GCM or ChaCha20-Poly1305 with careful nonce management.

When should I use deterministic mode?

Use it for key wrapping, where the plaintext is a secret key that nobody can predict. For ordinary messages, include a nonce so that equal messages do not give equal outputs.

References

1. Harkins, D. “Synthetic Initialization Vector (SIV) Authenticated Encryption Using the Advanced Encryption Standard (AES).” RFC 5297, 2008. Available at: https://www.rfc-editor.org/rfc/rfc5297

2. Rogaway, P. and Shrimpton, T. “Deterministic Authenticated Encryption: A Provable-Security Treatment of the Key-Wrap Problem.” Advances in Cryptology, EUROCRYPT 2006.

3. Song, JH., Poovendran, R., Lee, J., and Iwata, T. “The AES-CMAC Algorithm.” RFC 4493, 2006. Available at: https://www.rfc-editor.org/rfc/rfc4493

4. Google. “Project Wycheproof: AES-SIV-CMAC test vectors.” Available at: https://github.com/C2SP/wycheproof