CSE 539: Applied Cryptography

Project 2, Due date: Oct 7

Brute Forcing and Cryptanalysis

Groups

This project is to be done in groups of TWO. This requirement will be enforced.

Purpose

Brute force a set of encrypted files whose keys have been permanently lost and write a cryptanalysis report that reflects on how weaknesses in the cipher directly impact the security.

Objectives

        Apply brute force techniques to an encrypted pdf, png image, and text file

        Perform a cryptanalysis on an encrypted pdf, png image, and text file

 

Project Description

Keys play an important role in encryption and decryption. It is rare to guess or crack the key for an algorithm, but not impossible. One can try every possible key (brute force) or analyze the algorithm for some flaw in the design (cryptanalysis).

When brute forcing, it is important to be able to determine when to stop. Since the output is generated for every key, including the correct one, it is crucial to know something about correct output which separates it from all others.

The file encryption.zip contains three files: a pdf, an image in png format, and a text file. The encryption keys for these files are lost and can’t be recovered.

In the encryption.zip file you have two C programs: encrypt.c and decrypt.c. These programs use 32-bit block encryption like HW1. They also have md5.h, which contains MD-5 routines used by the encrypt/decrypt programs. Encrypted versions of all the three files pdf, image (.png format) and text mentioned above.

Note: For this project, you must use 32-bit machines. A 32-bit Linux works well--otherwise, you may compile with the –m32 option. You may need to run this command in the terminal:

sudo apt-get install libc6-dev-i386 gcc-multilib g++-multilib

Due to code in md5.h, you may see several warnings; you can ignore these warnings from the md5.h file. You may compile and run the encrypt program using the command ./encrypt <filename>.

The encrypted output will be in a file called “output”. The key used will be printed – the program generates a key from system entropy. This key is used for decryption. To run the decrypt program, use the command ./decrypt <key>. The key must be the correct key. The program will read encrypted data from “output” and write decrypted data into the file “output-dec”.

 

Directions 

1.      Compare the code for MD-5 with the block diagrams to get familiar with how MD5 works.

2.      Test the programs on your own text, image, and pdf files. Try to encrypt and decrypt them.

3.      Perform the initial cryptanalysis. In the Project 2 Submission document, Describe the design of the (provided) algorithm used and how it works. Explain whether or not you think this encryption algorithm “cheats” (that is it is not a self-contained encryption algorithm) and why you think so.

4.      Brute force the keys for the three files provided and find the keys used. You may modify the programs. Do not assume you know the plaintext, but assume you know what type of plaintext file it is. (Note: knowing the type of the file helps in brute forcing.) Record the key for each file and what the file contains in the Project 2 Submission document. Also record the runtime of the brute force algorithm.

5.      Find weakness(es) of the cipher design. Describe the weakness(es) and how they might have been avoided or could be fixed in the Project 2 Submission Document.

6.      Use the weakness(es) in the cipher design to find keys faster. Describe how the weakness(es) can be used to find keys faster in the Project 2 Submission Document. Also record the runtime of the faster algorithm.

Submission Directions for Project Deliverables

Generate and submit a document you generated for steps 3, 4, 5, 6. Keep it short. Put both names on the document but upload it only once.

Upload the document (.doc, pdf) to Canvas