[Cryptohack] Triple DES solution

For this challenge we are provided with the source code for the API we can use:

We have two options:

1. Encrypt arbitrary text with arbitrary key
2. Encrypt flag with arbitrary key

3DES introduction

Note, that in this challenge (unlike other challenges in “Block Ciphers” section) we have to work with 3DES. So let’s first see how 3DES works. 3DES is an extension of the old DES algorithm. If you do not know what DES is, you should read about it, it has pretty fascinating history. But for the purpose of this task it is enough to know that DES has several weaknesses. Major DES disadvantage is the key length — 64 bits (actually only 56 bits are used, but not important). DES was actually broken in late 1990s by simple brute force on a special machine within a day or two. This led to the development of a new encryption standard in early 2000s — AES. But there were also some attempts to increase DES security by extending DES. This allowed using earlier developed software and hardware with DES support and prolong life of DES. One of such attempts was 3DES.

The idea behind 3DES is fairly simple: if DES has small key, let’s use 3 different keys and encrypt 3 times. So instead of this

We now have this

Actually second encryption block in 3DES is changed to decryption block

This doesn’t really affect anything, but it is pretty convenient if we need simple DES (we can just set k1 == k2 and first two blocks will eliminate each other, so effectively text will be encrypted single time with k3).

Using 3 different keys increases encryption security only twice (because of the meet in the middle attack), so instead of 56 bit security we get 112 bit, which is actually not bad even for today (but don’t use 3DES, there are other reasons not to do that).

Challenge solution

Now as we know how 3DES works we can get back to the challenge. Recall that we can encrypt either arbitrary text with arbitrary key, or ask server to encrypt flag for us with arbitrary key. The solution actually might look pretty easy. If we control the key, we can ask server to encrypt the flag with any key, and then just decrypt it by ourselves with the same key. But there is a small problem. Server also uses key whitening technique to increase security.

Key whitening is another approach that was developed in pursue to increase DES security, leading to creation of DES-X. Key whitening is an extremely simple procedure

Although, in this challenge k1 == k3 == iv

So now we cannot just decrypt flag with our known key, because the plaintext passed to 3DES is first XORed with iv, and later the ciphertext is XORed with iv, and we do not know the iv. So we have to think of a different approach.

Now it is time to remember, that DES has another weakness — weak keys. Weak keys are the keys that make encryption and decryption operations to be equivalent, i.e. if we twice encrypt text with the weak key, we get the plain text again.

Let’s first illustrate the whole encryption that server performs

k1, k2, k3 are provided by us. Our attack is the following. Let’s take 3 different weak keys and pass it to flag encryption function, we will get encrypted flag. Now we swap k3 and k1 and pass encrypted flag and new keys k3, k2, k1 to arbitrary text encryption function. Server will encrypt the encrypted flag and we will get the decrypted flag. Let’s break it down by step by step.

1. We ask server to encrypt flag with weak keys k1||k2||k3, where || means concatenation.
2. Server XORes flag with iv -> p' = flag ^ iv.
3. p' is encrypted with k1 -> e1 = E(p', k1).
4. e1 is decrypted with k2 -> e2 = D(e1, k2).
5. e2 is encrypted with k3 -> e3 = E(e2, k3).
6. e3 is XORed with iv -> e = e3 ^ iv.
7. Now we take swap k1 and k3, and ask server to encrypt e with k3||k2||k1.
8. e is XORed with iv -> e3 = e ^ iv (because e = e3 ^ iv, e3 = e ^ iv = e3 ^ iv ^ iv = e3 ^ 0 = e3).
9. e3 is encrypted with k3, but k3 is a weak key, so effectively encryption is the same as decryption with k3 -> e2 = E(e3, k3) = D(e3, k3).
10. e2 is decrypted with k2 -> e1 = D(e2, k2) = E(e2, k2).
11. e1 is encrypted with k1 -> p' = E(e1, k1) = D(e1, k1).
12. Finally, p' is XORed with iv which yields the flag flag = p' ^ iv = flag ^ iv ^ iv = flag ^ 0 = flag.

You can find weak keys for DES here https://en.wikipedia.org/wiki/Weak_key

And here is the implementation: