Highly Parallel Cryptographic Attacks

We report on a large-scale statistical evaluation of pseudorandom properties of certain cryptographic functions such as DEs and md5. The evaluation is based on the well-known birthday attack. The attack requires large amounts of memory. We describe a parallel algorithm which can exploit the large amounts of secondary memory (local disks) available on many workstation clusters and parallel machines. The overheads due to communication and disk accesses can be minimized by techniques similar to those used in parallel data bases for parallel external sorting. We have implemented the algorithm using the message passing interface MPI. We display performance measurements on an IBM SP2 which show that the costs for communication and disk accesses are negligible.