Assignment 1
	Parallel Programming Assignments

Write an MPI program to crack the encryption key of files encrypted by the cripcryp program, available here. (Make sure you get the current version, 0003.) Cripcryp takes the already weak and aging DES encryption system, and runs over it with a truck. DES uses a 56-bit key, which was adequate at the time it was introduced, but has been rather outstripped by the current technology. To keep from us dying of old age using our cluster of 200-MHz whizzing wonders, cripcryp reduces this to 24 bits. The real DES starts by permuting a subset of the bits from an input 64-bit key to form a 56-bit key which is used for the rest of the process. CripDES replaces this with a fairly opaque sequence of duplication, shifting, and inversion to build the 56-bit key from an input 24-bit one.

Cripcryp

When you download and build cripcryp, you get a program which can encrypt to decrypt files using a key. Like this:

bennet@stlouis:~/tmp$ tar zfx cripcryp.tgz  bennet@stlouis:~/tmp$ ls cripcryp.tgz  cripcryp0003 bennet@stlouis:~/tmp$ cd cripcryp0003/ bennet@stlouis:~/tmp/cripcryp0003$ make cc -O   -c -o cripdes.o cripdes.c cc -O   -c -o cripcryp.o cripcryp.c cc -o cripcryp cripdes.o cripcryp.o bennet@stlouis:~/tmp/cripcryp0003$ ls Makefile  cripcryp  cripcryp.c  cripcryp.o  cripdes.c  cripdes.h  cripdes.o

The executable cripcryp can then be used as follows:

bennet@stlouis:~/tmp/cripcryp0003$ cat msg.txt Good morning, Mr. Phelps. Your mission, should you choose to accept it, is to put an end to the second law of thermodynamics, and clean up afterwords. bennet@stlouis:~/tmp/cripcryp0003$ cripcryp 0xF4E211 msg.txt > msg.enc bennet@stlouis:~/tmp/cripcryp0003$ od -a msg.txt | head -1 0000000   G   o   o   d  sp   m   o   r   n   i   n   g   ,  sp   M   r bennet@stlouis:~/tmp/cripcryp0003$ od -a msg.enc | head -1 0000000   l   ) stx  bs   U   C eot   E   s   L   /   ]  si   h etb  bs bennet@stlouis:~/tmp/cripcryp0003$  cripcryp -d 0xF4E211  msg.enc Good morning, Mr. Phelps. Your mission, should you choose to accept it, is to put an end to the second law of thermodynamics, and clean up afterwords. bennet@stlouis:~/tmp/cripcryp0003$

The program takes a flag -e or -d, for encrypt or decrypt, with -e being the default, a key, and an optional input file name. Without the input file name, it reads from standard input, and it always writes to standard output. The key may be either a hex number (when it starts with 0x), or an arbitrary string of three or four bytes. In the later case, the program builds the key from the ascii code values.

The encrypted file is always longer than the plain file. The encryption algorithm adds three bytes, then rounds up to the next multiple of eight to accommodate DES, which operates on eight-byte blocks. The three added bytes consist of one which gives the total number of bytes added (3 to 10) and a 16-bit checksum. The added information occupies the very last three bytes of the encrypted file, after any needed zero padding. It is appended to the plaintext, and encrypted as if it were part of the file. The decryption function uses this information to check that the key was correct, and to restored the original file size.

Cracking It

While the keyspace is small, the cripcryp version of DES should be sound in other respects. That means using an exhaustive key search to find the key for an encrypted file. Testing if your guess is correct is almost easy because of the size and checksum information stored by cripcryp. The decrypted size byte must be 3 to 10, and the checksum must agree. Also, any fill bytes must be zero, as the encryption program specifies.

This will not eliminate all incorrect keys, however. The basic key search may produce several keys which pass these tests. (A recent test on a short message turned up four such keys.) To choose which of these is correct, you must decide which translation is most "reasonable". The usual way to do this is to compute a histogram of decrypted data. Random data from a bad key should have a flat histogram, while the correctly-decrypted data should not. To decide which of the keys that pass the formal test is most likely the one, compute the byte histogram for each. Find the sum of the squares of the differences from the mean. The mean is just the file size / 256: the expected count on an even distribution. For each byte, take the difference between its actual count and the mean, square the difference, and total the squares. Report all the keys in order of decreasing value of this sum. The largest one is almost certainly the correct one.

So, your mission is: Create an MPI parallel program which will crack files encrypted by the cripcryp program. It should run on the cluster with mipexec, and take the file name on the command line. It should report all keys which pass the formal tests that cripcryp -d makes. For each of these, it should compute the histogram of the decrypted data, and find the sum of the differences from the mean. List the keys in order from largest to smallest of the sum of the squares.

Notes and Suggestions

I have implemented the key search, but not the histogram part. I essentially swiped the decode code from cripcryp and put it in a loop. Each worker computes its own range and pounds until a key works. You could do this by just executing cripcryp for each key and checking the exit code, but I figured this would be too slow. My sequential version of this can find all the keys on a single node in about 35 minutes. The parallel one takes about seven and a half minutes using all eight nodes.

You can use cripcryp to produce test data with known keys. There will also be a major prize (consisting entirely of a notice on the assignment web page) for the first person who can tell me the secret word which is part of msg.enc. We'll also have an listing of high honor for whoever's program can do do this in the least time, as soon as that is known.