ABCTF2016 [WriteUp] Encryption Service - 140

J'ai participé à l'ABCTF qui est un CTF en ligne de type jeopardy qui s'est déroulé du 15 Juillet 2016 au 22 Juillet 2016.
Je faisais partie de l'équipe Zenk-Security, on s'est bien amusé !
Je me suis bien éclaté sur un challenge de cryptographie : Encryption Service, du coup il mérite un petit write up !
Ce challenge, classé en cryptographie, valait 140 points, ce qui était pas mal du tout sachant que les 3 dernières épreuves valaient 200, 200, et 300 points.

Énoncé

See if you can break this!!
You can connect with nc 107.170.122.6 7765 and the source can be found here.

Le lien vers la source était un lien pastebin.
Voici la source :

#/usr/bin/env python
from Crypto.Cipher.AES import AESCipher

import SocketServer,threading,os,time
import signal

from secret2 import FLAG, KEY

PORT = 7765

def pad(s):
  l = len(s)
  needed = 16 - (l % 16)
  return s + (chr(needed) * needed)

def encrypt(s):
  return AESCipher(KEY).encrypt(pad('ENCRYPT:' + s.decode('hex') + FLAG))

class incoming(SocketServer.BaseRequestHandler):
    def handle(self):
        atfork()
        req = self.request

        def recvline():
            buf = ""
            while not buf.endswith("\n"):
                buf += req.recv(1)
            return buf
        signal.alarm(5)

        req.sendall("Send me some hex-encoded data to encrypt:\n")
        data = recvline()
        req.sendall("Here you go:")
        req.sendall(encrypt(data).encode('hex') + '\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()

Analyse

Donc on a un service qui utilise le chiffrement AES, mais le mode n'est pas spécifié.

Un peu de recherche sur AESCipher et on apprend que le mode par défaut est ECB.

Les blocs utilisés font 16 octets, ce qui explique également la fonction de padding « def pad(s): », qui ajoute du padding, même si la longueur de la chaîne totale est un facteur de 16 octets.

Notre message envoyé est entouré d'un préfixe et d'un suffixe, avant de passer par la fonction pad(s) et le chiffrement :

  return AESCipher(KEY).encrypt(pad('ENCRYPT:' + s.decode('hex') + FLAG))

Le préfixe est « ENCRYPT: » (donc sur 8 octets) et le suffixe le flag.
La longueur de la clé (KEY) ne change rien à la longueur du texte chiffré contrairement à la longueur notre chaîne envoyée en hexadécimal et celle du flag.
Ça sent le « chosen-plaintext attack »...
Ce serait bien de connaître la longueur du flag !

Résolution

Le mode ECB chiffre les blocs de 16 octets et concatène les résultats.
Si on envoie un caractère en hexadécimal, puis que la tentative suivante on en essaie deux, etc..., à un moment un bloc chiffré de 16 octets sera rajouté.
Cela nous permet de connaître la taille du flag :

'a'     => e80636ed084491d591c42d07ee00b9cd64851b9b4880d691d8e84fce0c35bbef
'aa'    => cac1b7717500255eef6012f2f67f423dbe7b5043b8560a65301e576c391a8ed4
'aaa'   => b94c4d0cbf2edb52efb805ea7aacbe44a1f9a1e562a68962c063a2bbc31fea52
'aaaa'  => f68e94b63d76c42f9ff02f8f99c778b17bdbd203a944cfb9f9bd97aad00c738f2f4af46106df0f8597a39283c045ee27

Avec quatre lettres on remplit le dernier bloc, et la fonction de padding ajoute un bloc de 16 octets de padding.
Donc 'ENCRYPT:' fait 8 octets, nos 4 caractères de la chaîne envoyée, et le bloc chiffré (sans le dernier bloc ajouté par la fonction pad(s)) fait 32 octets.
La taille du flag est donc de 20 caractères (32-8-4=20).

Maintenant pour retrouver le flag, ce sera pas beaucoup plus complexe.
Seul le suffixe est inconnu (le flag), et il fait 20 caractères.
Comme les blocs chiffrés sont indépendants, il est possible de travailler bloc par bloc.
Prenons par exemple le premier bloc « ENCRYPT:00000000 » ( les '0' étant les caractères envoyés ) si on le chiffre il nous donnera par exemple le bloc chiffré : a005673f8b404d921affa0d0d99a8dda.
Maintenant on supprime la dernière lettre du bloc : « ENCRYPT:0000000? », le dernier octet du bloc de 16 octets deviens donc le premier octet du flag, ce qui nous donnera un autre bloc chiffré, par exemple be758c24647becd6e06b2584d7964489.
Connaissant le texte chiffré et tous les caractères du texte clair sauf le dernier, il sera facile d'essayer tous les caractères jusqu'à retrouver le même bloc chiffré :

"ENCRYPT:0000000a" == "be758c24647becd6e06b2584d7964489" => False
"ENCRYPT:0000000b" == "be758c24647becd6e06b2584d7964489" => False
etc...

Un fois trouvé, il suffit alors de supprimer les deux dernières lettres du bloc.
Les deux dernières lettres seront donc les deux premières du flag, encore une fois il nous reste à deviner la dernière.
Nous répétons ce principe jusqu'à ce que nous avons le flag complet.
Pour notre flag, on va donc travailler sur deux blocs de 16 octets car il est composé de 20 caractères :

ENCRYPT:00000000 0000000000000000 FLAGSUR20CARACTERESX

Voici mon script python qui automatise tout ça et ressort juste le flag :

#/usr/bin/env python
import socket

hote = "107.170.122.6"
port = 7765
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_-+{}'
flag = ""

def remote_encrypt(plaintext):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((hote, port))
    s.recv(2048)
    s.send(plaintext.encode('hex')+"\n")
    s.recv(2048)
    cipher = s.recv(2048)
    s.close()
    return cipher

padding = "000000000000000000000000"
while len(flag) < 20:
    padding = padding[:-1]

    # get block cipher
    cipher = remote_encrypt(padding)

    # find the same block cipher
    for c in chars:
        tmp = padding + flag + c
        tmp_cipher = remote_encrypt(tmp)

        # we found one letter
        if tmp_cipher[:64] == cipher[:64]:
            flag += c 
            break
print "[+]FLAG : "+flag

N'hésitez pas à me poser toutes vos questions en commentaire.

Références

https://pythonhosted.org/pycrypto/Crypto.Cipher.AES-module.html#new
https://en.wikipedia.org/wiki/Chosen-plaintext_attack

Aller plus loin

http://zachgrace.com/2015/04/17/attacking-ecb.html
https://fr.wikipedia.org/wiki/Moded'opération(cryptographie)