Home > protocol, symmetric > MiFare’s CRYPTO1 algorithm mostly reverse-engineered

MiFare’s CRYPTO1 algorithm mostly reverse-engineered

December 29th, 2007 Leave a comment Go to comments

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).

  1. karsten
    December 29th, 2007 at 23:35 | #1

    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.

  2. January 2nd, 2008 at 19:59 | #2

    Hitag2 cipher has been reverse-engineered a long time ago. See http://cryptolib.com/ciphers/hitag2/

  3. January 2nd, 2008 at 20:03 | #3

    Happy New Year!

  4. January 2nd, 2008 at 20:33 | #4
  5. January 2nd, 2008 at 20:43 | #5

    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.

  6. karsten
    January 3rd, 2008 at 04:41 | #6

    It doesn’t appear to be the same cipher.

  7. pascal
    January 3rd, 2008 at 22:33 | #7

    Interesting information, but it has not been demonstrated that the algorythm has been cracked!!

  8. January 4th, 2008 at 13:13 | #8

    @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.

  9. January 8th, 2008 at 10:23 | #9

    If it’s not the same, it sounds remarkably similar – a 16-tap 48-bit LFSR with a 20-tap non-linear output combiner…

  10. karsten
    January 8th, 2008 at 23:51 | #10

    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

  11. January 11th, 2008 at 15:53 | #11

    Why does it say that Hitag2 systems are not affected? ;-) )) Someone should say something…

  12. January 11th, 2008 at 16:03 | #12

    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.

  13. cpaar
    January 11th, 2008 at 17:48 | #13

    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… :)

  14. January 12th, 2008 at 14:46 | #14

    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…

  15. January 12th, 2008 at 23:29 | #15

    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

  16. January 13th, 2008 at 02:15 | #16

    Ralf, you tried to correct me… I was talking about the http://www.cs.virginia.edu/~kn5f/OV-card_security.html article.

  17. January 13th, 2008 at 02:58 | #17

    @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.

  1. December 31st, 2007 at 15:14 | #1
  2. March 8th, 2008 at 18:57 | #2
You must be logged in to post a comment.