Re: [Cfrg] consequences of nonce reuse

[Ted Krovetz <tdk at acm.org>]

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

When

  tag  = prf(nonce) xor hash(m) and
  tag' = prf(nonce) xor hash(m'),

then any observer knows that tag xor tag' = hash(m) xor hash(m'). In  
other words, each time a nonce is reused, the adversary gets to know  
the difference between the hashes of two known messages (since tags  
and messages are often cleartext).

The definitions of universal hashing -- on which wegman-carter macs  
are based -- do not accommodate for this type of leak. One would have  
to develop universal hashing definitions conditioned on the adversary  
knowing some hash differences, and then functions used in wegman- 
carter macs would have to be re-proven in light of these new  
definitions.

For many hash functions, knowing hash differences likely makes it  
very easy to determine what hash key is in use. For example, simple  
polynomial hashing has enough mathematical structure that knowing a  
few differences could make it easy to determine the key in use.

It is probably best to accept that wegman-carter macs REQUIRE non- 
repeating nonces (and not insist on discussions in RFCs about the  
subtleties of this). If someone is able to prove that their wegman- 
carter mac can withstand repeated nonces, then they can point that  
fact out as special to their mac.

-Ted 

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