# ECTF 2016
###### tags: `Crypto`
## Daas
The challenge gave us two files, challenge.py and flag.encrypted.
The challenge is a RSA decryption service, it can decrypted any encoded hex except from the encrypted flag itself.

Since this is my first try on crypto, I had no idea. Then I looked up a something called the homomorphic property:
> E(a)*E(b) = (a^e mod n)*(b^e mod n) = (a*b)^e mod n = E(a*b)

So if the encrypted_flag = E(a*b), here are the following steps to solve the challenge:
1. let E(a) = 2, then E(b) = encrypted_flag/2
2. decrypt both E(a) and E(b), which we get 'a' and 'b'
3. flag = a*b%n

The thing I don't understand is why we have to mod n at the last step, isn't a*b the flag itself? (Maybe I'll understand when I do more challenges)

## counterattack
The challenge encrypts the flag with AES CTR mode, then there is a while loop waiting for user input, which we could do the following:
1. enter data with len(data)%16==0 and preform encryption to the data and store it in the output buffer
- There is something weird with this, since after spliting the data into block, it does not preform encryption on the individual blocks but on the original data instead.

2. enter 'stop' and it would output the encrypted flag and the encrypted data you sent.

After looking up CTR mode, I understood the process looks like:

**For each block**
1. encrypt a counter value with the key, call this feed
2. xor feed with plain text block
3. increase block

Since in the source code, the feed == IV + CTR, since IV is a constant during the session, and CTR = bin(counter%16)[2:].zfill(4).
CTR only has 16 possibilities(0000, 0001, 0010,....., 1111), so feed has only 16 possibilities.

Because xor(a, '\x00') = a, we can enter '\x00'*16 for 16 times to get all 16 possible feeds.

The final step is to xor the three blocks of the encrypted flag with three sequential feeds, try all 16 possibilites.

final script:

from collections import deque

cts = ['Z\xda@\xca\x02\xf1Q\xef\xbd\xb5\x9b\xaePJ\x03\x97', 'Z\xe5N6\xd8\xdb\xe1U"\xb2li\x99\xfd\x16\xb6', 'D@\xb3\x9695L\xec\x92\xc9oo\xd3\xa7\x8f\xb0', '\xb6\xa5Q\xb7h\x95W\xa1M\xff6\xff\x05\xe7Dg', '\x97\xb6"\xae\xae\x99\x8c\x8aq\xee\x81\xf9RJ[\x12', '\x87\\\x9eMTGm\xa6\x15\x94\x99M5$\xfb\x89', '\x1a\xe4uu\xef_\xf5\x94\xc7\x18\xa8}T\x08\xbe#', '\x16\xc9\xf9\xc7\x1a\xa8\xf0\xce]\x92\x06\xe67\xbb\xd0\xc1', '\x83\x1aK\x19\xdaR\x81\xdd>a\x97r\xd47v\x81', '\x1aU\xbd\xe3\x8a%\xe8(\xdd\xd9\xfa\xe76\x0b\x800', '\x8c\xb5?\xe3X\xb8~\xf1\x85R\x82\x13-\x1f\xa5\xb6', ',N\xa8\xb8k\xc5\x12{$\xf3%\xc1\xbc,]Q', '}l\xf2\ne\x8f\t\x98\x83\x8aY\x9c<e&w', '\xc1Y \xc4\xe6\xcb\xc2\xc0\xdf\xaa\x01\x91\xf9\xe0\xa7\xf7', '\x1d\xd7\xa3\xa8Q\x19!\x05\xf7\x84H2\xcbs\x18\xd9', '[\xc9e\xa2\xeeH\xfck2\r\x81\x90\xcf\tK\xe1', '\x0e\xb2%\xead\x9d0\x88\x9d\xdc\xe8\x8e\x15\tW\xd1', '!\x8c\x11U\xb9\xb5\x95\nG\xc4\t\x07\xc6\x9eb\xc4', '\x1b4\xdb\xf7Mj?\x98\xe7\xb9\x06\x0b\xba\xd3\xf6\xcd']

def xor(keystream, data):
         out = []
         for idx, ch in enumerate(data):
             out.append(chr(ord(ch) ^ ord(keystream[idx % 16])))
         return ''.join(out)

flag = cts[:3]
keystreams = deque(cts[3:])

for i in range(16):
        out = []
        for j in range(3):
                out.append(xor(keystreams[j], flag[j]))
        if 'CTF' in  ''.join(out):
                print ''.join(out)
                break
        keystreams.rotate(1)