[Cryptohack] Triple DES solution
For this challenge we are provided with the source code for the API we can use:
We have two options:
- Encrypt arbitrary text with arbitrary key
- Encrypt flag with arbitrary key
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
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).
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
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.
- We ask server to encrypt flag with weak keys
- Server XORes flag with
p' = flag ^ iv.
p'is encrypted with
e1 = E(p', k1).
e1is decrypted with
e2 = D(e1, k2).
e2is encrypted with
e3 = E(e2, k3).
e3is XORed with
e = e3 ^ iv.
- Now we take swap
k3, and ask server to encrypt
eis XORed with
e3 = e ^ iv(because
e = e3 ^ iv,
e3 = e ^ iv = e3 ^ iv ^ iv = e3 ^ 0 = e3).
e3is encrypted with
k3is a weak key, so effectively encryption is the same as decryption with
e2 = E(e3, k3) = D(e3, k3).
e2is decrypted with
e1 = D(e2, k2) = E(e2, k2).
e1is encrypted with
p' = E(e1, k1) = D(e1, k1).
p'is XORed with
ivwhich 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: