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

[Christian Huitema]

On 10/19/2017 6:43 AM, Jerry Leichter wrote:
>>> 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

Thanks for the pointer. As for the performance constraints, they
certainly are practical issues when the messages are long, but there are
applications in which messages are fairly short. Take for example IPSEC:
the unit of encryption is an IP packet, which in practice is at most
1500 bytes. TLS over TCP can have messages of up to 2^14 bytes, but when
using TLS with UDP for DTLS or QUIC, the message size is again at most
1500 bytes. 1500 bytes is not all that long. I also get the need to do
two passes, one to compute the message-dependent nonce and one to
perform the encryption. That's less memory efficient than the AES-GCM
pipelining, in which the result of encryption can be directly fed into
the checksum computation. But the number of operations would be about
the same, just reverse the order: perform a keyed hash to obtain the
nonce, then perform the encryption with the nonce as IV.

So this may well be worth a try, if there was a real security benefit.

-- 
Christian Huitema

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20171019/9947f684/attachment.html>