Efficient many-core architecture design for cryptanalytic collision search on FPGAs

Abstract Algorithms for collision search in finite sets are a key tool for security assessment of modern real world crypto-systems. Two notable applications of collision search are the Pollard rho algorithm to solve the elliptic curve discrete logarithm problem (ECDLP) and the birthday search for finding collisions of cryptographic hash functions like MD5 and SHA1. The ability to design and implement efficient hardware architectures for such algorithms can have a significant impact on the practical security of a variety of crypto-systems submitted in the real world. We present a general many-core architecture and an optimization methodology thereof, for cryptanalytic collision search on Field Programmable Gate Arrays (FPGAs). We use such architecture for two relevant case studies, i.e., (i) the Pollard rho algorithm to solve the ECDLP for security assessment of elliptic curve cryptography (ECC), and (ii) the birthday search algorithm to find chosen-prefix collisions for security assessment of the MD5 cryptographic hash function.