Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)? I was just going over my (old) notes from Coursera's Cryptography I course, and I was puzzled by the description of SIV as providing deterministic authenticated encryption (DAE). The general SIV construction shown is to first compute a MAC over the plaintext using a secure PRF, and then to encrypt the plaintext using a secure block cipher in CTR mode using the MAC tag as the IV and an independent key. The IV and the ciphertext are then output.

As far as I can tell, this is essentially an Encrypt-and-MAC scheme, which would seem to me to be open to the same kinds of chosen ciphertext attacks as SSH? Is there some aspect of SIV that excludes such attacks? Or are such attacks excluded by the definition of deterministic ciphertext integrity?

From http://cseweb.ucsd.edu/~mihir/papers/oem.pdf page 17:


  E&amp;M does not provide INT-CTXT. E&amp;M also fails to provide integrity of ciphertexts. This is because there are secure encryption schemes with the property that a ciphertext can be modified without changing its decryption. When such an encryption scheme is used as the base symmetric encryption scheme, an adversary can query the encryption oracle, modify part of the response, and still submit the result to the verification oracle as a valid ciphertext.


Is this ruled out because SIV is only defined over CTR mode and so excludes such encryption schemes?
The definition of DAE security, as given in Rogaway and Shrimpton's original paper (which both defines the security notion and proves that SIV mode satisfies it), does effectively require that a DAE scheme must protect ciphertext integrity.

Specifically, the definition of DAE security (definition 1 in the paper) says that an encryption scheme is DAE secure if an adversary cannot, with non-negligible advantage, tell whether it is talking to the real encryption and decryption oracle, or to a fake encryption oracle that returns for each distinct query a random bit string of the same length as the real encryption oracle would've returned, and a fake decryption oracle that treats all ciphertexts as invalid, with the limitation that the adversary may not submit strings previously returned by the encryption oracle to the decryption oracle or vice versa.

Crucially, while the definition forbids the adversary from submitting ciphertexts previously returned by the encryption oracle to the decryption oracle (and thereby winning trivially), it does not forbid the adversary from submitting a modified version of a previously obtained valid ciphertext to the decryption oracle.  Thus, if an adversary could modify a valid ciphertext in a way that does not almost certainly render it invalid, they could win the "DAE game" simply by requesting a ciphertext from the encryption oracle, modifying it somehow to obtain another, distinct valid ciphertext, and submitting it to the decryption oracle (which, if the adversary is indeed talking to the real oracles instead of the fake ones, would then successfully decrypt it).

In particular, since the SIV construction only directly verifies plaintext integrity, this implies that, for an SIV-style encryption scheme to be DAE secure according to Rogaway and Shrimpton's definition, the encryption layer must not allow the ciphertext to be modified in a way that leaves the plaintext unchanged.

Fortunately, CTR mode does satisfy this property (as indeed do all length-preserving classical encryption modes, such as OFB, CFB and even CBC with ciphertext stealing).  In particular, a simple counting argument shows that, for any encryption mode where the length of the ciphertext (excluding the IV!) equals the length of the plaintext, no two ciphertexts with the same IV can correspond to the same plaintext.  Thus, for these modes, verifying plaintext integrity is equivalent to verifying ciphertext integrity, assuming that the IV is unchanged.

What remains to be shown is that the adversary also cannot change the synthetic IV (possibly together with the ciphertext) in SIV mode in a way that would not be detected.

Indeed, for plain CTR mode, this would be trivial: given two CTR mode encrypted messages $m_1 = (iv_1, c_1)$ and $m_2 = (iv_2, c_2)$ of the same length, and the corresponding plaintexts $p_1$ and $p_2$, one can construct a new message $m' = (iv_1, c_1 \oplus p_1 \oplus p_2) \notin \{m_1, m_2\}$ that also decrypts to $p_2$.

However, in SIV mode, the IV also serves as the authentication tag for the plaintext.  Thus, in effect, it is not feasible for an adversary to find two plaintexts that would be valid for the same IV, and thus any modification attempts like the one described above will be detected.

Furthermore, the SIV construction requires that the (keyed) function used to derive the synthetic IV must be a PRF.  This is a significantly stronger requirement than merely requiring it to be a forgery-resistant MAC (or even a privacy-preserving one), and essentially requires that an adversary must not be able to find any valid IV / plaintext pairs other than those returned by the encryption oracle.  Thus, for any IVs other than those returned by the oracle, the adversary cannot produce any valid message; and for the IVs that the oracle does return, the adversary only has the single valid plaintext, and thus, due to the length-preserving encryption, only one valid ciphertext.

In short, the key properties that make the Encrypt-and-MAC construction in SIV mode provably DAE secure are that:


the encryption layer is length-preserving (and thus, for each IV, bijective),
the encryption layer IV also serves as the plaintext authentication tag, and
the function used to derive the IV from the plaintext is a PRF.


Ps. For further reading, you may also be interested in the following paper:


Namprempre, Rogaway and Shrimpton. "Reconsidering Generic Composition". Cryptology ePrint Archive, Report 2014/206, 2014.