Add to Quick Collection
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/1144903
170 Visitors
181 Hits
0 Downloads
- Title
- Cryptanalysis of rabbit
- Related
- Lecture Notes in Computer Science, Vol. 5222 LNCS, (2008), p.204-214
- DOI
- 10.1007/978-3-540-85886-7_14
- Publisher
- Springer
- Date
- 2008
- Author/Creator
- Lu, Y
- Author/Creator
- Wang, Huaxiong
- Author/Creator
- Ling, San
- Description
- 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.
- Description
- 11 page(s)
- Subject Keyword
- 080200 Computation Theory and Mathematics
- Subject Keyword
- Bias
- Subject Keyword
- Distinguishing attack
- Subject Keyword
- ECRYPT
- Subject Keyword
- Keystream
- Subject Keyword
- Rabbit
- Subject Keyword
- Stream cipher
- Resource Type
- journal article
- Organisation
- Macquarie University. Department of Computing
- Identifier
- http://hdl.handle.net/1959.14/1144903
- Identifier
- mq:54833
- Identifier
- ISSN:0302-9743
- Identifier
- mq-rm-2008990232
- Language
- eng
- Reviewed
Macquarie University ResearchOnline
