The breaking of the AR Hash Function

The AR hash function has been proposed by Algorithmic Research Ltd and is currently being used in practice in the German banking world. AR hash is based on DES and a variant of the CBC mode. It produces a 128 bit hash value.In this paper, we present two attacks on AR hash. The first one constructs in one DES encryption two messages with the same hash value. The second one finds, given an arbitrary message M, an M′ ≠ M with the same hash value as M. The attack is split into two parts, the first part needs about 233 DES encryptions and succeeds with probability 63%, the second part needs at most about 266 DES encryptions and succeeds with probability about 99% of the possible choices of keys in AR. Moreover, the 233 respectively 266 encryptions are necessary only in a one-time preprocessing phase, i.e. having done one of the attacks once with success, a new message can be attacked at the cost of no encryptions at all. Since the hash value is 128 bits long, the times for the attacks should be compared to 264, resp. 2128 DES encryptions for brute force attacks. For the particular keys chosen in AR hash we implemented the first part of the second attack. In 233 encryptions we found two messages that breaks AR hash.