Subject: [Cfrg] consequences of nonce reuse

From: "Wei Dai" <[email-masked]>
Date: Wed, 3 Jan 2007 04:08:31 +0800

I'd like to request that designers of nonce-based crypto schemes include an
analysis of the security consequences of nonce reused when proposing their
schemes. Considering nonce reuse is useful because guaranteeing the
uniqueness of nonces has a cost. If nonces are derived from state
information, that information is subject to corruption, memory loss,
desynchronization, etc. If nonces comes from a random source, they are
subject to collisions which limit the number of messages that can use the
same key. If the consequences of nonce reuse are published, the designer or
user of a protocol can choose a scheme that is less efficient but more
tolerant of nonce reuse when the cost of enforcing nonce uniqueness is
higher than the cost of the extra computations of the less efficient scheme.

As a motivating example, consider one of the differences between UMAC (1999
version) and VMAC. UMAC introduced the tag=PRF(hash, nonce) construction,
whereas VMAC returned to the older tag=hash xor PRF(nonce). (Actually this
change was already made in the 2000 version of UMAC , but I'll use VMAC in
the example for clarity. All subsequent mentions of UMAC refer to the 1999
version.)

While both designs state that nonces should be unique, UMAC is actually much
more tolerant of nonce reuse than VMAC but this property is not mentioned
anywhere as far as I know. The designers of UMAC state that if tag=PRF(hash)
had been used (i.e., if the scheme didn't use a nonce at all), its security
would decrease by a factor of q^2 where q is the number of messages
authenticated by the same key. So I think it's safe to conjecture that with
tag=PRF(hash, nonce), the security of UMAC only decreases by a factor of n^2
when some nonces are reused, where n is the number of messages not using
unique nonces. On the other hand, VMAC's security breaks completely as soon
as a single nonce is reused.

VMAC-128 is designed to have 120-bit security when unique nonces are used.
But with random nonces, we can expect a nonce collision (and therefore 0-bit
security) after only 2^64 messages (since the nonces are at most 128 bits
long). Similarly it has only 64-bit security after 2^32 messages with random
nonces. 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'll mention that tag=hash xor PRF(nonce) is more efficient, especially
noticeable for short messages, and in general tolerance for nonce reuse
probably has an efficiency cost, so I only ask that the consequences of
nonce reuse be considered and published to give users a choice.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Russ Housley <[email-masked]>
Date: Tue, 02 Jan 2007 15:24:14 -0500

I think that CCM (see RFC 3610) has the analysis you are 
requesting.  Do you think that something different is needed?

Russ

At 03:08 PM 1/2/2007, Wei Dai wrote:
>I'd like to request that designers of nonce-based crypto schemes 
>include an analysis of the security consequences of nonce reused 
>when proposing their schemes. Considering nonce reuse is useful 
>because guaranteeing the uniqueness of nonces has a cost. If nonces 
>are derived from state information, that information is subject to 
>corruption, memory loss, desynchronization, etc. If nonces comes 
>from a random source, they are subject to collisions which limit the 
>number of messages that can use the same key. If the consequences of 
>nonce reuse are published, the designer or user of a protocol can 
>choose a scheme that is less efficient but more tolerant of nonce 
>reuse when the cost of enforcing nonce uniqueness is higher than the 
>cost of the extra computations of the less efficient scheme.
>
>As a motivating example, consider one of the differences between 
>UMAC (1999 version) and VMAC. UMAC introduced the tag=PRF(hash, 
>nonce) construction, whereas VMAC returned to the older tag=hash xor 
>PRF(nonce). (Actually this change was already made in the 2000 
>version of UMAC , but I'll use VMAC in the example for clarity. All 
>subsequent mentions of UMAC refer to the 1999 version.)
>
>While both designs state that nonces should be unique, UMAC is 
>actually much more tolerant of nonce reuse than VMAC but this 
>property is not mentioned anywhere as far as I know. The designers 
>of UMAC state that if tag=PRF(hash) had been used ( i.e., if the 
>scheme didn't use a nonce at all), its security would decrease by a 
>factor of q^2 where q is the number of messages authenticated by the 
>same key. So I think it's safe to conjecture that with tag=PRF(hash, 
>nonce), the security of UMAC only decreases by a factor of n^2 when 
>some nonces are reused, where n is the number of messages not using 
>unique nonces. On the other hand, VMAC's security breaks completely 
>as soon as a single nonce is reused.
>
>VMAC-128 is designed to have 120-bit security when unique nonces are 
>used. But with random nonces, we can expect a nonce collision (and 
>therefore 0-bit security) after only 2^64 messages (since the nonces 
>are at most 128 bits long). Similarly it has only 64-bit security 
>after 2^32 messages with random nonces. 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'll mention that tag=hash xor PRF(nonce) is more efficient, 
>especially noticeable for short messages, and in general tolerance 
>for nonce reuse probably has an efficiency cost, so I only ask that 
>the consequences of nonce reuse be considered and published to give 
>users a choice.
>

---

From: "Wei Dai" <[email-masked]>
Date: Wed, 3 Jan 2007 05:24:13 +0800

> requesting.  Do you think that something different is needed?

Yes, this is another good example of the current situation that I'd like to
see improved. The analysis in the RFC (unless it's somewhere else that I've
skipped over) simply says:

Using the same nonce for two different messages
encrypted with the same key destroys the security properties of
this mode.

I'd like to know more about what actually happens when a nonce is reused.
For example, does it a) weaken the security bound by some factor? b)
immediately allow an attacker to obtain the XOR of two messages that used
the same nonce? or c) allow an attacker to recover the entire key or
otherwise decrypt arbitrary messages?
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 03 Jan 2007 16:32:54 +1300

"Wei Dai" <[email-masked]> writes:

>schemes. 

Seconded.  In addition designers should make clear whether a nonce should be:

- Nonrepeating (so a counter will do).
- High-entropy (a hash of the counter will do).
- Unpredictable (requiring a truly random value).

(note the order of increasing requirements on the nonce generation).  This
lack of detail has historically caused problems in a number of
implementations, for example in SSL the session ID is (according to the spec)
required to fit into the "unpredictable" category, so many (probably almost
all) implementations feed 32 bytes of output from their crypto RNG to an
attacker in cleartext on every handshake.  In fact all that's required is that
it's in the "nonrepeating" category.

Peter.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 4 Jan 2007 15:31:42 -0000

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)

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

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 4 Jan 2007 11:48:49 -0500

On 4 Jan 2007 15:31:42 -0000
"D. J. Bernstein" <[email-masked]> wrote:

> 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.
> 

The cost is being able to maintain state across reboots or power cycle
events.  This was one (of many) problems with WEP -- one reason that
the so-called IVs are reused so often is that many implementations use
counters and restart them from zero.  See Section 3 of Borisov,
Goldberg, and Wagner's paper on 802.11 insecurity; they mention
(though not by product name) that specific implementations do this.
(WEP IVs would repeat in any event, because they're 24 bits long, but
even a 64-bit IV would be problematic if the counter always started
from 0.)

There are analogous non-security issues with regard to the TCP sequence
number; see the text on "TCP Quiet Time" in RFC 793.

		--Steve Bellovin, http://www.cs.columbia.edu/~smb

---

From: "Wei Dai" <[email-masked]>
Date: Sun, 7 Jan 2007 15:04:39 +0800

> encrypted-TCP server (or client) has trouble counting 1, 2, 3, ...?

If you want to maintain a count across reboots, you have to write the
counter to disk. Then you'd have to worry about file system security,
detecting when the disk might have been restored from an earlier backup,
etc. I'd bet there are very few applications that do this securely. Most
applications that use counters probably don't bother to save them, and
instead, upon reboot either set their counters to random values or discard
all shared symmetric keys and re-establish them (in which case random nonces
are probably used as part of of the key agreement protocols).

Besides reboots, we now also have the possibility of our software running
inside virtual machines (e.g. VMware), where even volatile memory can be
rolled back to earlier checkpoints.

> then I don't see how you can "guarantee" anything about the frequency of

Perhaps from a theoretical perspective generating random numbers is much
harder than counting, but from a practical perspective, in many situations
random number generation is a solved problem whereas counting isn't. Modern
operating systems provide facilities to easily generate random numbers of
cryptographic quality. I think the above discussion implies that OS support
is also needed to easily maintain a count of cryptographic quality, but this
support isn't available yet.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "Marshall Eubanks" <[email-masked]>
Date: Sun, 7 Jan 2007 05:50:15 -0500

In the light of this discussion, wouldn't it make sense to require
that a NONCE used in a cryptographic context be either

- a counter concatenated  or hashed with a random number or
- a counter that is always reset to a random value, or
- a random number itself ?

While random number generation in a computer may have its problems, in
this case, the only goal is to make the probability of reuse very
small, which it should be possible to achieve.

Regards
Marshall Eubanks

---

From: Adam Back <[email-masked]>
Date: Sun, 7 Jan 2007 06:54:14 -0500

Problem is random numbers are subject to re-use faster than counters
due to the birthday principle.  (Probability of collision > 0.5 after
2^n/2 for n-bit counter).  Whereas a counter has a probability of
collision of exactly 1 after 2^n; and 2^n/2 is much bigger smaller
than 2^n.

Also with a counter and a permutation (block cipher), if you have a
counter that is the same size as a block cipher you can assure no
collision even though seeing random output.  You can distinguish it
from random output with increasing confidence after 2^n/2 outputs due
to the absense of collisions, but if the point is to avoid collisions
it is preferable and distinguishing from random output is not
relevant.

A counter reset to a random value rather than starting at 0 again will
actually collide 2x as quickly on average.

So I think the sensible thing to do is either:

- use a counter and change the key after counter-wrap (or after loss
of counter state)

  - optionally encrypt the counter with a block cipher (if the nonce
    size is equal to the block cipher size)

- or use a random value for few enough times per key such that
  probability of collision is acceptably low (relative to your
  security margin, and the severity of the consequences of
  nonce-reuse)

- and consider also the probability of key re-use if frequently
re-keying (in some protocols scenarios you might think re-keying every
message would be an alternative to ensuring nonces are really used
once)

Adam

---

From: "Marshall Eubanks" <[email-masked]>
Date: Sun, 7 Jan 2007 08:38:04 -0500

Hello;

> collision of exactly 1 after 2^n; and 2^n/2 is much bigger smaller

But if your counter is set to 1 after every reboot, then the
probability of a collision is
much higher than 1 / 2^n-1 - it's more like the birthday problem in a port where
all of the men are always at sea, except for the New Year's holidays.

>   security margin, and the severity of the consequences of

I like both of these ideas.

> message would be an alternative to ensuring nonces are really used

Regards
Marshall

---

From: Russ Housley <[email-masked]>
Date: Mon, 08 Jan 2007 10:45:12 -0500

Marshall:

There are several instances where nonces are counters that start with 
zero.  This allows the same value to provide the cryptographic 
protection and to provide replay detection.  This is the use in IEEE 
802.11i, where a fresh key is established with each new 802.11 
association, preventing the concerns discussed on this thread.

Russ