Problems with Dictionary key-lookups. No match when there should be

660 views Asked by At

I'm trying to simulate a Meet-in-the-Middle attack on Double DES which works as follows:

So I'm performing the MitM attack by first encrypting a known plaintext m and with all possible values of k1, and then subsequently I decrypt a known ciphertext c with all possible values of k2. Then there should be a match inbetween which gives me k1, and k2. I'm using a cut-down key size of 20 bits instead of 56bit (or 64bit which is what the DES implementation actually wants as input). I just pad with zeroes after 20bits.

I've implemented what I think is a right solution but not getting any matches.

My two hashtables:

Dictionary<string, string> hashTable = new Dictionary<string, string>();       
Dictionary<string, string> matches = new Dictionary<string, string>();

Encrypting:

Since I'm using a reduced 20bit key, there can be 220 different combinations of 20bits. So for each iteration, I take the counter i, convert it to a binary string representation, then I pad 0s until it makes a 64bit binary value. Then I convert this string to a byte array and encrypt the plaintext with the key. I'm storing the output (intermediary cipher) as the key in the hashTable and the actual key used to get that cipher, as the value.

//First generate all possible intermediary values
for(int i=0; i< Math.Pow(2,20); i++)
{ 
    string key1 = ToBin(i, 20);
    string paddedKey1 = ToBin(i, 20).PadRight(64, '0');

    //First encryption of plaintext1 using key1
    string intermediaryCipher = 
               DESWrapper.DES_Encrypt(plaintext1, ConvertBinaryStringToByteArray(paddedKey1));


    hashTable.Add(intermediaryCipher, key1);

    //Show the current iteration in binary
    Console.WriteLine(ToBin(i, 20));
}

DESWrapper.DES_Encrypt method:

public static string DES_Encrypt(string input, byte[] key)
{
    DESCryptoServiceProvider desCryptoService = new DESCryptoServiceProvider();

    //Reflection necessary otherwise it complains about a weak key, so bypassing that check
    MethodInfo mi = desCryptoService.GetType().GetMethod("_NewEncryptor", BindingFlags.NonPublic | BindingFlags.Instance);
    object[] Par = { key, desCryptoService.Mode, key, desCryptoService.FeedbackSize, 0 };

    ICryptoTransform trans = mi.Invoke(desCryptoService, Par) as ICryptoTransform;

    byte[] resultArray = trans.TransformFinalBlock(Encoding.Default.GetBytes(input), 0, Encoding.Default.GetBytes(input).Length);
    desCryptoService.Clear();
    return Convert.ToBase64String(resultArray, 0, resultArray.Length);
}

After the encryption I have a hastable with 220 entries. The next thing I do is to make the decryption:

Decrypting:

When I'm decrypting ciphertext1 with the current padded key, the result, if it is the correct key, will be an intermediary cipher which already exists in the hashTable as a Key. So I perform this lookup. If it exists I save the two keys to another hashtable matches. If it doesn't exist I move on.

for (int i = 0; i < Math.Pow(2, 20); i++)
{
     string key2 = ToBin(i, 20);
     string paddedKey2 = ToBin(i, 20).PadRight(64, '0');

    //Decrypting ciphertext1 with key2 (64bit padded)
    string intermediaryCipher =
    DESWrapper.DES_Decrypt(ciphertext1,   ConvertBinaryStringToByteArray(paddedKey2));

    var temp = hashTable.FirstOrDefault(x => x.Key == intermediaryCipher);
    if(temp.Key != null)
    {
        matches.Add(temp.Value, key2);
        Console.WriteLine("Found match!");
        Console.ReadKey();
    }

    //Show the current iteration in binary
    Console.WriteLine(ToBin(i, 20));
}

DESWrapper.DES_Decrypt:

public static string DES_Decrypt(string input, byte[] key)
{
    DESCryptoServiceProvider desCryptoService = new  DESCryptoServiceProvider();

    //Again have to use reflection..
    MethodInfo mi = desCryptoService.GetType().GetMethod("_NewEncryptor", BindingFlags.NonPublic | BindingFlags.Instance);
    object[] Par = { key, desCryptoService.Mode, key, desCryptoService.FeedbackSize, 0 };
    ICryptoTransform trans = mi.Invoke(desCryptoService, Par) as ICryptoTransform;

    byte[] resultArray = trans.TransformFinalBlock(Encoding.Default.GetBytes(input), 0, Encoding.Default.GetBytes(input).Length);
    desCryptoService.Clear();
    return Convert.ToBase64String(resultArray);
}

The problem:

I never get a match, so the hashtable lookup always returns an empty key-value pair. I don't understand why. Eventually it should match but it doesn't.

Could the problem be in the way I'm trying to look up the values in the hashTable?


Other information:

To encrypt the intial plaintext and ciphertext I use a fabricated key which the 17th bit set to 1 and all other 63 bits set to 0. This is done for both keys.

In this way I should get the match quite fast when I'm doing the decryption, but I'm not sure if the problem is here. Including the code anyway:

        private static void GeneratePlaintextCiphertextPairs(out string plainText1, out string plainText2, out string cipherText1, out string cipherText2)
    {
        Random rnd = new Random(Guid.NewGuid().GetHashCode());

        //Generate two random keys of 20 bits padded with 0s to reach 64 bits
        //We need 64 bits because the implementation of DES requires it. Internally,
        //it will only use 56 bits
        byte[] key1 = GenerateRandom64BitPaddedKey(rnd);
        byte[] key2 = GenerateRandom64BitPaddedKey(rnd);

        plainText1 = "Hello Dear World";

        //Perform double DES encryption
        cipherText1 = DESWrapper.DES_Encrypt(
                                DESWrapper.DES_Encrypt(plainText1, key1),
                                key2);

        plainText2 = "Hello Evil World";

        //Perform double DES encryption
        cipherText2 = DESWrapper.DES_Encrypt(
                                DESWrapper.DES_Encrypt(plainText2, key1),
                                key2);
    }

    private static byte[] GenerateRandom64BitPaddedKey(Random rnd)
    {
        short keySize = 64;

        //The first 20bits are of interest, the rest is padded with 0s
        BitArray bitArray = new BitArray(keySize);

        for (int i=0; i<keySize; i++)
        {
            //if(i < 20) { bitArray[i] = rnd.NextDouble() > 0.5; }
            //else { bitArray[i] = false; }
            if (i == 17) { bitArray[i] = true; }
            else { bitArray[i] = false; }
        }

        //Console.WriteLine("In Binary: " + ToDigitString(bitArray));
        byte[] key = new byte[8];
        ReverseBitArray(ref bitArray);     
        bitArray.CopyTo(key, 0);
        return key;            
    }
0

There are 0 answers