[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: 32 bit counter -- 96 bit HMAC-SHA/MD5
TRUNCATION of HMAC output: I support Hugo's suggestion
to go for 96 bits, but would suggest myself to even go
to 64 bits (MD5) or 80 bits (SHA-1).
parameters:
- size of key: k bits
- size of result: m bits
- size of internal memory: n bits
128 for MD5, 160 bits for SHA-1 and RIPEMD-160)
[what is RIPEMD-160? a European alternative for SHA-1
see http://www.esat.kuleuven.ac.be/~bosselae ]
We know of the following three attacks against HMAC
(there might be others, but that makes life interesting):
1. Guess the value of the MAC
Probability of success 2^{-m}.
Even for messages of high value, 64 bits is more than sufficient
for the next 10 to 15 years. 80 or 96 bits gives an ample safety
margin.
2. Brute force exhaustive key search
Needs about k/m known text-MAC pairs.
Work factor 2^{k-1}.
The work factor is essentially independent of m.
(this should answer Steve's question of Fri, 14 Feb 1997 16:53:30 -0500)
(same story as for exhaustive key search for encryption --
the difference is that the life time of a key is almost irrelevant -
only the lifetime of the system itself is relevant).
80 bits is ok for midterm, 128 bits is ok for 20 years or more.
3. Shortcut forgery attack
Needs 2^{n/2} known text-MAC pairs and 2^{n-m}$ chosen texts.
This attack becomes even more unrealistic if shortening is
applied (m < n), because then the number of chosen text increases.
The main problem is: other attacks.
If algorithm dependent attacks are ever found (extending Dobbertin's
results to MACs), they are affected by m as follows:
a. shortcut forgery attacks (IMHO not very probable):
reducing m might make the scheme weaker
b. shortcut key recovery attacks will become more difficult if
less information is given away -- fewer bits of the MAC
(I believe that this is a more likely scenario).
Also note that key recovery attacks are more serious than forgery attacks
anyway.
> Date: 14 Feb 1997 15:35:11 -0500
> From: Derek Atkins <warlord@MIT.EDU>
> To: HUGO@watson.ibm.com
> Cc: IPSEC@tis.com
> Subject: Re: 32 bit counter -- 96 bit HMAC-SHA/MD5
> I'd be afraid that truncating to 96 bits would make brute-force
> attacks too easy. We've already seen 48 bit RC5 keys falling in very
> short amounts of time (hours) using brute-force methods. Today.
> These MACs need to be secure for YEARS! I don't think that a 96-bit
> MAC is long-enough to survive brute-force attacks for very long.
> I'd be much happier with the extra 32-bits, keeping the MAC at 128.
> -derek
I am not aware of any brute force attack on a MAC which runs
in time 2^{m/2} (a MAC is not an unkeyed hash function).
If you know of such an attack, let me know asap.
> Date: Fri, 14 Feb 1997 16:35:35 -0500
> From: "Theodore Y. Ts'o" <tytso@MIT.EDU>
> To: Derek Atkins <warlord@MIT.EDU>
> Cc: HUGO@watson.ibm.com, IPSEC@tis.com
> Subject: Re: 32 bit counter -- 96 bit HMAC-SHA/MD5
>
> Derek,
> I'm not a cryptographer, so take my comments with a grain of
> salt, but my understanding is that MAC's, unlike cryptographic
> checksums, aren't subject to birthday attacks, since key used to
> generate the MAC is secret. Hence, HMAC truncated to 64 bits has an
> attack difficulty of O(2**64), and HMAC truncated to 96 bits has an
> attack difficulty of O(2**98), NOT O(2**48).
>
> - Ted
I try to be a cryptographer, and I would say
MD5 (with 128-bit key)
64 bits: 2^{128} off-line for key recovery
2^{64} known and 2^{64} chosen texts for forgery
2^{64} for guessing a MAC
96 bits: 2^{128} off-line for key recovery
2^{64} known and 2^{32} chosen texts for forgery
2^{96} for guessing a MAC
SHA-1 (with 128-bit key)
64 bits: 2^{128} off-line for key recovery
2^{80} known and 2^{96} chosen texts for forgery
2^{64} for guessing a MAC
96 bits: 2^{128} off-line for key recovery
2^{80} known and 2^{64} chosen texts for forgery
2^{96} for guessing a MAC
These are the best attacks we know of today.
Given the collision attacks on the compression function of MD5,
it seems realistic to expect that a key recovery is probably
easier than 2^{128} on the MD5 version (I have no attack yet).
But decreasing m would only help against such an attack.
Bart Preneel
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven tel. +32 16 32 11 48
Dept. Electrical Engineering-ESAT / COSIC fax. +32 16 32 19 86
K. Mercierlaan 94, B-3001 Heverlee, BELGIUM bart.preneel@esat.kuleuven.ac.be
-------------------------------------------------------------------------------
References: