**Tags:** crypto

Rating:

# Nullcon CTF

This directory contains solutions/writeups for _nullcon CTF 2019_ (02.02.2019)

## 2FUN

in this task we're given an encryption algorithm resembling 2DES

### Statement

```python

sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54,

217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107,

91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221,

63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81,

201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15,

151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119,

123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99,

82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129,

131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48,

97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125,

106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200,

70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153,

174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65,

176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83,

223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246,

169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117,

100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231,

0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222,

20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215,

50, 148, 159, 93, 80, 45, 17, 205, 95]

p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14]

def xor(a, b):

return bytearray(map(lambda s: s[0] ^ s[1], zip(a, b)))

def fun(key, pt):

assert len(pt) == BLOCK_LENGTH

assert len(key) == KEY_LENGTH

key = bytearray(unhexlify(md5(key).hexdigest()))

ct = bytearray(pt)

for _ in range(ROUND_COUNT):

ct = xor(ct, key)

for i in range(BLOCK_LENGTH):

ct[i] = sbox[ct[i]]

nct = bytearray(BLOCK_LENGTH)

for i in range(BLOCK_LENGTH):

nct[i] = ct[p[i]]

ct = nct

return hexlify(ct)

def toofun(key, pt):

assert len(key) == 2 * KEY_LENGTH

key1 = key[:KEY_LENGTH]

key2 = key[KEY_LENGTH:]

ct1 = unhexlify(fun(key1, pt))

ct2 = fun(key2, ct1)

return ct2

```

We are also given known ciphertext: `16 bit plaintext` -> `467a52afa8f15cfb8f0ea40365a6692`

The goal is to decrypt the flag `04b34e5af4a1f5260f6043b8b9abb4f8`

### Solution

After investigating `toofun` wee see that it is encrypting message with two 3-byte keys using `fun`. So step 1 woulbe be to learn how to decrypt message encrypted with `fun`. It can be done in quite straightforward way, by executing all the same actions in reverse:

```python

def defun(key, raw):

rp = [0 for _ in range(len(p))]

rsbox = [0 for _ in range(len(sbox))]

for i in range(len(p)):

rp[p[i]] = i

for i in range(len(sbox)):

rsbox[sbox[i]] = i

ct = list(unhexlify(raw))

key = bytearray(unhexlify(md5(key).hexdigest()))

#print("\n\n")

for _ in range(ROUND_COUNT):

nct = bytearray(BLOCK_LENGTH)

for i in range(BLOCK_LENGTH):

nct[i] = ct[rp[i]]

#print("DNCT: {}".format(str(nct)))

for i in range(BLOCK_LENGTH):

ct[i] = rsbox[nct[i]]

ct = xor(ct, key)

return hexlify(ct)

```

Now we have to find out 6-byte key, used for original encryption. Bruteforcing 2^48 keys is not an option here. However, we know, that `fun(key[:3], plaintext) == defun(key[3:], ciphertext)` (by the definion of toofun). Knowing this we can make Meet-in-the-middle attack: encrypt known plaintext with all keys, while decrypting knwon ciphertext with the all keys, hoping to find a common result, thus ubtaining the full key.

```python

fwd = {}

bwd = {}

k1 = ""

k2 = ""

for k in tqdm(keys):

#print("{}".format(k))

f = fun(k, b"16 bit plaintext")

if f in bwd:

print("FOUND: {} {}".format(k, bwd[f]))

k1 = k

k2 = bwd[f]

break

b = defun(k, b'0467a52afa8f15cfb8f0ea40365a6692')

if b in fwd:

print("FOUND: {} {}".format(fwd[b], k))

k1 = fwd[b]

k2 = k

break

fwd[f] = k

bwd[b] = k

```

finally, knowing `key=(k1, k2)` we can decrypt the flag:

`print(defun(k1, defun(k2, rf)))`

## ML-Auth

### Solution

This was a fun challenge. We are given keras model, that performs some sort of classification task on given input, and uses predicted probability as authorization measure.

It's known, that alot of Deep Learning models suffer from [adversarial attacks](https://www.google.com). in a simpliest scenario, we can perform gradient ascent, modifying input image, to maximize chances of input missclasification.

From preprocessing code

```python

prof_h = profile.split('0x')

ip = [int(_, 16) for _ in prof_h[1:]]

ip = np.array(ip, dtype='float32')/255

# reshape profile as required by the trained model

ip = ip.reshape([1,28,28,1])

```

we see, that input of our network is a 1-channel 28x28 "image" with 1-byte values. To generate adversarial example, we can use [foolbox](https://foolbox.readthedocs.io/en/latest/):

```python

fmodel = foolbox.models.KerasModel(model, bounds=(0, 255), preprocessing=(0, 255))

attack = foolbox.attacks.L1BasicIterativeAttack(fmodel)

```

we're using L1 as a metric. Input data will be divided by 255, before supplementing it to our model. Now we can perform an attack applying modifications to random image:

```python

d = np.random.rand(28,28,1) * 255

adversarial = attack(d, 0)

```

Only thing left is build token, that can be sent in url:

```python

profile = "".join([hex(int(t)) for t in adversarial.ravel()])

```

## GenuineCounterMode

### Statement

can you get the flag?

```python

#!/usr/bin/env python3

from Crypto.Cipher import AES

from Crypto.Util import Counter

from Crypto import Random

from secret import flag, key

from hashlib import sha256

from Crypto.Util.number import *

from binascii import hexlify

H = AES.new(key, AES.MODE_ECB).encrypt(bytes(16))

sessionid = b''

n = 327989969870981036659934487747327553919

def group(a, length=16):

count = len(a) // length

if len(a) % length != 0:

count += 1

return [a[i * length: (i + 1) * length] for i in range(count)]

def GHASH(ciphertext, nonce):

assert len(nonce) == 12

c = AES.new(key, AES.MODE_ECB).encrypt(nonce + bytes(3) + b'\x01')

blocks = group(ciphertext)

tag = bytes_to_long(c)

for i, b in enumerate(blocks):

tag += (bytes_to_long(b) * pow(bytes_to_long(H), i + 1, n)) % n

return long_to_bytes(tag)

def encrypt(msg):

nonce = sessionid + Random.get_random_bytes(2)

assert len(nonce) == 12

ctr = Counter.new(32, prefix=nonce)

cipher = AES.new(key, AES.MODE_CTR, counter=ctr)

ciphertext = cipher.encrypt(msg)

tag = GHASH(ciphertext, nonce)

return (nonce, ciphertext, tag)

def decrypt(nonce, ciphertext, tag):

assert len(nonce) == 12

assert GHASH(ciphertext, nonce) == tag

ctr = Counter.new(32, prefix=nonce)

cipher = AES.new(key, AES.MODE_CTR, counter=ctr)

plaintext = cipher.decrypt(ciphertext)

return plaintext

def main():

global sessionid

username = input('Enter username: ')

sessionid = sha256(username.encode()).digest()[:10]

while True:

print("Menu")

print("[1] Encrypt")

print("[2] Decrypt")

print("[3] Exit")

choice = input("> ")

if choice == '1':

msg = input('Enter message to be encrypted: ')

if 'flag' in msg:

print("You cant encrypt flag :(")

continue

c = encrypt(msg.encode())

nonce = hexlify(c[0]).decode()

ciphertext = hexlify(c[1]).decode()

tag = hexlify(c[2]).decode()

print(nonce + ':' + ciphertext + ':' + tag)

continue

if choice == '2':

nonce, ciphertext, tag = input(

'Enter message to be decrypted: ').split(':')

nonce = long_to_bytes(int(nonce, 16))

ciphertext = long_to_bytes(int(ciphertext, 16))

tag = long_to_bytes(int(tag, 16))

pt = decrypt(nonce, ciphertext, tag).decode()

if pt == 'may i please have the flag':

print("Congrats %s" % username)

print("Here is your flag: %s" % flag)

print(pt)

continue

if choice == '3':

break

if __name__ == '__main__':

main()

```

### Solution

We are given a server, that can encrypt everything, that doesn't contain word 'flag' in it. The only way to get the flag is to ask for it politely (e.g. submit properly ecrypted message `may i please have the flag`), only then it will return proper flag.

We can see, that AES is used CTR mode. That means, that AES generates a `key`, and plaintext is just a XORer with the said `key`. Therefore, we can easily manipulate ciphertext to modify the message: we can encrypt random message `rmsg` and then provide `encrypt(rmsg) XOR rmsg XOR "may i please have the flag"`. However, this would've been too easy, so we encryption also generates a `tag`, which is a function of ciphertext, and it's verified on every decription. Let's see if we can break it:

```python

H = AES.new(key, AES.MODE_ECB).encrypt(bytes(16))

n = 327989969870981036659934487747327553919

def GHASH(ciphertext, nonce):

assert len(nonce) == 12

c = AES.new(key, AES.MODE_ECB).encrypt(nonce + bytes(3) + b'\x01')

blocks = group(ciphertext)

tag = bytes_to_long(c)

for i, b in enumerate(blocks):

tag += (bytes_to_long(b) * pow(bytes_to_long(H), i + 1, n)) % n

return long_to_bytes(tag)

```

Few things to note here:

* `c` is just a function of `nonce`

* GHASH is a function of `ciphertext, nonce, H`. Out of this three, only H is unknown

* `n` is prime. Which means we can compute inverse module n really easy

Let's assume that we have a message `m` less than one block (16 bytes). Then it's tag is `c + (m * H) mod n`. We want to obtain H. To do this we can obtain 2 different messages with the same `nonce` , and then:

```

tag1 = c + (m1 * H) mod n

tag2 = c + (m2 * H) mod n

-----Therefore----

tag1-tag2 = (m1-m2) * H mod n

-----Therefore----

H = (tag1-tag2) * modInv(m1-m2, n)

```

Here `modInv(a, n)` is inverse module `n`. As mentioned above, `n` us prime, therefore we can use [EGCD]{https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm} to compute inverse

Next goal: obtain two short messages with same value of nonce. Fortunatelly, `nonce` has only 2 random bytes, which means we can just spam requests to encrypt random messages, until two of them have same `nonce`. Due to birthday paradox we're expected to make only about 256 requests

```python

from pwn import *

def getCollision():

was = {}

conn = remote('crypto.ctf.nullcon.net', 5000)

conn.send('wimag\r\n')

#conn.recvline()

i = 1

res = ""

while True:

print(conn.recvuntil('>', drop=True))

conn.send('1\n')

b = str(i)

print(conn.recvuntil(':', drop=True))

print(b)

conn.send(b)

conn.send("\r\n")

s = conn.recvline()

print(s)

nonce, _, _ = s.split(':')

if nonce in was:

was[nonce].append((b, s))

res = nonce

break

was[nonce] = [(b, s)]

i += 1

with open("tmp.txt", "w") as otp:

otp.write("{}: {}\n{}: {}".format(was[res][0][0], was[res][0][1], was[res][1][0], was[res][1][1]))

```

Now, we know H, time to retrieve the flag:

1. Encrypt message of the same length, like "may i please have the galf"

2. Retrieve value of `c` for GHASH:

```python

blocks = group(ciphertext)

t = 0

for i, b in enumerate(blocks):

t += (bytes_to_long(b) * pow(H, i + 1, n)) % n

c = itag - t

if c < 0:

c += n

```

3. Modify the ciphertext:

```python

ciphertext = xor(ciphertext, [ord(x) for x in b"may i please have the flag\x00"])

ciphertext = xor(ciphertext, [ord(x) for x in b"may i please have the galf\x00"])

```

4. Calculate the tag (just use same logics as in GHASH)

Original writeup (https://github.com/wimag/ctf/blob/master/nullcon/README.md#2fun).