Comment tester

Le prérequis est d'avoir installé gcc et une version vulnérable d'OpenSSL.

Pour le bogue dans BN_mod_sqrt() : compilez avec gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto, exécutez ./my_bad_sqrt et regardez-le se bloquer pour toujours ! :D

Avec un certificat : exécutez openssl x509 -in certs/cert.der.new -inform DER -text -noout en ligne de commande ; cela se bloque également.

Déclencher la boucle

La fonction BN_mod_sqrt() implémente l'algorithme de Tonelli-Shanks pour trouver une racine carrée modulaire, c'est-à-dire que, étant donné un entier a et un nombre premier p, elle retourne une valeur r telle que r^2 == a (mod p).

En analysant le commit qui corrige la vulnérabilité, on voit que le coupable est la boucle qui trouve le plus petit indice i tel que b^(2^i)==1 (mod p), où b est défini plus haut dans l'algorithme.

La boucle passe de

à

Dans le second cas, il y a une boucle for limitée par la variable e ; dans le code d'origine, il n'y a cependant qu'une vérification du cas i==e à l'intérieur d'une boucle while.

Comme ces boucles sont à l'intérieur d'une boucle plus grande qui, à chaque itération, définit la nouvelle valeur de e comme étant la valeur courante de i, nous essayons la stratégie d'attaque suivante :

1. lors de la première exécution de la boucle externe, faites en sorte que i=1 à la fin ; pour cela, nous avons besoin que b^2=1 (mod p).
2. de cette façon, lors de la seconde exécution nous aurons e=1, et si nous pouvons entrer dans la boucle interne, la vérification i==e échouera toujours
3. si nous parvenons à avoir toujours t != 1 (mod p), nous resterons alors dans la boucle pour toujours

Notez que les deux premières étapes peuvent en réalité se produire lors d'une exécution « normale », c'est-à-dire avec un nombre premier p. Cependant, si p est composé, nous pouvons également satisfaire la troisième étape !

Un peu de mathématiques

L'algorithme de Tonelli-Shanks fonctionne en écrivant p - 1 = 2^e * q, avec q impair. C'est aussi l'ordre du groupe multiplicatif des entiers modulo p, et les valeurs e et q seront utilisées de nombreuses fois pendant l'exécution ; cependant, si p n'est pas premier, l'ordre du groupe multiplicatif ne sera pas p-1, ce qui nous aidera à entrer dans la boucle infinie.

En particulier, b est initialisé comme b = a^q (mod p), ce qui signifie que si p était premier, alors b aurait pour ordre une puissance de 2, que nous trouverons ensuite en utilisant la boucle.

Mais si nous posons p = r * s, l'ordre du groupe multiplicatif est (r-1)*(s-1) = r*s - r - s + 1 au lieu de r*s-1. L'algorithme utilise la valeur q pour obtenir un élément y d'ordre exactement 2^e ; cependant, lorsque p n'est pas premier, la valeur q n'aura pas de signification particulière pour l'ordre, donc l'élément y n'aura pas un ordre qui soit une puissance de deux modulo p=r*s.

Comme à la fin de la première boucle externe b est défini comme b = b*y^(e-i) (mod p), à sa seconde itération la boucle interne essaiera de trouver une valeur i telle que b^(2^i) == 1 (mod p), mais échouera étant donné que y n'est plus garanti d'avoir un ordre qui soit une puissance de deux.

L'exploit

Les nombres dans l'exploit sont très simples : nous prenons r=17,s=41, ce qui donne p=r*s=697. Cela signifie que les valeurs calculées de e et q seront p-1 = 2^3 * 87.

Nous choisissons ensuite a=696, ce qui signifie que a == -1 (mod p) et aussi b == -1 (mod p) lors de l'initialisation. Cela satisfera l'étape 1 en définissant e=1 pour la boucle externe suivante.

Ensuite, b sera défini comme un élément dont l'ordre n'est pas une puissance de 2, et la boucle interne restera bloquée à essayer de trouver un i tel que b^(2^i)==1 (mod p).

Créer un certificat dangereux

OK, maintenant fabriquons un certificat dangereux qui contient des paramètres de courbe explicites invalides avec un point de base encodé sous forme compressée.

Les fichiers de cette section se trouvent dans le dossier certs.

Créer un certificat normal avec des paramètres de courbe explicites

Tout d'abord, nous devons créer une clé privée EC. Comme nous voulons un certificat cible avec des paramètres de courbe explicites, la clé doit également contenir des paramètres de courbe explicites.

Ensuite, pour plus de commodité, nous avons auto-signé un certificat et l'avons sorti au format DER.

Vérifions les informations du certificat. Il contient des paramètres de courbe explicites comme prévu.

Fabriquer un certificat invalide

Maintenant, nous devons modifier les valeurs de ces paramètres : Prime, A, B, Generator. Ils satisfont l'équation ci-dessous

où p est le Prime, a est le paramètre A et b est le paramètre B. p, a, b déterminent ensemble une courbe. Décompresser un point signifie calculer la coordonnée Y à partir de la coordonnée X correspondante.

Évidemment, l'opération de racine carrée modulaire doit être utilisée, ce qui fera appel à BN_mod_sqrt().

Sur la base des travaux de drago-96, nous prenons p=697, x^3+ax+b=696. Ensuite, il suffit de choisir des valeurs appropriées pour a, b, x qui satisfont la seconde équation. Nous prenons x=8, a=23, b=0 ici.

OK, nous pouvons maintenant commencer à nous attaquer au certificat. Éditer la structure ASN.1 manuellement est vraiment pénible. J'ai utilisé l'outil xxd pour transformer le certificat au format hexadécimal, puis je l'ai édité avec vim. Une fois l'édition terminée, je l'ai retransformé avec xxd -r.

Je n'ai pas trouvé d'outil plus pratique. Si quelqu'un connaît un tel outil, merci d'être généreux dans vos commentaires.

Les étapes de fabrication sont approximativement les suivantes :

1. Modifier les valeurs de Prime, A, B, Generator
   1. Changer Prime en 697, c'est-à-dire 0x2b9 en hexadécimal
   2. Changer A en 23, c'est-à-dire 0x17 en hexadécimal
   3. Changer B en 0
   4. Changer la coordonnée X de Generator en 8, c'est-à-dire 0x020008 (ou 0x030008) lorsqu'elle est encodée au format compressé
2. Comme OpenSSL vérifie le format de remplissage de ASN1_INTEGER, le Prime ne doit pas contenir d'octets zéro en tête, donc nous devons changer la longueur de Prime.
3. De même, OpenSSL compare la longueur de Prime avec la longueur de la chaîne du point, donc la longueur de la coordonnée X de Generator doit être identique à celle de Prime. C'est pourquoi nous définissons Generator comme 030008 et non comme 0308.
4. Parce que la structure ASN.1 du certificat est imbriquée, toutes les longueurs des objets externes doivent également être corrigées.
5. Notez qu'il peut y avoir un caractère de nouvelle ligne (0x0a) indésirable à la fin du fichier après avoir exécuté xxd -r. Éliminez-le.

Maintenant, regardons la structure ASN.1 du certificat normal. Les parties marquées par une ligne rouge doivent être modifiées.

Les longueurs avant et après modification sont listées comme suit :

Utilisation des modèles ASN1

Mis à jour le 2020-03-21 :

Une manière beaucoup plus simple est d'utiliser l'outil asn1template écrit par wllm-rbnt.

Clonez le dépôt :

Générez un modèle DER à partir de ce certificat :

Ensuite, modifiez les paramètres que nous venons de mentionner ci-dessus :

Convertissez-le à nouveau en ASN1 encodé DER avec ASN1_generate_nconf(3) :

Le résultat cert_new.der est équivalent à la version éditée manuellement.

Nous avons donc maintenant fabriqué avec succès un certificat invalide. Regardons la nouvelle structure ASN.1

Toutes les parties rouges ont été modifiées, et le certificat peut être correctement décodé en DER.

Test avec le certificat invalide

Maintenant, essayons d'analyser le certificat. Le processus entrera dans la boucle infinie si tout se passe comme prévu.

Comme on le voit, le %CPU du processus openssl est de 100, et la pile d'appels se trouve dans BN_mod_sqrt().

Si un attaquant malveillant envoie un tel certificat fabriqué lors d'une poignée de main SSL avec le serveur, le serveur entrera dans la boucle infinie, ce qui provoque une attaque par déni de service.

Créer un certificat, méthode alternative

Nous allons essayer de fabriquer un certificat en utilisant la bibliothèque C libcrypto d'OpenSSL.

Comme nous l'avons vu, nous devons utiliser une courbe avec un corps de base non premier et encoder les points sous forme compressée, afin de rencontrer le bogue dans BN_mod_sqrt() lors de l'analyse.

Cela peut être fait en définissant y^2 = x^3 + 1*x + 694 (mod 697) comme courbe, avec (1, 132) comme générateur ; cela appellera BN_mod_sqrt() avec exactement les mêmes paramètres que my_bad_sqrt.

L'exécution de gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group générera le fichier my_bad_group.der qui contient les paramètres EC au format DER.

Essayer d'analyser ces paramètres avec OpenSSL aboutira à la boucle infinie : openssl ecparam -in my_bad_group.der -inform der.

... WIP ...