Dismantling Megamos Crypto: Wirelessly Lockpicking a Vehicle Immobilizer

The Megamos Crypto transponder is used in one of the most widely deployed electronic vehicle immobilizers. It is used among others in most Audi, Fiat, Honda, Volkswagen and Volvo cars. Such an immobilizer is an anti-theft device which prevents the engine of the vehicle from starting when the corresponding transponder is not present. This transponder is a passive RFID tag which is embedded in the key of the vehicle.

In this paper we have reverse-engineered all proprietary security mechanisms of the transponder, including the cipher and the authentication protocol which we publish here in full detail. This article reveals several weaknesses in the design of the cipher, the authentication protocol and also in their implementation. We exploit these weaknesses in three practical attacks that recover the 96-bit transponder secret key. These three attacks only require wireless communication with the system. Our first attack exploits weaknesses in the cipher design and in the authentication protocol. We show that having access to only two eavesdropped authentication traces is enough to recover the 96-bit secret key with a computational complexity of 2⁵⁶ cipher ticks (equivalent to 2⁴⁹ encryptions). Our second attack exploits a weakness in the key update mechanism of the transponder. This attack recovers the secret key after 3×2¹⁶ authentication attempts with the transponder and negligible computational complexity. We have executed this attack in practice on several vehicles. We were able to recover the key and start the engine with a transponder emulating device. Executing this attack from beginning to end takes only 30 minutes. Our third attack exploits the fact that some car manufacturers set weak cryptographic keys in their vehicles. We propose a time-memory trade-off which recovers such a weak key after a few minutes of computation on a standard laptop.