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.

Step 6: Combine the unknown value from Step 1 with a known value so as to create a data key.
In step 6 we could re-use one of the values from step 3, but for tidiness we use a totally different known value. Note that this step can be done during the same session as steps 1..5, there is no need to wait for the "crack" to be completed. Step 6 needs the same Combine_Key_Parts permission as above.

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.

Step 7: Create a triple DES (3DES) "replicate key part" of unknown value.
A replicate key part has both halves of the 3DES key identical and it is used for interworking with legacy applications that can only handle DES encryption. Recall that with both halves of a 3DES key the same, 3DES encrypts exactly the same way as single DES.
 
Step 8: Create a 3DES replicate key part with both halves 0.
Step 9: XOR these two key parts together to create a 3DES exporter key
Step 10: Encrypt the data key created at step 6 with the exporter key and display the encrypted value.
Note that since the key being exported is a single DES key we are allowed to export it with a replicate 3DES key, since they are of equivalent strength. However, the secret keys that we want to steal are non-replicate 3DES keys and the CCA software will not allow them to be exported with a (far weaker) replicate key.
 
Step 11: Repeat steps 8 to 10 for values 1..16383 placed in each half of a replicate key part
Once again, as in step 5, there are a few implementation details relating to parity and the actual number of iterations.

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.

Step 12: Create a 3DES key part with both halves DIFFERENT but known.
Step 13: Combine this with the unknown replicate key part from Step 7 in order to create a 3DES exporter key with both halves different.
This is where the CCA software falls down. It allows us to bootstrap from a replicate 3DES key part to a non-replicate 3DES key.
 
Step 14: Export all the $$$ecret keys from the IBM 4758 using this 3DES exporter key.
Once again, it is possible to do steps 12..14 in the same session as all the previous steps. As soon as step 14 is complete, the various keys and key parts that have been made inside the IBM 4758 can be deleted and everything made tidy again. About two days later, when the FPGA design has been run twice, all the $$$ecret keys can be decrypted -- and suitable use made of them.
 

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


Back to main page

last modified 29 OCT 2001 -- http://www.cl.cam.ac.uk/~rnc1/descrack/attack.html