On the security of two MAC algorithms

The security of two message authentication code (MAC) al- gorithms is considered: the MD5-based envelope method (RFC 1828), and the banking standard MAA (ISO 8731-2). Customization of a general MAC forgery attack allows improvements in both cases. For the envelope method, the forgery attack is extended to allow key recovery; for example, a 128-bit key can be recovered using 267 known text-MAC pairs and time plus 213 chosen texts. For MAA, internal collisions are found with fewer and shorter messages than previously by exploiting the algorithm’s internal structure; consequently, the number of chosen texts (each 256 Kbyte long) for a forgery can be reduced by two orders of mag- nitude, e.g. from 224 to 217. This attack can be extended to one requiring only short messages (224 messages shorter than 1 Kbyte) to circumvent the special MAA mode for long messages. Moreover, certain internal collisions allow key recovery, and weak keys for MAA are identified