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

Posté par . Licence CC by-sa
66
16
juil.
2012

Sommaire

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.

  • # Petite erreur de sens

    Posté par . Évalué à 7. Dernière modification le 16/07/12 à 21:11.

    La probabilité que je regarde le chiffre i dépend de sa position dans le fingerprint (plus il est proche du centre du fingerprint, plus 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).

    Il fallait bien sûr lire moins. Si un modérateur aurait l'amabilité de corriger cela.

    Il y a aussi des puces qui ont sautés… (mais c'est probablement de ma faute).

    Il y a, et la ce n'est pas de ma faute, une mise en forme de titre qui s'est droguée dans la table des matières.

    • [^] # Re: Petite erreur de sens

      Posté par (page perso) . Évalué à 3.

      J'ai corrigé les puces et le moins. Pour les titres drogués, c'est un bug https://linuxfr.org/suivi/mise-en-forme-des-titres-ne-passe-pas-au-sommaire . Merci pour le journal.

      « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

    • [^] # Re: Petite erreur de sens

      Posté par (page perso) . Évalué à 8.

      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 fasse s'en prémunir

      Verbe faire ou falloir ? En plus la conjugaison va bien avec la sécurité ;).

      ce commentaire est sous licence cc by 4 et précédentes

      • [^] # Re: Petite erreur de sens

        Posté par . Évalué à 2. Dernière modification le 17/07/12 à 06:49.

        Je voulais dire falloir, donc qu'il faille s'en prémunir.

        Et pourtant je l'ai passé à Antidote, relu, et j'en ai corrigé des fautes…

        Mea culpa

        • [^] # Re: Petite erreur de sens

          Posté par (page perso) . Évalué à 3.

          Et comme pour le commun d'entre nous, il en reste encore des palanqués (NB: moi, ce sont surtout certaines négations tronquées qui m'arrachent les yeux : «  il n'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 », on pourra aussi se condouloir sur la savoureuse parade conclusive). Dès que la phonétique est bonne en revanche, je n'ai plus rien à redire.

          Le problème avec l'orthographe, c'est une certaine similarité avec le poste de président de la république. Il est indispensable d'y songer toujours. Les vérifications a posteriori sont vaines pour le commun des non littéraires, un peu comme d'écoper un océan à la petite cuillère.

        • [^] # Re: Petite erreur de sens

          Posté par (page perso) . Évalué à 3.

          Et pourtant je l'ai passé à Antidote

          Je crois que là tu atteins les limites d'Antidote ! La conjugaison était juste mais c'est le sens qui ne l'était pas. :D Je serai très impressionné qu'un logiciel puisse relever ce genre de coquille, c'est peut-être faisable avec des études d'erreur courante ou bien de formulation courante. Je crois que le traducteur de google compare ses traductions générées avec une base de traductions pour proposer les plus pertinentes… C'est peut-être faisable pour débusquer ce genre de petite faute, en sachant qu'un peu de créativité (gramaticalement valide et sémantiquement légitime) ferait hurler l' « évaluateur de conformisme ».

          ce commentaire est sous licence cc by 4 et précédentes

  • # résultat insuffisant ?

    Posté par . Évalué à 5.

    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

    C'est intéressant mais le résultat n'est pas très bon AMHA. Je ne crois pas que, même d'un oeil distrait, on puisse confondre les deux empreintes ci-dessus. Il faudrait vraiment qu'il n'y ait que deux ou trois chiffres qui changent.

    • [^] # Re: résultat insuffisant ?

      Posté par . Évalué à 7.

      Non mais c'est pas noël non plus. Si on est capable de trouver une quasi collision à deux ou trois chiffre près, on aurait du soucis à se faire pour SHA1 (même si on se fait déjà du soucis pour lui).

      Je maintiens que c'est suffisant pour duper un utilisateur distrait (qui vérifie le début et la fin, alors que la fin c'est l'id). En tout cas ça suffit je pense pour éduquer les utilisateurs.

      Après si tu veux plus précis, il suffit de laisser tourner plus longtemps (beaucoup, mais vraiment beaucoup plus longtemps).

      La façon dont est construite les fingerprints n'est pas anodine non plus, et c'est fait pour que les collisions soit pas si simple à trouver.

      Pour les clef OpenPGP version 3, l'id c'était les derniers bits du n du RSA, ce qui permettait de traiter le probleme en deux temps, trouver d'abort un n tel que les clefs aient le même identifiants, puis jouer avec e pour avoir un fpr qui ressemble à ce que l'on veut. Dans la version 4, le fait de déduire l'id à partir du fpr complique singulièrement la tâche, maix c'est fait pour ;-).

      • [^] # Re: résultat insuffisant ?

        Posté par . Évalué à 1.

        Je maintiens que c'est suffisant pour duper un utilisateur distrait (qui vérifie le début et la fin, alors que la fin c'est l'id)

        Ben, le début pour moi, c'est 8 ou 12 chiffres, et là c'est raté.
        Un utilisateur qui ne vérifierait que 4 chiffres n'a peut-être pas grand intérêt à faire de la crypto…

        • [^] # Re: résultat insuffisant ?

          Posté par . Évalué à 3.

          Enfin pour moi un utilisateur abaissant son systeme de sécurité pour une raison faible n'a pas interêt à faire de la crypto. Je rappelle que le but premier c'est de former les utilisateurs.

        • [^] # Re: résultat insuffisant ?

          Posté par . Évalué à 1.

          Oui, enfin, déjà rien qu'avec la key id, son résultat est satisfaisant et peut amener a des doutes … (vu que ce sont les 8 derniers caractères)

      • [^] # Re: résultat insuffisant ?

        Posté par (page perso) . Évalué à 3.

        Je maintiens que c'est suffisant pour duper un utilisateur distrait (qui vérifie le début et la fin, alors que la fin c'est l'id). En tout cas ça suffit je pense pour éduquer les utilisateurs.

        4096R/7C485DC1: E6…C1
        4096R/7C485DC1: E9…C1

        Mouais, faut vraiment lire que le première caractère ou bien être très distrait :-) Maintenant s'il n'y a que la fin qui est affichée, ça peut très bien fonctionner.

        • [^] # Re: résultat insuffisant ?

          Posté par . Évalué à 5.

          Il faut voir que le 6 et le 9 peuvent se confondre.

          Il faut imaginer une situation rééle, ici j'ai noté les deux fpr les uns au dessus des autres.

          Dans un cas réel d'utilisation, l'utilisateur aurait mon vrai fpr noté en minuscule au bas d'une carte de visite échangée lors d'une rencontre réele, et l'autre fingerprint sur son écran ayant téléchargé la clef falsifiée. En faisant des aller retours entre la carte et l'écran.

          Je n'ai pas de mémoire visuelle et pour vérifier une clef je la verbalise par morceau sur la carte pour l'avoir en tête, mais suivant les techniques il peut y avoir des faiblesses…

          • [^] # Re: résultat insuffisant ?

            Posté par . Évalué à 3.

            Il y a quand même un autre problème avec ton approche, c'est que l'attaque est risquée donc improbable. Je m'explique : si tu essaies de casser une clé ou un mot de passe, l'échec est silencieux (personne ne sait que tu as essayé de la casser). Mais si tu essaies d'usurper l'identité de quelqu'un, par définition l'échec est visible : tu fournis une information cruciale à la personne que tu attaques (et tu risques aussi de te faire choper si tu ne prends pas quelques préoccupations).

            Donc c'est vraiment le genre d'attaque qu'AMHA, on n'entreprend que quand les probabilités de réussite sont proches de 100%.

      • [^] # Re: résultat insuffisant ?

        Posté par . Évalué à 2.

        En fait tu peux évaluer les performances de ton approche en mettant au point un protocole d’expérimentation. Par exemple en montrant deux paires de signatures par essais, successivement ou en parallèle, puis en demandant si les paires étaient différentes ou similaires. Tu peux faire ça en variant tout un tas de paramètres, et en ayant plusieurs cas (deux paires identiques, différentes et aléatoires, ou différentes avec ton algo). Ça s’appelle faire de la psychophysique.

  • # Identification visuelle

    Posté par . Évalué à 5.

    As-tu regardé ce que ça donne avec le système d'identification visuelle de SSH ?
    Est-ce que ça ressemble, subjectivement, ou pas du tout ?

    (pour avoir une idée : http://www.screenage.de/blog/2008/10/15/having-fun-with-openssh-on-ubuntu-intrepid-ibex-visual-host-keys/ )

    • [^] # Re: Identification visuelle

      Posté par . Évalué à 4.

      Je me suis jamais posé la question, et je n'utilise pas… Je dois être un vieux aigri, j'ai un bout de papier dans mon portefeuille avec l'empreinte des clef publiques des serveurs ssh que j'utilise. De toute façon, je n'ai rigoureusement aucun mémoire visuelle, à un point cela en est handicapant («C'est qui ? Il a l'air de me connaître.», «Je sais pas mais tu as discuté une bonne heure avec lui ce matin», «Tu es sûr ?», «Oui»).

      Toutefois j'avoue que ça a l'air drôle de creuser ça, j'ai trouvé un truc marrant à faire.

  • # Décalages.

    Posté par (page perso) . Évalué à 9. Dernière modification le 17/07/12 à 14:19.

    Tu aurais pu aussi essayer de modéliser les décalages et inversion de lettres.
    Distance_de_Levenshtein

    (Il y a aussi la distance de Levenshtein pondérée, qui favorise les lettres similaires)

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.