Énoncé
Je vous présente une signature à usage unique inédite et à la pointe de l’innovation ! En plus j’ai bien fait attention à ne signer qu’un seul message. Il ne peut donc rien m’arriver de fâcheux, n’est ce pas ?
Le code source propose un mécanisme de
signature numérique,
présent dans la classe WiC.
Ce mécanisme de signature est très proche de
Winternitz One-Time Signature
proposée par Winternitz en 1979.
Encodage d’un message
L’algorithme supporte la signature de n’importe quel message de longueur allant de 0 à 20.
class WiC:
def __init__(self, W = 257, msglen = 20, siglen = 40):
self.siglen = siglen
# ...
def sign(self, message):
if len(message) > self.msglen:
print("Error: message too long.")
return None
# ...
Les messages sont systématiquement encodés en un tableau de 40 éléments à l’aide d’un code linéaire, plus précisément un code de Reed-Solomon.
class WiC:
def __init__(self, W = 257, msglen = 20, siglen = 40):
self.W = W
# ...
self.Support = [
8, 17, 26, 32, 52, 53, 57, 58,
59, 63, 64, 66, 67, 71, 73, 76,
79, 81, 111, 115, 132, 135, 141, 144,
151, 157, 170, 176, 191, 192, 200, 201,
202, 207, 216, 224, 228, 237, 241, 252,
]
def _encoding(self, msg):
w = [0] * len(self.Support)
for i in range(len(self.Support)):
for j in range(len(msg)):
# Constant coefficient is zero
w[i] += msg[j] * self.Support[i] ** (j + 1)
w[i] %= self.W
return w
Le paramètre $W = 257$, aussi appelé “paramètre de Winternitz”, indique que nous travaillons sur le corps fini de 257 éléments $F_{257}$. Pour encoder un message $m = (m_0, m_1, \dots, m_{19}) \in F^{20}$, le message est d’abord projeté au polynôme $p_m(a) \in F[X]$ par
$$ p_m(a) = \sum_{i = 0}^{19}m_ia^{i + 1}, $$
où $m_i$ est simplement remplacé par $0$ si le message fait moins de $i$ caractères.
L’encodage de $m$ est obtenu en évaluant $p_m$ sur 40 points différents
$a_0, a_1, \dots, a_{39}$ de $F$ définis dans le tableau Support.
Ainsi, on peut représenter l’encodage d’un message $m$ par la fonction
$$ C(m) = \begin{bmatrix} p_m(a_0) \\ p_m(a_1) \\ \dots \\ p_m(a_{39}) \end{bmatrix} $$
Cette fonction est une application linéaire, c’est à dire que $C(m) = Am$ pour la matrice $40 \times 20$ sur $F$ suivante~:
$$ C(m) = Am = \begin{bmatrix} a_0 & a_0^2 & a_0^3 & \dots & a_0^{20} \\ a_1 & a_1^2 & a_1^3 & \dots & a_1^{20} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{39} & a_{39}^2 & a_{39}^3 & \dots & a_{39}^{20} \end{bmatrix} \begin{bmatrix} m_0 \\ m_1 \\ \vdots \\ m_{19} \end{bmatrix} $$
Voici un court code SageMath permettant d’encoder et décoder un message dans les conditions du challenge, sans correction d’erreur :
F = GF(257)
A = [
F(8), F(17), F(26), F(32), F(52), F(53), F(57), F(58),
F(59), F(63), F(64), F(66), F(67), F(71), F(73), F(76),
F(79), F(81), F(111), F(115), F(132), F(135), F(141), F(144),
F(151), F(157), F(170), F(176), F(191), F(192), F(200), F(201),
F(202), F(207), F(216), F(224), F(228), F(237), F(241), F(252),
]
M = Matrix([
[a^i for i in range(1, 21)]
for a in A
])
def encode_msg(msg):
assert len(msg) <= 20
m = vector(msg.ljust(20, b'\x00'))
return M * msg
def decode_msg(code):
msg = bytes(M.solve_right(vector(code)))
return msg.rstrip(b'\x00')
Hachage
La classe WiC propose une
fonction de hachage cryptographique
qui repose sur la clé publique $K_H$ :
class WiC:
def _byte_xor(self, b1, b2):
assert len(b1) == len(b2), "Error: byte strings of different length."
return bytes([x ^ y for x, y in zip(b1, b2)])
def _H(self, s, m, i, j):
return sha256(
self._byte_xor(
s,
sha256(
m + i.to_bytes(self.n1) + j.to_bytes(self.n2)
).digest()
)
).digest()
Concrètement, avec $K_H$ la clé aléatoire enregistrée dans mask_seed,
la première partie de la clé publique, on a
$$ H_{i, j}(m) = \text{SHA256}(m \oplus \text{SHA256}(K_H~||~i~||~j)) $$
Grâce aux propriétés cryptographiques de SHA256, on peut s’assurer que $H$ est résistant à toute forme de collision, et par conséquent, $H$ est résistant à la pré-image.
Génération de clé
Comme bon nombre d’algorithmes de signature numérique, la signature fonctionne à l’aide d’une clé privée secrète dont la clé publique est dérivée.
class WiC:
def _keygen(self):
sk_seed = os.urandom(16)
SK = [
sha256(sk_seed + i.to_bytes(self.n1)).digest()
for i in range(self.siglen)
]
# ...
Dans notre cas, la clé secrète est la valeur initiale d’un compteur, dont est calculée l’empreinte SHA256 de 40 valeurs consécutives.
class WiC:
def _keygen(self):
# ...
PK = SK.copy()
for i in range(self.siglen):
for j in range(1, self.W):
PK[i] = self._H(PK[i], mask_seed, i, j)
self.sk = (mask_seed, sk_seed)
self.pk = (mask_seed, PK)
Pour dériver la clé publique, chaque empreinte est hachée par la fonction $H$ 256 fois.
Dérivation de la clé publique :
Signature et Vérification
class WiC:
def sign(self, message):
mask_seed, sk_seed = self.sk
w = self._encoding(message)
S = [
sha256(sk_seed + i.to_bytes(self.n1)).digest()
for i in range(self.siglen)
] # = S
for i in range(self.siglen):
for j in range(1, w[i] + 1):
S[i] = self._H(S[i], mask_seed, i, j)
return [s.hex() for s in S]
Afin de signer un message, le message $m$ est d’abord encodé en un élément $C(m)$ de $F_{257}^{40}$ par l’encodage décrit précédemment. Ensuite, en partant du compteur $SK$ dérivé de la clé secrète, chaque valeur $SK_{i}$ est hachée par $H$, $C(m)_i$ fois. Les 40 blocs résultants $\sigma$ forment la signature de $m$.
class WiC:
# message is a list of bytes
def verif(self, message, signature):
mask_seed, PK = self.pk
w = self._encoding(message)
for i in range(self.siglen):
for j in range(w[i] + 1, self.W):
signature[i] = self._H(signature[i], mask_seed, i, j)
return all(s == pk for s, pk in zip(signature, PK))
Pour valider une signature, il suffit de hacher chaque bloc de la signature autant de fois que nécessaire afin de retomber sur $PK$. Par exemple, si $C(m_0) = 42$, alors $\sigma_0 = H_0^{42}(SK_0)$, et on devrait retrouver $H_0^{214}(S_0) = H_0^{256}(SK_0) = PK_0$.
Signature et vérification d’un message $C(m) = (3, 1, 4, 256, 1, \dots, 2)$ :
Une signature est valide si l’on retrouve la clé publique après avoir appliqué $H$, $256 - C(m_i)$ fois pour chaque bloc.
Modèle d’attaque
Le challenge demande d’effectuer une falsification existentielle faible, c’est à dire, étant donné une signature valide, nous devons réussir à falsifier une autre signature de notre choix.
S = WiC()
pk = (
S.pk[0].hex(),
[ pk.hex() for pk in S.pk[1] ]
)
message = b"WINTERNITZ IS COMING"
signature = S.sign(message)
print (f"{message = }")
print (f"{signature = }")
print (f"{pk = }")
try:
print("Input your message (hex format):")
your_message = bytes.fromhex(input(">>> "))
print("Input your signature (list of hex strings):")
your_signature = literal_eval(input(">>> "))
your_signature = [bytes.fromhex(s) for s in your_signature]
assert message != your_message
assert len(your_message) == 20
assert len(your_signature) == 40
if S.verif(your_message, your_signature):
print("Congratulations! Here is your flag:")
print(open("flag.txt").read())
else:
print("Not quite, try again!")
except:
print("Please check your inputs.")
L’algorithme semble résistant à la falsification existentielle forte. Sans la connaissance de la signature donnée, trouver la signature d’un message $C(m)$ nécessiterait de trouver la $256 - C(m)_i$-ème préimage de $H$ pour chaque $i$. Étant donné la résistance à la préimage de $H$, le seul potentiel message possible à falsifier fortement serait $C(m) = (256, 256, \dots, 256)$, dont la signature serait $PK$. Cependant, ce code est un code invalide :
sage: M.solve_right(vector([F(256)] * 40))
ValueError: matrix equation has no solutions
Vulnérabilité
Mis à part $C(m) = (256, 256, \dots, 256)$, il est possible de falsifier une panoplie d’autres messages en ayant connaissance d’une signature valide. Étant donné $m$ et sa signature $\sigma$, nous pouvons calculer la signature $\sigma’$ de n’importe quel message $m’$ tant que $C(m’)_i \geq C(m)_i$ pour tout $i$.
En effet, supposons que nous connaissions la signature $\sigma$ associée à un message $m$, et que nous voulons signer un message $m’$ respectant $C(m’)_i \geq C(m)_i$ pour tout $i$. Alors, $\sigma’_i = H^{C(m’)_i - C(m)_i}(\sigma_i)$ nous permet de falsifier une signature valide pour $m’$. La validité de $\sigma’$ est vérifiée par
$$ \begin{align*} H^{256 - C(m’)_i}(\sigma’_i) &= H^{256 - C(m’)_i}(H^{C(m’)_i - C(m)_i}(\sigma_i)) \\ &= H^{256 - C(m)_i}(\sigma_i) \\ &= PK_i \end{align*} $$
Le challenge consiste donc à trouver un code valide toujours supérieur au code du message signé connu.
Exploitation
En choisissant un message au hasard, le script suivant révèle que nous avons environ une chance sur 2,594,485,356,476,117,289,818,603 de trouver un code toujours supérieur au code du message donné.
message = b'WINTERNITZ IS COMING'
code = encode_msg(message)
probabilite = 1
for i in code:
probabilite *= (258 - Integer(i)) / 257
print(float(1/probabilite))
# 2.594485356476117e+24
Au contraire, si nous sélectionnons au hasard un code supérieur au code de $m$, nous avons une chance sur $257^{40-20}$, c’est à dire une chance sur 1,580,019,571,820,317,063,568,778,786,121 273,112,555,213,952,001 que le code soit valide. Les chances que le code corresponde à un message falsifiable sont encore moindre, car la valeur $256$ est interdite dans le message de départ, car impossible à encoder en ASCII.
Il n’est donc pas envisageable de chercher de tels messages par force brute. Cependant, il est possible de traduire notre problème en une instance du problème du plus proche vecteur d’un réseau Euclidien.
Soit $C(m)$ le code du message dont la signature est connue. On cherche à trouver un vecteur $C(m’)$ tel que $C(m’)_i$ se situe entre $C(m)_i$ et $256$ (inclus) pour tout $i$. Cela se traduit par la contrainte suivante :
$$ C(m’)_i = \frac12(C(m)_i + 256) \pm \frac12(256 - C(m)_i). $$
Pour que $C(m’)$ représente un code valide, on doit avoir, pour tout $i$ entre 0 et 39, pour tout $j$ entre 0 et 19, et pour un certain vecteur $m$ dans $[![ 0, 255]!]^{20}$ :
$$ \begin{align*} &C_i(m’) = p_m(a_i) = \sum_{j=0}^{19}m_ja_i^{j+1} + 257\cdot\lambda_i, \quad \lambda_i \in \mathbb Z \\ &m_j = \dfrac{255}{2} \pm \dfrac{255}{2} \end{align*} $$
Afin de pouvoir travailler uniquement sur les entiers, on se permet de multiplier par deux toutes les contraintes~:
$$ \begin{align*} 2C_i(m’) &= \sum_{j=0}^{19} 2m_ja_i^{j+1} + 514 \cdot \lambda_i\\ &= C(m)_i + 256 \pm (256 - C(m)_i) &&\text{pour $i$ allant de 0 à 39}\\ 2m_j &= 255 \pm 255 &&\text{pour $j$ allant de 0 à 19} \end{align*} $$
De manière plus explicite, on cherche à trouver le vecteur
$$ (2C_0(m’), 2C_1(m’), \dots, 2C_{39}(m’), 2m_0, 2m_1, \dots, 2m_{19}), $$
qui appartient à un réseau Euclidien :
$$ \begin{alignat*}{7} 2C_1(m’) &= 2a_1 & & \cdot m_0 + 2a_1^2 & & \cdot m_1 + \dots + 2a_1^{20} & & \cdot m_{19} + 0 & & \cdot \lambda_0 + 514 & & \cdot \lambda_1 + \dots + 0 & & \cdot \lambda_{39} \\ & \vdots & & \vdots & & \ddots & & \vdots & & \vdots & & \ddots & & \vdots \\ 2C_{39}(m’) &= 2a_{39} & & \cdot m_0 + 2a_{39}^2 & & \cdot m_1 + \dots + 2a_{39}^{20} & & \cdot m_{19} + 0 & & \cdot \lambda_0 + 0 & & \cdot \lambda_1 + \dots + 514 & & \cdot \lambda_{39} \\ 2m_0 &= 2 & & \cdot m_0 + 0 & & \cdot m_1 + \dots + 0 & & \cdot m_{19} + 0 & & \cdot \lambda_0 + 0 & & \cdot \lambda_1 + \dots + 0 & & \cdot \lambda_{39} \\ 2m_1 &= 0 & & \cdot m_0 + 2 & & \cdot m_1 + \dots + 0 & & \cdot m_{19} + 0 & & \cdot \lambda_0 + 0 & & \cdot \lambda_1 + \dots + 0 & & \cdot \lambda_{39} \\ & \vdots & & \vdots & & \ddots & & \vdots & & \vdots & & \ddots & & \vdots \\ 2m_{19} &= 0 & & \cdot m_0 + 0 & & \cdot m_1 + \dots + 2 & & \cdot m_{19} + 0 & & \cdot \lambda_0 + 0 & & \cdot \lambda_1 + \dots + 0 & & \cdot \lambda_{39} \\ \end{alignat*} $$
L’objectif étant de trouver un vecteur respectant ces contraintes :
$$ \begin{alignat*}{2} 2C_0(m’) & = & C_0(m) + 256 &\pm(256 - C_0(m)) \\ 2C_1(m’) & = & C_1(m) + 256 &\pm(256 - C_1(m)) \\ \dots \\ 2C_{39}(m’) & = & C_{39}(m) + 256 &\pm(256 - C_{39}(m)) \\ 2m_0 & = & 255 & \pm 255 \\ 2m_1 & = & 255 & \pm 255 \\ \dots \\ 2m_{19} & = & 255 & \pm 255 \\ \end{alignat*} $$
On commence par uniformiser les contraintes en remplaçant les marges par leur plus petit commun multiple. Soit
$$ \Delta = \text{ppcm}(255, 256 - C_0(m), 256 - C_1(m), \dots, 256 - C_{39}(m)). $$
En multipliant chaque ligne par le facteur adéquat
$$ k_i = \begin{cases} \dfrac{\Delta}{256 - C_i(m)} & 0 \leq i < 40 \\ \dfrac{\Delta}{255} & 40 \leq i < 60 \end{cases} $$
on obtient un réseau généré par la base suivante :
$$ \left( \begin{pmatrix} 2a_0k_0 \\ 2a_1k_1 \\ \dots \\ 2a_{39}k_{39} \\ 2k_{40} \\ 0 \\ \dots \\ 0 \end{pmatrix}, \begin{pmatrix} 2a_0^2k_0 \\ 2a_1^2k_1 \\ \dots \\ 2a_{39}^2k_{39} \\ 0 \\ 2k_{41} \\ \dots \\ 0 \end{pmatrix}, \dots, \begin{pmatrix} 2a_0^{20}k_0 \\ 2a_1^{20}k_1 \\ \dots \\ 2a_{39}^{20}k_{39} \\ 0 \\ 0 \\ \dots \\ 2k_{59} \end{pmatrix}, \begin{pmatrix} 514 k_0 \\ 0 \\ \dots \\ 0 \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 514 k_1 \\ \dots \\ 0 \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix}, \dots, \begin{pmatrix} 0 \\ 0 \\ \dots \\ 514 k_{39} \\ 0 \\ 0 \\ \dots \\ 0 \end{pmatrix} \right), $$
dont l’objectif est de retrouver un vecteur appartenant à ce réseau étant égal à
$$ \begin{pmatrix} 2C_0(m’) k_0 \\ 2C_1(m’) k_1 \\ \dots \\ 2C_{39}(m’) k_{39} \\ 2m_0 k_{40} \\ 2m_1 k_{41} \\ \dots \\ 2m_{19} k_{60} \end{pmatrix} = \begin{pmatrix} (C_0(m) + 256) k_0 \pm \Delta \\ (C_1(m) + 256) k_1 \pm \Delta \\ \dots \\ (C_{39}(m) + 256) k_{39} \pm \Delta \\ 255 k_{40} \pm \Delta \\ 255 k_{41} \pm \Delta \\ \dots \\ 255 k_{60} \pm \Delta \\ \end{pmatrix} $$
Un tel vecteur, s’il existe, peut être découvert à l’aide de l’algorithme de Babai.
Mise en œuvre
from sage.modules.free_module_integer import IntegerLattice
from fpylll import IntegerMatrix, CVP
# message connu
message = b'WINTERNITZ IS COMING'
code = encode_msg(message)
# facteurs d'uniformisation des marges
delta = lcm([255] + [256 - Integer(cm) for cm in code])
k = [delta // (256 - Integer(cm)) for cm in code] + [delta // 255] * 20
# définition du réseau euclidien
base = [
[ 2 * Integer(A[i])^(j + 1) * k[i] for i in range(40) ]
+ [ 2 * k[i] if i - 40 == j else 0 for i in range(40, 60) ]
for j in range(20)
] + [
[ 514 * k[i] if i == j else 0 for i in range(40) ] + [0] * 20
for j in range(40)
]
reseau = IntegerLattice(Matrix(base), lll_reduce=True)
# vecteur cible
cible = vector([
(Integer(code[i]) + 256) * k[i] for i in range(40)
] + [255 * k[i] for i in range(40, 60)])
# résolution du CVP par Babai
resultat = reseau(CVP.babai(IntegerMatrix.from_matrix(reseau.reduced_basis), cible))
# extraction du message dont la signature est falsifiable
faux_code = vector([ F(resultat[i] // (2 * k[i])) for i in range(40) ])
faux_message = bytes([ resultat[i] // (2 * k[i]) for i in range(40, 60) ])
# sanity check
assert encode_msg(faux_message) == faux_code
assert all(Integer(faux_code[i]) >= Integer(code[i]) for i in range(40))
print(faux_message.hex())
# 3c1eaad51f9356bd45a64d9a36678274749d6f82
# signature associée au message connu
S = signature
for i in range(siglen):
for j in range(code[i] + 1, faux_code[i] + 1):
S[i] = _H(S[i], mask_seed, i, j)
fausse_signature = [s.hex() for s in S]
assert verif(faux_message, fausse_signature)
# On a réussi à falsifier une signature