MiFare’s CRYPTO1 stream cipher has captured my attention for a while. However, hardware reverse-engineering is not a field I actively engage in. So I was very happy when Karsten Nohl (University of Virginia), Starbug and Henryk Plötz gave a talk at the 24C3 [the 24th Congress of the Chaos Computer Club taking place in Berlin at this very moment] yesterday evening showing that they have reverse-engineered most parts of this cipher. CRYPTO1 uses a 48-bit LFSR-based filter generator to generate key stream.
The filter function – if I understood correctly – uses 24 20 taps (this was not mentioned in the talk, I asked Karsten privately about this) however the degree of the boolean function implementing the filter , thus it remains to be seen whether algebraic attacks can be applied. Even if no algebraic attacks are applied, a BSW sampling TMTO will break CRYPTO1 completely. This was pretty obvious before they gave their talk, but now vendors actually have to worry about this being out in the wild once the feedback and the filter function have been revealed.
My colleague Erik took photos of the slides which I put up on Zooomr. A video recording of the talk should be available shortly and will be linked here.
Update 2008-01-02: A recording of the talk now is available (MPEG4, iPod compatible).
Thanks for the exposure 🙂
Please note that the shown slide purposely omits many details. In particular, the combination of ID and key is more complicated than simple XOR as was hinted at in Henryk’s part of the talk.
Pingback: Kryptoblog » Blog Archive » Kryptanalys av Philips CRYPTO1 pÃ¥ CCC
Hitag2 cipher has been reverse-engineered a long time ago. See http://cryptolib.com/ciphers/hitag2/
Happy New Year!
See also http://hitag2.land.ru/
Oh. My. Goodness. Where did that come from? Mirror, mirror, mirror before the takedown request comes!
It’s amazing that a lot of people were trying to reverse engineer this cipher and it has been around in source form all this time. Do I understand correctly, that this particular device (described in the PDF) implements the cipher as micro code? Is that why it was reversed?
Oh yeah, and happy new year to all my readers, of course! May this be a fruitful year for cryptanalysis.
It doesn’t appear to be the same cipher.
Interesting information, but it has not been demonstrated that the algorythm has been cracked!!
@pascal: sorry, but with a key space of 48 bits, this cipher does not need anything more than mere brute force to be considered broken.
If you want a realtime attack, consider Biryukov-Shamir-Wagner sampling, as indicated in the post. See Biryukov’s and Shamir’s ASIACRYPT 2000 paper for more information. Heck, even a classic Hellman TMTO will smash this cipher to tiny little pieces.
If it’s not the same, it sounds remarkably similar – a 16-tap 48-bit LFSR with a 20-tap non-linear output combiner…
Our analysis has caused an extensive debate over the new Dutch ticketing system for public transport. Finally people are staring to be concerned about system security :).
Our take on the security of this and similar systems:
http://www.cs.virginia.edu/~kn5f/OV-card_security.html
Why does it say that Hitag2 systems are not affected? ;-))) Someone should say something…
Ruptor: Read carefully. Where does it say that Hitag2 is not affected? In fact, I haven’t said anything about Hitag2 at all, since I never looked into it. But if it has the same key size, it will of course be vulnerable to the same kind of TMTOs if the full specification is publicly available. And as I understood from your posts, it is. The question that was discussed previously is whether Hitag2 is identical or not to Mifare.
During the Q&A session at the end, there was a brief discussion about the PRESENT cipher. This is our new block cipher optimized for (cost sensitive) RFID chips. If anybody is interested, here is a description of the cipher:
http://www.crypto.ruhr-uni-bochum.de/en_publications.html
It is in the article “PRESENT: An Ultra-Lightweight Block Cipher” which appeared at this year’s CHES workshop.
PRESENT has an 80 bit key. Note that there is currently NO attack known against PRESENT which is better than the 2^80 steps that are needed for a brute-force attack.
REMARK: There is a result with an attack complextiy of 2^64, but that’s only an attack against the first 16 rounds PRESENT. However, PRESENT has 31 rounds and the attack completely fails against the full cipher. Breaking reduced round versions of block cipher is not uncommon in the scientific community. For instance, note that you can break 5-round AES with about 2^30 ciphertexts. However, this is of no practical use since AES has 10 rounds… 🙂
Ralf: I did read carefully ;-P
“Other types of RFID tags … including the Hitag2+ tags … are not affected by our findings.”
That is where you said it. Of course they are all affected! People will now rightfully doubt all those tags.
cpaar: I hear PRESENT is too big for the lowest-cost RFIDs. According to Karsten, 500 gates is the limit…
Ruptor, this is getting surreal. Maybe you’re confusing something. Please tell me where I supposedly have written the words that you’re stating! Remember I’m not part of the team that presented @24C3, I merely reported on Karsten, Henryk and Starbug’s presentation. Moreover, I don’t remember them saying much about Hitag2 in the talk, but I’d have to watch the whole video again to make sure.
Best,
Ralf
Ralf, you tried to correct me… I was talking about the http://www.cs.virginia.edu/~kn5f/OV-card_security.html article.
@Ruptor: alrighty. that’s not my content though. and neither is that page linked from here. I understand your point, I simply suggest that your finger is pointing into the wrong direction, that’s all. End of discussion on this topic.
Pingback: RFID Fails the counterfeit test « Counterfeit Drug Blog