Cryptanalysis of rabbit

Yi Lu*, Huaxiong Wang, San Ling

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

7 Citations (Scopus)

Abstract

The stream cipher Rabbit is one candidate to the ECRYPT Stream Cipher Project (eSTREAM) on the third evaluation phase. It has a 128-bit key, 64-bit IV and 513-bit internal state. Currently, only one paper [1] studied it besides a series of white papers by the authors of Rabbit. In [1], the bias of the keystream sub-blocks was studied and a distinguishing attack with the estimated complexity 2247 was proposed based on the largest bias computed. In this paper, we first computed the exact bias of the keystream sub-blocks by Fast Fourier Transform (FFT). Our result leads to the best distinguishing attack with the complexity 2158 so far, in comparison to 2247 in [1]. Meanwhile, our result also indicates that the approximation assumption used in [1] is critical for estimation of the bias and cannot be ignored. Secondly, our distinguishing attack is extended to a multi-frame key-recovery attack, assuming that the relation between part of the internal states of all frames is known. Our attack uses 251.5 frames and the first three keystream blocks of each frame. It takes memory O(232), precomputation O(2 32) and time O(297.5) to recover the keys for all frames. This is the first known key-recovery attack on Rabbit, though the attack assumption is unusually strong. Lastly, as an independent result, we introduced the property of Almost-Right-Distributivity of the bit-wise rotation over the modular addition for our algebraic analysis.This allows to solve the nonlinear yet symmetric equation system more efficiently for our problem.

Original languageEnglish
Title of host publicationInformation Security
Subtitle of host publication11th International Conference, ISC 2008, Proceedings
EditorsTzong-Chen Wu, Chin-Laung Lei, Vincent Rijmen, Der-Tsai Lee
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages204-214
Number of pages11
ISBN (Print)3540858849, 9783540858843
DOIs
Publication statusPublished - 2008
Event11th International Conference on Information Security, ISC 2008 - Taipei, Taiwan, Province of China
Duration: 15 Sep 200818 Sep 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5222 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other11th International Conference on Information Security, ISC 2008
CountryTaiwan, Province of China
CityTaipei
Period15/09/0818/09/08

Fingerprint Dive into the research topics of 'Cryptanalysis of rabbit'. Together they form a unique fingerprint.

Cite this