/ ndh2k17

NDH2K17 - Merkle

Pour ce challenge du wargame NDH édition 2017 nous avions à notre dispostion un code python et une capture de trames réseau.

Le code python était le suivant :

from math import sqrt
from random import randint, choice, shuffle
import hashlib
import sys
import json
from collections import OrderedDict
import socket
from Crypto import Random
from Crypto.Cipher import AES

pad = lambda s: s + (AES.block_size - len(s) % AES.block_size) * chr(AES.block_size - len(s) % AES.block_size)
unpad = lambda s : s[0:-ord(s[-1])]

def encrypt(message, key):
    message = pad(message)
    IV = Random.new().read(AES.block_size)
    aes= AES.new(key, AES.MODE_CBC, IV)
    return "%s%s" % (IV, aes.encrypt(message))

def decrypt(message, key):
    IV = message[:AES.block_size]
    aes = AES.new(key, AES.MODE_CBC, IV)
    return unpad(aes.decrypt(message[AES.block_size:]))

server = "0.0.0.0"
is_server = True
selectected_key = 0
shared_secret = ''
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

def generate_challenges():
    challenges = {}
    for i in xrange(512):
        challenges[i] = ''.join(choice(''.join([chr(_) for _ in xrange(0, 255)])) for x in range(AES.block_size))
    items = challenges.items()
    shuffle(items)
    challenges = OrderedDict(items)
    return challenges

def cipher(challenge):
    key = choice(''.join([chr(_) for _ in xrange(0, 255)])) * 16
    return encrypt(challenge, key)

def serialize_challenge(challenges):
    message = []
    for k, v in challenges.items():
        data = cipher('OK%s%s' % (k,v)).encode("hex")
        message.append(data)
    return json.dumps(message)

if __name__ == "__main__":

    if len(sys.argv) > 1:
        server = sys.argv[1]
        is_server = False

    # Prepare exchange    
    try:
        if is_server:
            challenges = generate_challenges()
            serialized_challenges = serialize_challenge(challenges)
            print("Start server")
            
            s.bind((server, 31337))
            while True:
                s.listen(5)
                client, accept = s.accept()

                # set exchange
                client.send(serialized_challenges)
                shared_secret = challenges[int(client.recv(32))]
                print("Key exchange completed")

                while True:
                    secret_message = client.recv(1024)
                    message = decrypt(secret_message, shared_secret)
                    print("<<< %s" % message)
                    message = raw_input(">>> ")
                    secret_message = encrypt(message, shared_secret)
                    client.send(secret_message)
        else:
            print("Connect to %s" % server)
            s.connect((server, 31337))
            while True:
                challenges = s.recv(51200)
                # set exchange
                challenges = json.loads(challenges)
                selected_challenge = choice(challenges)

                #BF challenge and send id
                for k in xrange(0, 255):
                    key = chr(k) * 16
                    try:
                        unciphered = decrypt(selected_challenge.decode("hex"), key)
                        if unciphered.startswith("OK"):
                            selected_challenge = unciphered
                            break
                    except TypeError:
                        pass
                key_index = selected_challenge[2:-16]
                shared_secret = selected_challenge[-16:]
                s.send(key_index)

                print("Key exchange completed")

                while True:
                    message = raw_input(">>> ")
                    secret_message = encrypt(message, shared_secret)
                    s.send(secret_message)
                    secret_message = s.recv(1024)
                    message = decrypt(secret_message, shared_secret)
                    print("<<< %s" % message)

    except:
        s.close()

Après lecture on peut dire que le code est une implémentation de l'algorithme d'échange de clé Merkle permettant ensuite à un client et un serveur de s'échanger des messages chiffrés.

L'algorithme ici peut être résumé de la manière suivante :
1- le serveur génère un dictionnaire de challenges aléatoires

2- le serveur chiffre chaque challenge préfixé par 'OK' et l'index du challenge (exemple OK125)

3- le serveur envoie les challenges chiffrés au client

4- le client choisi un des challenges chiffrés au hasard

5- le client essaye de les déchiffrer en itérant toutes les clés possibles jusqu'à obtenir un clair commencant par 'OK'

6- le client envoie ensuite au serveur l'index situé juste après le OK et conserve le reste comme secret partagé

7- le serveur grâce à l'index envoyé par le client récupère le secret partagé dans son dictionnaire

8- le serveur et le client peuvent maintenant s'echanger des messages chiffrés en utilisant le secret partagé comme clé.

Pour la résolution du challenge on récupère dans la capture réseau les messages échangés entre le client et le serveur comprenant les challenges chiffrés, l'index du challenge selectionné par le client et les messages chiffrés.

L'index du challenge utilisé lors de cette échange est donc '206'.
Nous reprenons la partie cliente du code fourni afin d'obtenir le script suivant :

challenges=["c354e6c51ab8b5ac3da4e200a846deed625716819509fb9473bd0bdbb3a07c1422e2cb8d2bc46f490a5b3894b1c92318"] 
challenges= json.loads(challenges)

for selected_challenge in challenges:
	for k in xrange(0, 255):
	    key = chr(k) * 16
	    try:
		unciphered = decrypt(selected_challenge.decode("hex"), key)
		#print unciphered                        
		if unciphered.startswith("OK"):
		    selected_challenge = unciphered
		    break
	    except TypeError:
		pass
	if selected_challenge[2:-16] == '206':
		break

Ce script permet pour chaque challenge de trouver la clé permettant de le déchiffrer ( if unciphered.startswith('OK'))
puis de vérifier que le challenge correspond à celui utilisé dans la capture réseau (if selected_challenge[2:-16] == '206')
Une fois que le bon challenge a été retrouvé nous isolons le secret partagé et il ne nous reste plus qu'a déchiffer les messages :

shared_secret = selected_challenge[-16:]

s1=';\xb2\xf6\xebk\x05-\xf4\xaa(\xe2\xfa\xe0\x1f\xe7+\xd7DJ\x90\x83\xc8\x1d\x8b\xfd\x93\xf2R\x169\x8e\x80'
s2='\x7f\tv7\xb7=\xd0\xe6\xd8\x1e\xc6-\x17\xf8\xee\x8aQ\xd2\np|j\xa2v\xbe\xca\x08o\xa9\x86\x1d\x8f'
s3="\x8f\xe2\x162\xc7\x94H7\x86T\xb9c\x04/\xfb\x8f\xb49\xe2\xe2\x968\xe0!+'\x08\xbe\xcd\xc6%\xc4\x04\x9b \xc9\xfc\x05[(\xeaz\t\x88\xf1\x11\xea\x82\x9f^\xba\x0c\x12\xaf\x10xq1\xc3\x7fD\xb06L"
s4='\x93\x97\x17c\xb2\x08`\xe0*\x93\xf3\x8e\x89\n\x86\xdbd=\xf3%\x10\xa9.\xfa\xfb\nUn7\xeb\x8f\xed@!\x9e>\x7fbt\xfdZ\xc6\x82\xcb\x17\xd4xx\xbc\xa3j\xaf[J\x83\xb2\x14JL.\xcc\xcc9\xcc'
s5='\x9c\xa6!\xdd\x92\xfe\xb2\x0b\x90\x1b\x02\xfd\xdf?S\xc0x\x7f\x84\xab"86\t\xa6!\x98\x0f<\xd1\xc7j'
s6='2\xcdw\xfeA\x86\xfe;J3\xf1\xafL\xc0\x0fL\x90\xd4\x93K\xab\xc0p:\xac\x8c\xaf\x10\xac\xe0\x1ea'
s7='M7[\xa14\x95\x94tm\x08\x8a\xec\xe7a\xdf.&\xc7\xc9\xe0|\xd7\xbc\x18\xa8\x0c\xc5\r\xa3E\xa5z'

m1 = decrypt(s1, shared_secret)
m2 = decrypt(s2, shared_secret)
m3 = decrypt(s3, shared_secret)
m4 = decrypt(s4, shared_secret)
m5 = decrypt(s5, shared_secret)
m6 = decrypt(s6, shared_secret)
m7 = decrypt(s7, shared_secret)
Hi !
Hi !
Can you give me the flag please ?
yeah ! ndh2k17_angela_sucks_at_crypto
Thx !
Bye
Bye