description.md

$$$$## 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<char> K(key1,key1+3);
    vector<char> 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<char>,vector<char> > 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<char>,vector<char> >::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

You are welcome to do this project in Python if you want. For a DES client you might use pycrypto. Obviously you would use the dict type to store the block/key pairs.