SIV and the Two-Pass Design of a Misuse-Resistant AEAD

Every AEAD mode discussed so far places a uniqueness obligation on the caller: the nonce must not repeat under a given key. This is a demanding requirement when encryption happens in many places, survives crashes, and is sometimes performed by hardware with no reliable state. The SIV construction was designed around a different premise — that the caller will eventually repeat a nonce, and that the mode should degrade gracefully when it does.

The degradation is specific and worth stating precisely, because it is the whole point. Under nonce reuse, an ordinary AEAD fails completely for the messages involved: confidentiality collapses to a plaintext XOR and, in GCM’s case, the authentication key is exposed. Under SIV, reuse reveals only whether two plaintexts were identical. Everything else stays hidden, and forgery remains infeasible.

Deterministic encryption as the underlying primitive

SIV is built on deterministic authenticated encryption, a scheme that takes no nonce at all. Deterministic means the same key, associated data, and plaintext always produce the same ciphertext. That is obviously too weak on its own for any setting where an attacker can see whether two messages were the same, but it is exactly the right primitive to build a nonce-based scheme from, because a nonce-based scheme can be obtained by deriving the nonce deterministically from what is being encrypted.

The gap between “same ciphertext for same message” and “same ciphertext for different messages that happen to share a header” is what the mode must close, and SIV closes it by putting the entire plaintext into the derivation.

The construction, in two passes

RFC 5297 defines SIV-AES with a 64-byte key split into two 32-byte halves, one for the MAC and one for the encryption. The first pass computes

$$V = \mathrm{S2V}\big(\mathrm{CMAC}(K_1, A_1) | \dots | \mathrm{CMAC}(K_1, A_n) | \mathrm{CMAC}(K_1, P)\big)$$

where the associated data strings and the plaintext are each MACed separately, the MAC outputs are concatenated, and a second MAC over that concatenation produces a 128-bit synthetic IV. The splitting and length-prefixing of the associated data strings is what makes the construction injective: S2V encodes the number of components and their lengths, so no rearrangement of the inputs produces the same value.

The second pass runs CTR mode with $K_2$, using an initial counter block derived from $V$: the high half of the counter block clears bit 31, the low 64 bits hold a copy of $V$, and encryption proceeds from there. The ciphertext is the CTR output; the tag is $V$ itself, or its high bits truncated to the configured length.

Two properties follow from the ordering. The tag depends on the plaintext, so a ciphertext cannot exist without its plaintext having been processed — this is why decryption must run the MAC second rather than first. And the IV depends on the plaintext, so two distinct plaintexts under the same nonce get different counter blocks. Reuse therefore produces two different keystreams, and the XOR leak that destroys CTR and GCM simply does not happen.

# Shape of the two passes, with the MAC and cipher as opaque callables.
def siv_encrypt(k_mac, k_enc, ad_list, plaintext, s2v):
    v = s2v(k_mac, ad_list, plaintext)      # synthetic IV over AD and P
    block = v[:]                            # counter block from V
    block[8] &= 0x7f                        # clear bit 31 of the 32-bit half
    block[12:] = v[8:]                      # low 64 bits copy V again
    return ctr_encrypt(k_enc, block, plaintext), v

What nonce reuse actually costs

Suppose the same nonce is used to encrypt plaintexts $P$ and $P’$ with the same associated data. The synthetic IVs are $V = F(P)$ and $V’ = F(P’)$, computed with the MAC key, which the attacker does not have. If $P \neq P’$, then $V \neq V’$ with high probability, so the counter blocks differ and the two keystreams are unrelated. The ciphertexts look like independent encryptions to an attacker without the key.

If $P = P’$, then $V = V’$ and the ciphertexts are identical. That equality is the only information leaked: the attacker learns that two messages with the same associated data are the same. This is stated in the security definition as resistance to a nonce-misuse adversary up to equality of plaintexts, and it is strictly weaker than what a deterministic scheme reveals (equality per associated-data tuple, which is the same thing) and strictly stronger than what GCM reveals (everything).

The catch is that the attacker learns this only if the associated data matches too. Since the MAC input includes the associated data, two different headers produce different synthetic IVs even for identical plaintexts.

The price of the second pass

Misuse resistance is bought with a full extra pass over the plaintext with a MAC keyed separately, and the MAC in the RFC is CMAC, which is itself a chain of block cipher invocations. Encryption therefore costs roughly twice the cipher work of GCM, and the MAC pass cannot begin until the plaintext is complete.

That constraint removes streaming. An implementation cannot emit the first block of ciphertext while receiving the plaintext, because the first block of ciphertext depends on the final synthetic IV, which depends on the last block of plaintext. For a protocol that must process a message incrementally — a large file upload, a network record arriving in segments — SIV requires buffering the whole plaintext. GCM and other one-pass modes can emit ciphertext with a bounded delay.

AES-GCM-SIV, defined in RFC 8452, addresses the cost by replacing CMAC-based S2V with a construction on top of the GCM primitives. It computes a synthetic IV from the associated data and plaintext using POLYVAL — a polynomial hash closely related to GHASH but over a different field representation, chosen so that the same carry-less multiplication instructions apply — then uses that IV as the nonce for a GCM-style encryption whose authentication tag is derived separately. It remains two-pass over the plaintext for the same reason, but the hashing uses the fast polynomial arithmetic rather than CBC chaining, which narrows the gap to one-pass modes considerably.

Where determinism is the point

There is a class of uses where deterministic encryption is not a fallback but the requirement. Key wrapping is the clearest: a key encrypting another key with no nonce available and no state to maintain. NIST SP 800-38F specifies key wrap modes for exactly this, and RFC 5297 lists key wrapping among its intended applications, using the associated data to bind the wrapped key to its context — an algorithm identifier, a key identifier, a usage statement.

Binding is the second function SIV performs well. Because every associated-data string enters the synthetic IV MAC, a ciphertext produced for one header fails to decrypt under a different header: the receiver recomputes the IV from the received header and plaintext, and a mismatch means the header was altered. This is the general AEAD property, but SIV makes the associated data contribute to the nonce rather than only to the tag, so header manipulation cannot even reach the decryption stage in a way that produces output.

Ciphertext databases and encrypted indexes are the other natural fit. A deterministic scheme produces the same ciphertext for the same plaintext under the same associated data, which is a searchable index by construction. SIV limits what that leaks to equality within the same associated-data context, and the associated data can be used to partition the index by a coarse attribute, keeping equality comparisons within a group rather than across the whole table.

Verification order and its failure modes

Decryption in SIV must recompute the synthetic IV from the received associated data and the decrypted plaintext, then compare it against the received tag. The plaintext is therefore produced before the tag is verified, which is the pattern discussed in releasing unverified plaintext. An implementation must not return plaintext to a caller until the comparison succeeds, and must compare in constant time.

The design also depends on the MAC and the cipher using independent keys. Sharing a key between the CMAC pass and the CTR pass would tie the two structures together in ways the security proof does not cover, and RFC 5297 is explicit that the two 32-byte halves are separate keys even though they are carried together. A key-derivation step that produces a 64-byte SIV key from a shorter master key must not produce the same bytes twice.

Finally, SIV is only as misuse-resistant as its nonce handling allows it to be with respect to associated data. Encrypting the same message twice with different associated data produces different ciphertexts, which is fine, but it also means that a protocol which puts a timestamp into the associated data forfeits the deterministic behaviour that indexing relies on. The mode makes the trade explicit; the caller still chooses which side of it to sit on.