Crypto Series: Mifare Crypto1

[♥•DaRkNeSsEs]

How the famous Crypto1 encryption built into the Mifare Classic, a RFID cards typically used to access to buildings but also for many other systems: Oyster Card in London, OV-Chipkaart in Holland, and so on.
Not discuss the details of the protocol itself, or how attacks work published, although the end of the post are a couple of interesting links about it.

Encryption Crypto1
Crypto1 encryption stream cipher is an owner of NXP which is in the RFID tags of the type Mifare Classic. In the first instance, the encryption was studied by Karsten Nohl reverse engineer the chip. This information was published in the CCC 07, but did not post too many details of the encryption itself.
In parallel, Radboud Universiteit Nijmegen was studying this type of card and with the help of information published in the CCC came to do a complete reverse engineering the encryption. Let's see how it works.
Crypto1 is a LFSR based encryption, which uses a single LFSR with a linear feedback function and a filtering function to produce output (keystream):

Crypto1 - General structure

The encryption structure was revealed in the presentation of the CCC, but the generator polynomial (the feedback of the LFSR) and the filter function was not. The generator polynomial, published by Karsten Nohl and others Usenix'08, is as follows:

This means that the bits 43,39,38 ..., 7,6,5,0 are used to form the new bits that enter into the record. In addition to these bits, using the input bit and performs an XOR of all to generate the next bit of the register. This polynomial is a polynomial primitive irreducible and generates all the states before rebuilding the initial state.
Furthermore, filtering functions were published by people in Esorics'08 RU Nijmegen. The figure below shows these filter functions along with the rest of encryption.

Crypto1 - Breakdown Structure

Each hexadecimal numbers identifying the filter functions should be read as a bitmap where the leftmost bit will be produced as output when all inputs are one and the rightmost bit is the output when all inputs are zeros. For example, 0 × 26c7 translated to binary would be:
0010 0110 1100 0111
This means that for entries (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 the other entries would be 1.
Links

This is fully described Crypto1 encryption used in Mifare Classic chips. I will not go into detail about the structure of the encryption or protocol used, among other things because I have not really discussed in depth, so for more information check out the following links:

www.cs.virginia.edu

www.sos.cs.ru.nl

www.cs.ru.nl

by Seifreed