~gapz


blog - archives - feed



Des histoires de key-IDs OpenPGP

Phrack 69, paru le 6 mai 2016 (avant hier, au moment de l’écriture de ces quelques lignes), traite dans son fameux Linenoise, de la génération de clefs RSA pour OpenPGP avec un key-IDs arbitrairement choisis par l’utilisateur. Pour ceux ne connaissant rien à GPG/PGP, le key-ID d’une clef dans la version 4 du format OpenPGP correspond aux 32 derniers bits de l’empreinte (celle-ci correspondant au hash SHA1 de la clef publique prise avec son timestamp). (Dans la version 3, il s’agissait directement des 32 derniers bits de la clef publique au format OpenPGP, c’est-à-dire entre autres avec l’user-ID et la date de création.) Par exemple :

$ gpg --fingerprint gapz | grep finger
      Key fingerprint = 02B5 3886 C14B 1F76 4977  78A5 A287 F11E 5FBC 0895

Ici, le short key-ID est alors :

5FBC0895

En 2014, j’avais écris quelques lignes en Go pour générer de manière non-optimisée une clef RSA au format OpenGPG avec un key-ID arbitraire. Voici un exemple (les tests furent faits sur 16 coeurs, dont j’ai oublié la fréquence, et j’avais choisi le key-ID DADADADA) :

$ go build dbfid.go
$ ./dbfid 
Found a key: DADADADA (in 1198.089134 sec and 2123600097 tries)
-----BEGIN PGP PUBLIC KEY BLOCK-----

xsBNBFEZ2scBCADWYL1TUZBhnH2cYeWs4uack7pVarmi1SDgG1NmuDgbklpoOi6n
vo0qv2F30N/eCeWiSYEvWLN4oQJefB8KXwCxCynrVqnz2kuLCyP07RzuiPXKBVA1
EpeISkLfmUziQpIsqQpIbA03qYkGfhJhKc1wy4/63DJyOLRq248bMwrxe9phFiKc
HUxVdcDB/UwBTP3Wa1b453FtHDkUJz7UKYDmKY6ICcdAWpmaRCuSv8hwdB9KjOnl
4fh3MWuX+OsN5dCqX7EUgebtrO8+Alolt3S3+5OC3MTY9DTqojabARC+llQXFFbX
G1yJXsBecMjMOM5DqzC7e8sLpovuWrKBD2ChABEBAAHNG3Rlc3QgKHRlc3QpIDx0
ZXN0QHRlc3QuY29tPsLAYgQTAQgAFgUCURnaxwkQPKR4rtra2toCGwMCGQEAAKWJ
CAAaYoZ7IBhmdn6/86LjP+O+2pZHz3lkahhCD3KO0smi/ZqvjdBXHm7No4IpMVP8
5QWj+YBps/2Dptq4R+S3nwdEIej+/rAXLYh7a6WOhhaVbyNTFgFjZeVUc5JixgoQ
9H2xp0N770gfbFxgR8i6mbdcedB1XZm7r0DnsDGLsS5Q0jwJF1RGe/qA4o3Q4OQm
bLtoKN0f/9TYt/6GA6TYGCYhUwKhhaklb+ovQR1tdFq6ezYaxXmhUibhs4Uyf/o+
KVMotrglVYUNZlwU4R8TPOQOW+PoxRFH4bp+W73xqgus7vd3yPIlvYOg22Vss7MH
GFplrgDR1Yn5xO2Hh8usRWi7
=yrXr
-----END PGP PUBLIC KEY BLOCK-----

$ gpg --dry-run --import out.pub 
gpg: key DADADADA: public key "[User ID not found]" imported
gpg: Total number processed: 1
gpg:               imported: 1  (RSA: 1)

Je m’étais même amusé à générer 42 clefs ayant pour short key-ID 0x00000042.

$ gpg --dry-run --import 0x00000042.pub 
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: key 00000042: public key "[User ID not found]" imported
 gpg: Total number processed: 42
 gpg:               imported: 42  (RSA: 42)

À l’époque, il n’y avait qu’un seul script (en Perl) pour générer de telles clefs : trollwot/bruteforce_keyid. J’avais alors décidé d’écrire à mon tour un programme pour faire la même chose, en me basant sur l’idée de ce script, à savoir : on choisit un timestamp initial, puis on l’incrémente d’une seconde en regénérant à chaque fois la clef RSA, jusqu’à ce que le short key-ID soit celui que l’on voulait obtenir (rappelez-vous : le short key-ID correspond aux 32 derniers bits du hash SHA1 de la clef et son timestamp). J’avais eu un peu de mal à écrire mon programme en Go, car l’API OpenPGP de Golang n’a pas été pensée pour faire n’importe quoi à bas niveau sur les paquets OpenPGP (par exemple changer l’empreinte SHA1), mais également parce que cette API avait un bug (x/crypto/openpgp: NewEntity won’t Serialize #6483).

Je m’étais alors fixé pour objectif d’optimiser un jour la procédure (en m’attaquant peut-être au calcul du SHA1 de la clef publique OpenPGP) afin de forger non plus une ou quelques clefs, mais un web of trust dans son entiereté. (L’auteur du script Perl trollwot/bruteforce_keyid l’avait suggéré lors de la conférence OHM 2013.) Seulement voilà, lors de la DEFCON 22, deux chercheurs parviennent à cet objectif en effectuant les calculs sur des GPUs et reforgent complètement le web of trust actuel de PGP (les short key-IDs sont coïncident et pourtant les clefs publiques sont toutes différentes) : http://pgp.evil32.com/. La présentation qu’ils ont faite et le site du projet montrent l’état bien avancé de décrépitude des short key-IDs :

Optimiser mon code avait alors perdu en intérêt, d’autant plus que les short key-IDs étaient déjà presque totalement obsolètes (il reste quelques vieux outils désuets n’utilisant que ça pour identifier des clefs). J’attends dès lors l’inévitable attaque contre SHA1 qui finira bien par arriver, et qui aura alors des conséquences désastreuses pour le format OpenPGP dans sa version actuelle (ce dernier étant rigide sur le choix de SHA1 pour le fingerprint, il n’est pas possible de choisir une autre fonction de hachage).

Concernant l’article de Phrack 69, il avait en fait été soumis en avril 2013 (depuis le numéro 63, les nouveaux articles sont en surnombre), ce qui suffit à expliquer pourquoi il semble un peu en retard dans son contenu. Quoiqu’il en soit, sa publication m’a amené à rédiger enfin ces quelques lignes pour satisfaire définitivement ma velléité de publier quoi que ce soit d’approfondi sur le sujet.