10
$\begingroup$

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&M does not provide INT-CTXT. E&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?

$\endgroup$
  • $\begingroup$ By IV you mean the value named nonce in this image? $\endgroup$ – puzzlepalace Jun 14 '16 at 15:56
  • $\begingroup$ Yes and no. The IV is effectively a random nonce (up to the collision resistance of the PRF), but the entire thing is treated as the counter and incremented for each block, rather than concatenating a nonce with a separate counter. $\endgroup$ – Neil Madden Jun 14 '16 at 18:04
10
$\begingroup$

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:

  1. the encryption layer is length-preserving (and thus, for each IV, bijective),

  2. the encryption layer IV also serves as the plaintext authentication tag, and

  3. 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:

$\endgroup$
  • $\begingroup$ Thanks, that's exactly the level of detail I was after. I will read the links you provided. $\endgroup$ – Neil Madden Jun 15 '16 at 19:57
4
$\begingroup$

SIV is considered determanistic authenticated encryption because:

  • It is deterministic; given a key, a plaintext maps to a specific ciphertext; there is no randomness involved.

  • It is authenticated encryption; it provides privacy (that is, someone with a set of ciphertexts but without the key gets no information about the plaintexts, other than its length, and whether they're distinct), and integrity (that is, someone with a set of ciphertexts but without the key is unable (with high probability) to generate a new ciphertext that will not generate an error.

[Paraphrased] Isn't this just an Encrypt-and-MAC scheme?

Not precisely; with SIV, the MAC modifies how the encryption takes place (that is, it provides the IV). However, that's not the main point. The issue from the site you provided complains that you could design a secure encryption system with multiple ciphertexts for a single plaintext where you could modify one ciphertext into another; the easiest would be to include a bit in the ciphertext that the decryptor ignores. However, as you suggested, CTR mode doesn't have this property; any change to the ciphertext modifies the decrypted plaintext.

$\endgroup$
  • $\begingroup$ That's a good point about the MAC modifying the encryption via the IV. That is enough of a difference that this is not really "just" E&M, even if it's not clear to me how that would provide ciphertext integrity. In particular, does SIV provide anything beyond what E&M using CTR mode on its own provides? $\endgroup$ – Neil Madden Jun 14 '16 at 18:10
  • $\begingroup$ Thinking about this some more, I think I am placing too much emphasis on the MAC. Would you agree that E&M with CTR mode provides ciphertext integrity already and that the MAC in SIV is just a way to get determinism without reusing an IV/key pair (with high probability)? $\endgroup$ – Neil Madden Jun 14 '16 at 18:15
  • $\begingroup$ I'm making a real hash of these comments (pun intended)! Everywhere I've written MAC in the above comment read "using the MAC output as the IV". Obviously the MAC itself is essential to the CT integrity. $\endgroup$ – Neil Madden Jun 14 '16 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.