An Experimentally Verified Attack on Full Grain-128 Using Dedicated Reconfigurable Hardware

Itai Dinur, Tim Güneysu, Chris­tof Paar, Adi Shamir, Ralf Zimmermann

Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011


In this paper we describe the fi rst single-key attack which can recover the full key of the full version of Grain-128 for arbitrary keys by an algorithm which is signi cantly faster than exhaustive search (by a factor of about 2^38). It is based on a new version of a cube tester, which uses an improved choice of dynamic variables to eliminate the previously made assumption that ten particular key bits are zero. In addition, the new attack is much faster than the previous weak-key attack, and has a simpler key recovery process. Since it is extremely di cult to mathematically analyze the expected behavior of such attacks, we implemented it on RIVYERA, which is a new massively parallel recon gurable hardware, and tested its main components for dozens of random keys. These tests experimentally veri ed the correctness and expected complexity of the attack, by finding a very signi cant bias in our new cube tester for about 7.5% of the keys we tested. This is the fi rst time that the main components of a complex analytical attack are successfully realized against a full-size cipher with a special-purpose machine. Moreover, it is also the fi rst attack that truly exploits the con gurable nature of an FPGA-based cryptanalytical hardware.

[DOI] [BibTeX] [pdf] [bib]

tags: Cryptanalysis, cube attacks, cube testers, experimental verification, Grain-128, RIVYERA, stream cipher