ASIS CTF Finals 2015 – 10-SED (crypto 175)

October 12, 2015

In this challenge we were given the source of a server which encrypts and decrypt messages for us with DES, a ciphertext and some kind of key.

server.py

After looking at the source, you can observe how it handles the userinput, namely using the “key” to generate indices for reading from its own private key-list and en/decrypting a given text with said keys.
For a given key the server also checks the length of the input to match (after hex-decoding) 3 (a valid key would thus e.g. be “001122”; more on that later).

An example run would look like this: send the key “414243”, server takes the “subkeys” (his private keys) at those positions from its key-list and en/decrypts userinput with those and returns

Ek3=keys[43](Ek2=keys[42](Ek1=keys[41](input))).encode(“hex”)

Nothing special about it yet. Special is the fact that there is a comment in the source “assert len(key) == 3#10”. If you take a look at the given “enc” file you can see the “key” in there is (after hex-decoding) of length 10.
What this means is that the ciphertext we have is the flag encrypted, 10 (!) times with some keys we don’t know (only the server does, we know the *positions* of those keys though). Luckily we can tell the server to decrypt it for us. If it wasn’t for the fact that the number got change from 10 to 3.
The decryption seems impossible now because the server only does decryption for us if we provide exactly 3 key-positions. Apparently we can “reduce” the encryption of the flag to 1 instead of 10 encryption rounds like this:

cipher = "7f62a70857410e0e9c2bb283fc9807f8b1d34bcf7a2b456e965e860e5c6818b40ac596fa43492c30"
# originalkey = 97c4b5a27177406c404f --- this means 10 positions for keys were given and the flag encrypted accordingly
first = interact(s, cipher, "6c404f", "DEC")
second = interact(s, first, "717740", "DEC")
third = interact(s, second, "c4b5a2", "DEC")

(short explanation: slice the given key(s) into groups of 3 and do decryption with them – full script will be shown in the end)

However what we get from that is a flag that is still encrypted with the key at position 97. There is no way to get a completely unencrypted flag it seems, until you check out the wiki article about DES:

https://en.wikipedia.org/wiki/Data_Encryption_Standard#Minor_cryptanalytic_properties

And this is the whole trick of the challenge:
There seem to exist some keys which have the property Ek(Ek(input)) = input (Equivalent to Dk(Dk(input)) = input)

This fits exactly what we need. The only thing left is running the decryption in a loop with all keys like “000097”, “010197”, “020297”,…
To be more precise: decrypt our flag which is only decrpyted with key at position “97” with the keys at following positions: “97” “00” “00” etc. etc. and wait.
Sadly, we don’t get a flag. It turned out, for some reason, ASIS didn’t go with this vulnerability but chose to take the one which requires much more bruteforcing:
We need to find two distinct keys k1, k2 which have the property Ek1(Ek2(plain)) = plain (the second “weakness” described in the wiki article).
So, same as above, but instead of iterating over 256 keys, we iterate over 256*256 keys… But after a while we get:

[#] testing da4f97
[enc] recv: Enter your key(hex encoded):
[enc] sent: da4f97
[enc] recv: Enter your message(hex encoded):
[enc] sent: 15c876f9e9a20af6d2e40c5fc7de5e721f50460969a5be17fdb8c5b5a01e70da05944650ae57e2b3
[enc] recv: Enter your command(ENC/DEC):
[enc] sent: DEC
[enc] recv: message(hex encoded):
[enc] result: 0e4eca072f192237f7dddb44aa441f06479fff6ee8f628b2e8e2e540d7062f56fd8293c249069f2c
[#] GOT PLAIN: '\x0eN\xca\x07/\x19"7\xf7\xdd\xdbD\xaaD\x1f\x06G\x9f\xffn\xe8\xf6(\xb2\xe8\xe2\xe5@\xd7\x06/V\xfd\x82\x93\xc2I\x06\x9f,'
[#] testing da5097
[enc] recv: Enter your key(hex encoded):
[enc] sent: da5097
[enc] recv: Enter your message(hex encoded):
[enc] sent: 15c876f9e9a20af6d2e40c5fc7de5e721f50460969a5be17fdb8c5b5a01e70da05944650ae57e2b3
[enc] recv: Enter your command(ENC/DEC):
[enc] sent: DEC
[enc] recv: message(hex encoded):
[enc] result: 415349537b39303135326333643665363635386632303537626261346338383965356364617d0000
[#] GOT PLAIN: 'ASIS{90152c3d6e6658f2057bba4c889e5cda}\x00\x00'

… a flag! 😀

Apparently keys at possitions 0xda and 0x50 fullfil the second property!
Really a very interesting challenge overall! I would have liked if the possitions of the keys were a bit more bruteforce-“friendly” though (like “02” “05”), since I almost gave up after a couple of tousand iterations.
This is how I got the flag a bit more quickly, professional multithreading.
asis-multi-sed

Full script here, as of writing this, the ASIS service is still up for testing 🙂
asisfinal15-sed.py

4 Responses to “ASIS CTF Finals 2015 – 10-SED (crypto 175)”

  1. Awesome. Thank you so much.

  2. Glad I could help. Thanks for your reply! 🙂

  3. You don’t need to iteratre over all 256*256 possibilites.
    There are only six pairs of keys that statisfy Ek1(Ek2(x))=x (semi week keys)
    and these key pairs could be find in the internet.
    So you can dowlnload 256 message: Ek1(Ek1(Ek1(“01234567”))),Ek2(Ek2(Ek2(“01234567”))),…
    Then compute offline Ek(Ek(Ek(“01234567”))) for all known semi-week keys and compare output with 256 downloaded encrypted messages.

  4. Thanks for your reply! When I already had my script to test the first 256 keys, I just thought why not test the other ~60k possibilities with that 🙂
    But you are right. Your solution is nicer and seems like the intended one, since you don’t need to bruteforce that much over the internet.

Leave a Reply