# gmx
**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.
## Challenge description
defund created a nonconformist hybrid cryptosystem. He even made a service running at `web.angstromctf.com:3000`; here's the [public key](https://angstromctf.com/static/crypto/gmx/pk). All you have to do is decrypt this [flag](https://angstromctf.com/static/crypto/gmx/flag.enc), which was encrypted with this [key](https://angstromctf.com/static/crypto/gmx/key.enc). We've also provided the relevant [source code](/static/crypto/gmx/gmx.zip). Note: connect with netcat or an equivalent tool.
## Analyzing the source code
The source is composed of **4 files**: **aes.py**, **gen.py**, **gm.py**, and **server.py**. Let's start with **aes.py**:
### aes.py
```pythonfrom Crypto import Randomfrom 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
```pythonfrom Crypto import Random
import aesimport 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
```pythonimport base64import signalimport SocketServer
import aesimport 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 = Trueserver = ReusableTCPServer(('0.0.0.0', PORT), incoming)
print 'Server listening on port %d' % PORTserver.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
```pythonfrom 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:
```pythonp, q = sk```
First it splits `sk` in two components. A quick look at the `generate` function confirms that `sk` is a tuple.
```pythonm = 0for 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**.
```pythonh = '%x' % ml = 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.
## Exploitation
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:
```pythonif 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:
```pythonimport aesimport base64import 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' * 16print 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:
```pythonimport aesimport base64import gmimport socket
# Connecting to the serversock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)sock.connect(('web.angstromctf.com', 3000))
# Yay!print '[+] Connected'
# Reading the encrypted keywith open('key.enc') as f:    enc_key = f.read().split('\n')
# Initializing the key for our methodbase_key = [0] * 128
# recv useless garbageprint sock.recv(1024)
# Send the key, which is basically all 0s at this pointfor i in range(len(base_key)):    sock.send(str(base_key[i]) + '\n')
# recv useless garbage againprint sock.recv(1024)
# Setting the decryption key to its initial valuedec_key = '\xff' * 16
# Retrieving the "witness" base64 encrypted stringb64witness = 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 againsock.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 fileprint '[+] 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](https://github.com/Inshallhack/Write-ups/raw/master/Angstrom-CTF-2018/gmx/images/angstrom_gmx_flag.jpg)
**Flag: actf{a_bit_of_homomorphism}**
## Conclusion
This CTF was really quite interesting. I especially enjoyed this challenge; quit making **RSA challenges** people, we need more of these!