Rejoignez-Nous sur

Capture the Coin – Solutions de catégorie de cryptographie

0*bAsbvjR0OEBHHl91

News

Capture the Coin – Solutions de catégorie de cryptographie

Coinbase

Par Jake Craige, Max Mikhaylov, Jesse Posner

Dans le dernier message du Capturez la pièce série de concours, nous allons plonger dans les solutions pour nos défis de cryptographie. N'hésitez pas non plus à revoir nos autres articles de la série pour Trivia, Blockchain aussi bien que Compétition et Prix annonces.

Par Jake Craige

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

def encrypt(message)require ‘openssl’# Encrypt the message using random key+iv with AES-128-OFBcipher = OpenSSL::Cipher.new(‘AES-128-OFB’).encryptrandom_key = cipher.random_keycipher.key = random_keyrandom_iv = cipher.random_ivcipher.iv = random_ivciphertext = cipher.update(message) + cipher.final# Encrypt the IV with AES-128-ECBsimple_cipher = OpenSSL::Cipher.new(‘AES-128-ECB’).encryptsimple_cipher.key = random_keyencrypted_iv = simple_cipher.update(random_iv) + simple_cipher.final{ciphertext: ciphertext.unpack(‘H*’).first,encrypted_iv: encrypted_iv.unpack(‘H*’).first}end

Si vous avez travaillé avec AES auparavant, il y a quelques parties qui peuvent vous sembler intéressantes.

Tout d'abord, il utilise le Retour de sortie (OFB) mode de fonctionnement vu par l'utilisation de «AES-128-OFB» dans l'invite. Il n'y a rien de mal à cela en soi, mais les modes Cipher Block Chaining (CBC) et Counter (CTR) sont plus courants et dans la pratique, cryptage authentifié (AE) comme Galois / Counter Mode (GCM) doit être utilisé.

Ensuite, nous voyons que l'IV est crypté et utilise le Codebook électronique (BCE) mode. Les IV sont des valeurs non secrètes et n'ont pas besoin d'être cryptées. La sécurité du chiffrement par bloc repose sur 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 à lui seul.

Voyons ce que sont les chiffrements et les modes de bloc, 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 et un texte en clair de taille fixe en entrée et génère une sortie de taille fixe, appelée bloc. Ils sont utilisés pour le chiffrement, ce qui implique qu'ils ont également une opération de déchiffrement qui accepte la clé et le texte chiffré et renvoie le texte en clair.

Un chiffrement par bloc en lui-même n'est pas sécurisé pour chiffrer plus d'un message car chiffrer deux fois le même message entraînerait le même texte chiffré, autrement dit, un chiffrement par bloc est déterministe.

Pourquoi c'est un problème? Supposons qu'une armée envoie un jour le message "Attaque à l'aube" et que son adversaire le comprenne. Un autre jour, si l'armée envoie le même message et que l'adversaire regarde, elle saura qu'une attaque est imminente et pourra mettre en place des défenses.

Formellement, nous disons qu'un chiffrement par bloc n'est pas IND-CPA sécurisé (impossible à distinguer sous une attaque en texte clair choisie). Cela signifie que si nous avons un service de chiffrement de données et que nous lui fournissons deux textes en clair séparés à 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 un chiffrement de bloc différent «Modes de fonctionnement». La valeur par défaut est ECB, qui n'est pas sécurisée, et d'autres modes la sécurisent en introduisant l'aléatoire et en enchaînant les blocs de diverses manières.

Nous passerons en revue les modes ECB et OFB car ils correspondent à ce que le défi utilise.

Codebook électronique (BCE)

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

Un exemple populaire de la raison pour laquelle ce mode ne parvient pas à fournir suffisamment de sécurité 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 donnerait à l'image cryptée un aspect aléatoire comme on le voit sur la troisième image. Des modes autres que la BCE le permettent.

Retour de sortie (OFB)

OFB introduit un vecteur d'initialisation, OR 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 chiffrement et préfixée au texte chiffré. La combinaison des blocs IV et de chaînage aléatoires résout ensemble les problèmes que nous avons décrits avec la BCE.

Avec une compréhension des chiffrements de blocs utilisés dans l'invite, nous pouvons examiner comment ils ont été utilisés et trouver la solution. Rappelons que les deux textes chiffrés sont générés comme suit:

  1. Le message est crypté avec une clé aléatoire et IV en utilisant AES-128-OFB.
  2. Le même IV est ensuite chiffré avec AES-128-ECB en utilisant le 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 en clair est exactement un bloc car AES-128 utilise des blocs de 128 bits. Compte tenu de cela, nous pouvons décrire le texte chiffré du message comme Chiffrer (clé, IV) le message XOR. Pour le cryptage IV, le mode ECB a été utilisé, donc le IV crypté 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 en clair par Ciphertext XOR EncryptedIV ce qui équivaut à Crypter (clé, IV) XOR Message XOR Crypter (clé, 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 affiche 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 codées hexadécimales utilisant la courbe secp256k1 pour la clé publique fournie. Ces signatures ont été générées en utilisant 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 à la soumettre (hex codée avec le préfixe 0x) comme solution à ce défi.

Pubkey (SER-compressed): 0x2341745fe027e0d9fd4e31d2078250b9c758e153ed7c79d84a833cf74aae9c0bbSig #1 (msg): what up defconSig #1 (r, s): (0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491, )Sig #1 (msg): uh oh this isn’t goodSig #2 (r, s): (0x5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491, 0xd67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee)

L'invite explique ce qui ne va pas, donc tout ce que nous avons à faire est de comprendre comment résoudre la clé privée. Une recherche rapide fournira diverses explications du problème et comment le résoudre. Wikipedia fournit un bonne explication de la façon dont les signatures ECDSA sont générées et documente la solution à la réutilisation nonce. Nous allons décrire les mathématiques ici 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 ’ qui a utilisé le même nonce, la première étape consiste à résoudre pour la clé privée est de résoudre pour 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:

import hashlib# secp256k1 orderorder = int(“fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141”, 16)# Input from challengez = int(hashlib.sha256(“what up defcon”).hexdigest(), 16)z_prime = int(hashlib.sha256(“uh oh this isn’t good”).hexdigest(), 16)s = int(“1a53499a4aafb33d59ed9a4c5fcc92c5850dcb23d208de40a909357f6fa2c12c”, 16)s_prime = int(“d67006bc8b7375e236e11154d576eed0fc8539c3bba566f696e9a5340bb92bee”, 16)r = int(“5d66e837a35ddc34be6fb126a3ec37153ff4767ff63cbfbbb32c04a795680491”, 16)# dividing within a field is not standard division so we need to define it as followsdef modinv(a, modulus): return pow(a, modulus — 2, modulus)def divmod(a, b, modulus): return (a * modinv(b, modulus)) % modulus# Solve for private key dk = divmod(z — z_prime, s — s_prime, order)d = divmod(k * s — z, r, order)# output challenge flagprint(hex(d))

Cela affiche correctement l'indicateur de défi 0x128e06938ac462d9.

Par Max Mikhaylov

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

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

En examinant les transactions qui ont été diffusées vers le nœud, nous constatons que toutes contiennent 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 transaction semble valide. Essayons de convertir ces clés publiques en points ECC sur la courbe brainpoolP160r1. Écrivons une fonction qui convertit une seule clé publique en un point de la courbe.

def key_to_point(key):return Point(int(key(2:42), 16), int(key(42:), 16), curve=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 sur la courbe

Il semble que la clé publique fournie par l'expéditeur ne se trouve pas sur la courbe brainpoolP160r1. En fait, aucune des clés publiques fournies ne se trouve sur cette courbe. D'après la description du modèle de transaction du Livre blanc sur le Cryptonote nous savons que le nœud doit effectuer une multiplication scalaire à l'aide de la clé publique de transaction de l'expéditeur et de 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 nœud n'était pas défectueuse, elle aurait vérifié si la clé publique fournie par l'expéditeur se trouve sur la courbe attendue et lève une exception si elle ne se trouve pas sur la courbe (tout 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 journal.

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 est 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(self, x, y, curve):self.x = xself.y = yself.curve = curvePoint.__init__ = point_init_monkey_patch

Nous pouvons maintenant essayer de convertir tx_pub_key en point ECC pour toutes les transactions une fois de plus; pas d'erreur:

Contribution:

pub_key_points = txs_to_pub_key_points(txs) # txs is dict of txs.json contents

Nous pouvons également convertir les valeurs secrètes partagées des journaux de nœuds en points ECC, maintenant que nous avons corrigé la bibliothèque ECC par monkey:

def err_log_to_shared_secret_points(err_log):    shared_secret_points = ()    for entry in err_log:        msg = entry(‘err_msg’)        shared_secret = msg.split(‘P_prime=’)(1).split()(0)        shared_secret_point = key_to_point(shared_secret)        shared_secret_points.append(shared_secret_point)     return shared_secret_pointsshared_secret_points = err_log_to_shared_secret_points(err_log) # err_log is dict of err_log.json contents

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

Contribution:

def point_order(p):    for x in range(2, brainpoolP160r1.p):    if x * p == p:        return x — 1point_order(pub_key_points(0))

Production:

2

C'est un ordre très bas! Il s'avère que d'autres points clés publics sont également de mauvaise qualité. 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 à courbe invalide. Vous pouvez en savoir plus sur ce qu'est une attaque par courbe invalide «Guide de la cryptographie à courbe elliptique» par Hankerson, Menezes et Vanstone à la page 182. Lisez également une récente CVE-2019–9836 décrivant cette attaque dans un cadre pratique (c'était le deuxième indice de ce défi).

L'essentiel 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 premier, et puisse trouver les résultats de ces calculs, nous pouvons récupérer le secret en utilisant le Théorème du reste chinois (CRT). Pour être plus précis, nous avons besoin que le produit de tous les points de commande inférieurs soit supérieur à la clé privée pour que la clé récupérée soit unique (donc, correspond à la clé privée). Si nous calculons le produit de l'ordre de tous les points dans `pub_key_points`, nous pouvons en fait voir que ce nombre ne tient pas sur 160 bits, doit donc être plus grand que la clé privée utilisée avec la courbe brainpoolP160r1.

Contribution:

product = 1for point in pub_key_points:    product *= point_order(point)from math import log2log2(product)

Production:

175.1126248794482 # the product occupies 176 bits in binary representation

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é le Implémentation CRT de Rosetta Code.

Nous sommes maintenant prêts à effectuer 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 en essayant simplement tous les scalaires possibles qui sont plus petits que l'ordre de la clé publique.
  • En renforçant brutalement le plus petit scalaire possible qui nous donne le secret partagé 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 principales est supérieur à la clé privée que nous recherchons, le résultat de l'application du CRT est unique.

Contribution:

v = () # can think of values in this list as the minimum number of EC additions of E_hat to itself to get shared_secretmoduli = () # prime moduli of the systemprint(“Constructing a system of simultaneous congruences:”)for P_hat, shared_secret in zip(pub_key_points, shared_secret_points):     order = point_order(P_hat)     # search for shared_secret mod o_prime; i.e. the min number of additions of E_hat to itself to get shared_secret     for x in range(1, brainpoolP160r1.p):         if x * P_hat == shared_secret: # found the min number of additions            print(f’e ≡ {x} mod {order}; ’, end=’’)            v.append(x)
moduli.append(order)
break

Production:

Construire un système de congruences simultanées:

e ≡ 1 mod 2; e ≡ 1 mod 11; e ≡ 7 mod 23; e ≡ 1 mod 5; e ≡ 34 mod 41; e ≡ 4 mod 7; e ≡ 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; e ≡ 4771 mod 9767; e ≡ 381213 mod 439511; e ≡ 758 mod 10009; e ≡ 14048 mod 26459; e ≡ 11 mod 37; e ≡ 196934 mod 949213;

Contribution:

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

Production:

‘0xdec1a551f1edc014ba5edefc042019’

Cet hex de clé privée a l'air inhabituel… C'est définitivement un drapeau!

P.S. Si vous êtes curieux de savoir comment j'ai trouvé des points d'ordre bas en premier lieu, voir ma question sur Cryptography Stack Exchange que j'ai demandé en travaillant sur ce défi.

Par Jesse Posner

Ce défi décrit un schéma de signature défectueux appelé Schnorrer signatures. Ce schéma est presque identique à 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 les contrastant avec une signature Schnorr. Une signature Schnorr applique le Heuristique Fiat-Shamir au protocole d'identification Schnorr, une preuve de connaissance interactive protocole sigma, et le transforme en signature numérique protocole.

À Schnorr, le défi heuristique Fiat-Shamir est généré par le hachage du message et du nonce public, mais à 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 signature Schnorrer compromet 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 prouveur et (3) un vérificateur. Le prouveur génère un secret, «x», et veut prouver au vérificateur qu'il connaît «x» sans le révéler au vérificateur.

Les deux parties devront convenir de certains paramètres: a groupe cyclique, avec un Générateur, «G» et un nombre premier module, «q». Par exemple, le protocole Bitcoin utilise le secp256k1 paramètres, avec un générateur spécifié par un courbe elliptique pointer avec comprimé coordonné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 prouveur utilise l'algorithme de génération de clés pour produire un paire de clés publique-privée, «x» et «P». «x» est un entier sélectionné au hasard dans un champ fini avec modulo «q». La clé publique `P` est calculée en utilisant` x` comme valeur scalaire et en la multipliant par `G`:

```x*G```

La clé privée, «x», est le logarithme discret de «P» avec la base «G», et donc le vérificateur est incapable de dériver efficacement la clé privée de la clé publique, et ainsi le prouveur peut révéler une clé publique sans révéler la clé privée, d'où le «public» et « dénotations privées.

Protocole

Supposons qu'Alice veuille prouver à Bob qu'elle connaît la valeur «x». Alice commence 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 la circonstance”). Alice calcule ensuite la valeur `r * G` pour dériver l'élément de groupe` R`, de la même manière que la clé publique a été générée. Cette valeur, «R», est généralement appelée le nonce public ou l'engagement nonce. Une fois qu'Alice a sa clé publique, «P», et le nonce public, «R», elle envoie ces valeurs à Bob.

Bob doit maintenant générer une autre valeur scalaire appelée la valeur de défi, «c». Après que Bob ait reçu «P» et «R», il génère ensuite «c» et l'envoie à Alice. Notez que bien que «c» soit indépendant de «R», il est très important que Bob attende d'avoir reçu «R» d'Alice avant de lui envoyer «c». En fait, si Bob ne parvient pas à le faire et envoie `c` à Alice avant de recevoir` R`, Alice peut faire croire à Bob qu'elle a connaissance de la clé secrète sans la connaître. L'intégrité de la vérification dépend de la génération de «R» avant «c», comme nous le verrons sous peu.

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 qui est appelé la valeur «s». `s` doit être modulo` q` (toutes les valeurs scalaires doivent être modulo `q` pour qu'elles tombent 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, `x`, et (2) une valeur choisie uniquement par Bob, à savoir le défi,` c`. Pourtant, Alice doit accomplir cela sans divulguer directement «x» à Bob. Si nous omettions le nonce du protocole, alors `s` serait égal à` x * c`, et, bien que cette valeur prouverait en effet la connaissance d'Alice de `x` à Bob, elle le fait de manière trop agressive et permet à Bob de calculer trivialement «x» en divisant «s» par «c».

```x = s/c```

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

```x = (s — r)/c```

En recevant `s` d'Alice, Bob vérifie les sorties du 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» par «c», et pourtant Alice connaissait le logarithme discret du résultat (compensé par le nonce public), «s». Ainsi, à moins qu'Alice ne dispose d'un moyen efficace pour calculer des logarithmes discrets, elle doit connaître «x».

Cependant, comme mentionné ci-dessus, si Bob fournit `c` à Alice avant de recevoir` R`, alors Alice peut choisir un `R` malveillant et inciter Bob à vérifier la sortie, bien qu'Alice ne connaisse pas réellement la clé privée, `x`, et le nonce,` r`. Alice le fait en sélectionnant un module aléatoire aléatoire `q` à utiliser comme` s`, puis calcule `s * G` et` c * P`. Ensuite, Alice soustrait `c * P` de` s * 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». Ainsi, nous pouvons voir qu'il est extrêmement important que Bob ne divulgue pas «c» à Alice jusqu'à ce qu'il ait reçu «R» de sa part, sinon Alice peut choisir «R» par malveillance, en 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 qui sont signées, et (2) le nonce public, «R». Le fait d'exiger `R` comme entrée d'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 ainsi «R» doit préexister «c».

Le protocole de signature procède de manière similaire au 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», qui sont fournies à Bob par Alice. Bob peut calculer `c` lui-même parce que` 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 déroule de la même manière 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, étant donné que la valeur de défi de signature Schnorrer n'inclut pas «R», Alice peut inverser l'ordre du protocole, choisir d'abord une valeur «s», puis calculer «R» comme la différence entre «s * G» et « c * P`, et donc 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 Pedersen entrants et sortants, vous devez construire une preuve que la différence entre les montants d'engagement est nulle. Nous allons utiliser la courbe secp256k1 et définir «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 parcourrons 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 crée en fait plus d'argent qui y est allé. Votre tâche consiste à 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 la courbe elliptique (engagements) sont fournis dans le codage compressé SEC. Pour la signature, nous utiliserons la preuve du protocole d'identification Schnorr décrite dans le PDF ci-joint. Vous devez utiliser le nonce fourni afin que nous obtenions un résultat déterministe pour la vérification CTF.

in=0x25b0d4d0ad70054b53c16d6b3269b03e7b8582aa091317cab4d755508062c6f43out=0x35e3bdfa735f413f2213aa61ae4f7622596feddb96ecc0f263892cb35ca460182y=0x20ab37bbcc43b8e96714aae06fdc1bbfc386d0165afb69500c9df1553e6c94ed1nonce=0x19

La soumission doit être au format `(t, s)` où `t 'est le point compressé codé hexadécimal et` s` est un entier non signé codé hexadécimal. Ils doivent tous les deux 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 digne de confiance, personne ne peut connaître le log discret de «h» par rapport à «g». Retraité: personne ne devrait connaître `x` tel que` h = g ^ x`. La connaissance de cela permet de forger des engagements.

Rappelons que notre engagement ressemble à «y = g ^ a⋅h ^ b» où «a» est le montant et «b» est le facteur aveuglant. Nous fournissons une preuve pour `y = h ^ z`. Avec un prouveur non malveillant, cela prouve un engagement à un montant nul car `y = g⁰⋅h ^ b = h ^ b`, nous prouvons donc simplement que nous connaissons le facteur aveuglant` b` et vérifions par rapport à la clé publique ` y`.

Malheureusement, en dérivant naïvement «h» de «g», nous connaissons le journal discret et pouvons forger la signature. Voici comment.

Nous mettons d'abord en place l'égalité que nous souhaitons forger, et la restructurons de telle sorte que tout se fasse dans la base «g». C'est l'étape qui ne peut être effectuée que si vous connaissez le journal discret de `h`qui est la valeur` x`.

À partir de cela, nous pouvons résoudre la valeur «z», ce dont nous avons besoin pour créer la preuve. Pour une notation plus simple, nous supprimons la base pour montrer comment cette valeur est résolue.

Avec cette équation en main, nous pouvons procéder à la création de la preuve. 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 comme big-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:

import hashlib# secp256k1 orderorder = int(“fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141”, 16)def modinv(a, modulus): return pow(a, modulus — 2, modulus)a = 4011b = 6420x = int(hashlib.sha256(“CoinbaesRulez”).hexdigest(), 16)z = (a * modinv(x, order) + b) % order

Maintenant que nous connaissons «z», la dernière étape consiste à créer une preuve de connaissance du journal discret à soumettre comme indicateur de solution. Cela se fait en utilisant le protocole d'identification Schnorr où nous utilisons la transformation Fiat-Shamir pour la rendre non interactive en définissant la valeur de défi comme étant la représentation big-endienne de la sortie SHA256 des points compressés H, T et Y concaténés ensemble en octets. La description du problème fournit un nonce fixe pour rendre la sortie déterministe. La solution en Python, s'appuyant sur l'ancien code Python, est:

from fastecdsa.curve import secp256k1from fastecdsa.point import Pointfrom fastecdsa.encoding.sec1 import SEC1Encoder# Challenge inputH = secp256k1.G * xr = 0x19# Generate the proof of knowledge of discrete logT = 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) % order# Print the formatted flagprint(“(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 dans les 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é en savoir plus sur une variété de sujets liés à la sécurité de la blockchain et que vous pourrez nous rejoindre à nouveau l'année prochaine.

En attendant, si résoudre des problèmes de sécurité de la blockchain est quelque chose que vous vous voyez faire à plein temps, alors rejoignez-nous à Coinbase pour aider à construire la marque la plus fiable dans le Crypto ici.



Traduction de l’article de Coinbase : Article Original

BlockBlog

Le Meilleur de l'Actualité Blockchain Francophone & Internationale | News, Guides, Avis & Tutoriels pour s'informer et démarrer facilement avec Bitcoin, les Crypto-Monnaies et le Blockchain. En Savoir Plus sur L'Équipe BlockBlog

Commenter cet Article

Commenter cet Article

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Plus dans News

Les Plus Populaires

Acheter des Bitcoin

Acheter des Alt-Coins

Sécuriser vos Cryptos

Vêtements et Produits Dérivés

Top