# Specification of the Megamos crypto algorithm

It has recently emerged that a paper that was scheduled to appear at Usenix Security 2013, titled "Dismantling Megamos Crypto: Wirelessly Lockpicking a Vehicle Immobiliser", has been censored according to a newspaper article in the "Guardian".

A court in the UK issued a temporary injunction barring the scientists from publishing their paper. Based upon the newspaper article, it sounds like the paper describes how to break Megamos, a crypto algorithm that is used in several luxury cars — "including Porsche, Audi, Bentley and Lamborghini".

That same newspaper article indicates that software for Megamos has been available on the Internet since 2009.

• Does anyone know what the Megamos algorithm is?
• Is there a specification of the algorithm that is publicly available, or any publicly available code that implements it?
-
Funny, I had seen on the usenix security page that the paper was presentation only. I was wondering why that was the case. – mikeazo Jul 27 '13 at 1:14
Timo Casper says in his 2011 PhD work (page 265 c.5.2) that Sokymat Magic/Megamos Crypto were not reversed to full description of protocol or encryption. – osgx Jul 27 '13 at 3:13
A jealously guarded proprietary cryptosystem was broken? Color me SHOCKED, you guys. – pg1989 Jul 27 '13 at 5:15
The article is badly written - it really doesn't make clear what it means by "code(s)". Does it mean the algorithm? Or as per a lot of these secret algorithms, is there a key that is common across all cars? – Cybergibbons Jul 27 '13 at 8:39

As cybergibbons notes in his answer, the court decision itself is quite interesting reading. In particular, while the details of the "Megamos algorithm" itself are obviously not given in the court decision, the manner in which it is used is described in a surprisingly clear manner in 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."

Translated (back) into standard crypto terminology, it appears that the "Megamos algorithm" is an (evidently failed) attempt to implement a pseudorandom function family (PRF).

Specifically, the authentication protocol described in the paragraphs above can be rephrased as follows:

Both the car computer $\rm C$ and the transponder $\rm T$ hold a shared secret key $K$ and a pseudorandom function family (implemented using the Megamos algorithm) $\sf PRF$, of which ${\sf PRF}_K$ is a specific instance parametrized by the key $K$. The PRF outputs a bitstring that is split into two parts, $F$ and $G$. To perform an authentication exchange:

1. $\rm C$ chooses a random number $r$ and computes $(F,G) = {\sf PRF}_K(r)$.
2. ${\rm C \to T:}\ r, F$
3. $\rm T$ computes $(F',G') = {\sf PRF}_K(r)$ and aborts unless $F = F'$.
4. ${\rm T \to C:}\ G'$
5. $\rm C$ verifies that $G = G'$.

Now $\rm C$ and $\rm T$ have verified that they can each compute ${\sf PRF}_K$, and therefore hold the same key $K$.

An interesting feature of this protocol is that, since $r$ is chosen solely by $\rm C$, an attacker who manages to eavesdrop on a legitimate exchange could easily impersonate $\rm C$ by replaying the earlier $r$ and $F$, and could even verify $\rm T$'s response by comparing it with the earlier $G$. Under the expected usage scenario, this might not be considered a major security risk, since the important part is presumably authenticating $\rm T$ to $\rm C$; on the other hand, since the protocol evidently does try to also authenticate $\rm C$ to $\rm T$, it might simply be that the summary above is incomplete, and that the actual protocol uses some additional mechanism to prevent such replay attacks.

That said, other than the flaw described above, the protocol seems solid provided that $\sf PRF$ is indeed a secure pseudorandom function family. In particular the assertion in the court decision that "[f]or the process to be secure, both pieces of information need to remain secret - the key and the algorithm" appears patently false: if the algorithm were a secure PRF, such as, say, AES-CMAC-PRF-128, the protocol described above would be secure as long as just the key $K$ was kept secure.

Indeed, the same holds regardless of the details of the protocol: by definition, any instance of a secure pseudorandom function family is indistinguishable from a truly random function, as long as one does not know the key used to choose the instance. Thus, by definition, the choice of the algorithm, or the manner in which it is used, does not matter as long as it's a secure PRF: they all look identical to anyone who doesn't know the key. Indeed, there are many published and freely usable PRF algorithms that have withstood extensive public scrutiny and cryptanalysis, and are in common use worldwide. By failing to publish their own algorithm (or to use one of the already published algorithms), the makers of the Megamos Crypto chip have not only violated Kerckhoffs' principle, but also deprived themselves of this scrutiny by the global crypto research community.

All that said, I can easily enough understand why they may have chosen to do so: the Megamos Crypto chip is designed to be embedded into a car key, with all the attendant limitations on memory capacity and power consumption. Implementing standard crypto primitives like AES on such small, low power devices is often a challenge, and of the few crypto algorithms specifically designed for such devices, most are new and still poorly analyzed, not to mention that even the published designs often end up making questionable tradeoffs in speed vs. security. The designers of Megamos Crypto may have been hoping that, by designing their own algorithm and keeping it secret, any security weaknesses it may have might not be so easily exploited.

Alas, Kerckhoffs' principle has a habit of reaffirming itself: if there's profit to be made in discovering the algorithm, someone will do so and profit from it. Indeed, based on the court decision, in this case this appears to have happened long ago, by 2009 (when the algorithm was included in the Tango Programmer tool, sold for €1000 by a Bulgarian company and described in the court decision as being of "clearly murky origin") if not earlier.

By the way, the court decision even quotes some interesting parts of the redacted paper, including the following, which sheds some light on the nature of the weaknesses discovered in the Megamos algorithm:

"Unfortunately, our first attack is hard to mitigate. It seems unfeasible to prevent an adversary from gathering two authentication traces. Furthermore, this attack exploits weaknesses in the course of the cipher's design - e.g. the size of the internal state. It would require a complete re-design of the cipher to fix these weaknesses. To that purpose, lightweight ciphers, like grain, and so on, have been proposed in the literature and could be considered as suitable replacements for the Megamos Crypto. On the positive side, our first attack is more computationally intensive than the attacks in section 6 and 7, which makes it important to take the aforementioned mitigating measures in order to prevent the more inexpensive attacks."

Earlier in the text, the defendants also note in their case (paragraph 19(xiv)) that:

"The attack based on the Megamos Crypto algorithm still requires the criminals to have a car, plus a key, plus two days to use a computer program which tries out a lot of possibilities."

From the phrasing, and from the suggestion of Grain as an alternative, it appears that the "Megamos algorithm" may in fact be some kind of a stream cipher. This does make sense, insofar as, with the input somehow combined with the key, a stream cipher may be regarded as PRF with arbitrary-length output. Stream ciphers, despite their limitations as crypto building blocks, also still remain very popular as crypto primitives for low-end systems.

The attack itself appears to be some kind of a related-key attack based on comparing the output of the cipher for two different random nonces (which are made known during the authentication process) and presumably involving some kind of "informed brute force" enumeration of the internal cipher state in order to recover the secret (fixed) part of the cipher key. Or at least, that's what it looks like based on the court decision.

-
Awesome answer. I wonder if someone taking a look at the software would leak more information without having to do any RE? – Cybergibbons Aug 9 '13 at 7:51

From the court decision, we find out that the researchers didn't in fact reverse engineer the key transponders themselves, but a piece of software called "Tango Programmer" which is a third party tool (software and hardware) used to make transponders.

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 the manufacturer's 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.

There are other tidbits of information in the court proceedings, I suggest reading them as there may be something of greater interest. They very strongly promote the school of thought that security through obscurity is valid.

Last but not least, there is a small article on EFF about the legal implications of the gag order.

-
1. ## “Does anyone know what the Megamos algorithm is?”

Yes. According to http://www.bicotech.com/doc/megamos_cr.pdf (PDF) — which provides the best description from my point of view — the Megamos crypto is:

MEGAMOS CRYPTO Read-Write High Security Device - Memory organisation

Description

The MC is a high security Read-Write RFID Transponder. A challenge and re-sponse cryptoalgorithm with 96 bits of user-configurable secretkey contained in EEPROM are implemented in the device.

A freely programmable USER-MEMORY of 30 bits and a unique device identification of 32 bits are characteristic of the Magic. Bits 15 and 14 of word 1 are used as Lock-Bits. At delivery, these two bits have the contents " 10" which is the requirement for writing and erasing the memory. Data transmission to the transceiver is performed by mdulating the amplitude of the electro-magnetic field. Receiving data and commands takes place in a similar way.

Features

• On Chip Crypto-Algorithm (Challenge & Response)
• Two Way Authentication
• 96 bits of Secret-Key in EEPROM (unreadable)
• 32 bits of fix Device Identification
• 32 bits of USER-MEMORY (UM) with read access (OTP)
• Secret-Key programmablecia CID-Interface
• Lock-Bits to inhibit programmation
• Data transmission performed by Amplitude Modulation
• Bit period = 32 periods of carrier frequency
You might want to read the complete PDF, as I've spared myself typing the "Memory Organization" part.

2. ## “Is there a specification of the algorithm that is publicly available, or any publicly available code that implements it?”

I can't give you a direct link to a paper which holds the specification of the crypto, since I am pretty sure that paper is not widely available to the general public in the first place.

Related publications that you should read are:

### How MEGAMOS works

To explain how the crypto works internally, let me simply quote that cybergibbons website as they've got it wrapped up pretty nicely: part of the answer by Ilmari Karonen*

* My original quote attributed the wrong person. Obviously, cybergibbons copy-and-pasted the quoted part into his website without proper attribution pointing to the original author – Ilmari Karonen’s answer, which resulted in me crediting the wrong person.:

A car $\text{C}$ and a transponder $\text{T}$ share a secret key K. A pseudo-random function family $\text{PRF}$ is keyed using key K i.e. $\text{PRF}_K$. The output from this PRF is split into two parts F and G.

• $\rm C$ chooses a random number $r$ and computes $(F,G) = {\sf PRF}_K(r)$.
• ${\rm C \to T:}\ r, F$
• $\rm T$ computes $(F',G') = {\sf PRF}_K(r)$ and aborts unless $F = F'$.
• ${\rm T \to C:}\ G'$
• $\rm C$ verifies that $G = G'$.

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.

### Code that implements it

I'm not sure why this question comes up. We have strong crypto that is secure, fast, and well-vetted. I don't know why one would want to fiddle with a crypto that is known to be weak (if not broken). At least 3 attacks are currently known and described in the publications I've linked to above.

But, if you really think it is wise to catch a falling knife…

Ignoring the fact that there are some legal restrictions which might boomerang into your face if you publish the algorithm (I am not a lawyer, so what do I know?), no one is stopping you from getting the software you need. Simply put some cash on the table and try to buy “Tango Programmer” including the needed hardware, and reverse the algorithm… (been there, seen it, laughed out loud, then closed the case on the Megamos algoritm — from my point of view, it's a waste of money).

-
Just for posterity, let me note that the protocol description that you quote above, via the cybergibbons website, appears to be originally quoted (without attribution, alas) from my answer to this question. (The cybergibbons version also has what appears to be a minor editing mistake in the second-to-last step, where it reads ${\rm T \to C}: r,G$ instead of ${\rm T \to C}: G'$, but you seem to have fixed that.) – Ilmari Karonen Jan 14 '15 at 20:10
@IlmariKaronen Ugh… thanks for the heads-up. I honestly didn’t notice that. Of course, I immediately corrected things. As said – thanks +1 (I’m really sorry for not having detected that myself). – e-sushi Jan 14 '15 at 21:46