Homework SourseDo some research on how DES was actually cracked in 199798 a
Solution
DES cracking in 1997-1998
1 .1 EFF DES cracker
In cryptography, the EFF DES cracker (nicknamed \"Deep Crack\") is a machine built by the Electronic Frontier Foundation (EFF) in 1998, to perform a brute force search of the Data Encryption Standard (DES) cipher\'s key space – that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that the key size of DES was not sufficient to be secure.
1.2 Reason behind Cracking
1.2.1 Des Modes of Operation
The DES algorithm turns a 64-bit message block M into a 64-bit cipher block C. If each 64-bit block is encrypted individually, then the mode of encryption is called Electronic Code Book (ECB) mode. There are two other modes of DES encryption, namely Chain Block Coding (CBC) and Cipher Feedback (CFB), which make each cipher block dependent on all the previous messages blocks through an initial XOR operation.
1.2.2 DES Cracking
Before DES was adopted as a national standard, during the period NBS was soliciting comments on the proposed algorithm, the creators of public key cryptography, Martin Hellman and Whitfield Diffie, registered some objections to the use of DES as an encryption algorithm. Hellman wrote: \"Whit Diffie and I have become concerned that the proposed data encryption standard, while probably secure against commercial assault, may be extremely vulnerable to attack by an intelligence organization\" (letter to NBS, October 22, 1975).
Diffie and Hellman then outlined a \"brute force\" attack on DES. (By \"brute force\" is meant that you try as many of the 2^56 possible keys as you have to before decrypting the ciphertext into a sensible plaintext message.) They proposed a special purpose \"parallel computer using one million chips to try one million keys each\" per second, and estimated the cost of such a machine at $20 million.
Fast forward to 1998. Under the direction of John Gilmore of the EFF, a team spent $220,000 and built a machine that can go through the entire 56-bit DES key space in an average of 4.5 days. On July 17, 1998, they announced they had cracked a 56-bit key in 56 hours. The computer, called Deep Crack, uses 27 boards each containing 64 chips, and is capable of testing 90 billion keys a second.
Despite this, as recently as June 8, 1998, Robert Litt, principal associate deputy attorney general at the Department of Justice, denied it was possible for the FBI to crack DES: \"Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message . . . . We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department.\"
Responded cryptograpy expert Bruce Schneier: \" . . . the FBI is either incompetent or lying, or both.\" Schneier went on to say: \"The only solution here is to pick an algorithm with a longer key; there isn\'t enough silicon in the galaxy or enough time before the sun burns out to brute- force triple-DES\" (Crypto-Gram, Counterpane Systems, August 15, 1998).
1.3 Simplified DES Example
Assume input 10-bit key, K, is: 1010000010
Then the steps for generating the two 8-bit round keys,
K1 and K2, are:
1. Rearrange K using P10: 1000001100
2. Left shift by 1 position both the left and right halves: 00001 11000
3. Rearrange the halves with P8 to produce K1: 10100100
4. Left shift by 2 positions the left and right halves: 00100 00011
5. Rearrange the halves with P8 to produce K2: 01000011
K1 and K2 are used as inputs in the encryption and decryption stages. Assume a 8-bit plaintext, P: 01110010 Then the steps for encryption are:
1. Apply the initial permutation, IP, on P: 10101001
2. Assume the input from step 1 is in two halves, L and R: L=1010, R=1001
3. Expand and permutate R using E/P: 11000011
4. XOR input from step 3 with K1: 10100100 XOR 11000011 = 01100111
5. Input left halve of step 4 into S-Box S0 and right halve into S-Box S1: a. For S0: 0110 as input: b1,b4 for row, b2,b3 for column b. Row 00, column 11 -> output is 10 c. For S1: 0111 as input: d. Row 01, column 11 -> output is 11
6. Rearrange outputs from step 5 (1011) using P4: 0111
7. XOR output from step 6 with L from step 2: 0111 XOR 1010 = 1101
8. Now we have the output of step 7 as the left half and the original R as the right half. Switch the halves and move to round 2: 1001 1101
9. E/P with right half: E/P(1101) = 11101011
10. XOR output of step 9 with K2: 11101011 XOR 01000011 = 10101000
11. Input to s-boxes: a. For S0, 1010 b. Row 10, column 01 -> output is 10 S-DES Example 25 Nov 2009 1 SIIT CSS 322 – Security and Cryptography c. For S1, 1000 d. Row 10, column 00 -> output is 11
12. Rearrange output from step 11 (1011) using P4: 0111
13. XOR output of step 12 with left halve from step 8: 0111 XOR 1001 = 1110
14. Input output from step 13 and right halve from step 8 into inverse IP
a. Input us 1110 1101
b. Output is: 01110111
So our encrypted result of plaintext 01110010 with key 1010000010 is: 01110111
NOTE- I used my example of present DES since I don’t know your example
1.4 Triple DES
In cryptography, Triple DES (3DES), officially the Triple Data Encryption Algorithm (TDEA or Triple DEA), is a symmetric-key block cipher, which applies the Data Encryption Standard (DES) cipher algorithm three times to each data block.
The original DES cipher\'s key size of 56 bits was generally sufficient when that algorithm was designed, but the availability of increasing computational power made brute-force attacks feasible. Triple DES provides a relatively simple method of increasing the key size of DES to protect against such attacks, without the need to design a completely new block cipher algorithm.
1.4.1 Triple DES Algorithm
Triple DES uses a \"key bundle\" that comprises three DES keys, K1, K2 and K3, each of 56 bits (excluding parity bits). The encryption algorithm is:
ciphertext = EK3(DK2(EK1(plaintext)))
I.e., DES encrypt with K1, DES decrypt with K2, then DES encrypt with K3.
Decryption is the reverse:
plaintext = DK1(EK2(DK3(ciphertext)))
I.e., decrypt with K3, encrypt with K2, then decrypt with K1.
Each triple encryption encrypts one block of 64 bits of data.
In each case the middle operation is the reverse of the first and last. This improves the strength of the algorithm when using keying option 2, and provides backward compatibility with DES with keying option 3.
1.4.2 Key Option
The standards define three keying options:
Keying option 1
All three keys are independent.
Keying option 2
K1 and K2 are independent, and K3 = K1.
Keying option 3
All three keys are identical, i.e. K1 = K2 = K3.
Keying option 1 is the strongest, with 3 × 56 = 168 independent key bits.
