A very impressive analysis of the Texas Instruments RFID technology used in a variety of security systems, such as vehicle immobilizers and ExxonMobil’s SpeedPass system.
Mistake number 1: The cryptographic algorithm is a proprietary 40-bit cipher.
Davi Ottenheimer • March 3, 2005 11:23 AM
Avi Rubin has been on CNN a few times where he basically says “TI chose to use a weak key developed in the 1990s when they could have used a stronger one (HMAC-SHA1)”. It would be interesting to know whether that was a price/risk calculation made by TI or SpeedPass?
Also, I find it interesting that they could break it in under an hour (http://rfidanalysis.org/DSTbreak.pdf) with $3500 in equipment. Considering the value of a stolen car, or just ten tanks of gas, someone at TI/SpeedPass must need a better calculator.
Is there an annual award for cost/time ratio in cryptographic attacks? If not, there should be. For example, this team would get a threat (likelihood) score of 3500/60 or 58.333. If you add the value of an asset at risk (e.g. one $50K vehicle) then the score could be translated into a dollar value: 50K x 58.333 = USD$2,916,650.
Just for fun, I wonder if we can use this silly system to see how 40bit compares to stronger keys? Perhaps if TI used a 1024-bit key and (based on estimates from Adi Shamir’s team at Technion in Israel) a machine to break it in one year would cost about USD$10 million. That comes out to a theoretical score of 19.026 (10M/525600), which translates into 50K x19.026 = USD$951,300.
But of course, if the system was designed to actually be safe to use it might ruin “innovation??? and we would see things like the wonderful consumer-driven SpeedPass watch delayed for several years:
http://www.timex.com/speedpass/
Joe Hammer • March 3, 2005 12:12 PM
“We used some new special-purpose cryptanalytic techniques to reconstruct the algorithm used in the DST tags, by simply observing the responses that actual DST tags computed when presented with a large number of specially chosen challeneges. Using this black-box reverse-engineering method, we were able to implement a software program that, when given the same challenge and key as an actual tag, would compute the same response.”
Does anyone know what this method is actually called so I could research it in more depth?
Davi Ottenheimer • March 3, 2005 12:27 PM
@Joe
Read the paper for details. It clearly states on page four “We omit details about that [sic] would permit direct reconstruction of the cipher. Our goal is to offer our fullest possible contribution to the scientific community, but at the same time to avoid fomenting abuse of our results. Once the industry has had time to take adequate security measures, we intend to divulge full cipher details in the interest of stimulating cryptanalytic research by the scientific community.”
Shon • March 3, 2005 2:57 PM
“We used some new special-purpose cryptanalytic techniques to reconstruct the algorithm used in the DST tags, by simply observing the responses that actual DST tags computed when presented with a large number of specially chosen challeneges.”
New? Did I miss something? Isn’t this normal cryptanalysis?
Davi Ottenheimer • March 3, 2005 4:23 PM
@Shon
If you read the paper on page four you will find that the researchers say “we are unaware of any puublished black-box reverse-engineering of a contemporary cipher, whether the original source be a software or a hardware implementation. Having no literature to refer to, we developed techniques for our effort in an ad hoc manner.” […] “In contrast, the key-recovery techniques we employed are well known.”
Davi Ottenheimer • March 3, 2005 6:26 PM
I don’t know if this qualifies, but it sure looks like a published paper on black-box reverse-engineering:
“Attacking an obfuscated cipher by injecting faults”
http://crypto.stanford.edu/DRM2002/drm1.pdf
The authors claim to “investigate a commercial state-of-the-art obfuscated cryptosystem that hides a secret key.” They conclude that most obfuscation is imperfect enough to enable automated extraction of a secret key. They also suggest a few methods of defence.
I rather think that TI didn’t make a price-risk calculation, but rather deployed an algorithm based on the criteria of something that actually worked.
I’ll call your attention to two items, one in the Fixes section of the main analysis page. When discussing changing to a standard, reviewed algorithm, they note “the required circuitry … might have other impacts on the overall system architecture due to increased power consumption”.
In the FAQ, there is a specific question about this…
“Why did the designers of the TI system use only 40-bit keys?
“We cannot offer an authoritative answer to this question. RFID devices, however, have a special characteristic that other computing devices don�t: They have no on-board source of power, and instead derive power from the reader signal. This fact imposes engineering constraints that may have led to the designers� choice of cryptographic algorithm.”
Both items concentrate on the fact that RFID tags are severely limited in available power. The power is broadcast to the chip in a power phase, often less than 1 ms long, and stored in an on-board tiny capacitor. All the calculations must be done with the few microwatts (if that) of power available in that few milliseconds — while leaving enough power to broadcast the results back to the receiver just before the power runs out and the whole chip stops operating.
With this in mind, I can see how the use of a proprietary algorithm might be a mistake — but the choice of 40 bits is more likely to be a hard cap imposed by the laws of physics. Every bit calculated drains a few precious electrons.
So, although there are algorithms you could use in the 40 bit range, if you’re going to be critical, then I think it behooves you to point to any reviewed algorithm that can operate under those constraints. Go through an algorithm, and work out how many adds and multiplies you need. Unfortunately, the TI algorithm isn’t available for comparison, but I think you will find it a model of calculation economy.
RFID designs will sometimes concentrate on terms you just don’t hear other places — tags with batteries draw just a couple of microamps. Passive tags are lower still. Suddenly, MIPS/watt is a make-or-break factor in a design. Certainly, the overall power of processors has climbed over the last decade, but we now have main CPUs that could be used to make popcorn!
As I wrote over a month ago, at http://blog.mutatron.com/000035.html, I think the far more noteworthy fact is that RFID readers are spoofable – something that has always been possible, but not discussed much. RFID, like any other security measure, is part of a system. It has to work with the system, and may not need to be perfected to do that.
Ed Davies • March 4, 2005 5:07 AM
Why use RFID for a key which is to be inserted in the car in the first place? Obviously this comment doesn’t apply to the SpeedPass system.
Using electrical contacts as used on “smart” ATM cards or the Dallas Semiconductor Java iButton would allow more power to be drawn from the reader so allowing longer key lengths, prevent in-pocket reading and hugely reduce the range at which evesdropping would work.
Quercus • March 4, 2005 9:37 AM
Ed — I’m not expert on automobile security, but I assume the reason for RFID on a car key is to have a physically distant backup in a location that’s hard to find and bypass (after all, people steal cars mostly by physically destroying/bypassing the lock, not by picking it). Though I suppose adding electrical contacts for power only to the lock and key might be workable (as long as the RFID reader is somewhere else).
And for speedpass, the whole point is that it’s easier than physical contact — after all if physical contact was required, there’s no reason not to just stick your credit card in a reader.
From my quick reading, it appears that this result isn’t a major issue for car keys — you need read access to the key to duplicate it, so a car thief would have to hang out near a target car until the owner got in, then get within 10 feet so they could read her key (and then still have to find the car later), which is probably not SOP or desireable for car thieves. On the other hand, it makes it easy to steal from a speedpass owner — all you need to do is walk around with a reader, and once you get a hit from anyone, you can immediately and anonymously charge anything you want to the victim. Ouch.
Duncan • March 5, 2005 11:57 AM
If I wanted to steal a car, I’d use a tow truck.
Roger • March 6, 2005 11:19 PM
@Chris:
Actually, in the draft academic paper (the PDF download, 274 kB) the algorithm is given, in detail, except that the f boxes and correct wiring between them is not given. (These could just be implemented as a 72 byte ROM with constant (very low) power consumption regardless of the exact functions.) Now I take your point in general, but this algorithm actually doesn’t look that much more efficient than some stronger algorithms targeted at microprocessors. Because DST takes two HUNDRED clocks to achieve adequate diffusion, it may well be worse. In fact at first glance I would say that even the DES, while needing about 3.6 times as much ROM, probably requires less computational power; a simple implementation of DES should require about 1,280 bits of XORing, 512 bits of ROM reads, 1024 bits of RAM reads, and 512 bits of RAM writes while DST looks like taking about 1,000 bits of XORing, 4,200 bits of ROM reads, 16,000 bits of RAM reads, and 400 bits of RAM writes. How that compares depends on the exact microjoules-per-bit cost of each operation but unless ROM and RAM reads are both two orders of magnitude cheaper than RAM writing, DES will be cheaper–perhaps even so cheaper that DES-X would be feasible, giving a solid algorithm with an (effective) 120 bit keyspace.
However, even if no other algorithm would do, it also seems to me that this one could easily have been modified to use a longer key at very little extra cost: just extend the key register to the left, by (say) 3 bytes (and move the LFSR taps to maximal spots for the new length). That will give slightly weaker key diffusion but the key diffusion is actually superb and no-one is attacking it, whereas the key length is weak and is being brute-forced.
Israel Torres • March 7, 2005 10:33 AM
Today’s Wired Article:
RFID Invades the Capital
http://www.wired.com/news/privacy/0,1848,66801-2,00.html?tw=wn_story_page_next1
“And it’s not just us (government workers),” said an employee of the U.S. General Services Administration, who would only give his name as Patrick. “Soon it will be everybody.”
Israel Torres
hannible • March 17, 2006 8:55 PM
alert(‘scuekr’)
nadir celiloglu • June 20, 2006 2:36 PM
The problem is resolved and it is now the safest locking system in the world. Do not make a big fuss out of it! Enough is enough!!
Remember nothing is really perfect in the life!
martin • December 21, 2010 6:34 AM
“Texas Instruments claimed its proprietary cryptographic systems might be stronger than AES. Nonetheless both firms are in the process of phasing out their home-cooked crypto tech in favour of industry standard encryption systems based on 128-bit AES.” 😉
http://www.theregister.co.uk/2010/12/20/car_immobiliser_security_flaws/
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Bill • March 3, 2005 10:34 AM
The sad thing to ask is: who will be the first to sue the researchers?