2013 | OriginalPaper | Buchkapitel
New Generic Attacks against Hash-Based MACs
verfasst von : Gaëtan Leurent, Thomas Peyrin, Lei Wang
Erschienen in: Advances in Cryptology - ASIACRYPT 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we study the security of hash-based MAC algorithms (such as
HMAC
and
NMAC
) above the birthday bound. Up to the birthday bound,
HMAC
and
NMAC
are proven to be secure under reasonable assumptions on the hash function. On the other hand, if an
n
-bit MAC is built from a hash function with a
l
-bit state (
l
≥
n
), there is a well-known existential forgery attack with complexity 2
l
/2
. However, the remaining security after 2
l
/2
computations is not well understood. In particular it is widely assumed that if the underlying hash function is sound, then a generic universal forgery attack should require 2
n
computations and some distinguishing (
e.g.
distinguishing-H but not distinguishing-R) and state-recovery attacks should also require 2
l
computations (or 2
k
if
k
<
l
).
In this work, we show that above the birthday bound, hash-based MACs offer significantly less security than previously believed. Our main result is a generic distinguishing-H and state-recovery attack against hash-based MACs with a complexity of only
$\tilde O(2^{l/2})$
. In addition, we show a key-recovery attack with complexity
$\tilde O(2^{3l/4})$
against
HMAC
used with a hash functions with an internal checksum, such as
GOST
. This surprising result shows that the use of a checksum might actually weaken a hash function when used in a MAC. We stress that our attacks are generic, and they are in fact more efficient than some previous attacks proposed on MACs instanciated with concrete hash functions.
We use techniques similar to the cycle-detection technique proposed by Peyrin
et al.
at Asiacrypt 2012 to attack
HMAC
in the related-key model. However, our attacks works in the single-key model for both
HMAC
and
NMAC
, and without restriction on the key size.