Cryptology ePrint Archive: Report 2009/218

Efficient FPGA Implementations of High-Dimensional Cube Testers on the Stream Cipher Grain-128

Jean-Philippe Aumasson and Itai Dinur and Luca Henzen and Willi Meier and Adi Shamir

Abstract: Cube testers are a generic class of methods for building disstinguishers, based on cube attacks and on algebraic property-testers. In this paper, we report on an efficient FPGA implementation of cube testers on the stream cipher Grain-128. Our best result (a distinguisher on Grain-128 reduced to 237 rounds, out of 256) was achieved after a computation involving 2^54 clockings of Grain-128, with a 25632 parallelization. An extrapolation of our results with standard methods suggests the possibility of a distinguishing attack on the full Grain-128 in time 2^83, which is well below the 2^128 complexity of exhaustive search. We also describe the method used for finding good cubes (a simple evolutionary algorithm), and report preliminary results on Grain-v1 obtained with a bitsliced C implementation.

Category / Keywords: secret-key cryptography / stream cipher, FPGA, cube tester, cube attack

Date: received 19 May 2009, last revised 27 May 2009

Contact author: jeanphilippe aumasson at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20090527:071323 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]