6
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Aug 10, 2014 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Thor
    Commented Aug 10, 2014 at 18:44
  • $\begingroup$ @Thor SIV actually comes a long way. It seems size efficient, but not very efficient with regards to CPU time. Thanks! $\endgroup$
    – Maarten Bodewes ♦
    Commented Aug 11, 2014 at 0:22
  • $\begingroup$ 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). $\;$ $\endgroup$
    – user991
    Commented Aug 11, 2014 at 5:21
  • 1
    $\begingroup$ Regarding CFB, cf. crypto.stackexchange.com/questions/5423/… $\endgroup$
    – otus
    Commented Aug 11, 2014 at 5:48

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Oh, cool, with a brand new paper linked too. $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 16, 2016 at 23:30
  • $\begingroup$ @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. $\endgroup$
    – SEJPM
    Commented Mar 16, 2016 at 23:31
  • $\begingroup$ 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! $\endgroup$
    – Maarten Bodewes ♦
    Commented Mar 16, 2016 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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