Capture the Coin – Solutions de catégorie de cryptographie


Coinbase

Par Jake Craige, Max Mikhaylov, Jesse Posner

Dans la dernière publication de la série de compétitions Capture the Coin, nous explorerons des solutions pour nos défis cryptographiques. Aussi, n'hésitez pas à revoir nos autres écrits de la série pour Trivia, Blockchain, ainsi que les annonces de concours et de récompenses.

Par Jake Craige

Ce défi vous présente la sortie d'un chiffrement et demande le message chiffré (texte brut) comme solution. Il a été chiffré avec Ruby comme suit:

def encrypt (message)nécessite "openssl"# Crypter le message à l'aide d'une clé aléatoire + iv avec AES-128-OFBcryptage = OpenSSL :: Cipher.new ("AES-128-OFB"). crypterrandom_key = cipher.random_keycipher.key = random_keyrandom_iv = cipher.random_ivcipher.iv = random_ivtexte chiffré = cipher.update (message) + cipher.final# Crypter le IV avec AES-128-ECBsimple_cipher = OpenSSL :: Cipher.new ("AES-128-ECB"). cryptersimple_cipher.key = random_keyencrypted_iv = simple_cipher.update (random_iv) + simple_cipher.final{Texte chiffré: texte chiffré. Déballez (& # 39; H * & # 39;). Premier,encrypted_iv: encrypted_iv.unpack (& ​​# 39; H * & # 39;). premier}finale

Si vous avez déjà travaillé avec AES, certaines parties peuvent vous mettre en évidence.

Tout d'abord, utilisez le mode de fonctionnement Feedback Output (OFB) comme indiqué par l'utilisation de "AES-128-OFB" dans l'indicateur. Il n'y a rien de mal à cela seul, mais les modes Cipher Block Chaining (CBC) et Counter (CTR) sont plus courants et, dans la pratique, un cryptage authentifié (AE) tel que Galois / Counter Mode (GCM) doit être utilisé. ).

Ensuite, nous voyons que l'IV est crypté et utilise le mode Electronic Code Book (ECB). Les IV sont des valeurs non secrètes et n'ont pas besoin d'être cryptées. La sécurité du chiffrement par bloc dépend de leur caractère aléatoire mais non secret. De plus, utiliser le mode ECB pour le chiffrement n'est jamais ce que vous voulez. Il est destiné à servir de bloc de construction pour d'autres modes, mais ne doit pas être utilisé comme mode seul.

Examinons ce que sont les chiffrements de blocs et les modes, car ils sont essentiels pour résoudre ce problème. Un chiffrement par bloc est un algorithme déterministe qui accepte une clé secrète de taille fixe et du texte brut en entrée et génère une sortie de taille fixe, appelée bloc. Ils sont utilisés pour le cryptage, ce qui signifie qu'ils ont également une opération de décryptage qui accepte la clé et le texte crypté et renvoie le texte brut.

Un chiffrement par bloc seul n'est pas sûr de chiffrer plus d'un message, car chiffrer deux fois le même message entraînerait le même texte chiffré, en d'autres termes, le chiffrement par bloc est déterministe.

Pourquoi est-ce un problème? Disons qu'une armée envoie un jour le message "Attaque à l'aube" et que son adversaire le résout. Un autre jour, si l'armée envoie le même message et que l'adversaire regarde, il saura qu'une attaque est imminente et pourra établir des défenses.

Formellement, nous disons qu'un chiffrement par bloc n'est pas sécurisé IND-CPA (indiscernable sous une attaque de texte brut choisi). Cela signifie que si nous avons un service de chiffrement des données et que nous fournissons deux textes clairs à chiffrer, nous ne devrions pas être en mesure d'identifier celui qui a été chiffré à partir du texte chiffré.

Nous résolvons ce problème en introduisant différents "modes de fonctionnement" du chiffrement par blocs. La valeur par défaut est ECB, qui n'est pas sécurisée, et d'autres modes le rendent sûr en introduisant l'aléatoire et le chaînage des blocs de plusieurs manières.

Nous passerons en revue les modes BCE et OFB, car ce sont ceux utilisés par le challenge.

Livre de codes électronique (BCE)

Le mode ECB fonctionne en divisant le texte brut en blocs et en chiffrant indépendamment chaque bloc. Le texte chiffré final est la concaténation de chaque texte de bloc chiffré.

Un exemple populaire de pourquoi ce mode ne parvient pas à fournir une sécurité suffisante peut être vu avec l'image "ECB Penguin". Nous voyons que même lorsque l'image est cryptée, vous pouvez toujours voir le pingouin. Il s'agit clairement d'une propriété indésirable d'un schéma de chiffrement. Un schéma de cryptage idéal ferait apparaître l'image cryptée de façon aléatoire, comme on le voit sur la troisième image. Des modes autres que la BCE le permettent.

Commentaires de sortie (OFB)

OFB introduit un vecteur d'initialisation, des OU exclusifs (XOR), et le texte chiffré du bloc précédent est utilisé comme entrée pour un autre. L'IV est une valeur aléatoire choisie au moment du cryptage et prédéfinie sur le texte crypté. La combinaison de blocs aléatoires IV et d'une chaîne résout ensemble les problèmes que nous décrivons avec la BCE.

Avec une compréhension des chiffrements par blocs utilisés dans l'application, nous pouvons examiner comment ils ont été utilisés et trouver la solution. N'oubliez pas que les deux textes chiffrés qui sont générés sont les suivants:

  1. Le message est crypté avec une clé aléatoire et IV en utilisant AES-128-OFB.
  2. Le même IV est chiffré avec AES-128-ECB en utilisant de même clé.

En regardant la taille du texte chiffré du message, nous pouvons voir qu'il fait 16 octets de long, ce qui signifie que le texte brut est exactement un bloc, car AES-128 utilise des blocs de 128 bits. Compte tenu de cela, nous pouvons décrire le texte crypté du message comme Chiffrer (clé, IV) le message XOR. Pour le cryptage IV, le mode ECB a été utilisé, donc le cryptage IV est simplement Chiffrer (clé, IV). En raison de la propriété de XOR où a XOR b XOR a = b, nous pouvons résoudre le texte brut en Texte chiffré XOR IV chiffré ce qui équivaut à Crypter (mot de passe, IV) Message XOR XOR Crypter (mot de passe, IV) = Message.

La solution dans Ruby peut être trouvée comme suit:

message_ct = [“1b08dbade73ae869436549ba781aa077”].pack ("H *")iv_ct = [“6f60eadec7539b4930002a8a49289343a7c0024b01568d35d223ae7a9eca2b5c”].pack ("H *")message_ct.bytes.zip (iv_ct.bytes) .map {| l, r | l ^ r} .pack ("C *")

Cela génère correctement l'indicateur CTF «th1s is sec01234».

Par Jake Craige

Ce défi est décrit comme suit:

Les données ci-dessous fournissent deux signatures ECDSA-SHA256 encodées en hexadécimal en utilisant la courbe secp256k1 pour la clé publique fournie. Ces signatures ont été générées à l'aide de la même valeur nonce qui permet la récupération de la clé privée.

Votre tâche consiste à trouver la clé privée et à l'envoyer (encodée en hexadécimal avec le préfixe 0x) comme solution à ce défi.

Clé pub (BE-compressé): 0x2341745fe027e0d9fd4e31d2078250b9c758e153ed7c79d84a833cf74aae9c0bbSig # 1 (msg): que se passe-t-il defconSig # 1 (r, s): (0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491,)Sig # 1 (message): euh oh, ce n'est pas bonSig # 2 (r, s): (0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491, 0xd67006bc8b7375e236e11154d576eed0fc8539c3bba566f40e9e

Le message explique ce qui ne va pas, donc tout ce que nous avons à faire est de découvrir comment résoudre la clé privée. Une recherche rapide fournira plusieurs explications du problème et comment le résoudre. Wikipedia fournit une bonne explication de la façon dont les signatures ECDSA sont générées et documente la solution de réutilisation nonce. Ici, nous décrirons les mathématiques en utilisant les mêmes noms de variables que Wikipedia.

Étant donné deux signatures s et s ’ de différents résumés de messages z et z & # 39; qui a utilisé le même nonce, la première étape consiste à résoudre la clé privée est de résoudre k.

Maintenant que nous savons k, nous avons suffisamment d'informations publiques pour restructurer l'équation de signature et résoudre la clé privée d_a.

Nous pouvons résoudre ce problème en Python avec le code suivant:

importer du hashlib# ordre secp256k1order = int ("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", 16)# Participation au défiz = int (hashlib.sha256 ("passant defcon"). hexdigest (), 16)z_prime = int (hashlib.sha256 ("euh oh, ce n'est pas bon"). hexdigest (), 16)s = int ("1a53499a4aafb33d59ed9a4c5fcc92c5850dcb23d208de40a909357f6fa2c12c", 16)s_prime = int ("d67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee", 16)r = int ("5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491", 16)# diviser dans un champ n'est pas une division standard, nous devons donc le définir comme suitdef modinv (a, module): return pow (a, module - 2, module)def divmod (a, b, module): return (a * modinv (b, module))% module# Résoudre pour la clé privée dk = divmod (z - z_prime, s - s_prime, ordre)d = divmod (k * s - z, r, ordre)# indicateur de défi de sortieimpression (hex (d))

Cela génère correctement l'indicateur de défi 0x128e06938ac462d9.

Par Max Mikhaylov

Il s'agit d'un défi cryptographique. Nous utiliserons Python pour le résoudre. Je suppose que vous connaissez la multiplication scalaire pour les courbes elliptiques sur les champs finis. Si ce sujet n'est pas familier, lisez les 3 premiers chapitres du livre de programmation Bitcoin de Jimmy Song. C'est une condition préalable pour comprendre le défi.

Pour ce défi, j'ai juste besoin d'un package non standard: fastecdsa. Nous l'utilisons pour faire de l'arithmétique aux points ECC de la courbe brainpoolP160r1. Nous n'utiliserons que deux classes de ce package: Point et brainpoolP160r1.

En regardant les transactions qui ont été transmises au nœud, nous voyons qu'elles contiennent toutes une clé de destination non valide. Le problème établit clairement le format des points ECC et la clé de destination ne le suit pas ("dest_key": "G0"). Ce n'est même pas un nombre hexadécimal valide.

Mais la clé publique de la transaction semble valide. Essayons de convertir ces clés publiques en points ECC dans la courbe brainpoolP160r1. Écrivons une fonction qui convertit une seule clé publique en un point de la courbe.

def key_to_point (clé):Point de retour (int (clé[2:42], 16), int (clé[42:], 16), courbe = brainpoolP160r1)

Si nous essayons de convertir certaines clés publiques en points avec cette fonction, nous obtiendrons une erreur: ValueError: les coordonnées ne sont pas courbes

Il semble que la clé publique fournie par l'expéditeur ne se trouve pas dans la courbe brainpoolP160r1. En fait, aucune des clés publiques fournies ne se trouve dans cette courbe. D'après la description du modèle de transaction du document technique Cryptonote, nous savons que le nœud doit effectuer une multiplication scalaire en utilisant la clé de transaction publique de l'expéditeur et sa propre clé privée. Est-il dangereux pour le nœud d'effectuer cette multiplication avec un point qui n'est pas sur la courbe attendue? Oui! Nous découvrirons pourquoi dans un instant.

Si l'implémentation du noeud n'était pas défectueuse, il aurait vérifié si la clé publique fournie par l'expéditeur se trouve dans la courbe attendue et lèverait une exception si elle n'est pas dans la courbe (comme la bibliothèque fastecdsa). Cependant, le nœud a accepté cette clé publique, a effectué une multiplication scalaire à l'aide de sa clé de suivi privée et a essayé de comparer si sa version du secret partagé (P_prime) était différente de celle fournie par l'expéditeur (P). Ce n'est que lors de la comparaison de ces valeurs que le nœud a généré une erreur car l'une des valeurs n'est pas un point ECC valide (la clé de destination fournie par l'expéditeur). Pour aggraver les choses (ou mieux pour nous en tant qu'attaquant), le nœud a exposé sa version du secret partagé (P_prime) dans le registre.

Le premier indice du défi nous dit que nous devons nous concentrer sur ces points ECC invalides fournis par l'expéditeur. Étant donné que le logiciel de nœud défectueux ne vérifie pas si le point fourni se trouve sur la courbe, nous pouvons corriger la classe Point de la bibliothèque fastecdsa pour supprimer la vérification suivante:

def point_init_monkey_patch (auto, x, y, courbe):self.x = xself.y = yself.curve = courbePoint .__ init__ = point_init_monkey_patch

Maintenant, nous pouvons essayer de convertir à nouveau tx_pub_key en point ECC pour toutes les transactions; Il n'y a pas d'erreur:

Entrée:

pub_key_points = txs_to_pub_key_points (txs) # txs est un contenu contenu de txs.json

Nous pouvons également convertir les valeurs secrètes partagées des enregistrements de nœuds en points ECC, maintenant que nous appliquons des correctifs à la bibliothèque ECC:

def err_log_to_shared_secret_points (err_log):                shared_secret_points = []                Pour saisir err_log:                                msg = entrée[‘err_msg’]                                shared_secret = msg.split (‘P_prime =’)[1].division ()[0]                                shared_secret_point = key_to_point (shared_secret)                                shared_secret_points.append (shared_secret_point)                    return shared_secrete_pointsshared_secret_points = err_log_to_shared_secret_points (err_log) # err_log est un contenu contenu de err_log.json

Revenons aux points clés publics. Le premier point clé public semble très suspect. Je veux dire que la coordonnée Y est 0. Essayons de calculer l'ordre de ce point.

Entrée:

def point_point (p):                pour x dans la plage (2, brainpoolP160r1.p):                si x * p == p:                                retour x - 1point_order (pub_key_points[0])

Départ:

2

C'est très bas! Il s'avère que d'autres points clés publics ont également un ordre faible. Cela nous donne-t-il un moyen de dériver la clé privée utilisée par le nœud pour calculer les secrets partagés?

Il s'avère que ces conditions exactes nous permettent de réaliser une attaque de courbe invalide. Vous pouvez en savoir plus sur ce qu'est une attaque par courbe non valide dans le «Guide de la cryptographie à courbe elliptique» de Hankerson, Menezes et Vanstone à la page 182. Lisez également un récent CVE-2019–9836 qui décrit cette attaque dans un Environnement pratique (c'était le deuxième indice de ce défi).

L'essence de l'attaque: si nous pouvons faire en sorte que le nœud calcule des secrets partagés à partir de points d'ordre inférieur d'ordre relativement cousin, et que nous puissions trouver des résultats à partir de ces calculs, nous pouvons récupérer le secret en utilisant le théorème de repos chinois (CRT). Pour être plus précis, nous avons besoin que le produit de tous les points d'ordre inférieur soit plus grand que la clé privée afin que la clé récupérée soit unique (par conséquent, elle correspond à la clé privée). Si nous calculons le produit de l'ordre de tous les points dans `pub_key_points`, en fait, nous pouvons voir que ce nombre ne tient pas sur 160 bits, par conséquent, il doit être supérieur à la clé privée utilisée avec la courbe brainpoolP160r1.

Entrée:

produit = 1pour le point dans pub_key_points:                produit * = order_point (point)du registre mathématique d'importation2log2 (produit)

Départ:

175.1126248794482 # le produit occupe 176 bits en représentation binaire

Premièrement, nous devons pouvoir utiliser le CRT. Il existe de nombreuses ressources sur le fonctionnement du CRT, vous pouvez donc les lire si vous êtes curieux de connaître les mathématiques derrière. Pour résoudre ce problème, j'ai copié l'implémentation CRT du code Rosetta.

Nous sommes maintenant prêts à mener l'attaque! L'idée principale derrière cela est la suivante:

  • Nous savons que la multiplication d'un point d'ordre bas par un très grand scalaire (la clé privée) se traduira par un point du même ordre bas (le secret partagé).
  • Nous pouvons calculer le plus petit scalaire possible qui, lorsqu'il est multiplié par la clé publique, donnera le même secret partagé d'ordre inférieur.
  • Nous pouvons le faire simplement en testant tous les scalaires possibles qui sont plus petits que l'ordre de la clé publique.
  • En appliquant la force brute à l'échelle la plus petite possible que le secret partagé nous donne lorsqu'il est multiplié par la clé publique, nous pouvons construire un système de congruences simultanées dans le format exact qui convient pour appliquer le CRT. Étant donné que le produit de toutes les commandes relativement premium est supérieur à la clé privée que nous recherchons, le résultat de l'application du CRT est unique.

Entrée:

v = [] # Vous pouvez considérer les valeurs de cette liste comme le nombre minimum d'ajouts EC de E_hat à vous-même pour obtenir shared_secretmodules = [] # modules système principauxprint ("Construire un système de congruence simultanée:")pour P_hat, shared_secret dans zip (pub_key_points, shared_secret_points):                    order = order_point (P_hat)                    # search shared_secret mod o_prime; c'est-à-dire le nombre minimum d'ajouts E_hat à lui-même pour obtenir shared_secret                    pour x dans la plage (1, brainpoolP160r1.p):                                    si x * P_hat == shared_secret: # a trouvé le nombre minimum d'ajouts                                                print (f'e ≡ {x} mod {order}; ’, end =’ ’)                                                v.append (x)
moduli.append (commande)
casser

Départ:

Construire un système de congruence simultanée:

e ≡ 1 mod 2; e ≡ 1 mod 11; e ≡ 7 mod 23; e ≡ 1 mod 5; e ≡ 34 mod 41; e ≡ 4 mod 7; et ≡ 273 mod 293; e ≡ 161 mod 691; e ≡ 93 mod 347; e ≡ 7 mod 17; e ≡ 162 mod 229; e ≡ 19 mod 53; e ≡ 7 mod 13; e ≡ 380 mod 977; e ≡ 83 mod 89; e ≡ 82 mod 109; et ≡ 4771 mod 9767; et ≡ 381213 mod 439511; e ≡ 758 mod 10009; e ≡ 14048 mod 26459; e ≡ 11 mod 37; et ≡ 196934 mod 949213;

Entrée:

e = chinese_remainder (modules, v)hex (e)

Départ:

«0xdec1a551f1edc014ba5edefc042019»

Ce sort de clé privée semble inhabituel … C'est définitivement un drapeau!

PS Si vous êtes curieux de savoir comment j'ai trouvé des points de commande bas en premier lieu, consultez ma question sur l'échange de pile cryptographique que j'ai posée lorsque j'ai travaillé sur ce défi.

Par Jesse Posner

Ce défi décrit un schéma de signature défectueux appelé signatures Schnorrer. Ce schéma est presque identique aux signatures Schnorr, cependant, il contient une faille critique qui permet aux signatures Schnorrer, contrairement aux signatures Schnorr, d'être facilement falsifiées. L'objectif du défi est de produire une signature Schnorrer valide pour une clé publique et un message donnés.

Une signature Schnorrer et son défaut sont mieux compris en contrastant avec une signature Schnorr. Une entreprise Schnorr applique l'heuristique Fiat-Shamir au protocole d'identification Schnorr, un protocole interactif de test de connaissances sigma, et le transforme en protocole de signature numérique.

Dans Schnorr, le défi heuristique de Fiat-Shamir est généré en mélangeant le message et le message public, mais dans Schnorrer le défi est le hachage du message et de la clé publique. En remplaçant le nonce public par la clé publique dans le hachage de défi, la firme Schnorrer sape la sécurité du système.

Le protocole d'identification Schnorr se compose de 3 éléments: (1) un algorithme de génération de clés, (2) un testeur et (3) un vérificateur. Le testeur génère un secret, «x», et veut montrer au vérificateur qu'il connaît «x» sans le révéler au vérificateur.

Les deux parties doivent s'accorder sur certains paramètres: un groupe cyclique, avec un générateur, «G», et un module principal, «q». Par exemple, le protocole Bitcoin utilise les paramètres secp256k1, avec un générateur spécifié par un point de courbe elliptique avec des coordonnées compressées:

02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

Une lettre majuscule, telle que «G», «P» ou «R», désigne un élément de groupe, par exemple, un point de courbe elliptique. Les lettres minuscules désignent des valeurs scalaires, telles que «x», «r» et «s».

Algorithme de génération de clés

Le testeur utilise l'algorithme de génération de clés pour produire une paire de clés publique-privée, «x» et «P». `x` est un entier sélectionné aléatoirement dans un champ fini avec le module`q`. La clé publique «P» est calculée en utilisant «x» comme valeur scalaire et multipliée par «G»:

`` x * G ''

La clé privée, «x», est le logarithme discret de «P» avec la base «G», et par conséquent le vérificateur ne peut pas dériver efficacement la clé privée de la clé publique, donc le testeur peut révéler une clé public sans révéler la clé privée, d'où les dénotations "public" et "private".

Protocole

Supposons qu'Alice veuille montrer à Bob qu'elle connaît la valeur & # 39; x & # 39 ;. Alice démarre le protocole d'identification Schnorr en générant un nonce, «r», à utiliser comme scalaire, similaire à la clé privée. Cependant, contrairement à la clé privée, le nonce ne doit être utilisé qu'une seule fois ("pour le nonce"). Ensuite, Alice calcule la valeur `r * G` pour dériver l'élément de groupe`R`, similaire à la façon dont la clé publique a été générée. Cette valeur, «R», est généralement appelée l'engagement public nonce ou l'engagement nonce. Une fois qu'Alice a sa clé publique, «P», et sa clé publique, «R», envoie ces valeurs à Bob.

Bob doit maintenant générer une autre valeur scalaire appelée valeur de défi, «c». Après que Bob ait reçu «P» et «R», il génère «c» et l'envoie à Alice. Notez que tandis que & # 39; c & # 39; est indépendant du & # 39; R & # 39;, il est très important que Bob attende d'avoir reçu le & # 39; R & # 39; Alice avant de l'envoyer & # 39; c & # 39;. En fait, si Bob ne le fait pas et envoie & # 39; c & # 39; Alice avant de recevoir le «  R '', Alice peut tromper Bob en lui faisant croire qu'il a connaissance de la clé secrète sans le savoir. L'intégrité de la vérification dépend de la génération de «R» avant «c», comme nous le verrons bientôt.

Alice termine la conversation avec Bob en multipliant sa clé privée, «x», par le défi, «c», et en ajoutant ce produit à son nonce privé, «r», pour produire ce que l'on appelle la valeur «s». `s` doit être module` q` (toutes les valeurs scalaires doivent être module`q` pour être dans l'ordre de la courbe).

Nous pouvons maintenant voir le but du nonce: il permet à Alice de produire une valeur qui est le produit de (1) la clé privée, & # 39; x & # 39;, et (2) une valeur choisie uniquement par Bob, à savoir, le défi, & # 39; c`. Cependant, Alice doit accomplir cela sans révéler directement & # 39; x & # 39; à Bob. Si nous omettons le nonce du protocole, alors `s` serait égal à` x * c`, et, bien que cette valeur démontrerait la connaissance d'Alice de` x` à Bob, elle le fait de manière trop agressive et permet à Bob de calculer Trivialement "x" divisant "par" c ".

`` x = s / c ''

Cependant, avec l'ajout de nonce, x est caché à Bob et ne peut pas être calculé uniquement à partir de `s`.

`` x = (s - r) / c ''

Lors de la réception du `s` d'Alice, Bob vérifie les sorties de protocole,` s` et `R` comme suit: Bob calcule`s * G` et vérifie si cette valeur est égale à la somme de (1) le public nonce, «R» et (2) la clé publique, «P», multipliée par le défi, «c». Bob peut être sûr qu'Alice connaît «x» si cette égalité est respectée, car Bob a mis à l'échelle «P» pour «c» et pourtant, Alice connaissait le logarithme discret du résultat (compensé par le nonce public), «s» . Par conséquent, à moins qu'Alice ne dispose d'un moyen efficace de calculer des logarithmes discrets, elle devrait connaître & # 39; x & # 39 ;.

Cependant, comme mentionné précédemment, si Bob fournit à Alice le `c` avant de recevoir le` R`, alors Alice peut choisir un `R` malveillant et inciter Bob à vérifier, même si Alice n'a aucune connaissance de la clé privée, «x», et du nonce, «r». Alice le fait en sélectionnant un module entier aléatoire «q» à utiliser comme «s», puis calcule «s * G» et «c * P». Ensuite, Alice soustrait «c * P» de «G» pour calculer «R».

`` R: = s * G - c * P ''

Maintenant, Alice a un nonce public valide, «R», sans connaître le nonce privé, «r», et un «s» valide sans connaître la clé privée, «x». Par conséquent, nous pouvons voir qu'il est extrêmement important que Bob ne révèle pas «c» à Alice jusqu'à ce qu'il ait reçu «R» de sa part, sinon Alice peut choisir «R» par malveillance, calculant la différence entre «c * P» et `s * G`.

L'heuristique Fiat-Shamir est une méthode qui transforme les protocoles Sigma en schémas de signature numérique. Pour ce faire, il remplace la valeur de défi, «c», par un hachage cryptographique de (1) un message, «m», qui est les données signées, et (2) le nonce public, «R». Exiger «R» comme entrée pour une fonction de hachage qui crée «c» empêche Alice de calculer «R» à partir de «c * P» et «s * G», car «c» est maintenant généré sur la base de «R» , et donc «R» doit préexister «c».

Le protocole de signature procède de la même manière que le protocole d'identité: Alice multiplie sa clé privée, «x», par la valeur de défi, «c», puis l'ajoute au nonce privé, «r», pour produire «s» . La signature se compose de la paire de valeurs «s» et de l'engagement nonce «R» qu'Alice fournit à Bob. Bob peut calculer le même «c» car «c: = H (m || R)».

La structure de l'algorithme de vérification est la même que celle du protocole d'identité: `s * G == R + c * P`

Une signature Schnorrer est identique à une signature Schnorr, sauf que la valeur de défi, «c», est un hachage de (1) le message et (2) de la clé publique, «P», au lieu de (1) le message et (2) l'engagement nonce, «R». Cette modification apparemment minime du schéma le rend peu sûr.

L'attaque par contrefaçon se poursuit dans le même sens que l'attaque d'identification décrite ci-dessus. Dans l'attaque d'identification, Bob a fourni la valeur du défi à Alice avant de recevoir le nonce public, «R». De même, comme la valeur de défi de la signature Schnorrer n'inclut pas «R», Alice peut inverser l'ordre du protocole et d'abord choisir une valeur «s», puis calculer «R» comme la différence entre «s» G` et `c * P`, et ainsi forger une signature, en d'autres termes, avec ce défaut, Alice peut produire une signature Schnorrer valide sans connaître la clé privée,` x`, (et aussi sans connaître le nonce, `r ').

Par Jake Craige

Ce défi est décrit comme suit:

Étant donné deux engagements de Pedersen à l'intérieur et à l'extérieur, vous devez établir la preuve que la différence entre les montants d'engagement est nulle. Nous utiliserons la courbe secp256k1 et définirons «g» comme point de base standard de la courbe et «h = g ^ SHA256 (« CoinbaesRulez »)».

Nous définirons les engagements d'entrée et de sortie comme «in = g¹³³⁷⋅h⁹⁸⁷⁶» et «out = g²⁶⁷⁴ ⋅h³⁴⁵⁶» et nous passerons par l'évaluation ici.

= in⋅out ^ −1= (g¹³³⁷⋅h⁹⁸⁷⁶) ⋅ (g ^ −2674⋅h³⁴⁵⁶) ^ - 1= g ^ (1337 + 2674) ⋅h ^ (9876-3456)y = g⁴⁰¹¹⋅h⁶⁴²⁰

Nous voyons que ce n'est pas un engagement à zéro et, en fait, crée plus d'argent que ce qui a été investi. Votre tâche est de nous fournir une paire «(t, s)» qui convainc un vérificateur que «y» est un engagement à zéro, même si ce n'est pas vrai.

Voici les données d'entrée que vous devez utiliser pour créer la signature. Les points de courbe elliptique (compromis) sont fournis dans le codage compressé SEC. Pour la signature, nous utiliserons le test du protocole d'identification Schnorr décrit dans le PDF ci-joint. Vous devez utiliser le nonce fourni pour obtenir un résultat déterministe pour la vérification CTF.

dans = 0x25b0d4d0ad70054b53c16d6b3269b03e7b8582aa091317cab4d755508062c6f43out = 0x35e3bdfa735f413f2213aa61ae4f7622596feddb96ecc0f263892cb35ca460182y = 0x20ab37bbcc43b8e96714aae06fdc1bbfc386d0165afb69500c9df1553e6c94ed1nonce = 0x19

La présentation doit être au format `(t, s)` où `t 'est le point compressé codé en hexadécimal et` s` est un entier non signé codé en hexadécimal. Les deux doivent avoir un préfixe `0x` et les parenthèses et`,` doivent être présents pour vérifier. Un exemple de format serait: `(0xdead, 0xbeef)`.

Le problème avec la construction définie ci-dessus est de savoir comment `h` est sélectionné. Pour qu'un engagement Pedersen soit fiable, personne ne peut connaître le dossier discret de & # 39; h & # 39; en ce qui concerne & # 39; g & # 39 ;. Ré-exprimé: personne ne devrait connaître «x» tel que «h = g ^ x». La connaissance de cela permet de forger des engagements.

N'oubliez pas que notre engagement ressemble à «y = g ^ a⋅h ^ b» où «a» est le montant et «b» est le facteur aveuglant. Nous fournissons un test pour «y = h ^ z». Avec un testeur non malveillant, cela démontre un engagement avec un montant nul car `y = g⁰⋅h ^ b = h ^ b`, nous montrons donc simplement que nous connaissons le facteur aveuglant` b` et vérifions avec la clé publique` et

Malheureusement, en dérivant naïvement «h» de «g», nous connaissons l'enregistrement discret et pouvons falsifier la signature. Voilà comment.

Nous établissons d'abord l'égalité que nous souhaitons forger, et nous la restructurons pour que tout se fasse sur la base du «g». C'est l'étape qui ne peut être effectuée que si vous connaissez l'enregistrement discret de `h`qui est la valeur` x`.

À partir de là, nous pouvons résoudre la valeur `z` qui est ce dont nous avons besoin pour créer le test. Pour une notation plus simple, nous libérons la base pour montrer comment cette valeur est résolue.

Avec cette équation en main, nous pouvons procéder à la création du test. Les valeurs de `a, b, x` peuvent être trouvées dans l'énoncé du problème:` a = 4011`, `b = 6420` et` x = SHA256 (" CoinbaesRulez ")` Nous traitons la sortie d'octets de la fonction SHA256 aussi grand endian pour le représenter comme un nombre.

En utilisant ces informations, nous pouvons calculer «z» en utilisant notre équation d'avant. En Python, cela peut être fait comme suit:

importer du hashlib# ordre secp256k1order = int ("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", 16)def modinv (a, module): return pow (a, module - 2, module)a = 4011b = 6420x = int (hashlib.sha256 ("CoinbaesRulez"). hexdigest (), 16)z = (a * modinv (x, ordre) + b)% ordre

Maintenant que nous connaissons «z», la dernière étape consiste à créer un test de connaissance d'enregistrement discret à envoyer comme indicateur de solution. Cela se fait à l'aide du protocole d'identification Schnorr, où nous utilisons la transformation Fiat-Shamir afin qu'elle ne soit pas interactive en définissant la valeur de défi comme la grande représentation endienne de la sortie SHA256 des points compressés H, T et Y concaténés ensemble comme octets La description du problème fournit un nonce fixe pour rendre la sortie déterministe. La solution en Python, basée sur le code Python précédent, est:

depuis fastecdsa.curve import secp256k1à partir du point d'importation fastecdsa.pointde fastecdsa.encoding.sec1 import SEC1Encoder# Participation au défiH = secp256k1.G * xr = 0x19# Générer le test de connaissances d'enregistrement discretT = H * rY = H * zhashInput = SEC1Encoder.encode_public_key (H)hashInput + = SEC1Encoder.encode_public_key (T)hashInput + = SEC1Encoder.encode_public_key (Y)c = int (hashlib.sha256 (hashInput) .hexdigest (), 16)s = (r + c * z)% ordre# Imprimer le drapeau formatéprint (“(0x” + SEC1Encoder.encode_public_key (T) .encode (“hex”) + “, 0x” + format (s, ‘x’) + “)”))

Pour en savoir plus sur la façon dont ces engagements Pedersen sont utilisés dans la pratique des blockchains, je recommande de lire sur les blockchains basées sur MimbleWimble.

Ceci conclut nos écrits pour le concours Capture the Coin. Nous espérons que vous avez apprécié d'en savoir plus sur une variété de problèmes de sécurité de la blockchain et que vous pourrez nous rejoindre l'année prochaine.

Mientras tanto, si resolver los desafíos de seguridad de blockchain es algo que ves haciendo a tiempo completo, únete a nosotros en Coinbase para ayudar a construir la marca más confiable en Crypto aquí.