UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Practical Algebraic Attacks on the Hitag2 Stream Cipher

Nicolas T Courtois, SOAJ-JQ; (2009) Practical Algebraic Attacks on the Hitag2 Stream Cipher. In: Ardagna, PSMYFMACA, (ed.) 12th International Conference, ISC 2009 Pisa, Italy, September 7-9, 2009 Proceedings. (pp. 167 - 176). Springer: Berlin.

Full text not available from this repository.

Abstract

Hitag2 is a stream cipher that is widely used in RFID car locks in the automobile industry. It can be seen as a (much) more secure version of the [in]famous Crypto-1 cipher that is used in MiFare Classic RFID products [18, 13]. Recently, a specification of Hitag2 was circulated on the Internet [27]. Is this cipher secure w.r.t. the recent algebraic attacks [8, 15, 1, 23] that allowed to break with success several LFSR-based stream ciphers? After running some computer simulations we saw that the Algebraic Immunity [23] is at least 4 and we see no hope to get a very e cient attack of this type. However, there are other algebraic attacks that rely on experimentation but nevertheless work. For example Faugere and Ars have discovered that many simple stream ciphers can be broken experimentally with Grobner bases, given an extremely small quantity of keystream, see [15]. Similarly reduced-round versions of DES [9] and KeeLoq [11, 12] were broken using SAT solvers, that actually seem to outperform Groobner basis techniques. Thus, we have implemented a generic experimental algebraic attack with conversion and SAT solvers, [10, 9]. As a result we are able to break Hitag2 quite easily, the full key can be recovered in a few hours on a PC. In addition, given the specific protocol in which Hitag2 cipher is used in cars, some of our attacks are practical.

Type:Proceedings paper
Title:Practical Algebraic Attacks on the Hitag2 Stream Cipher
Event:12th Information Security Conference, ISC 2009
Location:Pisa, Italy
Dates:2009-09-07 - 2009-09-09
ISBN-13:978-3-642-04473-1
DOI:10.1007/978-3-642-04474-8
Publisher version:http://www.springer.de/
Keywords:RFID tags, Hitag 2 algorithm, MiFare Crypto-1 cipher, stream ciphers, algebraic cryptanalysis, Boolean functions, Grobner bases, SAT solvers.
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record