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

From: "Whyte, William" <[email-masked]>
Date: Thu, 22 Apr 2004 12:36:32 -0400

> a) Are there any security advantages to truncating an (H)MAC value 
> (say to 96 bits), or is it just a performance advantage?  (I've seen
> arguments that not using all MAC bits hides something from some
> adversaries, is this so?) 

My understanding is that there is no significant security advantage
to truncating an HMAC, although the folklore has it that there is.
Consider messages A and B of the same length, such that the length 
is a multiple of the compression block size of the underlying hash 
function, and which produce the same MAC value M. Then an attacker 
can ask for the MAC on A || X, for any extension value X, and know 
that this will also be a MAC on B || X.

The argument that truncating is more secure goes as follows:
Say the internal chaining variable is of size k bits, and the
output MAC is also k bits. Then after 2^k/2 messages there will
be a collision, and the attacker will detect the collision by
noting that the MACs are the same.

However, if the output MAC is truncated to t bits, a collision
in the MAC no longer necessarily indicates an internal collision.
A MAC collision is necessary but not sufficient. The attacker
will have to observe 2^k/2 messages, which will result in roughly
2^(k-t) pairwise collisions, and then make an extended-message 
query for each of those collisions. More work for the attacker
==> truncated MACs are more secure. (You can also argue that
the attacker will send the victim 2^(k-t) messages, of which only
one will be accepted, and that this will alert the victim to the
fact that an attack's going on).

I think that represents the "more secure" argument fairly, but
it also shows why I don't really believe in it. There's an amount 
of additional work to be done by the attacker if the MAC is truncated.
However, it never increases the total number of queries to the MAC
oracle by a factor of more than 2. And the argument that a large number 
of fake MACs will alert the victim makes an assumption about the
behaviour of the victim, which I don't think we can rely on. 

In summary: if the internal chaining value is of size k bits, I
don't know of significant security advantages or disadvantages
to truncating the MAC to any length between k and k/2.

Cheers,

William (willing to be corrected...)

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

---

From: [email-masked] (David Wagner)
Date: Thu, 22 Apr 2004 18:31:44 +0000 (UTC)

Whyte, William wrote:
>it also shows why I don't really believe in it. [...]

For whatever it's worth, I agree with you.
I don't see any security advantages or disadvantages to truncating.
(There may well be performance advantages to truncation, of course.)