[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: No need for SHA-2 Packet Authentication - Open Letter to the WGand Area Directors




Two small corrections below. 

1) Some attacks on MAC algorithms DO depend on the length after truncation, 
but not as claimed: there is an attack that becomes more efficient 
(for a given hash function) if this length increases!

2) Moreover, there is indeed a birthday attack on HMAC (the proof  
by Bellare et al. stops at the birtday bound). It is not a realistic 
attack, but a key search for a 128-bit key is not realistic either.

This does not change the conclusion, but I believe that using incorrect
arguments to support the correct conclusion is not really helpful.

Bart Preneel
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven                       tel. +32 16 32 11 48
Dept. Electrical Engineering-ESAT / COSIC            fax. +32 16 32 19 69
Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, BELGIUM    

                           bart.preneel@esat.kuleuven.ac.be
                        http://www.esat.kuleuven.ac.be/~preneel
-------------------------------------------------------------------------------

On Wed, 17 Jul 2002, Russell Dietz wrote:

> First of all, the block size of SHA-256 (512 bits) is identical to that of
> SHA-1, so the first assertion in the quote above is simply false, although
> frankly it would have no relevance if true.  Second, there is no known
> reason why DRAFT-SHA-256 would in fact allow less frequent rekeying, using
> either 32-bit or 64-bit sequence numbers. Finally, and most importantly,
> while it is true that SHA-256 can output 256 bits, in the current draft the
> HMAC-SHA-256 output is in fact truncated to 96 bits, as is HMAC-SHA-1 in
> RFC2406.  For the HMAC-SHA-1-96 and DRAFT-SHA-256 algorithms, there is every
> reason to believe that the limiting factor in security is the number of bits
> of hash included in the packet, not the length before truncation.  The best
> attacks known on HMAC-SHA-1-96 and DRAFT-SHA-256 depend only on the length
> after truncation, not the length before truncation. Hence, the HMAC-SHA-1-96
> and DRAFT-SHA-256 have equivalent security against known attacks, and there
> seems to be little reason to prefer either one over the other, from a
> cryptographic perspective. For any given number of output bits, up to the
> SHA-1 limit of 160 bits, this would continue to be the case. If it was
> desired to have a MAC value longer than 160 bits, then the use of SHA-256
> would likely be appropriate, but there is no apparent need for such a MAC
> tag length, according to current knowledge.
> 
> [...]
> 
> However, while Figure 1 in FIPS 180-2 is correct for digital signatures, it
> has no direct relevance to the issue of packet authentication in ESP and AH
> as addressed in DRAFT-SHA-256. Packet authentication has a completely
> different attack model. In particular, there is no known feasible "birthday
> attack" problem in the packet authentication context, as has been shown by
> Krawczyk and others (e.g., "Keying Hash Functions for Message
> Authentication" by Bellare, Canetti, and Krawczyk, Crypto '96).
>
[...]

The best known attacks on any iterated MAC algorithm with a k-bit key,
an n-bit internal memory, and an m-bit result (some other conditions apply): 
  guess the MAC value: probability of success 2**-m
  find the key by exhaustive search: 2**k
  birthday attack [1]: 2**(n/2) text-MAC pairs and 2**(n-m+1) chosen texts

The best known attacks on HMAC-SHA-1-96:
  guess the MAC value: probability of success 2**-96
  find a 160-bit key by exhaustive search: 2**160 
  birthday attack [1]: 2**80 known text-MAC pairs and 2**65 chosen texts

It is safe to say that these attacks are infeasible or not relevant
for at least 15 years, so there is no need to upgrade.  

The best known attacks on DRAFT-SHA-256 with an m-bit result:
  guess the MAC: probability of success 2**-m
  find a 256-bit key by exhaustive search: 2**256
  birthday attack [1]: 2**128 text-MAC pairs and 2**(256-m+1) chosen texts

I believe that the following holds:
  * It is likely that better attacks than the above attack exist 
     for DRAFT-SHA-256.  Note that the complexities are huge. 
  * It is likely that DRAFT-SHA-256 is more secure than HMAC-SHA-1-96.
  * Both seem to offer a more than adequate security level (even if
     I would like to see more research on MAC-like properties of SHA-type
     hash functions). 

I agree that there is no cryptographic reason to upgrade. 

[1] B. Preneel, P.C. van Oorschot, "On the security of iterated Message
Authentication Codes," IEEE Transactions on Information Theory, 
Vol. 45, No. 1, January 1999, pp. 188-199. 

-------------------------------------------------------------------------------