Another “Crypto” Algorithm Broken

I used to give a talk called "Crypto Blunders". It was my most popular presentation, I received invitations from conferences all over the world to give it. I loved that talk because of all the free trips it got me.

Blunder #3 was "Don't use the best available algorithm." There are governments and companies that want to keep things secret, yet they use bad crypto, even though good crypto is readily available, often for free. In other cases, people who are not cryptographers, who have not studied the art, will design their own algorithms and use them.

Blunder #4 was "Implement the Algorithm Incorrectly". When implementing crypto, people will get sloppy and do a bad job of implementing the algorithm. These are mistakes that go beyond the classification of "bug" and become blunders.

Well, here's a case, I believe, of a company committing Blunders #3 and 4.

The Nov. 28, 2008 issue of Science reports on a group of Ph.D. students in The Netherlands that was able to break an RFID card. They totally broke it. Using their techniques they were able to continuously refill a subway token without paying, and "clone" cards used to open a garage gate.

I don't know if they performed other experiments, but I doubt they did anything particularly nefarious. However, in order to prove they actually broke the system, and that it was possible to implement the break in the real world, they did indeed show how to get free subway rides and gain access to a building for which they had no true authorization.

In the title, I put the word Crypto in quotes. Here's why. The way they broke the system was to break a key derivation, or pseudo-random number generating (PRNG) function. That's crypto. However, they also discovered that the function used a "linear feedback shift register" (LFSR), which, in my opinion is not true crypto. When you need secure random numbers for a key, or key stream, or any other purpose, you should use a cryptographically secure PRNG. The card maker, however, used something that has been shown many times to be unsecure. So the break looks like crypto, but the card maker used a non-crypto algorithm where crypto should be.

That's blunder #3, using an unsecure PRNG, when secure algorithms are readily available. Why did they use an unsecure algorithm? Here are some theories.

1: The designers didn't know that the random number generator has to be secure. Many developers probably know that the encryption algorithm must be secure, and that the key must be long (80 bits at least, usually 128 bits are used). But sometimes people just never make the connection between how the key material is generated and security.

2: The designers didn't know that LFSR was not secure. I can believe that, before I learned that LFSR was not secure, I didn't know that LFSR was not secure. You can't blame people for not knowing something. But who were the security experts on the team? Did they have any? Did anyone review the design? Possibly not, I've seen companies in the past build security products or add security to a product using personnel with no security experience. The belief is, security and crypto is easy, anyone can learn it.

3: They were dealing with severe constraints on size and speed (remember, this is a chip on a credit card, yet transactions had to be practically instantaneous). They had to come up with a solution that would not add too much size or complexity to the chip, nor slow things down. They probably did not have the space to load software, so the solution had to be hardware. Communications had to be very quick, performing some crypto algorithms might have taken too long. They felt the constraints eliminated AES or SHA-1 or RC4 or RC5 (the greatest block cipher ever). Of course, one of the constraints should have been security. Furthermore, DES on a chip is a problem solved long ago. Don't use DES to encrypt, but it can be used safely as the foundation of a PRNG.

Now on to blunder #4. Apparently, one thing the attackers were able to do was force the chip to accept 48 bits when it was supposed to accept only 32. In a communication between card and reader, the card sends a 32-bit ID. But the attackers sent a 48-bit ID, the reader accepted it and that helped them in acquiring the secret bits. Is that a bug? Accepting a 48-bit ID when IDs are defined as 32 bits? I think that goes beyond bug and into the realm of blunder.

Leave a Reply

Your email address will not be published. Required fields are marked *