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.) (Proceedings) 12th Information Security Conference, ISC 2009. (pp. pp. 167-176). Springer: Berlin.

Full text not available from this repository.


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: 07 September 2009 - 09 September 2009
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, Gr�obner bases, SAT solvers.
UCL classification: UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Engineering Science
URI: http://discovery.ucl.ac.uk/id/eprint/142973
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item