MD5 Collisions on GPU's

In December 2008, an MD5 chosen-prefix collision attack was performed on a cluster of 215 PlayStation 3 consoles to create a rogue CA certificate. A new implementation of this attack has been researched and developed to run an order of magnitude faster and more efficiently on video card GPUs. This paper gives an overview of the GPGPU technology. It then describes the most computing intensive part of the MD5 chosen-prefix collision attack, known as birthdaying. Finally it demonstrates how a breakthrough performance gain can be achieved by carefully implementing the MD5 birthdaying stage on ATI R700 family GPUs (HD4000 series).