## Project 4

#### Meet in the middle attack

In this project we will do a meet in the middle attack on 2DES. The idea of a meet in the middle attack is discussed in the textbook in Chapter 5. A description in pseudocode can be found below.

As you may recall from reading the book and from our discussions in class, the MITM attack on 2DES requires $2^{57}$ CPU operations, and a database with $2^{56}$ rows. Naturally we don't actually have those computational resources. To make the project possible we will use a version of DES that has a 21 bit key. We do this by making most of the key bits zero and only allowing 21 of them to vary. This cipher has the following code.

``` void DES_21_bit_key(const char pt[8],char ct[8],int decrypt, char key[3]) { keysched ks; char big_key[8] = {0}; //declare an 8 byte key of all 0's memcpy(big_key,key,3); //copy the 3 byte key into the first 3 bytes of the 8 byte key fsetkey(big_key,&ks); //build the key schedule using the 8 byte key if (ct != pt) memcpy(ct,pt,8); //copy pt into ct, which will be modified by fencrypt fencrypt(ct,decrypt,&ks); //Do the encryption/decryption } ``` The code makes use of `des56.h`, which we also used in Project 3. The function takes as input a plaintext block `pt` which is constant (not modified by the function). It also takes a ciphertext block `ct` which is modified so as to contain the ciphertext, an encrypt/decrypt flag called `decrypt` and a 3 byte key. Note that 3 bytes of memory is actually 24 bits, but because DES discards every 8th bit, only 21 of the bits are functional. Because every 8th bit is tossed out in the key, there is no reason to consider key bytes which are odd numbers.

With the `DES_21_bit_key` function serving as a DES substitute, we can define 2DES as follows.

```

void double_DES_21(char block[8],int decrypt, char key1[3], char key2[3]) { if(decrypt) { DES_21_bit_key(block,block,decrypt,key2); DES_21_bit_key(block,block,decrypt,key1); } else { DES_21_bit_key(block,block,decrypt,key1); DES_21_bit_key(block,block,decrypt,key2); } } ```

The above function takes a block as input, as well as an encrypt/decrypt flag and two independent keys. It simply calls our DES substitute twice, once with each key. For decryption the order of the keys is reversed. The block of input is modified so as to contain the resulting ciphertext (or decrypt, depending on the value of the `decrypt` parameter).

In this project there is a piece of ciphertext we would like to decrypt, namely the following.

``` ~/Crypto_Fall_17/project_4/optimized$ xxd encryption.des 00000000: 1ae8 ba6f b40f f2ea c9fc df8c c479 0bcc ...o.........y.. 00000010: c48e 20b6 c0b5 158e .. ..... ```

Fortunately we have a known-plaintext pair $(x,y)$, where $y = double\_DES\_21\_bits(x)$ and the key $k$ is the same as the one used to produce the target ciphertext. The pair is:

``` char x[8] = {'a','b','c','d','e','f','g','h'}; ///x value of known plaintext pair char y[8] = {0x03,0x8d ,0x8a,0xdf ,0x90,0xe7 ,0x0b,0xbe}; //y value of known plaintext pair ```

Expanding the template code in `template.cpp`, your job is to complete the MITM attack by implementing the following pseudocode description.

``` /*MITM attack on 2DES_21*/

Initialize a map structure M associating blocks to keys. For each i=0,1,...,2^21-1: z = 2DES_21(x) with key k_i T[z] = k_i End For

For each i=0,1,...,2^21-1: z = 2DES_21(y,decrypt=True) with key k_i // this is DES in *decrypt* mode if T[z] is defined: output T[z] and k_i as key1 and key2 break End For ```

On cocalc each loop should require about 10 seconds. Note that if we were using a brute force approach, the time required would be $2^{21}\cdot 10$ seconds, which is about 242 days. Thus the MITM strategy is helping considerably.

---

### Using the STL map data structure

We will use the C++ `map` datatype to store the association between intermediate blocks `z` and the keys that give rise to them (please see the above pseudocode for the meaning of `z`).

One difficulty is that our blocks and our keys are `char` arrays. While it is possible to use these with a `map` it will be more convenient to use `vector` types. Fortunately `char` arrays are easily converted into vectors, as shown below.

``` vector K(key1,key1+3); vector Z(z,z+8); ```

In the above code `K` will be the vector representation of the key `key1` and `Z` will be the vector representation of `z`. This constructor makes a copy, so you do not need to worry about changes to `z` affecting `Z`, for example.

Now we can easily associate these objects by using a `map`:

``` map,vector > M; M[Z] = K; ```

Another key part of the pseudocode (no pun intended) involves determining whether `M[Z]` is defined. That is, we want to know if an assignment of the form `M[Z]=K` has ever been made for a particular `Z`. One approach to doing this is the following:

``` map,vector >::iterator L = M.find(Z); if (L != M.end()) { // etc } ```

The inner part of the above conditional will execute exactly if `M[Z]` has already been defined. You can extract the value stored in the iterator `L` by using `L->second` notation, or just call `M[Z]` to get the value.

### Incrementing the key

To search through all keys you must find a way to check all _even_ values of the three bytes of a key.

``` char key[3] = {a,b,c}; ```

It is sufficient to check even byte values because DES discards every 8th bit, and these are exactly the least significant bits of each byte. You could just use all values, but this will make your code run 8 times slower (please don't do this!).

The way to write this function is as follows. The key should be initialized to have zero in each byte. To go to the "next key" value, first try to increment `c` (_i.e_ `key[2]`) by 2. If this byte is full then be sure to also increment `b` by 2. But if `b` is full then be sure to also increment `a` by 2. The simplest way to do this is probably using a recursive function.

### Testing the result

When your program successfully finds the key, there is a small chance that you found a false key. Check that this is not the case by decrypting the file `encryption.des`, located in the same directory as the code. The file is encrypted with 2DES_21 in ECB mode, so be sure to use the same mode when decrypting.

### Compiling the code

To compile the code you can use:

``` $ g++ main.cpp des56.cpp ```

To run the resulting program do:

``` $ ./a.out ```

If you're getting an overwhelming number of errors, the following can be useful. It will output only the first 10 lines of error messages.

``` $ g++ main.cpp des56.cpp 2> /tmp/errs ; head /tmp/errs ```

### Working in Python