• Event: starctf2018
  • Category: crypto
  • Points: 606/625
  • Solves: 14/13

This is a writeup for 2 very similar tasks named ssss and ssss2.
The second one is a harder version, but required knowledge of cryptography concepts is the same. The difference is only that it involves more logical thinking.

Here are original scripts of the tasks: ssss and ssss2. Also the information with IP and port is provided.

Reverse engineering ssss.py

There are AES, HMAC, sha256 and Argon2 in the code but it is not as complicated as it seems to be. Only AES is crucial here, the rest isn’t important.

def dosend(self, msg):
    print "sending "+msg
    if self.k!='':
        self.r += 1
        ctr_e=Counter.new(128, initial_value=self.r)
        a=AES.new(key=self.k,mode=AES.MODE_CTR,counter=ctr_e)
        pad = 16 - len(msg)%16
        plain = msg + chr(pad)*pad
        msg = ''
        for i in range(len(plain)/16):
            msg += a.encrypt(plain[i*16:(i+1)*16])
    self.request.sendall(msg)

def dorecv(self):
    msg = self.request.recv(1024)
    assert len(msg)>0
    if self.k!='':
        self.r += 1
        ctr_e=Counter.new(128, initial_value=self.r)
        a=AES.new(key=self.k,mode=AES.MODE_CTR,counter=ctr_e)
        cmsg = msg
        msg = ''
        assert len(cmsg)%16==0
        for i in range(len(cmsg)/16):
            msg += a.decrypt(cmsg[i*16:(i+1)*16])
        msg = msg[:-ord(msg[-1])]
    return msg

Functions dosend and dorecv send the data. If a secret value ( self.k ) is not set, the data is sent to the user as is. When this value is set, the message is encrypted using AES 128 in counter mode (CTR). The counter (self.r) is incremented every time before initializing AES class - a=AES.new(key=self.k,mode=AES.MODE_CTR,counter=ctr_e).

But encryption in this mode works in a way that the data is split into blocks of 16 bytes. Every block is encrypted independently with the same key. The counter is incremented by 1 for each block. The counter repeats in the program, which is a serious mistake.

The server receives 3 commands depending on the first character of the data sent by us:

  • “\x00”
  • “\x01”
  • “\x02”
if p[0]=='\x00':
    if len(p)<17:
        self.dosend('\xff'+'\x01')
        break
    self.n1 = p[1:17]
    self.n2 = hashlib.sha512(self.n1).digest()[:16]
    self.buf = argon2.argon2_hash(password=secret, salt=self.n1+self.n2, t=100, m=1000, p=10, buflen=128, argon_type=argon2.Argon2Type.Argon2_i)
    self.mk = self.buf[:16]
    msg = self.n2
    mac = hmac.new(self.mk,msg,hashlib.sha512).digest()[:8]
    self.dosend('\x00'+msg+mac)

In command "\x00" we can “register” our 16-byte value, in response we get hash from this value, and HMAC appended to it. Some internal values are set.

elif p[0]=='\x01':
    if len(p)<25:
        self.dosend('\xff'+'\x01')
        break
    self.r = int(binascii.hexlify(p[1:17]),16)
    mac = hmac.new(self.mk,p[1:17],hashlib.sha512).digest()[:8]
    if mac != p[17:25]:
        self.dosend('\xff'+'\x02')
        break
    msg = '\x01' + p[1:17]
    self.dosend(msg)
    self.k = self.buf[16:32]
    msg = '\x02' + menu
    self.dosend(msg)

In command "\x01" we can turn on encryption. We do it by sending the data received from the "\x00" command. The server only checks whether HMAC is correct and sets self.k to the value we cannot know. This value is used as a key for AES encryption inside dorecv and dosend functions. From this point all data sent and received is encrypted.

elif p[0]=='\x02':
    if self.k == '':
        self.dosend('\xff'+'\x03')
        break
    k=p[5:]
    if p[1:5] == 'set ':
        self.dosend('\x02'+'value?')
        v = self.dorecv()
        assert v[0] == '\x02'
        v = v[1:]
        self.dat[k] = v
        self.dosend('\x02'+'OK')
    elif p[1:5] == 'get ':
        v = self.dat[k] #the flag is in self.dat['flag']
        self.dosend('\x02'+v)
    else:
        self.dosend('\x02'+'invalid')

We can see that in "\x02" command, we can gain a flag easily, we only need to know how to encrypt and decrypt messages without the key.

Breaking CTR encryption with repeating key

Whenever it is needed to break some block cipher cryptography, I recommend to look at wikipedia. To be honest AES CTR isn’t a block cipher, but the keystream is generated block by block.

Below we can see a diagram of the algorithm (from wikipedia).

encryption

decryption

This is an algorithm for encrypting and decrypting data, it will look the same for every block cipher function. In our case it is AES. You can see that during encryption/decryption, keystream for each block is computed. When it is xored with plaintext, it gives ciphertext. The function in the block takes as an input a secret key and a counter. It always produces the same output for the same counter and secret key.

When we know the keystream, we can decipher the message. Note that there is a place in the script (in command "\x01") where the program sends to us encrypted known message - msg = '\x02' + menu. When the ciphertext and plaintext is known, we can obtain the keystream! Just xor ciphertext with plaintext.

To read the flag, we need to obtain more bytes of keystream. This can be made by setting a variable (set command) and reading it. After obtaining keystream for enough counter values, it is possible to read the flag (xor the keystream with received ciphertext). The script of solution can be found here

solving ssss2

The idea of solving the second task is the same. The code was changed a little bit and solution involves more logical thinking.

There are 2 crucial changes:

  • 12 captchas before getting the flag, that means that it is needed to get longer keystream
elif p[1:5] == 'get ':
    v = self.dat[k]
    if k[0]=='f':
        ok = True
        for i in range(12):
            a = random.randint(0,10000)
            b = random.randint(0,10000)
            self.dosend(str(a)+'+'+str(b)+'=?')
            c = self.dorecv()
            assert c[0] == '\x02'
            c = c[1:]
            try:
                c = int(c)
                if a+b != c:
                    ok=False
            except:
                ok = False
        if not ok:
            self.dosend('\xff'+'\x04')
            break
  • It is no longer possible to set a big variable in self.dat dictionary
if p[1:5] == 'set ':
    self.dosend('\x02'+'value?')
    v = self.dorecv()
    assert v[0] == '\x02'
    v = v[1:9]
    self.dat[k] = v
    self.dosend('\x02'+'OK')

We have to find out another way to obtain the keystream.

Interesting snippet of the code is here:

else:
    self.dosend('\x02'+'invalid')

This part of the code is triggered after sending inproperly constructed "\x02" command. In this place we gain one block of the keystream for next counter. To do this we exchange messages with the server. When only one block of the keystream is left, we need to send encrypted command "\x02bad". Then we receive ciphertext for known message - "\x02invalid". We xor it with with this message and the result is a block of the keystream for next counter.

Full code is here