Badly implementing encryption: Part IX–SIV

I mentioned in a previous post that nonce reuse is a serious problem. It is enough to reuse a nonce even once and you can have catastrophic results at your hands. The problem occurs, interestingly enough, when we are able to capture two separate messages generated with the same key & nonce. If we capture the same message twice, that is not an issue (we can XOR the values, they will be all zeroes).

The question is whether there is something that can be done about this. The answer to that is yes, we can create a construction that would be safe from nonce reuse. This is called SIV mode (Syntactic IV).

The way to do that is to make the nonce itself depend on the value that we are encrypting. Take a look at the following code:

The idea is that we get a nonce, as usual, but instead of relying on the nonce, we’ll compute a hash of the plain text using the nonce as a key. Aside from that, the rest of the system behaves as usual. In particular, there are no changes to the decryption.

Let’s see what the results are, shall we?

With a separate nonce per use:

attack at dawn!	838E1CE1A64D97E114237DE161A544DA5030FC5ECAB1C2 0D34AF838634D1C591AE208FC0AEE706690669E9F56F45C1
attack at dusk!	EEA7DE8A51A06FE6CA9374CDDEC1053249F8B1F0BF1995A 0EEEE7D6EBF68868ECAE7CBEFD6EE23017480ACD494D634

Now, what happens when we use the same nonce?

attack at dusk!	0442EFA977919327C92B47C7F6A0CD617AE4FD3138DF07D4 5994EBC2C4B709ACDE1130422924B7206354D03569FDAA
attack at dawn!	324A996C22F7FFDE62596C0E9EE37D7EE1F89569A10A1188B A4A03EE7B8C47DF347A20D1B73EB4523D3511F2F46FF2

As you can see, the values are completely different, even though we used the same key and nonce and the plain text is mostly the same.

Because we are generating the actual nonce we use from the hash of the input, reusing the nonce with different data will result in a wildly different nonce being actually used. We are safe from the catastrophe that is nonce reuse.

With SIV mode, we are paying with an additional hashing pass over the plain text data. In return, we have the following guarantees:

• If the nonce isn’t reused, we have nothing to worry about.
• If the nonce is reused, an attacker will not be able to learn anything about the content of the message.
• However, an attacker may be able to detect that the same message is being sent, if the nonce is reused.

Given the cost of nonce reuse without SIV, it is gratifying to see that the worst case scenario for SIV with nonce reuse is that an adversary can detect duplicate messages.

I’m not sure how up to date this is, but this report shows that SIV adds about 1.5 – 2.2 cycles to the overall cost of encryption. Note that this is for actual viable implementations, instead of what I’m doing, which is by design, not a good idea.