Re: [Cfrg] consequences of nonce reuse

["D. J. Bernstein" <djb at cr.yp.to>]

The word "nonce" means "number used once." The standard example of a
nonce is a simple counter: 1, 2, 3, etc. For example, in an encrypted
TCP-like protocol, you can use 1 for the first packet, 2 for the second
packet, 3 for the third packet, etc.

Wei Dai writes:
> Considering nonce reuse is useful because guaranteeing the
> uniqueness of nonces has a cost.

What exactly is the cost that you're referring to? Do you think that the
encrypted-TCP server (or client) has trouble counting 1, 2, 3, ...?

Can anyone point to a verifiable real-world example of a cryptographic
application in which producing counters is more expensive than an
alternative method of achieving security? I don't mean a vague
description of a category of hypothetical applications; I want names of
real applications that achieve security at lower cost without counters
than they would be able to achieve with counters.

  [ assuming that the "nonce" isn't actually a nonce ]
> In contrast, a variant of VMAC-128 that uses tag=PRF(hash, nonce)
> would lose only 1 or 2 bits of security after 2^64 messages.

I find myself quite skeptical of this claim. I haven't looked at the
VMAC details, but I know many similar systems in which 2^64 messages are
likely to produce a hash collision, and in which knowledge of a hash
collision allows forgeries of other messages. (Certainly this is true
for the 128-bit Gilbert-MacWilliams-Sloane MACs that were tweaked to
produce UMAC and VMAC.) A 128-bit PRF(hash,constant) will have
collisions somewhat more often than the internal hash, but not enough to
seriously degrade the attack's success probability.

You might say that your PRF(hash,"nonce") isn't PRF(hash,constant), and
that your "nonces" aren't likely to collide when the hashes do, but if
you think that the nonce generator is too stupid to count 1, 2, 3, ...
then I don't see how you can "guarantee" anything about the frequency of
nonce collisions.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg