1

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 ?

  • What do you mean with "key pairs" in this question? – Maarten Bodewes Jun 23 '15 at 21:42
  • @MaartenBodewes I mean that for a given plaintext p1, there are more than one set of keys (k1 and k2 is a set here) which yield the correct ciphertext. – DSF Jun 23 '15 at 21:43
  • @MaartenBodewes Does that make sense? – DSF Jun 23 '15 at 21:43
2

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.

  • Aah okay I see what you mean. But one thing I maybe didn't understand. Say for the key I've used, it has a lot of 0s. Practically only 3-4 1s the rest are 0s. Does that increase the chance of more "sets of keys" which map the plaintext to an identical ciphertext? – DSF Jun 23 '15 at 22:02
  • No not really. Each bit of the output should depend on each bit in the key. Even if there are a lot of zeros or ones changing one bit should change the ciphertext significantly (indistinguishable from random, so an average hamming distance of half of the block size, 32 bits). – Maarten Bodewes Jun 23 '15 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.