TMTO attacks on stream ciphers – theory and practice

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	KRHOVJÁK Jan KŮR Jiří ŠILER Ondřej LEYLAND Paul
Year of publication	2011
Type	Article in Proceedings
Conference	Security and Protection of Information 2011
MU Faculty or unit	Faculty of Informatics
Citation
Field	Informatics
Keywords	Hellman tables; Rainbow tables; stream ciphers; timememory tradeoff
Description	This paper deals with issues related to a cryptanalytic time-memory trade-off (TMTO) attacks on stream ciphers. We describe the basic theory and principles of TMTO attacks and their practical application on selected stream ciphers – namely on A5/1 cipher that is used in GSM (Global System for Mobile communications) standard. We focus mainly on the pre-computation phase of TMTO attacks. This phase includes data pre-computation and construction of various types of Hellman or Rainbow tables. The goal of the pre-computation is to cover some percentage of the key space with specially constructed chains. Our results demonstrate the real impact of various table parameters and chain constructions and show a substantial difference between theory and practice.
Related projects:	Czech Republic membership in the European Research Consortium for Informatics and Mathematics