[Cfrg] consequences of nonce reuse

["Wei Dai" <weidai at weidai.com>]

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
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg