Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Mifare Crypto1

Let's go back into Cryptography. This time I'll tell you how the (in)famous Crypto1 cipher works. It is used in the Mifare Classic RFID tags, typically used for building access control but also for many other systems such as the Oyster Card in London, the OV-Chipkaar in The Netherlands, etc.

We won't talk about the protocol details, nor about how the published attacks work. You'll find a couple of interesting links at the end though ;-).

Note: Images obtained from the papers linked at the end of the post.

The Crypto1 cipher

Crypto1 is a proprietary stream chiper from NXP found in the RFID tags from the Mifare Classic family. At first, it was studied by Karsten Nohl reverse engineering the chip itself. This information was published in the CCC 07, although not many details about the cipher were published.

In parallel, the Radboud Universiteit from Nijmegen was studying this kind of cards and with the help of the information published at CCC completely reverse engineered the cipher and published the details. Let's see how it works then...

Crypto1 is an LFSR based cipher, which uses just an LFSR with a linear feedback function and a filter function to generate the output stream (keystream):

Crypto1 - Overall structure

The overall structure of the cipher was revealed in the presentation at CCC, but the generating polynomian (the feedback function used by the LFSR) and the filter function was not. The generating polynomial, published by Karsten Nohl et al at Usenix'08, is as follows:

This means that bits 43,39,38...,7,6,5,0 are used to create the new bit that will be shifted into the register. Further, the input bit is used and a XOR of all them is executed to generated the next bit. This polynomial is primitive: irreducible and generates all the possible states before cycling back to the initial state.

On the other hand,the filter functions were published by the people from RU Nijmegen at Esorics'08. The following picture shows those filter functions together with the rest of the cipher.

Crypto1 - Detailed structure

Each of the hexadecimal numbers identifying the filter functions should be read as a bitmap where the left-most bit will be produced as an output of the filter function when the input was all-ones while the right-most bit will be produced as an output when the input was all-zero. For instance, 0x26c7 in binary form would be:

0010 0110 1100 0111

Which means that for inputs (1,1,1,1), (1,1,1,0), (1,1,0,0), (1,0,0,1), (0,1,1,0), (0,1,0,1)  and (0,1,0,0) the result of the filter function would be 0, and 1 otherwise.

Links

This completes the description of the Crypto1 cipher used by Mifare Classic chips. I don't want to get into more details about the structure of the cipher and the protocol, because I didn't look at it in depth amongst other reasons, so for more information you can follow these links:

Reverse-Engineering a Cryptographic RFID Tag - Karsten Nohl et al. Usenix'08

Dismantling MIFARE Classic - Flavio D. Garcia et al. (RU Nijmegen). Esorics'08

Lecture on Mifare Classic from HW and OS Security course at RU Nijmegen