Interesting Devices Ltd
Home Forums Register FAQ Calendar Arcade Mark Forums Read
Main Menu

Categories

Products
Random Products


Arcade Control Bundle Pack


GBA FM Radio


Action Replay (PAL Only)


Gamebit Driver 4.5mm


ISO 7816 Dual Speed Smart Card Reader/Writer Interface


Smart Card Reader/Writer Enclosure
Sponsors
sophiesnappycakes.co.uk


  
Go Back   Interesting Devices Ltd > General > General Chit Chat
Reload this Page 3DES Cracked on the cheap!
General Chit Chat An area for general discussion of any subject we do not have a forum for. MAKE SURE THERE IS NOT A FORUM FOR YOUR POST FIRST.

Reply
 
Thread Tools Display Modes
3DES Cracked on the cheap!
Old
  (#1)
stout
Guest
 
Posts: n/a
   
3DES Cracked on the cheap! - 8th May 2002, 01:28 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/index.html#faq

Extracting a 3DES key from an IBM 4758
Summary
The IBM 4758 is an extremely secure cryptographic co-processor. It is used by banking systems and in other security conscious applications to hold keying material. It is designed to make it impossible to extract this keying material unless you have the correct permissions and can involve others in a conspiracy.

We are able, by a mixture of sleight-of-hand and raw processing power, to persuade an IBM 4758 running IBM's ATM (cash machine) support software called the "Common Cryptographic Architecture" (CCA) to export any and all of this program's DES and 3DES keys to us. All we need is:

about 20 minutes uninterrupted access to the device
one person's ability to use the Combine_Key_Parts permission
a standard off-the-shelf $995 FPGA evaluation board from Altera
about two days of "cracking" time
The attack can only be performed by an insider with physical access to the cryptographic co-processor, but they can act alone. The FPGA evaluation board is used as a "brute force key cracking" machine. Programming this is a reasonably straightforward task that does not require specialist hardware design knowledge. Since the board is pre-built and comes with all the necessary connectors and tools, it is entirely suitable for amateur use.

Besides being the first documented attack on the IBM 4758 to be run "in anger", we believe that this is only the second DES cracking machine in the open community that has actually been built and then used to find an unknown key!

Until IBM fix the CCA software to prevent our attack, banks are vulnerable to a dishonest branch manager whose teenager has $995 and a few hours to spend in duplicating our work.

NEW: 5 FEB 2002: Version 2.41 of the CCA has now been made available available on IBM's website at http://www-3.ibm.com/security/crypto...lease241.shtml . Version 2.41 includes fixes specifically designed to prevent the attack described on this website, and some of the related weaknesses described in Mike Bond's paper "Attacks on Cryptoprocessor Transaction Sets".
The major modification to the transaction set is the separation of duty between confidentiality and integrity assurance for clear loading of symmetric keys. The old modes of operation for Key_Part_Import were FIRST, MIDDLE, and LAST. New modes of operation ADD and COMPLETE have been created. The party responsible for testing the integrity of a key (using Key_Test) can now use the COMPLETE mode, which does not permit modification of the key being tested.
Several changes have been made to the semantics of Key_Part_Import, and the symmetric key inport and export commands to prevent type changes between replicate and non-replicate keys during import, and to prevent export of non-replicate keys under replicate keys.
Extra access control points have been created which disable the fixes in order to permit upgrade to version 2.41 for reasons other than security.
The CCA is a much safer product now that no single individual can damage the integrity of the key material. The attack described on this website was based purely on specification level faults. Note that some of the security-related fixes in release 2.41 relate to implementation faults; these have no direct connection with the attacks described on this site, but presumably came to light as a consequence of the closer examination of the CCA code that followed the publicity.
  
Reply With Quote
Part 1: What is an IBM 4758 ?
Old
  (#2)
stout
Guest
 
Posts: n/a
   
Default Part 1: What is an IBM 4758 ? - 8th May 2002, 01:31 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/ibm4758.html

Extracting a 3DES key from an IBM 4758
Part 1: What is an IBM 4758 ?

Photo of IBM 4758 Cryptographic Coprocessor (courtesy of Steve Weingart)

The IBM 4758 is a commercially available cryptoprocessor. It was the first such device to have been successfully evaluated to the highest level of tamper resistance, the US Government standard called FIPS 140-1 level 41. It is also of interest because there is a great deal of publicly available documentation regarding its design evolution2, protection mechanisms3,4 and the transaction set it supports.5

To understand the substantial physical security provided by the IBM 4758, a history lesson is necessary... (a longer version of this account appears in Chapter 14 of Ross Anderson's book6)

The arrival of multi-user operating systems in the 1960s showed that it was extremely difficult to process sensitive data on a computer and protect it from other programs running on the same computer. The operating systems were meant to provide protection, but in practice there were bugs and design limitations that meant that cryptographic keys and personal identification numbers (PINs) were always at risk. This led to the development of standalone "security modules" such as the IBM 3848 and the VISA security module. These were basically just microprocessors in robust metal enclosures. When you opened the lid the power supply was disabled and they "forgot" their sensitive information.

The obvious attack is to drill through the lid; so devices acquired photocells and tilt devices. Later, it was realised that substantial protection could be acquired by "potting" the device in a block of epoxy resin. The idea was that the device would be "tamper evident" in that the epoxy would be damaged -- and since the device was in a secure location, someone might notice you drilling into it.

However, if you could get a few minutes alone with the device, it turned out to be possible to scrape away the epoxy with a knife and drop a logic analyser probe onto the microprocessor bus. Cryptographic algorithms like RSA and DES have the unfortunate property that monitoring a single bitplane during the computation allows access to the key7. So anyone looking like a maintenance engineer who can get a logic analyser near the device has a reasonable chance of obtaining secret key material.

The response to this threat was the development of tamper-sensing barriers. On the IBM ľABYSS system3 this was 40 gauge nichrome wire wound around the device before it was embedded in the epoxy. If you mount a physical attack on the epoxy then you break the wire and the keys are erased. In the IBM 4758 this type of protection has been significantly enhanced. It has four overlapping zig-zag conducting patterns doped into a urethane sheet which in turn is potted in a chemically similar substance. An attacker has difficulty detecting the conductive path and attempts to remove the potting material are very likely to damage it. Other types of attack relate to memory remanence. If keys are stored in the same place in RAM forever then those locations will "remember" the values even when the power is removed. Devices attempt to avoid this 8 by techniques such as constant movement of values from place to place, rather as a screen saver avoids "burning" patterns onto a VDU screen.

If you can get the memory very cold (below -20 degrees C) then it will maintain its contents for many minutes9 -- long enough for a physical attack to get through the outer protective layers. The 4758 detects changes of temperature and erases the key material if it starts getting chilly. Similar issues arise if you bombard the memory chips with X- rays. So the 4758 has a radiation sensor as well.

Computers also leak electromagnetic signals, or consume different amounts of power depending upon what they are doing. So called "Tempest" or "power analysis" looks for these signals and deduces what calculations the processor is performing. The 4758 has solid aluminium shielding and a low-pass filter on the power supply to minimise this type of radiation.

So all in all, the IBM 4758 is a pretty secure device from a physical point of view. There's no known attack upon it.

Next part: What is an FPGA ?

Links
1 National Institute of Standards and Technology, "Security Requirements for Cryptographic Modules" (11 Jan 1994). http://www.itl.nist.gov/fipspubs/0-toc.htm#cs

2 S W Smith, S H Weingart, "Building a High-Performance, Programmable Secure Coprocessor", Computer Networks (Special Issue on Computer Network Security) 31: pp 831-860. (April 1999) http://www.cs.dartmouth.edu/~sws/papers/cn99.pdf

3 S H Weingart, "Physical Security for the ľABYSS System", in Proceedings of the 1987 IEEE Symposium on Security and Privacy, IEEE Computer Society Press, pp 52-58.

4 S H Weingart, S R White, W C Arnold, G P Double "An Evaluation System for the Physical Security of Computing Systems", in Sixth Annual Computer Security Applications Conference (Dec 3-7, 1990) Tucson Az. Proceedings published by the IEEE (1990), pp 232-243.

5 IBM PCI Cryptographic Coprocessor Library http://www-3.ibm.com/security/crypto.../library.shtml

6 R Anderson, "Security Engineering. A Guide to Building Dependable Distributed Systems." Wiley 2001. http://www.cl.cam.ac.uk/~rja14/book.html

7 H Handschuh, P Paillier, J Stern "Probing Attacks on Tamper-Resistant Devices" in "Cryptographic Hardware and Embedded Systems -- CHES 99" Springer LNCS 1717, pp 303-315. http://www.di.ens.fr/~stern/data/St78.pdf

8 Department of Defense, "A Guide to Understanding Data Remanence in Automated Information Systems", NCSC-TG-025 (1991). [usually known as 'The Forest Green Book']

9 Sergei Skorobogatov, "Low Temperature Data Remanence in Static RAM" http://www.cl.cam.ac.uk/~sps32/sram_article.pdf
  
Reply With Quote
Part 2: What is an FPGA ?
Old
  (#3)
stout
Guest
 
Posts: n/a
   
Default Part 2: What is an FPGA ? - 8th May 2002, 01:31 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/fpga.html

Extracting a 3DES key from an IBM 4758
Part 2: What is an FPGA ?

Photo of Altera's Excalibur development board

A Field Programmable Gate Array (FPGA) is an integrated circuit whose functionality can be programmed in the field after manufacture. FPGA capacities have been growing year after year and modern devices can provide two million gate designs in a single chip. This is about the level of complexity of the first Intel Pentium microprocessors.

When originally introduced FPGAs only had a handful of gates and designs were specified as logic equations connecting them up. Nowadays they are programmed in high level Hardware Description Languages (HDLs) such as Verilog1 , which superficially resembles high level programming languages such as C. For example, a linear feedback shift register might be expressed as:

always @(posedge clk)
begin
count[73:0] <= count[74:1];
count[74] <= count[26] ^ count[23] ^ count[21] ^ count[19];
end

The great advantage of an FPGA is the fast development time and very low cost of design cycles. Instead of spending thousands of dollars and waiting weeks for your design to come back from the fabrication plant you can program the FPGA, test it, and if you've made an error then within a few minutes you can fix the problem and reprogram the same device with a corrected design.

Of course, an FPGA is only one part of a working system, which will need memory, connectors, a circuit board and a power supply. For the DES cracking project we avoided all the hard work of creating such a system by using an off-the-shelf development board, part of an 'Excalibur' kit2 from Altera3. Altera kindly provided ours for free (thanks!), but they'd be happy to sell you one for just $995. If you want to build your own circuit board then the chip will cost you from $178 upwards (one off) 4 though Altera suggest volume pricing will be about $5 5 [this sort of price differential for one off devices is typical for the industry].

The Excalibur system includes all the tools you need for programming the FPGA. You'll also need to provide your own PC to run the tools -- we used an 800MHz Windows 2000 system with 512MB of RAM. Speed is less important than RAM because otherwise the tools swap continuously and run very slowly indeed!

The kit provides the design for a small microprocessor called a NIOS 6 (indeed the Excalibur board we used is intended for evaluation and development of NIOS based designs). The NIOS occupies about 20% of the FPGA leaving the rest for problem specific logic. This is a very powerful technique because it allows hardware to be used for the performance critical parts of a design and software running on the NIOS can be used to glue it together and communicate with the outside world.

Next part: What are DES and 3DES ?
Previous part: What is an IBM 4758 ?

Links
1 Verilog 2001 http://www.verilog-2001.com/

2 Excalibur Development Kit, Featuring NIOS http://www.altera.com/products/devic...r/exc-kit.html

3 Altera Inc http://www.altera.com/

4 Arrow Electronics Inc http://www.arrow.com/

5 Altera Introduces The NiosTM Embedded Processor, Industry's First RISC-Based Embedded Processor Developed for SOPC Integration http://www.altera.com/corporate/pres...r_ex_nios.html

6 NIOS Embedded Processor http://www.altera.com/products/devic...ios_index.html
  
Reply With Quote
Part 3: What are DES and 3DES ?
Old
  (#4)
stout
Guest
 
Posts: n/a
   
Default Part 3: What are DES and 3DES ? - 8th May 2002, 01:32 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/des3des.html

Extracting a 3DES key from an IBM 4758
Part 3: What are DES and 3DES ?
The first of these web pages explained how the IBM 4758 cryptoprocessor provided a secure way of doing encryption. The second explained about how FPGAs provide programmable hardware.

In the next part we'll cover how to program an FPGA to deal with DES and then move on to the attack on the IBM 4758. First, though it will be useful to understand just a little bit about how the DES and 3DES encryption algorithms work.



The Data Encryption Standard (DES) was created in the early 1970s. It processes input data that is 64 bits wide, encrypting these values using a 56 bit key.

The basic layout of the cipher is as shown in the graphic above. The data is split into two 32 bit halves and the left half is XORd with a non-linear function of the right half mediated by the key value. E is an expansion permutation, P a simple permutation and the key has its own permuation from round to round. The full DES function involves 16 such stages plus an initial and final permutation. The details can be found in most cryptographic textbooks, or you can read the FIPS standard 1 .

Although DES was just about secure in the 1970s, it now uses keys that are susceptible to "brute-force" attacks. Triple DES (also a standard as ANSI X5.92) uses three DES operations to provide significantly more security. It uses two keys and performs an encryption with Key1, a decryption with Key2 and then an further encryption with Key1. Hence for legacy applications it can set Key1 to the same as Key2 and Triple DES will fall back to merely acting as if it were DES.


Since Triple DES uses two keys, the effective key length is 112 bits. This is a lot more secure. If you could break DES by brute-force in one second (which is very far from being the case) then it would take 2.285 billion years to break Triple DES.

Next part: How the DES cracker works
Previous part: What is an FPGA ?

Links
1 "Data Encryption Standard" FIPS 46 http://csrc.nist.gov/publications/fi...3/fips46-3.pdf
  
Reply With Quote
Part 4: How the DES cracker works
Old
  (#5)
stout
Guest
 
Posts: n/a
   
Default Part 4: How the DES cracker works - 8th May 2002, 01:33 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/cracker.html

Extracting a 3DES key from an IBM 4758
Part 4: How the DES cracker works
The basic idea of a brute force "DES cracker" is to try all possible keys in turn and stop when one is found that will correctly decrypt a given value into its plaintext. Sometimes, as in problems we have been tackling, the plaintext that we need to match is known (we often use all zeros) and sometimes the correct decryption can only be determined statistically (for example, in the RSA challenges posed in the late 90s, the value looked like English text).

This cracker design actually works the other way round; viz it takes an initial (zero) value and encrypt it under incrementing key values until this output matches the encrypted value we seek. The design runs at 33MHz ie: it tries 33 million keys per second. This might sound fast, however this is rather slow for cracking DES keys - and it would take, with average luck, about 34.6 years to crack a single key. So we arrange to crack up to 16384 keys in parallel (ie: we have available the results of encrypting zero with 16384 different DES keys and we check against all of these at the same time). It would still take nearly 70 years to be sure of cracking all of them - but during that 70 years one would have, on average, have been cracking one key every 37 hours and one would expect, with average luck, to find the first key after about 25 hours. (For the detail of these sums have a quick peek here). Since cracking just one key is of use to us in our attack on the IBM 4758, we need only consider waiting about a day for results.. so our design is of real practical use.

As an aside, you may be wondering why we choose to crack exactly 16384 keys in parallel. Cracking more would speed things up -- but unfortunately on the system being used there is only 256K bits of memory available to hold the encrypted values and 16384 values is the most that this will hold.

Our DES cracker uses the Altera NIOS Development board described earlier. This board contains an APEX EP20K200EFC484-2X FPGA chip1 which contains 8320 Logic Units (LUTs) which can be viewed as being equivalent to approximately 200,000 logic gates. The FPGA is programmed with a DES cracking design alongside of which, within the FPGA, is placed a 16-bit NIOS processor. The NIOS processor runs a simple program (written in C and loaded into some local RAM on the FPGA) which looks after a serial link. The values for the DES crack are loaded down the serial link, and when results are obtained they are sent back this way. This diagram shows the general arrangement:


In a software version of DES you'd use the same variables for each round and a "for loop" such as:

for (i=0; i<16; i++)
{
ShiftAndRotate(key);
temp = R;
R = L ^ DESfunction(R, key);
L = temp;
}

For the hardware DES cracker a pipelined version of the algorithm is used:


At each clock interval, all of the LR pairs are moved down into the next set of registers. Therefore, after an initial start-up period of 16 clocks, results appear from the end of pipeline at the clock rate of 33MHz. The key values are not pipelined from stage to stage along with L and R. Instead a Linear Feedback Shift Register is used, which is extended to the right of its actual 56 bits so as to record older values of the key. These can then be statically connected, in an appropriate manner to the various pipeline stages. This space-saving technique was previously used by Hamer and Chow in their Transmogrifier DES cracker design 2.

In order to determine whether there is a match to one of 16384 values, the value is "hashed" down from 64 bits to 14 and this gives the RAM address to be consulted. If the value at this RAM address matches the entire value then the crack is finished. Otherwise, the system continues.

A tedious complication is that the Altera board has a limited amount of RAM on board, just two SRAMS each 32K by 16 bits. This means that the 64-bit compare has to be done in two 32-bit halves. If the first half matches (as happens every few seconds) then the pipeline is suspended and the second half of the value is checked. You can see this happening on this logic analyser picture below. The regular signal on the third line is the clock. The second signal down shows a 32-bit match is occurring. This causes a STOP of the pipeline (top signal) and access to an odd numbered address value (bottom signal). The other signals are some of the data and address lines.


Next part: How the attack works
Previous part: What are DES and 3DES ?

Links
1 APEX 20K Programmable Logic Device Family Data Sheet http://www.altera.com/literature/ds/apex.pdf

2 Ivan Hamer and Paul Chow. "DES Cracking on the Transmogrifier 2a" Cryptographic Hardware and Embedded Systems, LNCS 1717, Springer-Verlag, 1999. pp 13-24. http://www.eecg.toronto.edu/~pc/rese...s.ches99.ps.gz
  
Reply With Quote
Part 5: How the attack works
Old
  (#6)
stout
Guest
 
Posts: n/a
   
Default Part 5: How the attack works - 8th May 2002, 01:34 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/attack.html

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 from the CCA software running inside the remarkably secure IBM 4758, 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.
  
Reply With Quote
Part 6: Some real results
Old
  (#7)
stout
Guest
 
Posts: n/a
   
Default Part 6: Some real results - 8th May 2002, 01:36 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/results.html

Extracting a 3DES key from an IBM 4758
Part 6: Some real results
This is some output from a real attack on an IBM 4758 running the CCA software. First we determined the value of a DES key that had been used to encrypt zero:


--------------------------------------------------------------------------------

OFFLINE >online
DESMIM Engine on COM1

ONLINE >set data 0
t1D4E6
OK0774
t01427
OK0774
ONLINE >runtv r:\variant_data_harvest_09oct.tv
Retrieving test vector set from file 'r:\variant_data_harvest_09oct.tv'

.................................................. ..............

Total test vectors loaded : 65536
Total number of clashes : 49468
Total unusable test vectors : 0
Loading test vector set into DESMIM engine
.0..800..1000..1800..2000..2800..3000..3800..4000. .4800..5000..5800..6000..6800.
.7000..7800..8000..8800..9000..9800..A000..A800..B 000..B800..C000..C800..D000..D
800..E000..E800..F000..F800..10000..10800..11000.. 11800..12000..12800..13000..13
800..14000..14800..15000..15800..16000..16800..170 00..17800..18000..18800..19000
..19800..1A000..1A800..1B000..1B800..1C000..1C800. .1D000..1D800..1E000..1E800..1
F000..1F800.

16384 lots of 2 * 32-bit chunks loaded.


Done.
rr85A4
OK0774
Wait started at: Tue Oct 9 17:01:43 2001

Run completed at: Wed Oct 10 11:13:22 2001


Result = #73EB2E8955BD46F4, Key = #3EEA4C4CC68CCCC2

With corrected (odd) parity key = #3EEA4C4CC78CCDC2

Result corresponds to key number #E2E6

which is an XORing value of #0000000000068BCC
ie: the key really wanted = #3EEA4C4CC78A460E
ONLINE >



--------------------------------------------------------------------------------

When the attack software was run on the IBM 4758 at "step 6" we had combined what we now know to be a value of #3EEA.4C4C.C78A.460E with #7D00.7D00.0309.0000 (don't ask -- it was just a randomish value chosen from thin air on the 3rd of September (03/09)!). Hence the single DES key that we exported was #43EA314CC483460E and cracking the replicate key used for exporting went like this:


--------------------------------------------------------------------------------

OFFLINE >online
DESMIM Engine on COM1

ONLINE >set data 43ea314cc483460e
t1D4E6
OK0774
t01427
OK0774
ONLINE >runtv r:\variant_exporter_harvest_09oct.tv
Retrieving test vector set from file 'r:\variant_exporter_harvest_09oct.tv'

.................................................. ..............

Total test vectors loaded : 65536
Total number of clashes : 49432
Total unusable test vectors : 0
Loading test vector set into DESMIM engine
.0..800..1000..1800..2000..2800..3000..3800..4000. .4800..5000..5800..6000..6800.
.7000..7800..8000..8800..9000..9800..A000..A800..B 000..B800..C000..C800..D000..D
800..E000..E800..F000..F800..10000..10800..11000.. 11800..12000..12800..13000..13
800..14000..14800..15000..15800..16000..16800..170 00..17800..18000..18800..19000
..19800..1A000..1A800..1B000..1B800..1C000..1C800. .1D000..1D800..1E000..1E800..1
F000..1F800.

16384 lots of 2 * 32-bit chunks loaded.


Done.
rr85A4
OK0774
Wait started at: Wed Oct 10 18:17:19 2001

Run completed at: Fri Oct 12 06:53:36 2001


Result = #8BA3F18A17504AF0, Key = #B256466EDE78F8B2

With corrected (odd) parity key = #B357466EDF79F8B3

Result corresponds to key number #B95C

which is an XORing value of #000000000005E4B8
ie: the key really wanted = #B357466EDF7C1C0B
ONLINE >


--------------------------------------------------------------------------------

Hence in two cracking sessions of 16 hours and 37 hours we had determined that the 3DES replicate key part was #B357.466E.DF7C.1C0B.B357.466E.DF7C.1C0B and this knowledge allowed us create a non-replicant 3DES key and export any value we wanted.


--------------------------------------------------------------------------------

The token that emerged was (we've annotated the fields to show the structure):

-START-------------------
externaltoken EXTERNAL V0x00
int_ext 02
res1 00 00 00
version 00
res 02 00
flags1 c0
flags 02 00
res 03 00 00 00 00 00 00 00 00
keyleft b3 d7 80 e8 2b f8 4d 59
keyright 3d 0f 65 ff 99 01 29 4a
cvkeft 00 41 7d 00 03 41 00 00
cvright 00 41 7d 00 03 21 00 00
res 4 00 00 00 00 00 00 00 00 00 00 00 00
tvv be c6 17 8a
-END-------------------

The 3DES key we want is "keyleft"."keyright" and is encrypted with a key that we now know the value of. The second (non-replicate) key part we used was: #7D00.7D00.0309.0000.0000.007D.007D.007D (you still should avoid asking why!). Hence we can now calculate the exporter key value:

B357466EDF7C1C0B B357466EDF7C1C0B // from the cracker

7D007D0003090000 0000007D007D007D // chosen key part

CE573B6EDC751C0B B3574613DF011C76 // these two XORd together

We can now decrypt the left and right halves of the key from the token by using this 3DES exporter key. As a final twist, we have to add in a "control vector" for each half (this is part of the key typing mechanism used by the the system and the details are in the CCA documentation).


00417d0003410000 00417d0003410000 // left half control vector

CE16466EDF341C0B B3163B13DC401C76 // key XOR LH control vector

00417d0003210000 00417d0003210000 // right half control vector

CE16466EDF541C0B B3163B13DC201C76 // key XOR RH control vector

We now decrypt each half of the external token, using the completed exporter key (ie: the exporter combined with the relevant control vector)

3DES key = CE16466EDF341C0B B3163B13DC401C76
data = B3D780E82BF84D59
decrypt = 52C1A27975F4A407

3DES key = CE9680E82BD04D59 B396FD9528A44D24
data = 3D0F65FF9901294A
decrypt = 1049858C9D433BB5

ie: the valuable key that was encapsulated in the key token and which the attack has now revealed is:

#52C1 A279 75F4 A407 1049 858C 9D43 3BB5

Next part: Who are we ?
Previous part: How the attack works
  
Reply With Quote
Part 7: Who are we ?
Old
  (#8)
stout
Guest
 
Posts: n/a
   
Default Part 7: Who are we ? - 8th May 2002, 01:37 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/whoarewe.html

Extracting a 3DES key from an IBM 4758
Part 7: Who are we ?
We are two research students in our second year of a PhD course in the Security Research Group of the Cambridge University Computer Laboratory .

Mike Bond's PhD thesis will be on cryptoprocessor APIs. He invented this attack on the IBM 4758. It is related to, but not the same as a number of attacks that were described in his CHES 2001 paper. Readers may also be interested in a more general paper co-written with Dr Ross Anderson in the October 2001 edition of IEEE Computer magazine.

Richard Clayton's PhD will be on an unrelated topic, which will draw upon his many years in the ISP industry. He worked on this particular project just for fun! His contribution was the FPGA design that was used in the attack. Using hardware is very much faster then using programs on general purpose computers. It means that the attack can be mounted for $995 in two days, rather than requiring a $3000 high speed PC for two months.

Richard's web page that collects together a whole heap of information on brute force attacks on crypto systems -- and on DES in particular can be found here.

At an earlier stage of this project, when we were considering this attack, but many details were still to be settled, we gave a talk as part of the Security Group Seminar Series. The slides from this talk can be found here.

We'd like to acknowledge the generosity of Altera in providing the FPGA board used in this project for free. We'd also like to thank Ross Anderson and Simon Moore for their helpful comments and encouragement throughout.

Finally, if anyone has access to an IBM 4758 in a real world application (the more valuable the data it's transferring the better) we'd be delighted to have the opportunity to run our attack "for real" :-)

Next part: Do It Yourself !
Previous part: Some real results
  
Reply With Quote
Part 8: Do It Yourself !
Old
  (#9)
stout
Guest
 
Posts: n/a
   
Default Part 8: Do It Yourself ! - 8th May 2002, 01:38 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/diy.html

Extracting a 3DES key from an IBM 4758
Part 8: Do It Yourself !
We have bundled up the various parts of our cracking system if you'd like to have a go yourself! You will need to purchase an Altera Excalibur NIOS Evaluation Board ($995). Then download http://www.cl.cam.ac.uk/~rnc1/descrack/cracker.zip

The files are:

sram.v
Top level Verilog file for DES cracker
des.v
Pipelined DES algorithm
ffunct.v
Non-linear function for DES
sbox.v
SBOX contents (specially arranged for minimum chip area)
lfsr.v
Linear feedback shift register
keysched.v
Key manipulation for DES pipeline stages
Compile these files. We used Exemplar Logic's LeonardoSpectrum v20001 for this. Ensure you enable pass 3 optimisation (this comes out best) and DISABLE automatic creation of ROMs and RAMs (otherwise the SBOXs are turned into RAMs and the design will not fit into the chip!).

You will need your own NIOS processor (sorry, but we cannot place the Verilog for this on the web). You get all the files required with the $995 Excalibur kit. You should create the NIOS processor as follows:

Name Type Base Address IRQ
processor 16-bit NIOS : 14-bit address bus
128 register file
shift 1 bit per clock N/A N/A
GERMS-ROM Read-only on-chip memory : 16 bits * 1K
Contains GERMS monitor 0x0000 N/A
Program RAM Writeable on-chip memory : 16 bits * 8K
Set blank 0x2000 N/A
uart RS232 serial port : 115200, 8, N, 1
fixed baudrate 0x1000 26
pio_cmd Parallel I/O : 10 bits
Output only 0x0010 N/A
pio_data Parallel I/O : 16 bits
Tri-state 0x0018 N/A
pio_status Parallel I/O : 4 bits
Input only 0x0020 N/A

You should now take the ".edf" file output by Leonardo and the NIOS files and combine them together using:

DESign.bdf
Connections to NIOS design
We used Altera Quartus II v1.1 for this. It yielded a design with 8303 out of 8320 LUTs in use ! So, don't be tempted to add much to what we've provided.

You should then download the design into the evaluation board. To shortcut all of the above, the ZIP file also contains the ".sof" file that needs to be downloaded.

DESign.sof
DES cracker design for APEX 20KE200EFX484-2X
Next step is compile the program to be run by the NIOS processor. We've provided the C source for this, and the evaluation board comes with a suitable version of GNU C that is targetted on the NIOS.

desmim.c
DES cracker loading program
desmim.srec
Loadable binary (for the NIOS design specced above)
Having compiled this program then load it into the NIOS (with nios-run).

The next component is the communications program that you run on your PC to talk to the NIOS program over a serial link. We've supplied not only the source for this but also the files needed to compile it with Microsoft's Visual C++ system.

destalk.dsw
Visual Studio workspace file
destalk.dsp
Visual Studio project file
stdafx.h
standard includes
talk-desmim.cpp
source for DES talker program
The final component is the program to be run on the IBM 4758. The source for this is also provided. Compile it as a WIN32 console application with Visual C++. You will need csunincl.h and csunsapi.lib, IBM's library for the CCA API.

harvest.dsw
Visual Studio workspace file
harvest.dsp
Visual Studio project file
harvest.c
source for IBM 4758 program
If you're still waiting to get access to a real IBM 4758 then you can use these two sets of encrypted results that we used.

variant_data_harvest_09oct.tv
variant_exporter_harvest_09oct.tv
Have fun! and do let us know (perhaps a postcard from your hideaway on Bermuda?) how you got on.

Next part: Frequently Asked Questions
Previous part: Who are we ?
  
Reply With Quote
Some relevant sums
Old
  (#10)
stout
Guest
 
Posts: n/a
   
Default Some relevant sums - 8th May 2002, 01:39 AM

from http://www.cl.cam.ac.uk/~rnc1/descrack/sums.html

Extracting a 3DES key from an IBM 4758
Some relevant sums
The DES cracker is searching a 256 key space (72,058,000,000,000,000 keys) at a speed of 33.333 MHz (ie 33.333 million keys/second). To search the entire key space would therefore take 68.50 years.

The DES cracker is actually searching for up to 16384 keys in parallel. If the whole key space was searched it would find keys at an average rate of one per 68.50/16384 years, which is one every 36.65 hours.

To calculate the expected time until the first key is found, one treats the system as having a Poisson distribution. Since the linear feedback shiftback register is walking the keyspace pretty much at random this is a reasonable assumption.

So we have 256 possible keys in the keyspace and 214 possible matches.

Let the mean rate of matching be m = 214 / 256 = 2-42

The probability that any particular cell is empty is (m0 / 0!) e-m

Simplifying this (m0 = 1 and 0! = 1) we get the probability that a cell is empty = e-m

Let the probability that the first r cells are empty be p


Then p = (e-m)r [independent events]

So p = e-mr


Taking the natural log of both sides and solving for r we have


r = -ln(p) / m


So for a probability, p, equal to 0.5 (ie average luck) for our value of m we need to search r keys where r = 0.6931472 / 2.2737734E-13 = 3,048,497,000,000 keys. At 33.333MHz this will take 25.40 hours.

Note carefully that if your luck is worse, then one time in a thousand cracking attempts (ie: p = 0.001) then a lot more keys will need to be searched. In fact it will take about 10.5 days at 33.333MHz.

In practice we've had cracks that ran in times between 5 and 37 hours -- so we've never been especially unlucky

Go back
Our thanks to Bruce Christianson for assisting us to get this calculation right at long last!
  
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Forum Jump





Powered by vBulletin® Version 3.7.5
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com
Copyright ©1995 - 2009, Interesting Devices Ltd

Page generated in 0.31491 seconds with 9 queries