Cryptology ePrint Archive: Report 2008/166

Algebraic Attacks on the Crypto-1 Stream Cipher in MiFare Classic and Oyster Cards

Nicolas T. Courtois and Karsten Nohl and Sean O'Neil

Abstract: MiFare Crypto 1 is a lightweight stream cipher used in London's Oyster card, Netherland's OV-Chipcard, US Boston's CharlieCard, and in numerous wireless access control and ticketing systems worldwide. Recently, researchers have been able to recover this algorithm by reverse engineering.

We have examined MiFare from the point of view of the so called "algebraic attacks". We can recover the full 48-bit key of MiFare algorithm in 200 seconds on a PC, given 1 known IV (from one single encryption).

The security of this cipher is therefore close to zero. This is particularly shocking, given the fact that, according to the Dutch press, 1 billion of MiFare Classic chips are used worldwide, including in many governmental security systems.

Category / Keywords: secret-key cryptography / Mifare Crypto 1 algorithm, stream ciphers, algebraic cryptanalysis, Boolean functions, Gröbner bases, SAT solvers

Date: received 13 Apr 2008, last revised 14 Apr 2008

Contact author: n courtois at ucl ac uk

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080414:185254 (All versions of this report)

Discussion forum: Show discussion | Start new discussion