×

On guess and determine analysis of Rabbit. (English) Zbl 1225.94016

Summary: Rabbit is a stream cipher proposed by M. Boesgaard et al. [Lect. Notes Comput. Sci. 2887, 307–329 (2003; Zbl 1225.68087)], and has been selected into the final portfolio after three evaluation phases of the ECRYPT Stream Cipher Project (eSTREAM). So far only a few papers studied its security besides a series of white papers by the designers of Rabbit. Recently we presented a new idea to evaluate the security of a word-oriented stream cipher algorithm from a smaller data granularity instead of its original data granularity and applied it successfully to the stream cipher SOSEMANUK. In this work we apply the same idea to the Rabbit algorithm and analyze its security in resistance against the guess and determine attack from the viewpoint of byte units. As a result, we present two new approaches of solving all \(x_{j,t+1}\)’s and \(g_{j,t}\)’s from the next-state function and the extraction scheme of Rabbit, whose complexities are \(2^{166}\) and \(2^{140.68}\), respectively, which are dramatically lower than those proposed by Y. Lu, H. Wang and S. Ling [Lect. Notes Comput. Sci. 5222, 204–214 (2008; Zbl 1181.94100)] (\(2^{192}\) and \(2^{174}\) resp.) at ISC 2008. Finally, based on the above new results, we propose a byte-based guess and determine attack on Rabbit, which only needs a small segment of known keystream to recover the whole internal state of Rabbit with time complexity \(2^{242}\). Though the complexity of our attack is far higher than that of a brute force \((2^{128})\), we believe that some new techniques adopted in this paper are of interest for future work on Rabbit.

MSC:

94A60 Cryptography

Software:

Rabbit; SOSEMANUK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boesgaard M., LNCS2887 pp 307– (2003)
[2] Lu Y., ISC 2008 pp 5222– (2008)
[3] Hawkes P., LNCS 2595 pp 37– (2002)
[4] Feng X., LNCS 6477 pp 146– (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.