[Cryptography] Severe flaw in all generality : key or nonce reuse

[Jerry Leichter]

> 
>> I hate to ask silly questions, but is there any cryptosystem or any
>> mode whatsoever where key/nonce reuse is acceptable?
> 
> The interesting property would be that every bit in the encrypted
> message statistically depends on all bits in the key, the nonce, and the
> clear text message. Reusing the same key and nonce would only reveal
> something if it was used with exactly the same message, in which case it
> would just reveal that two messages were identical.
There are modes that do this - going back to Rivest's package transforms - and there are fairly natural definitions of security that end up, after analysis, requiring it. The problem, of course, is that such a mode cannot be on-line:  You have to have the entire plaintext available before you can emit a single bit of ciphertext (and perhaps the other way around as well, though I don't immediately see an argument for why that must be so).  In a world of multi-GB/sec streams of data some of them tens of GB long this is not workable.

An alternative is to work in blocks of some fixed length, with the property that ever bit of block i of the ciphertext depends on every bit of blocks 0 ... i of the plaintext.  There are modes like that, too.

This is discussed in the introduction to http://web.cs.ucdavis.edu/%7Erogaway/papers/oae.pdf

                                                        -- Jerry