find DES key using plain text and cipher text

[Ray Chappel]

I have been given an assignment in which I am supposed to write a program that takes a plaintext and a cipher text (encrypted using DES) and does an exhaustive search for the key. So I need a few things:

Import the plaintext file (a .txt) and the ciphertext file (a .txt)
compare the two files and find the key (key must be at least 8 characters)
Has to be done using brute force

plain text: Seize the Day!
Cipher Text: püš½:©¹ÝBõ¿

Again, the plain text was encrypted using DES.

I have no idea where to start with this and how to do what needs to be done. Any sources, code, or suggestions are greatly appreciated.

[Ulf Dittmer]

Start by learning about the JCE API, which is the standard Java API for encryption and which implements DES: http://www.java2s.com/Code/Java/Security/EncryptingandDecryptingwiththeJCE.htm

[Richard Tookey]

Ray Chappel wrote:I have been given an assignment in which I am supposed to write a program that takes a plaintext and a cipher text (encrypted using DES) and does an exhaustive search for the key. So I need a few things:

Import the plaintext file (a .txt) and the ciphertext file (a .txt)
compare the two files and find the key (key must be at least 8 characters)
Has to be done using brute force

plain text: Seize the Day!
Cipher Text: püš½:©¹ÝBõ¿

Again, the plain text was encrypted using DES.

I have no idea where to start with this and how to do what needs to be done. Any sources, code, or suggestions are greatly appreciated.

You have just about zero chance of going through all 2^56 different keys. Normally when this problem is set a partial key is given. A week or so ago someone posted had a similar homework problem but he was given the first 4 bytes (28 bits) of the key and had to find the last 4 bytes (28 bits). I implemented a solution and my computer took 45 minutes to find the rest of the key. Assuming that you are given no part of the key then it could take over 200 million hours!

There is two other problems. First, your plain text is not a multiple of 8 bytes so some form of padding is used but you don't say what! Second, the cipher text does not seem to be an exact multiple of 8 bytes; it is difficult to tell for sure but it should not be displayed as characters without some form of encodiing such as Base64 or Hex.

This all suggest to me that there is something about the assignment that you are not telling us.

[Ray Chappel]

The following plaintext:
Seize the Day!
was encrypted with DES the algorithm implemented at:
http://www.avajava.com/tutorials/lessons/how-do-i-encrypt-and-decrypt-files-using-des.html
Three files (original.txt, encrypted.txt, and CipherExample.java) are included with this assignment. Note that the key in the code was changed.
Write code that given the plaintext and ciphertext above will try and exhaustive search for the key.

The above quote is everything that is listed on the assignment

The CipherExample.java is

/*****************************************************************/
/* Copyright 2009 avajava.com                                    */
/* This code may be freely used and distributed in any project.  */
/* However, please do not remove this credit if you publish this */
/* code in paper or electronic form, such as on a web site.      */
/*****************************************************************/

 

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.DESKeySpec;

public class CipherExample {

	public static void main(String[] args) {
		try {
			String key = "putkeyhere"; // needs to be at least 8 characters for DES

			FileInputStream fis = new FileInputStream("original.txt");
			FileOutputStream fos = new FileOutputStream("encrypted.txt");
			encrypt(key, fis, fos);

			FileInputStream fis2 = new FileInputStream("encrypted.txt");
			FileOutputStream fos2 = new FileOutputStream("decrypted.txt");
			decrypt(key, fis2, fos2);
		} catch (Throwable e) {
			e.printStackTrace();
		}
	}

	public static void encrypt(String key, InputStream is, OutputStream os) throws Throwable {
		encryptOrDecrypt(key, Cipher.ENCRYPT_MODE, is, os);
	}

	public static void decrypt(String key, InputStream is, OutputStream os) throws Throwable {
		encryptOrDecrypt(key, Cipher.DECRYPT_MODE, is, os);
	}

	public static void encryptOrDecrypt(String key, int mode, InputStream is, OutputStream os) throws Throwable {

		DESKeySpec dks = new DESKeySpec(key.getBytes());
		SecretKeyFactory skf = SecretKeyFactory.getInstance("DES");
		SecretKey desKey = skf.generateSecret(dks);
		Cipher cipher = Cipher.getInstance("DES"); // DES/ECB/PKCS5Padding for SunJCE

		if (mode == Cipher.ENCRYPT_MODE) {
			cipher.init(Cipher.ENCRYPT_MODE, desKey);
			CipherInputStream cis = new CipherInputStream(is, cipher);
			doCopy(cis, os);
		} else if (mode == Cipher.DECRYPT_MODE) {
			cipher.init(Cipher.DECRYPT_MODE, desKey);
			CipherOutputStream cos = new CipherOutputStream(os, cipher);
			doCopy(is, cos);
		}
	}

	public static void doCopy(InputStream is, OutputStream os) throws IOException {
		byte[] bytes = new byte[64];
		int numBytes;
		while ((numBytes = is.read(bytes)) != -1) {
			os.write(bytes, 0, numBytes);
		}
		os.flush();
		os.close();
		is.close();
	}

}

I'm not sure if this helps at all, but this is all I have to go off of

[Ulf Dittmer]

Ah, so you have source code for doing encryption - you might have mentioned that; it sounded as if you didn't.

[Ray Chappel]

Sorry, I didn't think it was relevent. Not sure why I thought that

[Richard Tookey]

The statement "Write code that given the plaintext and ciphertext above will try and exhaustive search for the key." implies that you are not actually expected to actually be able to find the key but just write code that given 200,000,000 or so hours could be expected to find the key. Given the code you have then writing the search code is a trivial extension so what are you having a problem with?

[Ray Chappel]

Well the goal is to try and find the key. However, yes, it may not be able to if it would take too long. So the goal is to write a program that will try to find the key.

My problem is that I'm not sure how to do it.

I have very little java (or programming) experience so I'm not sure where to start.

[Richard Tookey]

Ray Chappel wrote:Well the goal is to try and find the key. However, yes, it may not be able to if it would take too long. So the goal is to write a program that will try to find the key.

My problem is that I'm not sure how to do it.

I have very little java (or programming) experience so I'm not sure where to start.

I'm very uncomfortable with this. It is difficult to see how a Java course could jump in with a homework requirement such as this so I assume it builds on lectures and previous homework. Your task does not really rely on understanding the JCE; the JCE is just clutter and the homework requires that you be able to iterate through all the 2^56 possible key values and then use them in the code given.

If you really are as stuck as it seems then you should go to see your lecturer since he seems to have failed in giving you the background information you need.

Note - a DES key is just 56 bits packaged in 8 bytes with the least significant bit of each byte being a parity bit. The JCE ignores this parity bit so you just have to go though the 128 values of each byte that ignore the least significant bit. This can be done very simply using recursion but could equally well be done by counting though the first 2^56 values of a long and converting the first 56 bits of the long to 8 bytes (7 bits at a time) using the shift operators. The actual approach you take will depend on what you have done in the course so far.


Note 1 - the code you published is flawed. It assumes that the key can always be represented by a String and that it can be converted to bytes using the platform default character encoding! This makes it non-portable since for a given key String the actual bytes of the key will depend on the platform default character encoding!

[Ray Chappel]

Richard Tookey wrote:

I'm very uncomfortable with this. It is difficult to see how a Java course could jump in with a homework requirement such as this so I assume it builds on lectures and previous homework. Your task does not really rely on understanding the JCE; the JCE is just clutter and the homework requires that you be able to iterate through all the 2^56 possible key values and then use them in the code given.

I transferred in to the school last fall. There are 2 prerecs for this course, beginning Java 1 and 2. However, I took two classes on C++ at my previous school and my current school counted the C++ courses for the 2 Java courses. Unfortunately, those C++ courses were taken 2 years ago and I don't even remember much of that. After talking to other students who have taken the Java 1 and 2 courses, those courses didn't teach anything like this assignment either and they are having trouble as well.

Note - a DES key is just 56 bits packaged in 8 bytes with the least significant bit of each byte being a parity bit. The JCE ignores this parity bit so you just have to go though the 128 values of each byte that ignore the least significant bit. This can be done very simply using recursion but could equally well be done by counting though the first 2^56 values of a long and converting the first 56 bits of the long to 8 bytes (7 bits at a time) using the shift operators. The actual approach you take will depend on what you have done in the course so far.


Note 1 - the code you published is flawed. It assumes that the key can always be represented by a String and that it can be converted to bytes using the platform default character encoding! This makes it non-portable since for a given key String the actual bytes of the key will depend on the platform default character encoding!

Yea, the professor had just google searched how to do DES encryption and decryption with java. He found that code and copied it. The code I provided was what was used to encrypt the plain text. What we have to do is write code (can be a new file or add/modify the existing one) that does an exhaustive search for the key.

[Richard Tookey]

It is difficult to advise you on how to continue with this assignment since I suspect your Java background is not going to be adequate. | have outlined the basics of what you have to do and nobody here is going to write the code for you so you are going to have to make an attempt and then come back if you have problems. Since your key is specified as a string and not as bytes you need to slightly modify the approach I outlined but it is not difficult.

There is one other consideration. Since the key is specified as a String and your lecturer seems not to understand the limitations I would work on the assumption that the set of characters of each key byte are the printable ASCII characters. This means that the most significant bit of each key bytes is zero and since the least significant bit of each key byte is ignored then you only have to consider each alternate character starting with a space. I'm betting that your lecturer only use the alpha set then I would consider just the alternate characters of the alpha set - A,C,E ... X and a,c,e .... x - a total of 26 different values for each byte and a total of 26 ^ 8 (208,827,064,576) different keys; still a big number but much more manageable.

[Ray Chappel]

/*****************************************************************/
/* Copyright 2009 avajava.com                                    */
/* This code may be freely used and distributed in any project.  */
/* However, please do not remove this credit if you publish this */
/* code in paper or electronic form, such as on a web site.      */
/*****************************************************************/

 

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import javax.crypto.Cipher;
import javax.crypto.CipherInputStream;
import javax.crypto.CipherOutputStream;
import javax.crypto.SecretKey;
import javax.crypto.SecretKeyFactory;
import javax.crypto.spec.DESKeySpec;

public class CipherExample {

	public static void main(String[] args) {
		long startTime = System.nanoTime(); //start timer
		try 
		{
		
			String key = "AAAAAAA"; // needs to be at least 8 characters for DES
			
			
			for (int i = 0; i < 10; i++) //for loop to find characters in string
			{
			String myKey = key + (char)(i + 65); //finds additional character for key

			FileInputStream fis = new FileInputStream("original.txt");
			FileOutputStream fos = new FileOutputStream("encrypted.txt"); 
			encrypt(myKey, fis, fos); //changed key to myKey and fos to fes

			FileInputStream fis2 = new FileInputStream("encrypted.txt");
			FileOutputStream fos2 = new FileOutputStream("decrypted.txt");
			decrypt(myKey, fis2, fos2); //changed key to myKey
			
			System.out.println(myKey); //outprints key
			}
		} 
		catch (Throwable e) 
		{
			e.printStackTrace();
		}
		long endTime = System.nanoTime(); //end time
		System.out.println("It took: " + (endTime - startTime) + " nanoseconds to run"); //display time
	}

	public static void encrypt(String myKey, InputStream is, OutputStream os) throws Throwable //changed key to myKey, os to es
	{
		encryptOrDecrypt(myKey, Cipher.ENCRYPT_MODE, is, os);//changed key to myKey and os to es
	}

	public static void decrypt(String myKey, InputStream is, OutputStream os) throws Throwable //changed key to myKey and OutputStream os to InputStream es
	{
		encryptOrDecrypt(myKey, Cipher.DECRYPT_MODE, is, os);//change key to myKey and os to es
	}

	public static void encryptOrDecrypt(String key, int mode, InputStream is, OutputStream os) throws Throwable 
	{//changed OutputStream os to InputStream es

		DESKeySpec dks = new DESKeySpec(key.getBytes());
		SecretKeyFactory skf = SecretKeyFactory.getInstance("DES");
		SecretKey desKey = skf.generateSecret(dks);
		Cipher cipher = Cipher.getInstance("DES"); // DES/ECB/PKCS5Padding for SunJCE

		if (mode == Cipher.ENCRYPT_MODE) 
		{
			cipher.init(Cipher.ENCRYPT_MODE, desKey);
			CipherInputStream cis = new CipherInputStream(is, cipher);
			doCopy(cis, os);
		} 
		else if (mode == Cipher.DECRYPT_MODE) 
		{
			cipher.init(Cipher.DECRYPT_MODE, desKey);
			CipherOutputStream cos = new CipherOutputStream(os, cipher);
			doCopy(is, cos);
		}
	}

	public static void doCopy(InputStream is, OutputStream os) throws IOException 
	{
		byte[] bytes = new byte[64];
		int numBytes;
		while ((numBytes = is.read(bytes)) != -1) 
		{
			os.write(bytes, 0, numBytes);
		}
		//os.flush();
		os.close();
		is.close();
	}

}

This is what I have so far, mostly just made changes to main. The first thing I am trying to accomplish is to create a key of every combinations. What I have written right now, just adds an 8th character to the key of "AAAAAAA". To my understanding, I want to do a series of 8 nested for loops to generate 8 characters for each one in the key. I have tried a couple of things, but it only results in errors. I guess I am not sure how to do the nested for loops properly.

[Richard Tookey]

Java nested loops are just about the same as C++ nested loops though you will find that a recursive approach is much easier.