Signature - Pourquoi est-il important que les noms occasionnels lors de la signature ne soient pas liés ?

Je vais utiliser l'équation de Schnorr ici (s = k + H(R||P||m)*d pour la signature (R,s), pubkey P = d*G, message m), mais tout s'applique également à ECDSA (qui utilise s = (H(m) + Rx*d) / k), voire à des mixages entre les deux. Toutes les équations sont modulo n, l'ordre des groupes.

Le même occasionnel

Imaginez que vous ayez deux signatures avec la même clé privée et que même occasionnellement, sur deux messages différents. Cela signifie que vous avez :

s1 = k + H(R||P||m1)*d
s2 = k + H(R||P||m2)*d

En soustrayant ces deux équations l’une de l’autre, on obtient :

s2 - s1 = (H(R||P||m2) - H(R||P||m1))*d

Ce qui peut être résolu pour d :

d = (s2 - s1) / (H(R||P||m2) - H(R||P||m1)

Noms occasionnels avec décalage connu

Nous savons donc que vous ne devriez pas utiliser le même nom occasionnel pour plusieurs signatures. Mais que se passe-t-il si vous utilisez les noms occasionnels k1 et k2 où k1 est aléatoire, mais k2 = k1 + f, pour le décalage f connu de l'attaquant.

Maintenant, vous obtenez :

s1 = k1 + H(R||P||m1)*d
s2 = k2 + H(R||P||m2)*d = k1 + f + H(R||P||m2)*d

Soustraire encore nous donne :

s2 - s1 = f + (H(R||P||m2) - H(R||P||m1)*d

Autrement dit:

d = (s2 - s1 - f) / (H(R||P||m2) - H(R||P||m1)

Occasions avec facteur connu

Ok, donc l'attaquant ne peut pas faire la différence entre les deux noms occasionnels. Et s'ils connaissaient seulement un facteur entre eux ? k2 = k1*u.

s1 = k1 + H(R||P||m1)*d
s2 = k2 + H(R||P||m2)*d = k1*u + H(R||P||m2)*d

Le calcul de s2 - u*s1 donne maintenant :

s2 - u*s1 = H(R||P||m2)*d - H(R||P||m1)*d*u

Et ainsi:

d = (s2 - u*s1) / (H(R||P||m2) - H(R||P||m1)*u)

Donc ça aussi c'est un problème.

Relation arbitraire connue entre les nonces

Si la relation entre les noms occasionnels est plus complexe qu'une relation linéaire de la forme k2 = u*k1 + f, en général, il n'y aura pas de formule simple permettant de calculer facilement la clé privée à partir des signatures. Cependant, l'absence de formule connue ne signifie pas qu'il n'en existe pas, et ne constitue pas une preuve de sécurité.

La question qui nous préoccupe est de savoir dans quelles circonstances la relation entre les valeurs occasionnelles est suffisamment complexe pour que les attaquants ne puissent pas l'exploiter. Il s'avère qu'il existe plusieurs façons d'en avoir la preuve :

Tous les noms occasionnels sont générés uniformément de manière aléatoire
Les noms occasionnels sont calculés en sortie d'un PRF (fonction pseudo-aléatoire) ; ce qui correspond à peu près à ce que fait la RFC6979 (ensemencement du PRF avec la clé de signataire)
Fonction occasionnelle déterministe de MuSig-DN

D’un autre côté, nous connaissons un certain nombre de méthodes activement interrompues :

Les noms occasionnels qui ont une relation linéaire connue les uns avec les autres (comme démontré ci-dessus)
Noms occasionnels tirés d'une petite plage de nombres

Mais entre ces deux-là, il existe un énorme fossé entre des techniques qui ne sont ni connues pour être inefficaces, ni prouvées comme étant sûres. Beaucoup d’entre eux pourraient bien être sécurisés, mais nous ne le savons pas. Malheureusement, cela signifie qu’il n’y a en fait aucune réponse à la question « de quelle propriété est-il nécessaire » ; tout ce que nous savons, ce sont des techniques qui fonctionnent.