Some of you might have read the stories going around a few weeks ago – “Scientist banned from revealing codes used to start luxury cars“. The short of it is that a security researcher has had a injunction imposed on him, preventing him from publishing a paper. The paper reveals security problems in the Megamos Crypto system used in the immobiliser system of many cars. Volkswagen are not happy – it really seems they want this shut down.

(As an aside, I hate the way that mainstream media refers to “codes” – it can mean source code, executables, an algorithm, or even a secret key. Often used interchangeably in the same article)

Details were a little scant, but last night the EFF passed comment, based on the court’s decision.

I am not a lawyer – I’m not going to pass judgement on the legal side. But what is interesting is how the researchers got hold of the Megamos Crypto algorithm. It wasn’t by decapping the chips in the transponders, it wasn’t from observing them black-box, it wasn’t from looking at an embedded software implementation – they took a Windows program used to clone car key transponders and reverse engineered that.

In terms of working out how Megamos was implemented, someone else had already done the hard work. This left the researchers to perform detailed cryptanalysis of the algorithm and – rumour has it – find some serious problems.

The piece of software is called “Tango Programmer“, a third party tool (software and hardware) used to make transponders. This has been available since at least 2009.

Tango Programmer is readily available, but it appears that it needs to be bought alongside a physical programmer. I strongly suspect that the software would be available on file sharing sites illegally, or possibly even legitimately on another site if you look hard enough.

Another company, Bicotech, produce a similar tool called RwProg. The software is downloadable from their website. The executable is packed, but I am sure it would be perfectly possible to reverse engineer the algorithm from the binary.

The court decision itself contains valuable information on Megamos as well, notably from paragraphs 4 and 5:

In detail the way this works is as follows: both the car computer and the transponder know a secret number. The number is unique to that car. It is called the “secret key”. Both the car computer and the transponder also know a secret algorithm. That is a complex mathematical formula. Given two numbers it will produce a third number. The algorithm is the same for all cars which use the Megamos Crypto chip. Carrying out that calculation is what the Megamos Crypto chip does.

When the process starts the car generates a random number. It is sent to the transponder. Now both computers perform the complex mathematical operation using two numbers they both should know, the random number and the secret key. They each produce a third number. The number is split into two parts called F and G. Both computers now know F and G. The car sends its F to the transponder. The transponder can check that the car has correctly calculated F. That proves to the transponder that the car knows both the secret key and the Megamos Crypto algorithm. The transponder can now be satisfied that the car is genuinely the car it is supposed to be. If the transponder is happy, the transponder sends G to the car. The car checks that G is correct. If it is correct then the car is happy that the transponder also knows the secret key and the Megamos Crypto algorithm. Thus the car can be satisfied that the transponder is genuine. So both devices have confirmed the identity of the other without actually revealing the secret key or the secret algorithm. The car can safely start. The verification of identity in this process depends on the shared secret knowledge. For the process to be secure, both pieces of information need to remain secret – the key and the algorithm.

In standard cryptography terminology:

A car and a transponder share a secret key . A pseudo-random function family is keyed using key i.e. . The output from this PRF is split into two parts and .

1. generates a random number .
2. calculates
3. 
4. calculates
5. checks that
6. 
7. checks that

This process means that the transponder believes the car knows the key and PRF, and the car believes the transponder knows the key and PRF. They should have authenticated themselves with each other.

What is a PRF? A pseudo-random function is similar in many respects to a psuedo-random number generator (PRNG), except instead of sequentially generating output, you can randomly access any of the outputs using an index (r in the example above). The key is analogous to the seed of the PRNG. Using a certain key, a given input will map to a determined output.

Importantly, the output of a PRF should be indistinguisable to an observer from a random function, and by extension you should not be able to derive the key even if inputs, outputs, or free access to the function is given. You should also not be able to tell which PRF is in use even if you can control the inputs and read the outputs.

So – if this is a secure, solid, verified PRF, the protocol should be secure, even if we know what the PRF is. The only thing that needs to be kept secret is the key.

But the court decision says:

The verification of identity in this process depends on the shared secret knowledge. For the process to be secure, both pieces of information need to remain secret – the key and the algorithm.

This suggests a few things:

1. The PRF used is not secure
2. They don’t know what they are talking about

Both are entirely possible, but I would strongly suspect that the PRF has issues and they want to keep it secret. This would be a clear example of “security through obscurity”.

How could a PRF be insecure?

• Using one or more input/output pairs, it might be possible to derive the key.
• You might not need a key to derive the output given the input.
• The key length might not be long enough to prevent bruteforcing.
• F and G might not depend on the whole key i.e. you might be able to calculate G given part of the key.

The protocol itself might suffer from further issues:

• There does not appear to be any protection from replay attacks (prevented from being used as a direct vulnerability because the authentication is bidirectional).
• Is the random nummber actually random? Does it matter if it isn’t? If they are re-used (i.e. it’s not a nonce), it probably does matter.
• The transponder can bypass the check for F = F’ – it can be a “yes” key. If we don’t need the entire key to compute G, this matters.
• The key might be constant across an entire line or make of cars. Recover the key from one transponder and there would be no secrets left.
• The key might be derived from an open piece of information like the car VIN number
• The key might be derived from something like the manufacture date/time of the car, massively reducing keyspace
• Probably a million more things

Let’s look at the attacks described in the court decision.

Firstly, note:

The attacks are not, themselves, trivial things to do. However, they allow someone, especially a sophisticated criminal gang with the right tools, to break the security and steal a car.

This makes it sound like some of these attacks are practical i.e. it won’t take 2 weeks of effort after decapping and reading the key from EEPROM.

Attack 1:

One attack relies on weaknesses in the secret keys that are used in certain cars. That “weak key” weakness arises because certain car makers have used weak secret keys which are easier to guess than they need to be. In effect, it is a bit like using the word “password” for a password.

As I mentioned above, there are a number of situations where the keys chosen might be poor. It might be the case that the researchers need 2 weeks to work out the key given a car and transponder, but then if the same key is used across all cars, it doesn’t really matter.

Attack 2:

Another is concerned with key updates. The details do not matter.

This is very vague.  Maybe you can alter or add keys easily if you already have access to the car?

Attack 3:

The third attack relates to weaknesses in the Megamos Crypto algorithm itself. The academics explain this attack in the paper, and, as I say, the paper also sets out the whole of the algorithm. It is these two elements that the claimants seek to prevent publication of. The claimants wish to remove the Megamos Crypto algorithm and information about the attack based on the weakness in it from the paper.

This is where we get to the point that it sounds like the PRF is not secure. It sounds like this attack may take days of work with access to both the car and transponder.

This could be like the insecurities found in Keeloq. The first step was determining the details of the algorithm. The first few papers detailed weaknesses that meant the protocol was insecure, but the weakness could not practically be exploited. After this, papers were released that detailed faster, more effective attacks, until finally we are at the stage where Keeloq can be called “broken”.

A quick look at some of the software

I haven’t got hold of Tango Programmer, but I do have RwProg up and running. Here is a screenshot:

What can we tell from this? Well, the crypto key looks to be 96bits long – too long to bruteforce.

There are a few videos as well:

http://www.youtube.com/watch?v=SKTMawm5Ffw

http://www.youtube.com/watch?v=EX4FuK1JUEE

Nothing really groundbreaking. I can’t see how the software reads and then writes the crypto key.

Conclusion

Regardless of the court decision, it looks like there is enough information out there for other people to start work on this. Download the software, maybe buy Tango Programmer, reverse the algorithm and then let the world loose on it!