# Streaming mode of operation that is more resistant against nonce reuse

Is it possible to create a streaming mode of operation where the reuse of a nonce does not destroy confidentiality?

In this question it would be allowed for the streaming mode to leak if ciphertexts are (partially) identical or not - like in CBC mode of operation. It is of course not permitted to introduce other secrets or random values other than the key and original nonce.

I've got the feeling that this is only possible by mixing in information from the plaintext, but that would make the cipher much less efficient.

• A blockcipher in CFB mode only leaks the xor of the first block that differs and not the xor of the whole message. I think keccak's duplex mode has similar properties. – CodesInChaos Aug 10 '14 at 18:19
• The SIV mode (Synthetic IV) is designed as misuse resistant, but it requires the plaintext to be processed twice. So probably not what you are looking for. – Thor Aug 10 '14 at 18:44
• @Thor SIV actually comes a long way. It seems size efficient, but not very efficient with regards to CPU time. Thanks! – Maarten Bodewes Aug 11 '14 at 0:22
• When I thought about this before, the candidate that I came up with was letting each block's key be the result of applying a PRF to the previous block (starting with the IV). $\;$ – user991 Aug 11 '14 at 5:21
• Regarding CFB, cf. crypto.stackexchange.com/questions/5423/… – otus Aug 11 '14 at 5:48

For my answer I'll distinguish two cases: a) By "streaming" you mean "online" and b) by "streaming" you mean "can encrypt arbitrarily sized messages". See the CAESAR survey paper for the notions I use here.

There can be no fully nonce-misuse resistant online authenticated encryption scheme, i.e. a scheme where the only information leaked upon nonce reuse is whether two messages are identical. However, there's a weaker notion of nonce misuse resistance that allows the "longest common prefix of the messages" to be leaked. I think this notion may be sufficient to you.

The survey paper I linked above lists some candidate constructions for this property and may be more up-to-date than this answer (especially if the round three candidates are already in).

If you are willing to allow offline schemes (i.e. schemes that need at least some information about the complete message before being able to output cipher texts), then you're lucky. It is possible for those schemes to achieve the strong nonce misuse resistance. The most recent and most efficient example I've seen in this category (with full security proofs) being GCM-SIV by Gueron and Lindell.

• Oh, cool, with a brand new paper linked too. – Maarten Bodewes Mar 16 '16 at 23:30
• @MaartenBodewes "brand new" is relative, the original GCM-SIV seems to have appeared in early 2015 (notice the low IACR number?) and it was updated every now and then and I think most recently because the authors are asking for standardization by CFRG. – SEJPM Mar 16 '16 at 23:31
• Interesting paper none-the-less. Don't ask me to repeat the security proof though, that's still too fresh. My question still predates the paper :P Thanks for spellunking to this old question! – Maarten Bodewes Mar 16 '16 at 23:40