Macaron (crypto, 200)
Description du challenge
1
Le but du challenge est de trouver une contrefaçon sur le code d'authentification de message Macaron.
2
3
Service : nc challenges1.france-cybersecurity-challenge.fr 2005
Copied!
Solution
On nous donne le code d'un serveur sur lequel on peut signer des messages :
1
#!/usr/bin/env python3
2
3
import os
4
from hashlib import sha256
5
import hmac
6
import sys
7
from Crypto.Util.number import long_to_bytes
8
from Crypto.Util.Padding import pad
9
from flag import flag
10
11
class Macaron():
12
def __init__(self, k1 = os.urandom(16), k2 = os.urandom(16)):
13
self.ctr = 0
14
self.k1 = k1
15
self.k2 = k2
16
17
def tag(self, input):
18
m = pad(input, 2 * 30)
19
nb_blocks = len(m) // 30
20
21
tag_hash = bytearray(32)
22
nonce_block = long_to_bytes(self.ctr, 2)
23
prev_block = nonce_block + m[:30]
24
tag_nonce = nonce_block
25
self.ctr += 1
26
27
for i in range(nb_blocks - 1):
28
nonce_block = long_to_bytes(self.ctr, 2)
29
next_block = nonce_block + m[30*(i+1):30*(i+2)]
30
big_block = prev_block + next_block
31
digest = hmac.new(self.k1, big_block, sha256).digest()
32
tag_hash = bytearray([x ^ y for (x,y) in zip(tag_hash, digest)])
33
prev_block = next_block
34
tag_nonce = tag_nonce + nonce_block
35
self.ctr += 1
36
37
tag_hash = hmac.new(self.k2, tag_hash, sha256).digest()
38
return tag_hash, tag_nonce
39
40
def verify(self, input, tag):
41
m = pad(input, 2 * 30)
42
tag_hash, tag_nonce = tag
43
44
nb_blocks_m = len(m) // 30
45
nb_blocks_nonce = len(tag_nonce) // 2
46
47
if nb_blocks_nonce != nb_blocks_m:
48
return False
49
50
if len(tag_nonce) % 2 != 0 or len(tag_hash) % 32 != 0:
51
return False
52
53
tag_hash_ = bytearray(32)
54
prev_block = tag_nonce[:2] + m[:30]
55
56
for i in range(nb_blocks_m - 1):
57
next_block = tag_nonce[2*(i+1):2*(i+2)] + m[30*(i+1):30*(i+2)]
58
big_block = prev_block + next_block
59
digest = hmac.new(self.k1, big_block, sha256).digest()
60
tag_hash_ = bytearray([x ^ y for (x,y) in zip(tag_hash_, digest)])
61
prev_block = next_block
62
63
tag_hash_recomputed = hmac.new(self.k2, tag_hash_, sha256).digest()
64
return (tag_hash == tag_hash_recomputed)
65
66
def menu():
67
print("Commands are:")
68
print("|-> t tag a message")
69
print("|-> v verify a couple (message, tag)")
70
print("|-> q Quit")
71
72
if __name__ == "__main__":
73
74
L = []
75
macaron = Macaron()
76
while len(L) <= 32:
77
78
try:
79
menu()
80
cmd = input(">>> ")
81
82
if len(cmd) == 0 or cmd not in ['t', 'v', 'q']:
83
continue
84
85
if cmd == 'q':
86
break
87
88
if cmd == 't':
89
print("Input the message:")
90
message = str.encode(input(">>> "))
91
if not len(message):
92
print("Error: the message must not be empty.")
93
continue
94
95
tag = macaron.tag(message)
96
print("Tag hash: {}".format(tag[0].hex()))
97
print("Tag nonce: {}".format(tag[1].hex()))
98
L.append(message)
99
100
elif cmd == 'v':
101
print("Input the message to verify:")
102
message = str.encode(input(">>> "))
103
if not len(message):
104
print("Error: the message must not be empty.")
105
continue
106
107
print("Input the associated tag hash:")
108
tag_hash = bytearray.fromhex(input(">>> "))
109
110
print("Input the associated tag nonce:")
111
tag_nonce = bytearray.fromhex(input(">>> "))
112
113
check = macaron.verify(message, (tag_hash, tag_nonce))
114
if check:
115
if message not in L:
116
print("Congrats!! Here is the flag: {}".format(flag))
117
else:
118
print("Tag valid, but this message is not new.")
119
else:
120
print("Invalid tag. Try again")
121
122
except:
123
print("Error: check your input.")
124
continue
Copied!
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 :
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
3
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
4
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Copied!
Les HMAC calculés seront ceux de :
1
\x00\x00aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\x00\x01aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
2
\x00\x01aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
3
\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\x00\x03<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Copied!
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 :
1
\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
2
\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
3
\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
4
\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
5
\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
6
\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Copied!
Le calcul effectué par le serveur est :
1
hmac(\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) #
2
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #
3
XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #
4
XOR hmac(\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
5
XOR hmac(\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
Copied!
Rajoutons deux blocs qui s'annulent au milieu :
1
hmac(\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) #
2
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .
3
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .
4
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #
5
XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #
6
XOR hmac(\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
7
XOR hmac(\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
Copied!
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 :
1
hmac(\0\0aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) #
2
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .
3
XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) .
4
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) .
5
XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa) .
6
XOR hmac(\0\1aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #
7
XOR hmac(\0\2bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb) #
8
XOR hmac(\0\3bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
9
XOR hmac(\0\4<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\0\5<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<) #
Copied!
Les 4 blocs rajoutés au total s'annulent car 2 à 2 identiques, et respectent bien le suivi des sous-blocs. Tout est bon !
1
$ nc challenges1.france-cybersecurity-challenge.fr 2005
2
Commands are:
3
|-> t tag a message
4
|-> v verify a couple (message, tag)
5
|-> q Quit
6
>>> t
7
Input the message:
8
>>> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
9
Tag hash: 3baec174ae8d9af05f83650b377f49d51b8ebb3a97cfc147cc81eaab043d3dc3
10
Tag nonce: 000000010002000300040005
11
Commands are:
12
|-> t tag a message
13
|-> v verify a couple (message, tag)
14
|-> q Quit
15
>>> v
16
Input the message to verify:
17
>>> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
18
Input the associated tag hash:
19
>>> 3baec174ae8d9af05f83650b377f49d51b8ebb3a97cfc147cc81eaab043d3dc3
20
Input the associated tag nonce:
21
>>> 0000000100020001000200010002000300040005
22
Congrats!! Here is the flag: FCSC{529d5fb1ea316b2627c16190060af9f70dc420438afa7e8eb71d144a54a0}
Copied!
Last modified 2yr ago
Copy link