CPS472_572 - Programming Assignment #1 -  TEA  - Solved

1. Purpose  

This homework builds an understanding of classic block ciphers and cryptanalytic attacks.  
2.1.   TEA  
The Tiny Encryption Algorithm (TEA) block cipher operates on 64-bit blocks of plaintext using a 128-bit key. The plaintext is divided into two 32-bit blocks (L0, R0), and the key is divided into four 32-bit blocks (K0, K1, K2, K3). Encryption involves repeated application of two Feistel rounds (making up one cycle of TEA), defined as follows for round i and i+1:  

                                                                                                                    Li-1                                    Ri-1 

                Li         = Ri-1

                  Ri        = Li-1          F(Ri-1, K0, K1, δi);

                Li+1      = Ri

                Ri+1      = Li          F(Ri, K2, K3, δi+1);

 Li Ri where     denotes modulus +, the logical left shift of x by y bits is denoted by x << y, the logical right shift of x by y bits is denoted by x

>> y, δi is a sequence of predetermined constants, and F is defined as  

 

  F(X, Kj, Kk, δi ) = ((X << 4)        Kj)  ⊕  ((X >> 5)      Kk)  ⊕  (X + δi).

 

The encryption function is given next, written in C, for encoding with key k[0] … k[3]. Data is in v[0] and v[1] and there are 32 cycles (i.e., 64 rounds).  

 2.2.   Attack Method  
In this project, we will develop a C++ program that performs an attack on 1 round of TEA. In 1 round of TEA the key size is effectively reduced to 64 bits, because only half of the 128 bit key is used in 1 round of TEA. Using known plaintexts and their resulting ciphertexts, we will perform a brute force attack on the 64-bit key by repeatedly guessing 32 bits of the key, which will eventually lead us to deduce the other 32 bits.  

We only need to search through 232 possible keys, since given a subkey K0, we can calculate a value for the other subkey K1 by using known plaintext/ciphertex pairs (i.e., derive an equation for K1 in terms of K0 and a pair of plaintext/ciphertext).  

In this project, first implement the TEA encryption method and then generate 100 random plaintexts and their corresponding ciphertexts using 1 round of TEA encryption (see Figure below). That is, each plaintext is <L0, R0> and its corresponding ciphertext is simply <L1, R1>. Output the plaintext/ciphertext pairs to a file.   

      L 0                                                      R0 

  

      L1                                                    R1
 

The following steps/pseudocode outline the general procedure of the attack program. 

 

1.  Read in the file with the plaintext/ciphertext pairs into lists. These values are then converted from strings in the file to 32 bit unsigned integers. 

2.  Guess a value for subkey K0, starting at 0. 

3.  Calculate the value for K1 using our guess K0 and the first plaintext/ciphertext pair. 

4.  Calculate the value for K1 using our guess K0 and the second plaintext/ciphertext pair. 

5.  Do those two values of K1 match? 

6.  If not, this is the incorrect guess for K0. Increment our guess and go back to Step 3. 

6.  If yes, we need to verify that this guess for subkey K0 is correct 

7.  Repeat steps 3 and 4 ten times with different plaintext/ciphertext pairs 

8.  If the values of K1 did not match every time, increment our guess for K0 and go back to Step 3. 

 

9.  If the values of K1 matched every time, this is the correct guess for K0 and we’ve found the key!! Print the key and the run time of your project.