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

4

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

Melab

Posted 2018-01-02T21:55:44.170

Reputation: 1 413

Answers

5

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

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.

Luis Casillas

Posted 2018-01-02T21:55:44.170

Reputation: 9 317

That was a mighty interesting read; I'm however not sure if it directly answers the question. Maybe some kind of final wrap up would be in order. – Maarten Bodewes – 2018-01-04T08:59:37.073

2How do you understand the question? I took it to refer to the often-repeated statement that encrypt-then-MAC is the one composition of encryption and authentication, and the fact that SIV violates that seeming "rule," a question I once had myself. Looking at the title again, it does seem to have a "not" that I missed at first glance, but now that I notice that I just don't understand the question, other than to speculate that perhaps the "not" is extraneous. – Luis Casillas – 2018-01-04T20:18:55.343

OK, we both have different angles on this one it seems. I'll remove the comment. – Maarten Bodewes – 2018-01-04T20:33:08.933

Just noticed that I too missed the "not", probably because without it the question makes more sense. – otus – 2018-01-07T18:37:00.387

2

The main advantage of SIV over modes that came before it is its better resistance to nonce reuse1. 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.

1 SIV can also be used without a nonce, but then you only get deterministic encryption.

otus

Posted 2018-01-02T21:55:44.170

Reputation: 27 710

Why is it resistant to nonce reuse? – Melab – 2018-01-02T22:53:04.527

2@Melab, because the whole plaintext affects the encryption nonce. When used with a nonce input it degrades to still otherwise secure deterministic encryption when you reuse nonces, rather than being completely insecure like most modes. E.g. with CTR known plaintext allows decrypting all messages with the same nonce (up to that length) and with GCM you can make forgeries after seeing just one message pair with the same nonse. – otus – 2018-01-03T08:34:36.200

1SIV is obviously only partly resistant against nonce-reuse; you will still get the same ciphertext if you input the same AAD / plaintext. That will keep the message confidential, but it will leak information about the message. – Maarten Bodewes – 2018-01-04T09:27:57.253

@MaartenBodewes, it is not immune to nonce-reuse, but it is resistant. Or is that terminology wrong? Anyway, the more important (IMO) part is that SIV authentication is strong even with reuse, unlike e.g. GCM which fails catastrophically. – otus – 2018-01-04T13:46:58.093

1It's not good or wrong, it just requires additional explanation, as you do in above comment; you could possibly integrate it into he answer instead? – Maarten Bodewes – 2018-01-04T15:00:47.180

2

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.

Maarten Bodewes

Posted 2018-01-02T21:55:44.170

Reputation: 51 933

Isn’t a single pass SIV mode impossible, if every bit of the plaintext must be consumed to generate the nonce, which must be computed before the plaintext can be encrypted? – rmalayter – 2018-01-27T18:43:59.560