Journal Générer des clefs GPG avec une empreinte « proche » d’une cible

Sommaire

• Contexte
  • Restriction
• Contenu d’une clef standard
• Génération d’une clef
  • Clef RSA
  • Génération à la chaîne
  • Définition d’empreintes « proches »
    • Probabilités de regard
    • Probabilité de confusion
  • Écriture des clefs
• Code
• Démonstration sur ma clef
• Avertissement
• nimage

Synopsis :

Je vais vous parler de clefs OpenPGP avec GnuPG, et de fabrication de clefs avec une empreinte « proche ». Il y a une nimage à la fin pour les amateurs.

Contexte

Le réseau de confiance PGP, c’est le seul réseau social auquel je participe (très modestement). Ça a tout du réseau social idéal, on a des liens avec d’autres personnes, c’est décentralisé, c’est sécurisé, et ça ne met pas trop en danger la vie privée.

Comme beaucoup de personnes étant attachées à la sécurité, j’ai été amené à faire du prosélytisme autour de moi. Et donc, je me suis retrouvé à quelques reprises à expliquer, en rentrant plus ou moins dans le détail, le fonctionnement d’OpenPGP (avec GnuPG) à diverses personnes.

Il y a un point que j’ai toujours répété :

• « Il faut absolument vérifier l’empreinte de la clef dans sa totalité, il est possible de construire une clef ayant un même identifiant avec une empreinte proche. »

Comme toujours en matière de sécurité, il y a pas besoin que quelque chose soit réalisé pour que l’on considère qu’il faille s’en prémunir, il n’y a même pas besoin que ce quelque chose soit réalisable, il suffit que l’on puisse concevoir que la chose soit éventuellement réalisable pour la considérer comme dangereuse.

Toutefois, je me suis demandé si la chose était réalisable (je savais que oui) et à ma portée, n’ayant rien trouvé sur le Web disant que c’était déjà implémenté.

J’ai lu Fuzzy Fingerprints Attacking Vulnerabilities in the Human Brain, et je m’en suis inspiré sur bien des points.

Après avoir mangé la RFC 4880 sur la définition d’OpenPGP, j’ai été en mesure de proposer quelque chose.

Avant tout, je vais rentrer dans le détail. Je suppose le principe général de clef privée/publique connu.

Restriction

Afin de simplifier, je ne vais parler ici, et dans mon implémentation que de clefs RSA.

Contenu d’une clef standard

Une clef standard est en réalité généralement un ensemble de paquets OpenPGP :

• une clef principale (de signature), cette clef sert à signer les sous‐clefs, les identités, les clefs d’autres personnes, et éventuellement à signer des messages si l’on n’a pas de sous‐clef dédiées à la signature ;
• une ou plusieurs identités, une de ces identités peut être définie comme principale, sinon les implémentations peuvent choisir au pif, et leur conseillant de choisir l’identité avec l’auto‐signature la plus récente. Une photo peut être une identité. Les signatures sont accompagnées :
  • de la signature de la clef principale (avec une date d’expiration),
  • des signatures tierces de l’identité ;
• zéro, une ou plusieurs clefs de chiffrement. Dans le cas général, il n’y en a qu’une de valide, il peut y en avoir zéro, si la clef ne sert qu’à signer. Il est irrationnel d’avoir plusieurs clefs de chiffrement valides en même temps, l’expéditeur d’un message ne saurait pas laquelle utiliser pour chiffrer. Avec :
  • signature de la clef principale (avec une date d’expiration) ;
• zéro, une ou plusieurs clefs de signature. Utile si l’on veut signer sur un poste sans risquer de compromettre sa clef principale gardée, elle, en lieu sûr. Cela permet de révoquer la sous‐clef sans avoir à rebâtir son réseau de confiance. Avec :
  • signature de la clef principale (avec une date d’expiration).

Si vous avez envie de découper votre clef, il existe l’outil gpgsplit qui fait ça très bien pour vous.

Pour les clefs version 4 (pour mémoire les clefs version 3 utilisent md5, gpg vous engueule à chaque fois que vous voulez communiquer avec quelqu’un qui vit dans le passé) :

• l’empreinte est les 20 octets du condensat (SHA1) du paquet de la clef publique principale. Noté habituellement sous forme de 10 × 4 caractères hexa dont les lettres sont en capitales.
• l’identifiant de clef est constitué des 4 derniers octets de l’empreinte, noté de la même façon.

Génération d’une clef

Bon, alors, comme on vient de le voir précédemment, pour générer une clef avec une empreinte proche, il suffit de travailler sur la clef principale, on pourra ajouter ultérieurement la sous‐clef de chiffrement ainsi que les identités.
Pour une raison obscure, GPG refuse d’importer une clef (publique ou privée) sans identité associée. Par contre, paradoxalement, il accepte d’importer une clef avec une identité non auto‐signée (à condition de lui demander explicitement, toutefois). Donc, en fait je générerai une identité non auto‐signée nommée delete_me qu’il faudra supprimer après avoir rajouté une vraie identité.

Clef RSA

Pour générer une clef RSA, il faut avoir :

• p,q deux nombres premiers (p < q)
• n = p × q
• e, premier avec (p-1)(q-1)
• d, inverse de e modulo (p-1)(q-1)

La clef publique est constituée de :

• n
• e

La clef privée est constituée (au sens d’OpenPGP, car au sens de RSA n,d suffisent, mais connaître les autres est nécessaire à propos de détails d’implémentation importants au niveau de la sécurité, mais que je maîtrise pas).

• la clef publique
• p
• q
• d
• u (inverse de p modulo q)

Digression :

Puisque la clef privée contient la clef publique, pourquoi gpg n’est pas capable de retrouver la clef publique quand il n’a que la clef privée ? C’est un vrai mystère pour moi.

Fin de la digression

Génération à la chaîne

Alors tout d’abord pour générer une clef, calculer des inverses modulaires, et travailler avec des entiers énormes, je me base entièrement sur openssl, qui au travers de son API, me fournit tout ce dont j’ai besoin.

L’approche naïve consiste à :

• générer une clef RSA ;
• écrire la clef publique correspondante ;
• calculer son condensat, s’il est proche de ce que je recherche je garde, sinon je jette.

Cette méthode est non exploitable dans la pratique, car la génération d’une clef RSA est chronophage, et à moins de vouloir tester moins de 100 clefs/seconde (dans le meilleur des cas).

Les étapes suivantes prennent beaucoup de temps :

• géneration d’un couple (p,q) (littéralement, un temps énorme) ;
• calcul d’un inverse modulaire ;
• test de primalité entre deux entiers.

De même que ffp, j’utilise une version plus rapide :

• je génère une clef RSA ;
• j’écris la clef publique correspondante ;
• je calcule son condensat ;
• si le condensat est proche, alors :
  • je vérifie que e est premier avec (p-1)(q-1), sinon je jette,
  • je calcule d (inverse de e modulo (p-1)(q-1)),
  • je sauve le couple clef publique/privée ;
• j’incrémente e de deux ((p-1)(q-1) est pair, aucune chance qu’un nombre pair soit premier avec (p-1)(q-1)) sans verifier que e est premier avec (p-1)(q-1).

Je change la clef RSA de temps en temps (dans mon cas tous les 50 × 10⁶ essais). Le fait de ne pas vérifier que e est premier avec (p-1)(q-1) est un risque à prendre, tant pis si on jette en se faisant une fausse joie. Dans les cas que j’ai essayés, il est très rare que e ne soit pas premier avec (p-1)(q-1).

Avec cette technique, je teste un peu moins de 7×10⁵ clefs/seconde/processeur sur ma machine.

Définition d’empreintes « proches »

Tout d’abord, je considère que des empreintes sont proches si elles ont les mêmes 4 derniers octets. Ça veut dire que les clefs auront les mêmes identifiants. Toutes les clefs satisfaisant ce critère seront sauvées sur le disque. Ensuite, un score est affecté à chaque clef.

Pour constituer mon modèle de score, je me suis basé sur la même idée que ffp, c’est‐à‐dire d’accepter une confusion entre les caractères, et un poids dépendant de la position dans la chaîne. Toutefois, le fait de gagner mon casse-croûte en faisant des modèles statistiques a influencé ma manière de voir. J’ai donc proposé un modèle.

Je cherche à modéliser la probabilité d’accepter une empreinte. Pour cela, je travaille seulement sur les 16 premiers octets, les 4 derniers étant fixés comme il faut.

Mon modèle :

• L’événement « j’accepte cette empreinte » est l’intersection des événements indépendants :
  • j’accepte chaque chiffre i.

Et :

• L’événement j’accepte le chiffre i est l’union des événements suivants :
  • je regarde le chiffre i et je le confonds (à tort ou à raison) avec le bon chiffre ;
  • je ne regarde pas le chiffre i.

Mon score sera donc l’opposé de cette log proba. Je cherche donc à minimiser ce score. C’est une espèce de maximisation de la vraisemblance.

Probabilités de regard

La probabilité que je regarde le chiffre i dépend de sa position dans l’empreinte (plus il est proche du centre de l’empreinte, moins j’ai de chance de le regarder), et de sa position dans le bloc de 4 lettres (les chiffres sur les bords des blocs sont plus observés).

Pour estimer l’effet « bord de bloc », j’ai utilisé les résultats d’un apprentissage, Cf. partie suivante.

Probabilité de confusion

Je n’ai pas été convaincu par le modèle de confusion développé par ffp, de surcroît calculé avec des lettres minuscules. De plus, je n’ai rien trouvé sur le Web. J’ai donc développé le mien. J’ai ainsi fait tourner un script Perl qui me proposait des blocs de 4 lettres affichés, un chouia de temps, et le but était de le recopier. Je me suis basé sur ces valeurs pour construire la proba de confusion.

Un truc drôle, c’est que la bonne empreinte n’a pas une proba de 1 (même si elle est très grande) avec ce modèle…

Écriture des clefs

Tout d’abord, j’écris toutes les clefs, ayant le bon id, le nom de fichier commence par le score (comme ça un classement basé sur le nom de fichier montre la clef la plus satisfaisante, tout en laissant le choix à l’utilisateur d’en choisir une autre), puis mentionne ensuite l’empreinte.

Pour écrire les clefs, je me suis basé sur la RFC, excepté deux points :

• La RFC ne précise pas qu’une identité est obligatoire (sauf si je me suis planté), mais GnuPG refuse d’importer une clef sans identité. J’écris donc une identité nommée delete_me, non auto‐signée, il faut donc forcer GPG pour l’importer.
• La RFC précise que la clef privée est suivie d’une somme de contrôle, mais que les implémentations ne devraient pas l’utiliser. GnuPG ne l’utilise pas, donc j’écris des zéros à la place (je sais, c’est mal de ne pas respecter les RFC, mais j’avais la flemme).

Donc, il faut une fois une clef satisfaisante générée :

• l’importer dans GnuPG (en le forçant à accepter une identité non auto‐signée) ;
• ajouter une identité (et la signer !) ;
• virer l’identité bidon ;
• mettre une date d’expiration (comme la clef n’avait aucune auto‐signature et que l’expiration est définie dans la self‐sig…) ;
• éventuellement, chiffrer la clef privée (qui était en clair) en changeant la phrase de passe ;
• éventuellement, rajouter une sous‐clef de chiffrement.

Tout cela se fait avec gpg et son mode --edit-key.

Code

Comme de bien entendu, vous voulez le code, et vous avez raison.

Voici une archive tar contenant ce qu’il faut pour générer une clef à l’empreinte proche d’une empreinte donnée.

Tout est en C, ça utilise openssl (ldflags -lssl et -lcrypto) et la bibliothèque mathématique (-lm).

Ça se configure dans le fichier conf.h (je ne vais pas me mettre à analyser des arguments, j’ai autre chose à foutre).

Il y a besoin d’un seul argument, c’est le préfixe pour écrire les fichiers (le préfixe peut contenir un « / » pour pouvoir les mettre dans un dossier).

Sur une machine multiprocesseur, il peut être opportun de lancer plusieurs processus.

Démonstration sur ma clef

Ma clef GPG est la suivante :

4096R/7C485DC1: E67A 2102 E00B D185 3BD2  E96B 196A 3B2C 7C48 5DC1

Après environ 5 × 10¹¹ clefs testées, j’ai obtenu 123 clefs avec le même identifiant, voici la clef la plus proche :

4096R/7C485DC1: E97A A54F 9FB2 0D85 F23D  E560 9BD3 F25B 7C48 5DC1

Quelqu’un qui vérifie mal peut se faire avoir. Cool, j’ai atteint mon objectif ! Je suis satisfait. En sous‐produit de ce code (super simple au final), j’en fais un journal sur LinuxFr.

Avertissement

J’ai deux points à aborder :

• Je n’ai aucune connaissance particulière en crypto. Il est donc hors de question de faire usage des clefs par cette méthode dans un cas réel d’utilisation. C’est juste une démonstration de faisabilité. Toutefois, dans le cas d’un attaquant qui veut intercepter des communications ou usurper une identité, la sûreté des méthodes n’est pas son but premier.
• J’ai hésité avant de publier ce journal. Mais, si moi j’ai été capable de le faire, plein d’autres l’ont sûrement déjà fait, ou sont capables de le faire. Il paraît donc sain de rendre public mon travail (faible travail, toutefois).

nimage

Comme promis, une nimage.