Le but du challenge est de trouver une contrefaçon sur le code d'authentification de message Macaron.Service : nc challenges1.france-cybersecurity-challenge.fr 2005
On nous donne le code d'un serveur sur lequel on peut signer des messages :
#!/usr/bin/env python3import osfrom hashlib import sha256import hmacimport sysfrom Crypto.Util.number import long_to_bytesfrom Crypto.Util.Padding import padfrom flag import flagclass Macaron():def __init__(self, k1 = os.urandom(16), k2 = os.urandom(16)):self.ctr = 0self.k1 = k1self.k2 = k2def tag(self, input):m = pad(input, 2 * 30)nb_blocks = len(m) // 30tag_hash = bytearray(32)nonce_block = long_to_bytes(self.ctr, 2)prev_block = nonce_block + m[:30]tag_nonce = nonce_blockself.ctr += 1for i in range(nb_blocks - 1):nonce_block = long_to_bytes(self.ctr, 2)next_block = nonce_block + m[30*(i+1):30*(i+2)]big_block = prev_block + next_blockdigest = hmac.new(self.k1, big_block, sha256).digest()tag_hash = bytearray([x ^ y for (x,y) in zip(tag_hash, digest)])prev_block = next_blocktag_nonce = tag_nonce + nonce_blockself.ctr += 1tag_hash = hmac.new(self.k2, tag_hash, sha256).digest()return tag_hash, tag_noncedef verify(self, input, tag):m = pad(input, 2 * 30)tag_hash, tag_nonce = tagnb_blocks_m = len(m) // 30nb_blocks_nonce = len(tag_nonce) // 2if nb_blocks_nonce != nb_blocks_m:return Falseif len(tag_nonce) % 2 != 0 or len(tag_hash) % 32 != 0:return Falsetag_hash_ = bytearray(32)prev_block = tag_nonce[:2] + m[:30]for i in range(nb_blocks_m - 1):next_block = tag_nonce[2*(i+1):2*(i+2)] + m[30*(i+1):30*(i+2)]big_block = prev_block + next_blockdigest = hmac.new(self.k1, big_block, sha256).digest()tag_hash_ = bytearray([x ^ y for (x,y) in zip(tag_hash_, digest)])prev_block = next_blocktag_hash_recomputed = hmac.new(self.k2, tag_hash_, sha256).digest()return (tag_hash == tag_hash_recomputed)def menu():print("Commands are:")print("|-> t tag a message")print("|-> v verify a couple (message, tag)")print("|-> q Quit")if __name__ == "__main__":L = []macaron = Macaron()while len(L) <= 32:try:menu()cmd = input(">>> ")if len(cmd) == 0 or cmd not in ['t', 'v', 'q']:continueif cmd == 'q':breakif cmd == 't':print("Input the message:")message = str.encode(input(">>> "))if not len(message):print("Error: the message must not be empty.")continuetag = macaron.tag(message)print("Tag hash: {}".format(tag[0].hex()))print("Tag nonce: {}".format(tag[1].hex()))L.append(message)elif cmd == 'v':print("Input the message to verify:")message = str.encode(input(">>> "))if not len(message):print("Error: the message must not be empty.")continueprint("Input the associated tag hash:")tag_hash = bytearray.fromhex(input(">>> "))print("Input the associated tag nonce:")tag_nonce = bytearray.fromhex(input(">>> "))check = macaron.verify(message, (tag_hash, tag_nonce))if check:if message not in L:print("Congrats!! Here is the flag: {}".format(flag))else:print("Tag valid, but this message is not new.")else:print("Invalid tag. Try again")except:print("Error: check your input.")continue
Une signature consiste en un couple (tag_hash, tag_nonce). Si on arrive à fournir au serveur un message signé sans qu'on ait généré sa signature avant, c'est gagné.
Le serveur initialise trois données :
Un compteur ctr à 0
Deux clés k1 et k2 pseudo-aléatoires a priori inexploitables
La signature fonctionne de la façon suivante :
Padder le message m pour avoir une taille multiple de 60 octets (standard PKCS, donc si on envoie un message de la bonne taille, un bloc entier de padding sera ajouté, garantissant l'unicité du message paddé)
On commence à construire tag_nonce à l'aide du compteur sur 2 octets en big endian (par exemple, 0 devient "0000", 1 devient "0001")
On initialise tag_hash (32 octets) à 0
Pour chaque bloc de 30 octets de m, on construit un big_block qui est la concaténation de deux sous-blocs :
Le premier sous-bloc est le next_block de l'itération précédente (si c'est la première itération, alors il s'agit du premier tag_nonce concaténé aux 30 premiers octets du message)
Le deuxième sous-bloc, next_block est donné par la concaténation du nouveau nonce (compteur incrémenté) et des 30 octets suivants de m.
Ce big_block est passé dans un HMAC avec la clé k1
tag_hash est mis à jour en étant XORé avec ce HMAC
On rajoute le nouveau nonce à tag_nonce
A la fin, tag_hash est un HMAC de lui-même avec la clé k2 et on le renvoie aux côtés de tag_nonce
Un exemple pour y voir plus clair. Supposons que le compteur soit à 0 et que je veuille signer le message aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(60 caractères).
Mon message est d'abord paddé : on rajoute 60 octets de valeur ASCII 60, c'est-à-dire le caractère <
. m ressemble donc à aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
.
Le tag_nonce est initialisé à "0000". On découpe notre message en blocs de 30 octets :
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Les HMAC calculés seront ceux de :
\x00\x00aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\x00\x01aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\x00\x01aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\x00\x03<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Ces trois HMAC seront XORés entre eux, puis le résultat passera dans un nouveau HMAC avec une clé différente. Le tag_nonce renvoyé sera 0000000100020003
.
Un petit schéma :
Passons désormais à l'exploitation. Comment construire un message qui donnera un tag_hash que l'on prévoir à l'avance ?
Il est évident que l'on ne pourra pas recalculer un tag_hash, puisque l'on a pas la clé k2 (et aussi parce que le HMAC c'est assez bien foutu donc pas d'attaque de type hash-length extension).
L'idée serait donc de soumettre un message au serveur, d'obtenir un hash, et d'essayer de construire un message différent qui donne le même hash, en se concentrant sur l'idée d'obtenir une valeur identique avant le calcul du dernier HMAC.
A ce moment-là, on peut avoir l'intuition : pour avoir deux messages identiques à partir d'un XOR de plusieurs valeurs, il suffit de rajouter par exemple deux valeurs identiques, dont le XOR va s'annuler.
La faiblesse lors de la vérification de la signature consiste en le fait que l'on peut non seulement envoyer des nonce non-ordonnés, mais surtout les réutiliser.
Sans plus attendre, voici ma solution. On demande au serveur à signer le message aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
.
Son découpage en blocs est le suivant :
\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Le calcul effectué par le serveur est :
hmac(\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) #XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #XOR hmac(\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #XOR hmac(\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
Rajoutons deux blocs qui s'annulent au milieu :
hmac(\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) #XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #XOR hmac(\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #XOR hmac(\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
Seul problème à régler : les blocs ne se recouvrent pas (construction avec les previous_block et next_block). En effet, il faut que la fin de ce qui rentre dans le deuxième HMAC coïncide avec le début de ce qui rentre dans le troisième HMAC.
Pour cela, il suffit d'intercaler deux autres blocs de la façon suivante :
hmac(\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) #XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) .XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) .XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #XOR hmac(\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #XOR hmac(\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
Les 4 blocs rajoutés au total s'annulent car 2 à 2 identiques, et respectent bien le suivi des sous-blocs. Tout est bon !
$ nc challenges1.france-cybersecurity-challenge.fr 2005Commands are:|-> t tag a message|-> v verify a couple (message, tag)|-> q Quit>>> tInput the message:>>> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbTag hash: 3baec174ae8d9af05f83650b377f49d51b8ebb3a97cfc147cc81eaab043d3dc3Tag nonce: 000000010002000300040005Commands are:|-> t tag a message|-> v verify a couple (message, tag)|-> q Quit>>> vInput the message to verify:>>> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbInput the associated tag hash:>>> 3baec174ae8d9af05f83650b377f49d51b8ebb3a97cfc147cc81eaab043d3dc3Input the associated tag nonce:>>> 0000000100020001000200010002000300040005Congrats!! Here is the flag: FCSC{529d5fb1ea316b2627c16190060af9f70dc420438afa7e8eb71d144a54a0}