Extracting a 3DES key from an IBM 4758

Part 5: How the attack works

The IBM 4758 with its CCA software is widely used in the banking industry to hold encryption keys securely. The device is extremely tamper-resistant and no physical attack is known that will allow keys to be accessed.

Clearly, if you hold sufficient permissions then you can extract the encryption keys via software means. The CCA software is designed to ensure that two or more people must combine their permissions before security sensitive procedures will be allowed. Our attack succeeds with very limited access permissions and does not require collusion with other people.

Communications to and from a branch will be encrypted with "triple DES" (3DES) keys that are shared between the two ends of the link. For example, cash machines (ATM) will need to communicate with a central system to validate customer PINs and thereby establish if a bona fide request for money is being made.

When a 3DES key is to be changed the central computer will cause a new key to be generated securely within its IBM 4758. It actually makes two separate values (called "key parts") which can be exclusive ORd (XORd) together to produce this key. These two key parts are printed on a secure printer (perhaps onto sealed, tamper-evident line printer forms) and given to two of the bank's security officers. The security officers travel to the branch and each types in their key part and destroys their piece of paper. The branch's IBM 4758 now XORs the two key parts together to reconstruct the 3DES key. Communications may now be done using a 3DES key that is entirely secure. The security officers cannot determine the value of the key unless they collude with each other and the key has never existed outside the physically secure confines of the cryptoprocessor modules.

In order to "steal" this valuable 3DES key we arrange for it to be exported from the branch machine. The CCA software will allow this export -- provided that the 3DES key has been encrypted with another securely held 3DES key. The CCA software's security design relies upon us not being able to learn such a 3DES key. Our attack involves using some "sleight-of-hand" to create a 3DES "exporter key" in such a way that we do know its value.

But first, let's start at the beginning! Our attack requires that we begin by learning the value of a "single DES" data key that is supposedly unknown to us. So we write a program to do the following tasks and load it into the IBM 4758.

Step 1:	Create a single DES key part of unknown value. Creating a key part requires permission to run the "generate" command. If this is not available, then you can get the same effect by presenting a random chosenly token which the system will decrypt to a unknowable value. Many such values will have incorrect parity, but a little perserverance in repeating this action will eventually yield a usable value.
Step 2:	Create a single DES key part of value 0.
Step 3:	XOR these two key parts together to create a DES data key Step 3 requires an access permission called Combine_Key_Parts. It isn't possible to transfer keys to branches without this permission being held by someone at the branch.
Step 4:	Encrypt zero (the simplest possible data value) with the data key and display the encrypted value.
Step 5:	Repeat steps 2 to 4 for values 1..16383 There are a few implementation details in step 5 to do with parity bits on the DES key and creating more that 16384 values to allow for the 64->14 value hashing function in the FPGA design -- but they merely obscure the simplicity of what is being done here and so they've been omitted.

This set of tasks less than 10 minutes to run, and at the end of them we have 16384 different encrypted versions of zero. We can then use our FPGA design to crack these values in parallel. With average luck then one of the values will be found after about 25 hours. By seeing which value it is, we can determine which value (from 0 to 16383) was involved -- and hence we have determined the "unknown" value from Step 1.

We now know the value of a data key within the IBM 4758. However, the attack is not yet over, because a mere data key is not permitted to export the secret keys we want to steal. Some more work is needed.

This set of tasks, 7 to 11 (which bear considerable resemblance to steps 1 to 5) also takes about 10 minutes and can be done immediately after steps 1 to 6 as part of the same session. When they are complete, we will have 16384 different encrypted versions of the single DES key made at step 6.

As soon as the FPGA cracking operation described above has been completed we will know the value of the step 6 key. We can then use the FPGA board for a second time, using the step 10 data in order to determine the unknown value of the replicate key part we made at step 7.

Note that since the keys we made at step 9 were exporter keys we were not allowed to encrypt data with them -- hence we couldn't just encrypt zero as we did in the first part of the attack. This explains why the first part of the attack was necessary -- we needed a known key value to use in the second part of the attack.

ie: we've stolen any and all of the secret keys that are held inside an IBM 4758 running the CCA software and all we needed was:

• about 20 minutes uninterrupted access to the device
• the Combine_Key_Parts permission
• an off-the-shelf $995 FPGA evaluation board
• about two days of "cracking" time

Oops!

To be strictly accurate, some detail has been skated over in Step 14. You can only export some keys from the IBM 4758 because the CCA software may only have marked some keys as exportable. If the keys you want are not marked this way then you'll need to do a bit more work. You'll need to create a random importer key (ensuring that it is exportable!) and export it. Once its value is known (ie once you've finished all the above steps) then you can reimport keys you have previously observed being imported and can typecast them to "exportable" during this importation. The details are rather messy and are left as an exercise for the interested reader.

Next part: Some real results
Previous part: How the DES cracker works