Hack.lu 2018 CTF- Relations Writeup

Relations

Solved by: D1X1T, 4lph4, v3ctor, nsg99, s0rc3r3r 

This was a fairly easy challenge although we are not given any encryption script. We are given three operations on the nc service to choose, XOR, ADD and DEC (decrypt). Then, we have to give an input string on which the selected operation is done.

How the operation takes place was unknown at that particular point of time. But we see something strange here:

So now we know that DEC operation takes in base64 key which it then uses to AES decrypt some string, which could possibly be our flag.

Then, we started giving random inputs to XOR and ADD operations and my teammates noticed this:

For the same input ​00, ADD and XOR operations give the same output! We immediately thought that we can use this to leak out the string to which our input is XORed or ADDed.  And that string could possibly be the key used as an input in ​DEC to AES decrypt our flag. How can we exploit this?

Consider A, B of size 1-bit each. If A=1, A xor B and A+B will be equal only when B = 0. That’s it! We can use this property to generalise and get all the bits of the key:

1. Send  as inputs for both XOR and ADD and check if the outputs for XOR and ADD for an input match.
   1. If they match, then add 0 to the binary keystring, otherwise add 1.

Wrote the following script to implement this attack:

from pwn import *
import string

def choose_XOR_op(input):
    for i in input:
        assert i in string.hexdigits
    r.recvuntil("*")
    r.sendline("XOR")
    r.recvuntil(">>")
    r.sendline(input)
    ct = r.recvline()[17:].strip()
    unknown = r.recvline().strip()
    return ct, unknown

def choose_ADD_op(input):
    for i in input:
        assert i in string.hexdigits
    r.recvuntil("*")
    r.sendline("ADD")
    r.recvuntil(">>")
    r.sendline(input)
    ct = r.recvline()[17:].strip()
    unknown = r.recvline().strip()
    return ct, unknown

def choose_DEC_op(input):
    r.recvuntil("*")
    r.sendline("DEC")
    r.recvuntil(">>")
    r.sendline(input)
    print r.recvline()
    print r.recvline()
    r.close()

list1 = [2**i for i in range(128)]
key = ""

r = remote("arcade.fluxfingers.net","1821")
for i in list1:
    ct, unknown = choose_XOR_op(hex(i)[2:].replace("L",""))
    ct1, unknown1 = choose_ADD_op(hex(i)[2:].replace("L",""))
    if ct+unknown == ct1+unknown1:
        key += "0"
        print key
    else:
        key += "1"
        print key

key = hex(int(key[::-1], 2))[2:].replace("L","").decode("hex").encode("base64").replace("\n","")
choose_DEC_op(key)

r.close()

And got the flag!

Voila!