Getting multiple key matches on plaintext/ciphertext pairs in double DES

Question

I'm trying to implement a Meet-in-the-Middle attack and just to test it out I've done some hardcoding of values, which is simply this block of simple code:

byte[] key1 = new byte[] { 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
byte[] key2 = new byte[] { 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };

string p1 = "Hello Dear World";
string p2 = "Hello Evil World";

//SimpleDES is just a C# implementation of DES that I've wrapped in its own class
SimpleDES des1 = new SimpleDES(key1);
SimpleDES des2 = new SimpleDES(key2);

byte[] toEncrypt1 = Encoding.ASCII.GetBytes(p1);           
c1 = Convert.ToBase64String(des2.Encrypt(des1.Encrypt(toEncrypt1)));

byte[] toEncrypt2 = Encoding.ASCII.GetBytes(p2);
c2 = Convert.ToBase64String(des2.Encrypt(des1.Encrypt(toEncrypt2)));

I'll leave out any more code, unless it is requested by any of you.

The problem is that given the above simple test keys and test plaintexts, I'm getting several different key pairs which when encrypted with key1 and then key2 yields the same ciphertext.

Is there something obvious, from what I have stated so far, which explains it, or do I need to look closer at my brute-force code.

Is it caused by the short key that I'm using ?

Answer 1

For a cipher each key defines a different permutation, but that doesn't mean that there cannot be identical 1:1 relations. Take AES-256, which maps 2^128 values to another 2^128 values using a 256 bit key and you encrypt one 16 byte plaintext, say all zero's. The output will also have 2^128 values. So there must be keys that map the same plaintext to the same ciphertext.

That's probably not what's biting you though. DES keys have parity bits, which is the lower bit in each byte. This bit makes sure that the number of bits in the byte is always odd. An implementation may chose to ignore the parity bit. If you have a key that only differs with regards to parity then the key value used to derive the sub-keys is identical. So only the topmost 7 bits of each byte matters, giving DES an effective bit size of 64 - 8 = 56 bits.