Nicolas T Courtois, SOAJ-JQ;
Practical Algebraic Attacks on the Hitag2 Stream Cipher.
Presented at: 12th Information Security Conference, ISC 2009, Pisa, Italy.
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 . 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  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 . Similarly reduced-round versions of DES  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:||Conference item (UNSPECIFIED)|
|Title:||Practical Algebraic Attacks on the Hitag2 Stream Cipher|
|Event:||12th Information Security Conference, ISC 2009|
|Dates:||07 September 2009 - 09 September 2009|
|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 > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
Archive Staff Only