Cryptanalysis of Crypto-1
University of Virginia
The secret cipher that secures Mifare Classic RFID tags used in access control systems, subway
tickets, and various other security-related applications has recently been disclosed . Since the
security of the Mifare cards partly relies on the secrecy of this algorithm, we concluded that the
cards are too weak for all security-related applications since the algorithm can be found with
modest effort. A report for the Dutch government that assesses the impact of our findings on a
nationwide ticketing system in the Netherlands was released on February 29th . The report
confirms our findings, but asserts that systems will likely be secure for another two years since
the attack is still costly. In the report, the attack is estimated to require $9,000 worth of hardware
to break secrets keys in a matter of hours. We argue that this is a gross over-estimate and present
an attack that recovers secret keys within minutes on a typical desktop PC or within seconds on
an FPGA. Our attack exploits statistical weaknesses of the cipher.
The Crypto-1 cipher consists of a linear feedback shift register (LFSR) and a filter function, f(⋅),
as shown in Figure 1. During the initialization, the secret 48-bit key is loaded into the shift
register and the string (ID xor Rb) is shifted into the state, where ID is the identifier of the tag, and
Rb is a random number chosen by the tag. Rb is also sent to the reader as a first challenge in a
challenge-response protocol in which tag and reader prove knowledge of the secret key. Since in
our attack, the attacker only needs to communicate with the reader, the challenge can freely be
chosen and does not need to be random.
In each clock cycle, the filter function, f(⋅), computes one bit of key stream from 20 LFSR bits.
The function is composed from 6 instantiations of 3 smaller functions as depicted in Figure 2.
These functions are statistically biased: if one input bit is