Partial key recovery attack against RMAC

In this paper new “partial” key recovery attacks against the RMAC block cipher based Message Authentication Code scheme are described. That is we describe attacks that, in some cases, recover one of the two RMAC keys much more efficiently than previously described attacks. Although all attacks, but one, are of no major threat in practice, in some cases there is reason for concern.

In particular, the recovery of the second RMAC key (of k bits) may only require around 2k/2 block cipher operations (encryptions or decryptions). The RMAC implementation using triple DES proposed by NIST is shown to be very weak.