If you skipped today’s crypto news, you missed some good press for David Oswald and Christof Paar’s recent side-channel attack on the Mifare DESFire MF3ICD40 chip.* I’m hardly an expert on side-channel attacks, but being uninformed has never stopped me before, and I figured it might be fun to read the paper and talk about this very neat attack.

What’s the DESFire MF3ICD40 and where is it used?

Clipper card.

The MF3ICD40, henceforth “MF3”, is a capable little chip.  It’s a Radio Frequency Identification (RFID) device, meaning that it communicates wirelessly with a reader — e.g., a Clipper card turnstyle.  It can store a certain amount of information and retrieve it on demand.  Like the DST chip I mentioned in an earlier post, every MF3 contains a cryptographic key and a cipher, which it can use to (among other things) perform a challenge/response authentication protocol.

Unlike the DST, the MF3 uses a pretty reasonable cipher for its authentication protocol. Specifically, it employs Triple-DES with a 112-bit key.  While 3DES is definitely getting a bit long in the tooth (it’s been deprecated in FIPS), it’s not thought to be vulnerable to any truly practical attacks.  Nor, to the best of my knowledge, is there anything wrong with the way that the MF3 uses 3DES.

So if the crypto is ok, what’s the problem?

Just like the DST, the MF3 chip contains no internal power source.  Instead, power for the chip is extracted from a magnetic field generated by the reader.  This is mostly a good thing — by powering the chip this way, the designers were able to dramatically reduce its size and cost.  Moreover, you don’t need to replace your MF3 when some crappy battery dies.

Unfortunately, the use of an external power source opens the device up to a special class of side-channel attack known as Correlation Power Analysis, or CPA.  Since the MF3 draws power from the reader, a malicious reader can actually tell — from moment to moment — how much power the device is using.

Ordinarily this wouldn’t be very interesting. However, if you know exactly how the device performs the computation, and you can repeatedly measure the device’s power consumption while sending it carefully crafted input values, you can actually learn quite a lot.  Specifically, when the device encrypts (or decrypts) your chosen inputs, those power fluctuations can actually leak the bits of the cryptographic key.  In the case of MF3, you can obtain the full 112-bit key in about seven hours.

Isn’t side channel analysis pretty well known?

Yes, and that’s what makes this interesting.  With caveats.

Side channel attacks themselves are hardly a new thing.  The concept of using power analysis to attack cipher implementations was first proposed in CRYPTO ’99 by Paul Kocher, Joshua Jaffe and Benjamin Jun, all of whom worked for Paul’s company, Cryptography Research.  In a truly inspired move, Paul and his researchers turned around and patented the standard set of countermeasures to the very attack they had invented.  These countermeasures can be found in just about every high-security smart card manufactured today.

This story is important because the MF3 clearly didn’t have the latest and greatest hardware countermeasures built into it.  If it had, the Oswald and Paar attacks wouldn’t have gone anywhere. (Though interestingly, it did have one countermeasure, see below.)

This seems to be a common situation for a certain class of RFID devices, of which the MF3 is one.  These devices toe a funny line between “contactless smart card” (where SCA countermeasures would be expected) and “plain-old RFID” where security isn’t thought to be as important. Unfortunately, the people who select these systems may not realize this, and that’s when bad things can happen.

I should also add that — unlike a recent side-channel attack on KeeLoq — this attack does not require the adversary to physically crack open the device. It’s implemented purely via the EM field.

So how does the attack work?

This is clearly the crux of the matter, and unfortunately this is where I’m going to have to let you off with a warning.  Side channel analysis is just not my area, and there’s little I can offer here that would improve on reading the paper itself.**, ***

But to make a very short go of it, DES works by breaking the key up into smaller pieces called “subkeys”, each of which is used in a different round of the cipher.  Portions of these subkeys are combined with bits of of an attacker-supplied input and sent to a series of small functions called S-boxes.  Since only a few bits go into each S-box, there is a relatively small set of possible input values, each of which results in a slightly different power consumption profile.

By observing the power consumed when calculating these S-boxes on different inputs — both for known and unknown keys, and over many, many experiments — the attacker can correlate these traces to figure out the bits that come from an unknown key.  The full key recovery attack takes ~250,000 traces, which require about 7 hours to collect.

The most interesting aspect of the paper is that the authors didn’t actually know how the DES implementation in the MF3 worked.  Much of the paper is devoted to reverse-engineering the necessary details of the operation by examining power traces.  What’s most interesting about this discussion is that along the way, they discovered that the MF3 actually does implement a countermeasure to CPA — specifically, it randomly adds up to eight “dummy rounds” to DES. Unfortunately for the MF3, this protection was not sufficient to prevent the attack.

Figure from the Oswald-Paar paper.  These charts show the operation of the DES cipher  on several input values.  The authors used this information to reverse-engineer the operation of the device.

So what’s next for MF3?

A quick glance at the MF3 website will tell you that the manufacturer “has begun phasing out the MF3ICD40”, but that “orders … will continue to be taken until December 31st, so start planning your new year’s party now!” (Ok, I made up the last bit.) From here on out, it looks like it’s going to be AES-based cards all the way.

The note doesn’t specifically mention this attack, but I assume that’s what’s behind it.  If so, that’s a pretty good response for a manufacturer.  To pull a profitable card off of the market probably cost them quite a bit, but it protects their reputation, not to mention their customers.  Unfortunately, there’s no indication that the newer AES-based cards actually have stronger protections against side channel analysis; they’re just using a different cipher.  But I guess that’s what next year’s CHES is for.

Notes:

* This post brought to you by David Oswald and Christof Paar.  Breaking Mifare DESFire MF3ICD40: Power Analysis and Templates in the Real World.  In CHES ’11.

** This is an extended version of the conference paper that I read. Thanks to Bart Coppens for finding the link.

*** If you want to hear from people who do know their side channels, see Luke Mather’s excellent post on DPA and distinguishers from the Bristol Cryptography Blog.