## 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 `XOR`ed or `ADD`ed.  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!