**gmx** was a 160 point cryptography challenge in **Ångstrom CTF 2018**. I thought it was very interesting, especially because it used an actual cryptosystem I had no knowledge of, and surprisingly validated by less than 30 teams among the almost 2000 that were participating.

defund created a nonconformist hybrid cryptosystem. He even made a service running at `web.angstromctf.com:3000`

; here’s the public key. All you have to do is decrypt this flag, which was encrypted with this key. We’ve also provided the relevant source code. Note: connect with netcat or an equivalent tool.

The source is composed of **4 files**: **aes.py**, **gen.py**, **gm.py**, and **server.py**. Let’s start with **aes.py**:

## aes.py

```
from Crypto import Random
from Crypto.Cipher import AES def encrypt(k, m): iv = Random.new().read(16) cipher = AES.new(k, AES.MODE_CFB, iv) return iv + cipher.encrypt(m) def decrypt(k, c): cipher = AES.new(k, AES.MODE_CFB, c[:16]) return cipher.decrypt(c[16:])
```

Nothing special happening here, these functions are pretty much wrappers to **encrypt** and **decrypt** with **AES in CFB mode** with a **random IV that is prepended to the ciphertext during encryption**.

## gen.py

```
from Crypto import Random import aes
import gm flag = open('flag').read() key = Random.new().read(16)
pk, sk = gm.generate() encflag = aes.encrypt(key, flag)
enckey = gm.encrypt(key, pk) with open('pk', 'w') as f: f.write('\n'.join([str(x) for x in pk])) with open('sk', 'w') as f: f.write('\n'.join([str(x) for x in sk])) with open('key.enc', 'w') as f: f.write('\n'.join([str(x) for x in enckey])) with open('flag.enc', 'w') as f: f.write(encflag)
```

In **gen.py**, we can basically see how the files we were provided were generated; the flag is encrypted using the `encrypt`

function from **aes.py**, and then written to a file. The key is then encrypted with an `encrypt`

function presumably defined in **gm.py**, using the **public key** we have been provided, and then written to a file. Each of the keys in the generated keypair (*pk and sk*) is then also written to a file.

Because the crux of the problem will most likely lie in **gm.py** (*that’s my experience speaking*), let’s continue with **server.py** so as to not get too deep in unnecessary considerations.

## server.py

```
import base64
import signal
import SocketServer import aes
import gm PORT = 3000 message = open('message').read() with open('sk') as f: p = int(f.readline()) q = int(f.readline()) sk = (p, q) class incoming(SocketServer.BaseRequestHandler): def handle(self): req = self.request def receive(): buf = '' while not buf.endswith('\n'): buf += req.recv(1) return buf[:-1] signal.alarm(60) req.sendall('Welcome to the Goldwasser-Micali key exchange!\n') req.sendall('Please send us an encrypted 128 bit key for us to use.\n') req.sendall('Each encrypted bit should be sent line by line in integer format.\n') enckey = [] for i in range(128): enckey.append(int(receive())) key = gm.decrypt(enckey, sk) encmessage = aes.encrypt(key, message) req.sendall(base64.b64encode(encmessage)+'\n') req.close() class ReusableTCPServer(SocketServer.ForkingMixIn, SocketServer.TCPServer): pass SocketServer.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(('0.0.0.0', PORT), incoming) print 'Server listening on port %d' % PORT
server.serve_forever(
```

So basically, the code here waits for us to send an **AES key encrypted with gm** (*which we can now deduce means “Goldwasser-Micali”*), then it **decrypts it using the secret key** generated in **gen.py**. Then, a **certain message** is **encrypted using the decrypted AES key**. It is then **base64-encoded** and sent back to us. Since `message`

is also read from a file, it is safe to assume that it doesn’t change between each connection to the service. An obvious deduction is that the **service will serve as some kind of oracle**.

## gm.py

```
from Crypto.Util.number import *
from gmpy import legendre def generate(): p = getStrongPrime(1024) q = getStrongPrime(1024) n = p*q x = getRandomRange(0, n) while legendre(x, p) != -1 or legendre(x, q) != -1: x = getRandomRange(0, n) return (n, x), (p, q) def encrypt(m, pk): n, x = pk for b in format(int(m.encode('hex'), 16), 'b').zfill(len(m) * 8): y = getRandomRange(0, n) yield pow(y, 2) * pow(x, int(b)) % n def decrypt(c, sk): p, q = sk m = 0 for z in c: m <<= 1 if legendre(z % p, p) != 1 or legendre(z % q, q) != 1: m += 1 h = '%x' % m l = len(h) return h.zfill(l + l % 2).decode('hex')
```

Here comes the non-straightforward part… Because only `gm.decrypt`

is used in **server.py** (*and not gm.encrypt*), we can assume that it is the function of interest in this challenge. Let’s break it down:

First it splits `sk`

in two components. A quick look at the `generate`

function confirms that `sk`

is a tuple.

```
m = 0
for z in c: m <<= 1 if legendre(z % p, p) != 1 or legendre(z % q, q) != 1: m += 1
```

Seeing `m = 0`

, `m <<= 1`

and `m += 1`

, we understand that the rightmost bit of `m`

is set at each iteration. If `legendre(z % p, p) != 1`

or if `legendre(z % q, q) != 1`

, it is set to **1**; otherwise, it is set to **0**. It is not clear what `legendre`

is supposed to do; let’s have a look at Wikipedia:

**<Wikipedia>**

In number theory, the **Legendre symbol** is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number p: its value on a (nonzero) quadratic residue mod p is 1 and on a non-quadratic residue (non-residue) is −1. Its value on zero is 0.

**</Wikipedia>**

Now, just for the sake of being clear, let’s check what a **quadratic residue** is:

**<Wikipedia>**

In number theory, an integer q is called a **quadratic residue** modulo n if it is congruent to a perfect square modulo n.

**</Wikipedia>**

Phew, that is clearer!

Let’s note that when this function is called from **server.py**, since **128 lines are parsed by the service, 128 iterations of the loop occur**. This means that **128 bits are set**, which corresponds exactly to the length of an **AES-128 key**.

```
h = '%x' % m
l = len(h)
return h.zfill(l + l % 2).decode('hex')
```

Then, `m`

is formatted in **hex**, properly padded, decoded and returned. From this analysis follows the fact that `m`

is at most `len(c)`

bits long, and most likely close to that.

Our goal is obviously to retrieve the **AES key** in **key.enc**, so that we can use it to decrypt **flag.enc**.

First, we know that `legendre(a, p)`

returns **0** if **a % p = 0**. Since we have the following line:

```
if legendre(z % p, p) != 1 or legendre(z % q, q) != 1: m += 1
```

we can deduce that sending 128 lines equal to **“0”** to the service will result in the generation of a key `key = "\xff" * 16`

.

Using this property, we retrieve the value of `message`

(*defined in server.py*) using the following script:

```
import aes
import base64
import socket sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('web.angstromctf.com', 3000)) print '[+] Connected' print sock.recv(1024) for i in range(128): sock.send('0\n') print sock.recv(1024)
key = '\xff' * 16
print aes.decrypt(key, base64.b64decode(sock.recv(1024))) sock.close()
```

and we get the following message:

```
Hi, this is defund and you're reading my super secret message! Unfortunately, getting this message is not the challenge whatsoever. I don't have much else to talk about, so I guess follow me at github.com/defund, twitter.com/defunded, and keybase.io/defund. Also, here's a fake flag that you're going to submit anyways:
actf{this_is_a_fake_flag} Good luck with the challenge! ;)
```

Obviously, we try to validate using the fake flag… But it doesn’t work, surprisingly.

We figured that we’re somehow able to control the return value of `legendre`

so that it returns 0 **regardless of what the secret GM key actually is**.

If we were to replace the first line in our all “0” encrypted key with the first line of **key.enc**, we would be able to receive a ciphertext encrypted with a key whose first bit corresponds to the first line of **key.enc**. Then, **it is just a matter of testing whether the bit should be a 1 or a 0**; this is **easily doable by checking which of the two possible keys decrypts the ciphertext to the expected plaintext**!

Because we’re pretty lazy (*at least I am*), we want to reuse the `gm.decrypt`

function to generate our key. It is therefore useful to know that, in the same way `legendre(a, p)`

returns **0** for any value of `p`

provided that `a = 0`

, `legendre(a, p)`

returns **1** for any value of `p`

provided that `a = 1`

. The reason is obvious: **1 is a perfect square**, and since **it is not a prime**, it is not an adequate value for `p`

. Note that **4** would also be an acceptable value, as **2 is not an odd prime**.

With this idea, we create the following (*dirty*) script:

```
import aes
import base64
import gm
import socket # Connecting to the server
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('web.angstromctf.com', 3000)) # Yay!
print '[+] Connected' # Reading the encrypted key
with open('key.enc') as f: enc_key = f.read().split('\n') # Initializing the key for our method
base_key = [0] * 128 # recv useless garbage
print sock.recv(1024) # Send the key, which is basically all 0s at this point
for i in range(len(base_key)): sock.send(str(base_key[i]) + '\n') # recv useless garbage again
print sock.recv(1024) # Setting the decryption key to its initial value
dec_key = '\xff' * 16 # Retrieving the "witness" base64 encrypted string
b64witness = sock.recv(1024) # Decrypting the witness and storing it so as to compare all the subsequent
# results with it.
witness = aes.decrypt(dec_key, base64.b64decode(b64witness)) print 'Witness is: ' + witness # :'( gotta open again
sock.close() for i in range(128): # Open, open, open sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.connect(('web.angstromctf.com', 3000)) print '[+] Connected (' + str(i + 1) + ')' # Getting useless garbage sock.recv(1024) # Setting the current encrypted bit to the one in the encrypted key base_key[i] = int(enc_key[i]) # Send the key for j in range(len(base_key)): sock.send(str(base_key[j]) + '\n') res = '' # Fetching the result, with super dirty error correction, idc while len(res) < 10 or 'Please send' in res: res = sock.recv(1024) # Checking whether the decryption works properly with the key we have if aes.decrypt(dec_key, base64.b64decode(res)) == witness: base_key[i] = 0 # Otherwise, we need to change the key else: # Cause I'm lazy base_key[i] = 1 # Modifying the key as it should be dec_key = gm.decrypt(base_key, (17, 19)) sock.close() # Got the key :-)
print '[+] Key is: ' + ' '.join([str(ord(c)) for c in dec_key]) # Writing to file
print '[+] Writing to \'result\'...'
with open('result', 'w') as fres: with open('flag.enc') as flag: fres.write(aes.decrypt(dec_key, flag.read()))
```

Aaand, we get a jpg file, which contains… **the flag**!

**Flag: actf{a_bit_of_homomorphism}**

This CTF was really quite interesting. I especially enjoyed this challenge; quit making **RSA challenges** people, we need more of these!