Updates on Generic Attacks against HMAC and NMAC

摘要

In this paper, we present new generic attacks against HMAC and other similar MACs when instantiated with an n-bit output hash function maintaining a l-bit internal state. Firstly, we describe two types of selective forgery attacks (a forgery for which the adversary commits on the forged message beforehand). The first type is a tight attack which requires O(2~(l/2)) computations, while the second one requires O(2~(2l/3)) computations, but offers much more freedom degrees in the choice of the committed message. Secondly, we propose an improved universal forgery attack which significantly reduces the complexity of the best known attack from O(2~(5l/6)) to O(2~(3l/4)). Finally, we describe the very first time-memory tradeoff for key recovery attack on HMAC. With O(2~l) precomputation, the internal key K_(out) is firstly recovered with O(2~(2l/3)) computations by exploiting the Hellman's time-memory tradeoff, and then the other internal key K_(in) is recovered with O(2~(3l/4)) computations by a novel approach. This tends to indicate an inefficiency in using long keys for HMAC.