Proprietary Encryption in Car Immobilizers Cracked

This shouldn’t be a surprise:

Karsten Nohl’s assessment of dozens of car makes and models found weaknesses in the way immobilisers are integrated with the rest of the car’s electronics.

The immobiliser unit should be connected securely to the vehicle’s electronic engine control unit, using the car’s internal data network. But these networks often use weaker encryption than the immobiliser itself, making them easier to crack.

What’s more, one manufacturer was even found to use the vehicle ID number as the supposedly secret key for this internal network. The VIN, a unique serial number used to identify individual vehicles, is usually printed on the car. “It doesn’t get any weaker than that,” Nohl says.

Tags: , , ,

Posted on December 23, 2010 at 2:02 PM • 32 Comments

Comments

Nostromo • December 23, 2010 3:32 PM

Sorry to be off-topic … but please can someone tell us this is untrue?:
‘The CIA is forming a task force to deal with the fallout from the diplomatic cables released by WikiLeaks. It’s been given the simple name of WikiLeaks Task Force, or WTF.’

Clive Robinson • December 23, 2010 4:29 PM

One of the most dismal of these proprietary systems is made by an organisation (NXP) who used to be Phillips Semiconductors…

Phillips Semiconductors you might have heared of because of the equaly dismal MiFare classic cards used in travel cards like the London Oyster card.

The encryption used in both products being propriatory and well not exactly a shining example of anything.

Oh and guess what they are proposing using the MiFare system in bank direct debit and credit cards for contactless no pin usage…

Now can people guess why I don’t want one of these “hole in your bank account” cards?

Archon • December 23, 2010 4:42 PM

And don’t some cars come with RFID VIN tags to make things easier on the shippers and salespeople? If that was the case, couldn’t the car be stopped by literally anyone passing it by who had the right tech?

Jon • December 23, 2010 6:21 PM

From the article:

the VIN is “usually” printed on the car? Um, it’s always printed on the car, in several readily visible places, as is legally required (at least in the USA. I can’t imagine it’s much different in any developed country).

J.

Gabriel • December 23, 2010 7:12 PM

Yeah, bottom corner on the driver’s side of the windshield. Since eons ago.

But I thought if it was proprietary no one could crack it?

RobertT • December 23, 2010 9:04 PM

I worked on one of the proprietary systems mentioned, so I can attest to the fact that they use unbelievably weak encryption. What is worse is that the automotive integration systems protocols are even weaker than the encryption. Think layers of leaks rather than layers of security!

Focusing on the weakness is missing the whole point of the product. For the chip maker the product is good if it sells in large numbers (100M/year), it is great if it creates some form of customer lock-in and it is fantastic if it also has Gross margins above 70%.

The entire Automotive market in US is only about 13M cars per year, so even if every car has an immobilizer and you get 30% share it is only about 4M cars (maybe 8M key fobs / year). The chip to read / decrypt sell for about $0.50 USD. generating about $0.25 gross profit per unit.

Total gross profit = 4M * $0.25 = $1MUSD /yr

This is only enough profit to support 2 engineers, 1/2 programmer (FAE), 1/2 Marketing eng. ($600KUSD costs)

best case net profit = $400K USD / yr

In case you missed it there are ZERO cryptographers on the payroll.

The right question to ask yourself is:
Why would a chip maker bother to increase on chip algorithm security when the framework and protocols have more leaks than the US state department?

frizzen • December 23, 2010 9:09 PM

A car’s VIN number is like your social security number (and more). It is a serial number (like your social security number) but also encodes a lot more data about the make, model, and major factory options.

How many discussions of have there been about problems with misuse of SSNs? Change a couple of words and many of the apply to VIN numbers.

Nick Waters • December 23, 2010 9:53 PM

Please explain why it is so critical that this system be unhackable? Isn’t the concern a bit overblown since probably 99.99999% of potential thieves wouldn’t even have a clue?

Davi Ottenheimer • December 23, 2010 10:01 PM

“Total gross profit = 4M * $0.25 = $1MUSD /yr. This is only enough profit to support 2 engineers, 1/2 programmer (FAE), 1/2 Marketing eng. ($600KUSD costs) .”

Oh, you mean USD$600K covers four FTE for one year to make a product that one USD$5-10K test will render worthless?

How much net profit on the rewrite?

Davi Ottenheimer • December 23, 2010 10:16 PM

“From the article: the VIN is “usually” printed on the car? Um, it’s always printed on the car, in several readily visible places, as is legally required (at least in the USA. I can’t imagine it’s much different in any developed country).”

Heh, I guess you are in the USA?

I have in my mind a cartoon with someone saying: “Look, we got VIN numbers. We developed”

A country’s development is often measured on health or education, but on VIN numbers? That’s a new one.

The VIN is based on ISO 3779, a global standard adopted by the USA in 1980.

The standard is not only public, it’s easy to figure out about half the digits from a distance — just by looking at some cars.

Jon • December 23, 2010 11:08 PM

You are correct in that I am in the USA.

What I had in mind was that in some countries enforcement may be completely non-existent and therefore the law, even if it is on the books since the last revolution, is irrelevant.

If you scrape all the VIN placards and stampings and stickers off a pickup truck in southern Sudan, then put a 50-caliber machine gun on a tripod in the bed manned by people who know how to use it and will cheerily do so, I don’t think anyone is going to have a problem with the lack of visible VIN.

And VINs have been around in the USA for a lot longer than that. My 1971 Mustang has a VIN, although it’s much shorter than my other cars’, and probably doesn’t conform to ISO 3779, it’s good enough to uniquely identify her.

Points if you can guess it… 😉

J.

Clive Robinson • December 24, 2010 12:29 AM

@ Davi,

“How much net profit on the rewrite?”

Err do you mean “re-chip” many of these devices are so cheap they don’t have the real estate for a CPU&memory. At best a simple state machine…

@ Bruce,

If you look a bit further in New Scientist you will see another article which might “blow your socks off” even more. Have a look past the dull article on cracking the MS Kinect (p22) onto “The application ‘fighter jet’ has unexpectedly quit…” (p24).

It’s a fascinating and all to brief article on “phoney” MIL spec chips and other frauds in the semiconductor industry (a bit like phoney pharmaceuticals, aircraft parts etc).

@ Robert T,

Yup no cryptographers and not really any engineers either (think under grad interns on their summer “work experiance”). The simple fact is they pull from a standard library of bits a block of gates. They have no more idea what’s inside there than the marketing droid and probbably a lot less than the “out sourced” Chinese janitor 😉

A horror story from when I worked in FMCE, one ot the “costs” on a production line is soldering and cutting of links, especially if it’s a product ID number used for security such as in cordless phones (remember those 😉

Well the MD aproached me one day and asked me to cast my eye over the “software random number generator” the Korean “engineers” had come up with because it was failing on the production line very badly.

As I glanced at the machine code I quite litterly said “WTF were they thinking”. He looked some what shocked and I explained briefly by doing a pencil and paper walk through with him.

What the Korean’s had done was take the uninitialised or “power up” values of three bytes (a very bad idea) and then applied random looking logic which had a very high percentage of “AND’s” with magic numbers in it. After the quick walk through the MD understood why at best they where only getting 128 random numbers not the 16million they thought they would get…

For those a bit rusty on their logic the AND function reduces to zero as can be seen from it’s truth table

AB:Q = {00=0, 01=0, 10=0, 11=1}

The OR function reduces to one,

AB:Q = {00=0, 01=1, 10=1, 11=1}

Importantly neither function is reversable that is knowing one of the inputs and the output does not uniquly identify the other input.

The XOR function has a balanced output however it is reversible and the output is also linear,

AB:Q = {00=0, 01=1, 10=1, 11=0}

You can make lattices or matrices of gates that are nearly balanced and also nonlinear with a mixture of AND and OR gates but it is generaly very wasteful (four bits of input, 2AND, 1OR to get 1 bit of output of 9:7 zeros to ones).

To get around this inefficiency people tend to use bits twice which can make a psuedo XOR function within the matrix giving linear and reversible behaviour thus leaking input state in the output which is not desirable in a crypto function.

There are some basic design rules you can work out to assist in the design of a nonlinear matrix but these tend to magnify the inefficiency and slow down the potential output rate and also increase side channel issues (time and power spectrum).

It is one of the reasons NESSIE did not originaly produce a good stream cipher (SNOW2 was about as good as it got at the time).

For those who want to know more have a look at,

http://homepages.ucalgary.ca/~hahmadi/index_files/snow_CSICC.pdf

salach • December 24, 2010 1:03 AM

I think you are all missing the real point, which is an economical one.
I am quite sure car makers put encrypted immobilizers in cars not against thiefs but rather against independent locksmiths. Losing a modern car key is very painful and they charge you an arm and a leg for a replacement key. The meaning of all this: a significant aftermarket.
now who is going to benefit from this aftermarket? if keys are easy to duplicate then you will probably go to the nearest locksmith and do it. If keys are hard to duplicate then you have to go to an authorised mechanic and pay half your monthly salary for the new key.
I really dont think car thiefs bother with cracking the keys at all. They just break into your house to get the keys, connect their own ECU, tow your car etc.
Bottom line: they have a lot of low-tech workarounds. A rise in car theft should probably be attributed to the emergence of a well organized gang of car thiefs, rather than the thiefs becoming more sophisticated.
Several generations of immobilizers were quite easy to duplicate and/or crack the protocol between them and the ECU but still car theft was declining.

Davi Ottenheimer • December 24, 2010 2:11 AM

“If you scrape all the VIN placards and stampings and stickers off a pickup truck in southern Sudan…I don’t think anyone is going to have a problem with the lack of visible VIN.”

Meh, no one seems to have a big problem with it in America. A friend of mine used to drive what he called a “classic” car from the 70s around NYC. It had mis-matched and missing numbers, but he just called them upgrades and he never had any trouble.

American car identification, before the 1980s, was easily forged and mangled since it lacked integrity control, like the check digit in the ISO-standard VIN. The check prevents random numbers, but it is still easy to duplicate a VIN (no confidentiality control)

Anyway, those dealing the most with enforcement in the US tend to be classic car restoration shops or stolen-car operations. A group like the one you describe, a few guys and a gun, probably would not run into any problems.

If you’re saying that countries that don’t strictly enforce VINs are less developed, well, I’d like to see evidence of that correlation. Until then, measures of education and healthcare make the most sense to me

http://www.flyingpenguin.com/?p=8654

Woo • December 24, 2010 2:34 AM

“an arm and a leg for a replacement key”? Your body parts must be rather cheap then.. or your dealer is ripping you off.
The last time I broke one of the keys to my BMW, it cost me roughly 50E (~70$) for a new one.. and that included about half an hour tech service to transfer the driver settings stuff to the new key. Sure, more expensive than cutting a new standard metal key, but still reasonable.

Danny Moules • December 24, 2010 3:24 AM

“In case you missed it there are ZERO cryptographers on the payroll.”

…and yet they’re still rolling their own implementations and ALGORITHMS? There’s an easy, cost-effective solution to this: Use what everyone else does. The free, tried, open and tested stuff.

Hospitals don’t ‘roll their own’ medicines. They don’t need pharmacologists on their staff! (though, like having a cryptographer on your staff, it is helpful when somebody screws up).

RobertT • December 24, 2010 3:26 AM

@Clive
“these devices are so cheap they don’t have the real estate for a CPU&memory. At best a simple state machine…”

Actually you are wrong they are all based on low end microcontrollers something like 6809, 8051 or PIC. Usually the program is stored in on chip Flash memory (usually about 4k bytes). The whole core including RAM 256byte and Flash has a a die area of about 1mmsq in a cheap process (say 0.18 micron)

The reason for using Flash is that the total unit volume of 4M units is too low to bother with masked ROM’s and not every car maker wants exactly the same program or interface. They also like the idea that Ford keys do not work in GM cars and generic keys do not work in either. There are bits in the protocol to identify that the chip is a genuine GM product. They care more about these “value adding” features than crypto security.

Dirk Praet • December 24, 2010 4:39 AM

“And a Texas Instruments spokesperson argues that in some cases the firm’s proprietary cryptographic systems have been shown to be stronger than AES.”

Security through obscurity ? What we do ourselves, we do better ? Kinda proves again that when you start from a false premise, then get your method wrong too you are bound to fail in the end.

“Convincing car-makers to adopt the new systems remains a challenge, says Juels. He thinks they still believe hacking is a minor problem compared with more direct ways of stealing cars.”

Hacking is a minor problem. For sure. In an age where 16-year olds can use DDOS-tools found on the internet to bring down major sites and every major government is preparing for cyber warfare, this totally makes sense.

RobertT • December 24, 2010 8:22 AM

@Danny

“…and yet they’re still rolling their own implementations and ALGORITHMS?”

It appears that you believe there is value in the strong cryptography, but that does not mean that the chip makers or their customers car makers agree!

The chip guys want non-standard proprietary methods because it provides some customer “lock-in”. The rest of the system, is designed around the implemented protocol so there are patents about what was implemented and over time this becomes the standard.

The car guys don’t really care, any crypto regardless of how insecure will defeat your average doped-up car thief. Professionals thieves will always be able to overcome whatever security you implement, worst case they’ll just use a tow truck.

As I said originally, there are such massive holes in the security of the automotive comms protocol, that fixing the on chip crypto is the least worrying aspect.

d&d • December 24, 2010 9:04 AM

The last six numbers of the VIN used to be used as a code for the key bitting or in some cases, it was the bitting expressed in the clear.
I think they changed that a while back.
So the functions of the Vin number have changed over the years.

Nick Waters • December 24, 2010 10:23 AM

Again, what is the real issue here? In practice, does this security issue mean anything to the consumer?

Jon • December 24, 2010 2:10 PM

Alas, the numbers in my Mustang don’t match, either. It’s a pity; She’d be worth a lot more if they did, but there’s a different (bigger) engine in her now than what she came off the assembly line with.

Also see above boolean logic: If A (Country developed) Then B (The law cares about VINs) does not imply If Not A Then Not B. A statement about developed countries says nothing either way about undeveloped countries, whatever criteria you choose for ‘development’.

Another example: If A (is a helicopter), then B (it can fly). If A is not a helicopter, that says nothing about whether it can fly or not.

Provided, of course, that the helicopter works. But you get the idea.

J.

Jon • December 24, 2010 2:20 PM

Just as another aside, there is a significant secondary trade in VIN numbers. Hopelessly wrecked antiques are often bought just for the VIN, which is then put on a replica as a ‘restoration’, which grants the replica legitimacy as a true antique, not a completely new car.

This makes a huge difference legally, as a restoration only has to comply with the laws in effect when it was built, has exemption from smog regulations, is permitted to carry certain ‘Classic’ registrations, is allowed to compete in certain ‘Classic’ events, &c. &c. &c.

J.

Thomas • December 24, 2010 5:43 PM

Seasons greetings, and here’s hoping for a speedy recovery for all sufferers of VNS(*) syndrome.

Thomas

(*) VIN Number Syndrome

David Schwartz • December 26, 2010 5:54 PM

“Please explain why it is so critical that this system be unhackable? Isn’t the concern a bit overblown since probably 99.99999% of potential thieves wouldn’t even have a clue?”

You don’t need a clue to exploit a weakness. All you have to do is take someone else’s packaged exploit and learn how to use it.

There are many examples of exploits that weren’t fixed for years because of a belief that it would be too difficult to exploit them until someone did the hard work and released a packaged exploit that didn’t require any significant knowledge to deploy. Firesheep is a good example.

David Schwartz • December 27, 2010 5:41 PM

“Again, what is the real issue here? In practice, does this security issue mean anything to the consumer?”

Do you want to be the person to find out? People said the same thing about cookie hijacking issues, and then Firesheep came out.

To attach a system you have to first find a vulnerability and then figure out how to exploit it. Usually the first part is the harder part. If that’s already done, all that’s left is the second part.

Jonathan Wilson • December 30, 2010 10:30 PM

For a lock system (on a car or otherwise) couldnt you have a unique shared secret stored on both the lock and key and then do something like this:
1.Call the shared secret x
2.The lock generates a random number, call it y and sends it to the key.
3.The lock and key both calculate z = f(x,y) where f is a function such that given y and z its impossible to calculate x short of brute forcing it.
4.The key sends z to the lock which compares it with its own caluclation of z and if they match, unlocks (e.g. opens the car, starts the engine etc)

A good cryptographically secure MAC function should work just fine for this idea.

Unless you can obtain the key (and obtain x from it) or force the lock to use a known value for y (and have a rainbow table for x) then the only way to crack things is to sniff a y and z pair and then brute force x.

In any case this shows yet again why writing a custom encryption algorithim instead of using a well-tested off-the-shelf algorithim is a bad idea.

RonW • December 31, 2010 12:36 AM

I have worked on 3 such systems. The first time, my company was only supplying the security ECU, with a different company supplying the electronic keys. The algorithm the OEM imposed on us was a farce, but we had no choice but to implement it. The second time, we supplied both the ECU and keys, so we could implement what we wanted. We managed to fit an implementation of Blowflish into the key’s micro. Unfortunately, we had no control of the algorithm used to “talk” to engine ECU, so that was still a joke. The 3rd one, we persuaded the OEM to let us send our crypto source code to the engine people. They used it. Our new “handshake” between the ECUs worked as we intended. Sadly, there was still a hole: The diagnostic specification for the engine ECU did not state that reading the parameter storing the secret key in the engine ECU required secured access.

RobertT • December 31, 2010 1:48 AM

@Jonathan
Good idea BUT you are ignoring key power!

For real systems the key must work for at least 5 years off a single Li button cell.
This power restraint is one of the main reason for weak cryptography in the link.

Generally power restraints mean that the Key generates the Random Number, or just uses an incrementing code that is known to both key and lock. In the simplest systems this code is just a suitable length LSFR with a known starting index .

When a function f(x,y) is used the function is often trivial, so that the key chip can easily calculate f(x,y) with very little cpu power (and a small RAM space).

If you want to understand the power problem , Look at minimum power implementations of AES, multiply this by say 10 key presses per day. Now divide the total amp-hour of a suitable battery by the power/day to get an idea of the number of days of battery life.

Low calculation Power is the main reason that Elliptic Curve Cryptography is so interesting for this type of application.

BTW

When Lock to key comms are needed, they often happen with sufficient Tx power that the Key’s Rx signal, at the antenna causes “digital logic” levels on at the chip. This is similar to RFID comms. This means the key does not require a sensitive power hungry LNA and limiter.

Last point: better crypto means longer length codes = more power AND a lower chance of error free reception, for the same average Tx power. So there are lots of reasons why the simple incrementing LSFR solutions with 40bits Tx code are still the most practical.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.