Subject: RE: [Cfrg] MACs: to truncate or not to truncate?

From: "Whyte, William" <[email-masked]>
Date: Mon, 26 Apr 2004 15:13:04 -0400

Hi Dan,

> William's attack on HMAC-SHA1-160 uses only 2^80 MAC generation queries
> to find a MAC forgery, right? If so,  does HMAC-SHA1-160 have at most
> "80-bit security"?  Or, can we use a different "exchange rate" for
> online queries, so that the 2^80 MAC generation queries are regarded as
> a "160-bit" cost in the attack? 

> The security level of HMAC-SHA1 may well depend on the "exchange rate"
> between off-line and on-line work (as well as MAC generation vs
> verification queries, and treatment of failed verifications), but
> wouldn't a conservative, and maybe "oversimplified", answer would take
> the worst security rating over all exchange rates?  I agree that a more
> aggressive rating could be used with application-specific detailed
> threat analysis. 

I'd say that it's reasonable under certain circumstances to
assume a different (and higher) cost for MAC generation queries 
than for offline queries. But I'd always treat MAC verification 
queries as essentially free -- the sender has no guaratee over
how the receiver will treat a failed message.

The most conservative estimate of security might cap the
strength at 80 bits. I think if it can be guaranteed that
key lifetime will be less than a certain amount, the
security can be considered higher. For example, if key 
lifetime is 2^16 messages, there's only a (roughly) 2^-128 
chance of an internal collision. It seems reasonable to
use HMAC-SHA1-128 or HMAC-SHA1-160 for 128-bit security
under these circumstances.

> Has anybody ever formally studied the security of HMAC-SHA1-80 vs
> HMAC-SHA1-160, or is it just "folklore" that one is better than, as
> good as, or worse than the other? 

I have a memory of seeing this addressed somewhere -- I
thought by Bellare and Rogaway, but I can't track it
down. There's surprisingly little discussion of the
effect of truncation in the literature.

> Anyway, am I right to infer that "80-bit security" is the most
> conservative rating for both HMAC-SHA1-80 and HMAC-SHA1-160? 
> What's the most conservative rating for HMAC-SHA1-96 or HMAC-SHA1-128?
> What are the ratings under other "reasonable", but more aggressive,
> exchange rates? Is there a simple characterization of some useful
> situations when these more aggressive ratings are safe to use (instead
> of going through an analysis for every application)? 

80-bit security is the most conservative rating for all of them.
For 96-bit or 128-bit MACs, the attacker has to make attempts
to get a MAC accepted that are unlikely to succeed, but he
never has to make more than 2^80 of them.

> So, the suggestions on this mailing list to a 32-bit MAC for per-packet
> protection may be inappropriate if the packet payloads are encrypted,
> but may be fine if the packets are plaintext? 

Interesting take on it. In either case, the attacker
wants to have a forged packet be accepted, and the chance
of this happening is (essentially) 2^-32. If the encryption
scheme is CBC-pad + 32-bit MAC, and if the decrypting side
throws an error that distinguishes between MAC failure and
unpadding failure (as in Vaudenay's Eurocrypt attack,
http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Vau02a),
then the attacker can mount Vaudenay's attack, at 2^32 times
more effort than the raw attack would take, and the short MAC 
compromises confidentiality. So, yes, in certain circumstances
a short MAC seems less suited to encrypted packets than to
plaintext packets. But my feeling is that this is simply
an illustration of the risks of short MACs, rather than
a difference in the requirements of plaintexts and ciphertexts.
Say you had nuclear launch codes unencrypted, but 
authenticated with a 32-bit MAC, for instance... I
think short MACs are pretty scary full stop.

Cheers,

William

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg