Why is SIV a thing if MAC-and-encrypt is not the most secure way to go?

Question

The question that I am asking is exactly what I ask in the title.

Answer 1

Skimming these three papers should give you an idea (which I list roughly in the order I recommend you look at them):

• Rogaway, Philip. 2004. "Nonce-based symmetric encryption."
• Namprempre, Chanathip, Phillip Rogaway and Thomas Shrimpton. 2014. "Reconsidering Generic Composition."
• Bellare, Mihir and Chanathip Namprempre. 2000. "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm"

To make a long story short, results about generic composition of encryption and authentication are very sensitive to how you define the concept of "encryption." In a classic textbook definition, encryption schemes are defined in terms of probabilistic algorithms. As the Rogaway paper puts it:

Ever since Goldwasser and Micali’s landmark paper [7], formalizations of encryption schemes have usually made the encryption algorithm probabilistic or stateful. In this paper we investigate a different formalization for symmetric encryption: the encryption algorithm is made to be a deterministic function, but one of its argument is a user-supplied initialization vector (IV). Effectively, the user and not the encryption algorithm is made responsible for flipping coins or maintaining state.

The Bellare and Namprempre's famous result that encrypt-then-MAC is the only secure composition uses the classic, probabilistic framework for encryption. But if you start from Rogaway's IV- or nonce-based definitions, as the 2014 Namprempre et al paper does, you get more nuanced results. Some but not all versions of MAC-and-encrypt—including SIV—turn out to be secure, whereas all versions of encrypt-then-MAC are secure. As the paper puts it:

One might interpret our results as saying that the conventional wisdom—that Encrypt-then-MAC is the only safe GC method—is wrong, an artifact of early work having admitted sloppy schemes and considered only pE+MAC → pAE conversion. An alternative interpretation is that the conventional wisdom is essentially right, that Encrypt-then-MAC is the only safe GC method, for it works across multiple definitional settings, whereas the story becomes nuanced for other GC schemes.

Nothing in this paper should be understood as suggesting that there is anything wrong with BN. If that paper has been misconstrued, it was not for a lack of clarity. Our definitions and results are complementary.

Answer 2

The main advantage of SIV over modes that came before it is its better resistance to nonce reuse¹. While using the same nonce it becomes deterministic (allowing an attacker to see if two messages are equal), but otherwise retains its security – including the security of authentication which in many other systems is lost completely. E.g. AES-GCM authentication allows forgeries after just one nonce reuse.

SIV is not encrypt-then-MAC, but closer to encrypt-and-MAC. However, the potential problems with encrypt-and-MAC do not apply to SIV because it uses a PRF (rather than a weaker MAC) and an encryption system with some further restrictions as well.

_{¹ SIV can also be used without a nonce, but then you only get deterministic encryption.}

Answer 3

With SIV it is not required to use a nonce at all. That is: the uniqueness that is required to make the deterministic SIV scheme secure must reside in the plaintext or additional authenticated data. From this uniqueness an authentication tag is constructed that doubles as authentication tag (which is required to have similar properties). This makes it different from all indeterministic schemes, including those based on encrypt-then-MAC.

This makes SIV especially useful for key wrapping; a key will always have some kind of uniqueness to it, as it contains a large amount of entropy. So as long as you remember that an adversary can distinguish copies, the algorithm is secure even without IV. That means that the nonce doesn't need to be generated; no additional RNG or counter required. The nonce or counter state doesn't need to be stored either.

If SIV is considered secure then the fact that encrypt-and-MAC is considered not-the-best is of course not a problem anymore. As long as this specific AEAD scheme is secure that isn't an issue. The answer of Luis Casillas dives deeper into the security arguments of SIV-mode.

---

You can and should of course still use SIV with some kind of explicit nonce if you expect that your plaintext can repeat. Otherwise you will get the same ciphertext and break CPA security.

---

[somewhat off topic discussion of SIV]

The necessary inclusion of the authentication tag in the ciphertext will still expand the ciphertext: something that is detrimental to the usability of the scheme. The fact that it is placed at the front unfortunately doesn't help either as it doesn't allow for in-place encryption and specifying where the authentication tag resides was a mistake, in my opinion.

Of course, this does come at a price; SIV is a full two-pass AEAD scheme that requires two keys (and sorry, no, just concatenating the keys doesn't hide this fact at all). SIV could do with an update and if anybody is looking for a good paper to write: one that specifies a single or 1/2 pass SIV mode (i.e. deterministic authenticated encryption with associated data) with a single key and separate authentication tag would be nice.