A determined 'hacker' decrypts RDS-TMC

As told in a previous post, I like to watch the RDS-TMC traffic messages every now and then, just for fun. Even though I've never had a car. Actually I haven't done it for years now, but thought I'd share with you the joy of solving the enigma.[disclaimer 1]

RDS-TMC is used in car navigators to inform the driver about traffic jams, roadworks and urgent stuff like that. It's being broadcast on a subcarrier of a public radio FM transmission. It's encrypted in many countries, including mine, so that it could be monetized by selling the encryption keys.

A draft of the encryption standard, namely ISO/DIS 14819-6, is freely available online. Here's an excerpt[disclaimer 2] that reads blatantly like a challenge:

"After calling for candidate proposals [for a method of encryption], the submission from Deutsche Telekom was judged by an expert panel to have best met the pre-determined criteria the task force had established. The method encrypts the sixteen bits that form the Location element in each RDS-TMC message to render the message virtually useless without decryption. The encryption is only 'light' but was adjudged to be adequate to deter other than the most determined 'hacker'. More secure systems were rejected because of the RDS capacity overhead that was required."

TMC messages consist mostly of numeric references to a static database of preset sentences and locations; no actual text is being transmitted. The database is not a secret and is freely available. The location information is encrypted with a key that changes daily. Every night, a random key is picked from 31 pregenerated alternatives. The key is never transferred over the air, only its numeric ID (1–31). The keys are preprogrammed into all licensed TMC receivers, and they can decrypt the locations knowing the key ID.

The size of the key space is 2¹⁶ and the encryption algorithm consists of three permutation operations:

The algorithm is simple enough to be run using pen-and-paper hardware, and that's just what I did while creating the above crypto diagram:

The tricky part is that I don't know the keys. But there's a catch. To save bandwidth, only regional messages are transmitted. This limits the space of possible locations, giving us a lot of information about the encrypted data. Assuming all messages are from this limited region, we can limit the number of keys to a very small number, in the dozens.

The next day, we have an all new encryption key again. But there's another catch. Many messages persist over several days, if not weeks. These would be messages about long-lasting roadworks and such. We just need to wait for messages that we heard yesterday that only have their location code changed, and we can continue limiting the keyspace by collecting more data.

Once we've limited the keyspace to a single key, we can decrypt all of today's messages. When the key changes again, it is trivial to find today's key by knowing yesterday's key and comparing the locations of persistent messages; this is known as a known-plaintext attack or KPA.

Here's some encrypted data straight from the radio.

$ ./redsea.pl | grep TMC
══╡ TMC msg 00 1828 4400
══╡ TMC sysmsg 6040
══╡ TMC msg 00 1828 4400
══╡ TMC msg 07 8264 0294
══╡ TMC msg 07 8264 0294
══╡ TMC msg 07 8264 0294
══╡ TMC sysmsg 0021
══╡ TMC msg 07 5964 72ca
█

A little Perl script then decodes everything and even plots the affected segment on a little map. The screenshot is from a few years back.

Now I just need a car. Well, actually I prefer motorcycles. But I guess it would work, too.

Tools used: Ordinary FM radio, sound card, computer. All data is from public sources. RDS was decoded from intermodulation distortion in the radio's Line Out audio caused by the stereo demuxer circuitry.

Update 2014-07-27: Some news seem to highlight that I was the first one to break this joke of a cipher. This could be true; I don't really care. In any case, the often-referred-to 2007 work by Barisani and Bianco (PDF 13MB) was done on unencrypted RDS-TMC and no cryptanalysis was involved; "encryption is supported for commercial services but irrelevant to our goals". I encourage you to read it, it addressed some of the real-world security implications of injecting crafted TMC messages into cars.

---

Disclaimer 1: I will take this post down on the first appearance of any complaint from any party, of course. My intent is not malicious and I'm not even publishing any keys or code.

Disclaimer 2: This use of the above excerpt of the ISO standard is not an infringement of copyright as it is being used here under the doctrine of "Fair Use" of the United States Copyright Law (17 U.S.C. § 107), seeing as this blog is hosted on US soil.