28-04-2008 - Mifare (In)Security Update March 2008
Early March the digital security group at Radboud University in the Netherlands has revealed a security vulnerability in the Mifare Classic chip. They demonstrated that the Crypto-1 encryption algorithm allowed the 48 bit keys to be relatively easily retrieved. They commented that the vulnerability was particularly acute for access control systems where a common global key is used.
Their attack recovers the key from the Mifare reader. In order to mount the attack they gathered a modest amount of data from a genuine reader. They then computed the key off-line. They claim that recovering the secret key is as efficient as using a look-up table and that it is much more efficient than a
key exhaustion attack on the 48 bit key. They further claim to have implemented and executed this attack in practice and to have recovered the key in minutes. They have a movie on their web site that demonstrates the attack on the card access control system protecting the building in their university. They point out on their web site that the reverse engineering attack published by Karsten Nohl and Henryk Plotz contributed to their understanding of the Crypto-1 algorithm.
Although they have broken the physical access control system at the university they have not been able to demonstrate an attack on the ov-chipkaart which also uses the Mifare Classic. The Digital Security group found weaknesses in the authentication mechanism of the Mifare Classic.
In particular:
- The working of the CRYPTO1 encryption algorithm was reverse engineered, and they have developed their own implementation of the algorithm.
- They found a relatively easy method to retrieve cryptographic keys, which does not rely on expensive equipment.
To reverse engineer the CRYPTO1 encryption algorithm they used flawed authentication attempts. They point out that if one does not precisely follow the rules of the prescribed protocol, it is possible to obtain some information about the way the algorithm works. It is presumed that they used this information in conjunction with the published results of Nohl and Plotz to reconstruct the algorithm, their publication revealed most of what you need but omitted details of the filter function for the key combination (see Smart Card News January 2008 for further details). They also admit to having had communications with Nohl and Plotz.
Once the algorithm is known then clearly you can find the keys by a brute force attack since the key is only 48 bits (i.e. simply trying all possible keys). Trying all the keys then takes only a few hours using a hardware investment (e.g. a FPGA implementation of the algorithm) of about $9000, according to the recent TNO report 34643 `Security Analysis of the Dutch OV-chipkaart, published on February 26th 2008.
But this is where the work of the Digital Security Group gets interesting. They discovered that certain flaws in the authentication protocol could be exploited. This leads to their second point, that there is a way to relatively easily retrieve the key without carrying out a lengthy brute force attack. This can be done by first carrying out many failed authentication attempts, which provides some information. Storing the results of this in a big table, one can look for a match and retrieve the key. The table only has to be constructed once, and can be prepared in advance by repeatedly running the CRYPTO1 algorithm on a fixed input. It is not clear what they are saying here unless it is just a memory time trade off which is a common cryptographic attack mechanism. A full table might need several thousand Terabytes but it would not be practical from a time point of view to collect so many authentication attempts (i.e. one for each key) which suggests they have been able to construct the key from a much smaller table. For a well designed algorithm/protocol this should not be possible which leads to thoughts of linearity.
Their proof-of-concept demonstration of this attack still required many authentication attempts once this table had been constructed. Recording these attempts took several hours, but could be carried out by a hidden antenna to eavesdrop on a card reader. It seems, they comment, that the complexity can be further reduced, possibly dramatically so, making the attack much simpler. Whatever they have done it would appear that they have discovered something new to the results of Nohl and Plotz however they do note that they have been unable to demonstrate an attack on the OV-chipkaart transport scheme which has a more complicated protocol. This is a contradiction because the Mifare authentication protocol is common to both schemes. The only difference is that the access control system is using global keys and the transport scheme is using derived keys unique to each card. Breaking an individual key should be the same effort for both schemes albeit the impact is very different.
We referred earlier to the TNO report on their response to Nohl and Plotz's work. This was some work undertaken by the TNO Information and Communication Technology division in Delft, the original home of the security evaluation team one of the pioneers in chip security which has now spun off from TNO as a private company called Brightsight but still located in Delft.
The work was commissioned by Trans Link Systems which was established by the five largest Dutch public transport companies to implement a single payment system for public transport called the OV-chipkaart. This scheme uses the Mifare Classic 4K card and also the Mifare Ultralight chips which have no cryptographic protection. The latter chip is used for disposable public transport cards, they are much simpler and cheaper than the Mifare Classic.
TNO were originally commissioned to do a very fast investigation to assess the immediate risks to the OVchipkaart system on the basis of Nohl and Plotz's presentations to the Chaos Congress in Berlin in December 2007. They were further commissioned to undertake a more thorough investigation to assess not only the immediate risks but also the risks of potential further discoveries by Nohl and Plotz or others (now of course the Radboud University).
The initial response agrees that Nohl and Plotz have either fully reverse engineered the Crypto-1 algorithm or if not will do so in the near future. They further agree that once the algorithm is known that a key of 48 bits is too small to resist a key search attack. In summary they conclude that the attack is very credible in most aspects and that there is the possibility of building a key cracker within 6 months.
The more complete TNO report 34642 was published in February but not made publicly available. A public excerpt TNO report 34642 was however produced which further substantiates the original findings. The report advises that the Mifare Classic 4K will need to be replaced and that Trans Link Systems should have a migration strategy ready within 2 years.
A damming report indeed and probably the end of the Mifare Classic as we know it but let us not forget it has had a good run and has been at the forefront of contactless smart card technology particularly in the mass transit sector.
Dr David Everett, www.smartcard.co.uk
