Breaking $H^2$-MAC Using Birthday Paradox

Fanbao Liu; Tao Xie; Changxiang Shen

Paper 2011/647

Breaking $H^2$-MAC Using Birthday Paradox

Fanbao Liu, Tao Xie, and Changxiang Shen

Abstract

$H^2$-MAC was proposed to increase efficiency over HMAC by omitting its outer key, and keep the advantage and security of HMAC at the same time. However, as pointed out by the designer, the security of $H^2$-MAC also depends on the secrecy of the intermediate value (the equivalent key) of the inner hashing. In this paper, we propose an efficient method to break $H^2$-MAC, by using a generalized birthday attack to recover the equivalent key, under the assumption that the underlying hash function is secure (weak collision resistance). We can successfully recover the equivalent key of $H^2$-MAC in about $2^{n/2}$ on-line MAC queries and $2^{n/2}$ off-line MAC computations with great probability. Moreover, we can improve the attack efficiency by reducing the on-line MAC queries, which can't be done concurrently. This attack shows that the security of $H^2$-MAC is totally dependent on the (weak) collision resistance of the underlying hash function, instead of the PRF-AX of the underlying compression function in the origin security proof of $H^2$-MAC.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): liufanbao @ gmail com
History: 2011-12-09: received
Short URL: https://ia.cr/2011/647
License: CC BY

BibTeX

@misc{cryptoeprint:2011/647,
      author = {Fanbao Liu and Tao Xie and Changxiang Shen},
      title = {Breaking $H^2$-{MAC} Using Birthday Paradox},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/647},
      year = {2011},
      url = {https://eprint.iacr.org/2011/647}
}