Experimentally Verifying a Complex Algebraic Attack on the Grain-128 Cipher Using Dedicated Reconfigurable Hardware

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

SHARCS 2012 (http://2012.sharcs.org/index.html), 17-18 March 2012, Washington DC, USA


Abstract

In this work, we describe the first single-key attack on the full version of Grain-128 that can recover arbitrary keys. Our attack is based on a new version of a cube tester, which is a factor of about 2^38 faster than exhaustive search. To practically verify our results, we implemented the attack on the reconfigurable hardware cluster RIVYERA and tested the main components of the attack for dozens of random keys. Our experiments successfully demonstrated the correctness and expected complexity of the attack by finding a very significant bias in our new cube tester for about 7.5% of the tested keys. This is the first time that the main components of a complex analytical attack against a digital full-size cipher were successfully implemented using special-purpose hardware, truly exploiting the reconfigurable nature of an FPGA-based cryptanalytical device.

[SHARCS 2012 website] [pdf]

Tags: Cryptanalysis, cube attacks, cube testers, Grain-128, special-purpose hardware, stream cipher