SECURITY ANALYSIS OF THE MESSAGE AUTHENTICATOR ALGORITHM (MAA)

The security of the ISO banking standard Message Authenticator Algorit hm (ISO 8731-2), also known as MAA, is considered. The attacks present ed herein, which exploit the internal structure of the algorithm, are the first computationally feasible attacks on MAA. First a MAC forgery attack is presented that requires 2(17) messages of 256 kbytes or 2(2 4) messages of 1 kbyte; the latter circumvents the special MAA mode fo r long messages defined in the standard. Next a key recovery attack on MAA is described which requires 2(32) chosen texts consisting of a si ngle message block. The number of off-line multiplications for this at tack varies between 2(44) for one key in 1000 to about 2(51) for one k ey in 50. This should be compared to about 3 . 2(65) multiplications f or an exhaustive key search. Finally it is shown that MAA has 2(33) ke ys for which it is rather easy to create a large cluster of collisions . These keys can be detected and recovered with 2(27) chosen texts. Fr om these attacks follows the identification of several classes of weak keys for MAA.