Extraction de clef publique : le cas des vouchers de m0n0wall

Magazine
Marque
MISC
Numéro
78
Mois de parution
mars 2015
Spécialité(s)


Résumé

Dans un système utilisant la cryptographie asymétrique, il arrive que la clef publique ne soit pas divulguée ou accessible. Les schémas de signature courants utilisant RSA sont vulnérables à une extraction de la clef publique, ce qui, sur des systèmes possédants une clef de faible taille peut conduire à une factorisation de celle-ci. Cet article présente une attaque de ce type sur le système de vouchers du portail captif de m0n0wall.


Body

1. Extraction de clef publique

Il se peut, pour des raisons allant de la volonté de cacher une faiblesse (clef trop petite) à un simple usage privé ou interne, qu'un système utilisant un mécanisme de cryptographie asymétrique ne publie pas sa clef publique. Or, comme on a pu le voir lors de conférences données par Renaud Lifchitz l'an passé [0] avec des applications pratiques sur PGP et VIGIK, il est possible d'exploiter une faiblesse de certains schémas de signature afin d'extraire le module de la clef publique. C'est une faiblesse connue avec des solutions d'ores et déjà existantes (par exemple RSA-PSS), dont la portée est toute relative, on parle bien de la clef publique ! Cependant, la sécurité de RSA repose à l'heure actuelle sur la difficulté à pouvoir factoriser le module de la clef publique, ce qui, avec le temps devient de plus en plus réalisable et efficace en engageant de gros moyens. Ainsi, des systèmes ne mettant pas à jour leur clef ou étant simplement limités par la capacité de stockage de cette dernière (typiquement les systèmes embarqués) se verront exposés à une attaque d'extraction puis de factorisation de la clef. Pour ne citer qu'un exemple, tiré de la conférence citée précédemment, le système de contrôle d'accès VIGIK largement déployé en France pour permettre aux usagers (ainsi qu'à La Poste, France Telecom et EDF) d'accéder aux immeubles résidentiels, ne permet pas de stocker une clef plus grande que 1024 bits. On peut noter également qu'en accédant à la clef publique, il est possible d'authentifier toute communication utilisant cette dernière : par exemple, pour une série d'e-mails signée par une même source, il sera possible de vérifier que les signatures ont été effectuées par la même clef et cela sans la nécessité d'accéder à un serveur de clef.

1.1 Schéma de signature

Pour rappel, voici les éléments essentiels de RSA (on ne décrira pas les relations élémentaires) :

  • le module RSA N, produit de deux grands nombres premiers p et q ;
  • l'exposant public e ;
  • l'exposant privé d , inverse de e modulo φ(N)) (φ étant l'indicatrice d'Euler) ;
  • la clef privée est le couple (N, d) ;
  • la clef publique est le couple (N,e) .

Une valeur très courante de l'exposant public e est le nombre de Fermat F4 (22n  + 1 avec n=4), soit 65537, qui permet quelques optimisations dans les calculs. C'est notamment cette valeur qui est utilisée par défaut par GnuPG et OpenSSL lors de la génération des clefs. Détail d'importance, car cela signifie que si l'on cherche à extraire la clef publique, alors seul le module sera considéré comme inconnu. Dans un schéma classique de signature utilisant RSA, on a les relations suivantes, étant la signature :

 

100002010000039B000000C90C1ED80B

 

La seconde relation est obtenue en utilisant le théorème d'Euler. Avec h une fonction de hachage et b une fonction de bourrage (padding), servant notamment à se prémunir d'attaques exploitant la propriété de multiplicativité de RSA, et m le message. Pour de plus de détails sur les notions de base relatives aux attaques sur un tel schéma de signature, voir « How (Not) to Design RSA Signature Schemes » [1].

1.2 Extraction du module RSA

Connaissant deux messages en clair m1 et m2 ainsi que leurs signatures respectives s1 et  s2 , générées selon le schéma présenté précédemment, on a par définition :

 

100002010000035B000000C826641A10

 

Avec k1 et k2 deux entiers positifs ou nuls. On peut alors écrire :

 

100002010000073D00000053A2028BC9

 

Le gcd correspond ici au calcul du plus grand commun diviseur. Ce résultat donne un multiple du module RSA  qui, dans la plupart des cas, ne nécessite que quelques divisions afin de tomber sur une taille de module connue (1024, 512, etc.). Aussi, il est bien entendu possible d'effectuer le même calcul en rajoutant des messages et leurs signatures correspondantes, ce qui permettrait de réduire la taille du résultat du gcd.

2. Qu'est-ce qu'un voucher ?

2.1 Définitions 

On retrouve le mécanisme de voucher au sein du portail captif de m0n0wall (mais également pfsense) afin de fournir à un utilisateur invité un moyen de s'authentifier pour une durée finie. L'idée est de fournir une chaîne de caractères de faible longueur qui pourra être aisément recopiée et que l'utilisateur saisira sur la page du portail captif. Une fois la période expirée, ce voucher sera alors inutilisable. L'usage classique qui en est fait dans la réalité est la génération et l'impression de quelques centaines de vouchers qui seront distribués à l'unité par un hôtel ou un bar pour chaque nuit ou café réglés par exemple.

2.2 Format et implémentation

Il y a plusieurs possibilités pour implémenter un tel concept de voucher. Celle qui va être décrite ici correspond à l'implémentation présente sur les systèmes m0n0wall et pfsense, tous deux étant des distributions basées sur FreeBSD et centrées sur un service de pare-feu, la seconde étant un fork du premier. Afin d'effectuer les tests, l'outil en ligne de commandes qui est appelé par le portail captif sera directement utilisé. Vous pourrez retrouver le code utilisé sur le svn de m0n0wall [2]. Les raisons avancées relatives aux choix effectués, du fait de leurs caractères parfois atypiques, ont été discutées avec le développeur principal de m0n0wall. Tout d'abord, voici le format d'un voucher, tel que défini selon la configuration par défaut (présent dans le fichier voucher.cfg) :

% cat voucher.cfg 

16,10,5,1174491274,1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

 

 63                                                 0

 +----//----+------------+-------------+------------+

 |  magic   |  checksum  |  ticketid   |  rollid    |

 +----//----+------+-----+-------------+------------+

Notons tout d'abord un élément déterminant quant à la solidité du voucher, sa taille. Elle sera fixe et de 64 bits, du fait de la taille de la clef utilisée pour chiffrer celui-ci (oui, même une calculette pourrait la factoriser).  Les trois premiers nombres concernent respectivement la taille des champs roll ID, ticket ID et checksum. Le roll ID sert à définir une durée d'accès (configurée sur m0n0wall directement, on ne voit ici qu'un ID) et le ticket ID offre, en quelque sorte, un numéro de ticket valable. Le checksum permet de vérifier l'intégrité du voucher (sa présence semble injustifiée). Le nombre suivant (ici 174491274) est un magic number qui sert à effectuer un bourrage constant (dans le sens où sera toujours utilisé le même magic number). Le dernier élément correspond au charset qui est utilisé par le voucher (on pourrait limiter à abcd par exemple pour faciliter la mémorisation de celui-ci). Ce voucher en clair est ensuite chiffré en utilisant la clef privée d'une paire de clefs RSA afin de fournir notre voucher final. En reprenant les équations d'un schéma classique de signature RSA, en considérant que b est l'ajout du bourrage et m le voucher sans la partie magic number, on a :

 

10000201000002CB00000060269CECF4

 

Ce résultat sera alors converti dans le charset donné. Avant de rentrer dans l'analyse, voici un exemple pour rendre tout cela un peu plus intelligible. Tout d'abord, la génération de la paire de clefs RSA de 64 bits :

% openssl genrsa 64 > key64.private

Generating RSA private key, 64 bit long modulus

..+++++++++++++++++++++++++++

..+++++++++++++++++++++++++++

e is 65537 (0x10001)

% openssl rsa -pubout < key64.private >key64.public

writing RSA key

Ensuite, l'utilisation du programme en ligne de commandes (source[2]) afin de générer nos fameux vouchers :

% ./voucher -c voucher.cfg -p key64.private 1 2

# Voucher Tickets 1..2 for Roll 1

# Nr of Roll Bits     16

# Nr of Ticket Bits   10

# Nr of Checksum Bits 5

# magic initializer   1174491274 (32 Bits used)

# Character Set used  1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

#

" P4qkV2H5snc"

" asQ1CctSuKa"

Les deux derniers arguments de la ligne de commandes permettent de spécifier le roll ID à utiliser ainsi que le nombre de tickets à générer pour celui-ci, le résultat sont les deux vouchers P4qkV2H5snc et asQ1CctSuKa. Enfin, la vérification de la validité de ces deux vouchers (vérification qui ne fait pas partie du processus de génération des vouchers, seulement lorsqu'ils seront saisis sur le portail captif) :

% ./voucher -c voucher.cfg -k key64.public P4qkV2H5snc asQ1CctSuKa

OK 1 1

OK 1 2

Plusieurs remarques : rien n'est stocké hormis le format du voucher et la paire de clefs (c'est au portail captif de faire la différence entre les vouchers en cours de validité et ceux ayant expiré). Lors de la validation, notons que c'est bien la partie checksum et la partie magic number qui sont vérifiées. Concernant la sécurité de ce système, il y a beaucoup d'aspects à remettre en cause : tout d'abord, la complexité générale du fait notamment des contraintes initiales (m0n0wall est un système en quasi lecture seule sans capacité de stockage réelle, pas de comptes temporaires générés préalablement et stockés sur le système donc), mais aussi à cause de la configurabilité de celui-ci (permettant par exemple de changer le format même des vouchers offrant par exemple un nombre disponible de tickets très grand par l'agrandissement du champ ticket ID) ; l'usage d'un bourrage constant (l'auteur indique même en commentaire dans le code que le message est trop petit pour appliquer PKCS1) ; et, de manière générale l'usage de RSA avec des clefs de 64 bits qui est justifié par le développeur de cette implémentation par le fait que la vérification et la génération des vouchers pourraient avoir lieu sur des machines distinctes : d'un côté le service délivrant des vouchers en utilisant la clef privée et de l'autre, le portail captif avec la clef publique permettant la validation de ceux-ci.

3. Extraction de clef publique sur les vouchers

3.1 L'attaque

Le schéma présenté ici utilisant RSA ressemble de près à un schéma de signature : l'ensemble d'un voucher est chiffré, non pas pour protéger son contenu (principalement le roll ID et le ticket ID qui seront de toute façon vérifiés par le portail captif lui-même après avoir été validés par le système de voucher), mais afin de fournir une authentification lors de sa validation, c'est-à-dire qu'il a bien été émis par l'administrateur du portail captif. L'attaque proposée est l'extraction de la clef publique et sa factorisation afin de générer des vouchers valides dans le but d'avoir un accès invité valide. Les hypothèses sont :

  • le magic number est connu ;
  • au moins deux vouchers sont connus ainsi que leurs valeurs en clair ;
  • l'exposant public RSA est connu ;
  • le format du message est connu ;
  • le charset du message est connu.

Il est à noter que l'attaque proposée ici a une portée nulle si elle n'est pas combinée avec une autre attaque qui permettrait de deviner ou extraire efficacement le magic number. Aussi, le contournement d'un portail captif est dans de nombreux cas très simple au niveau réseau (avec tunnel DNS par exemple) : cette attaque a donc un but avant tout didactique. Les trois dernières hypothèses relèvent souvent d'un travail consistant à deviner ces éléments qui, dans une majorité de cas sont triviaux. Ainsi, l'attaque présentée en section 1.2 va permettre l'extraction du module RSA.

3.2 Implémentation

Les sources de la preuve de concept développées ici sont en golang version 1.3 et sont disponibles en ligne [3]. Cette section s'attachera à décrire succinctement comment a été implémentée l'attaque.

En premier lieu, il est nécessaire de générer les vouchers en clair (on utilisera les deux vouchers P4qkV2H5snc et asQ1CctSuKa illustrant l'exemple précédant) via une fonction gen_voucher_plain qui prend en argument le contenu et le format détaillé d'un voucher (voucher_magic étant une constante ayant comme valeur le magic number) :

plain1 := gen_voucher_plain(1, 1, 16, 10, 5, 32, voucher_magic)

plain2 := gen_voucher_plain(2, 1, 16, 10, 5, 32, voucher_magic)

Comme les vouchers chiffrés sont présentés sous une forme convertie dans un charset donné, il faut leur redonner leur format initial via conv_voucher :

cipher1 := conv_voucher('P4qkV2H5snc', charset)

cipher2 := conv_voucher('asQ1CctSuKa', charset)

L'extraction du module RSA peut alors commencer, comme présentée en section 1.2 :

p1 := new(big.Int).SetUint64(plain1)

p2 := new(big.Int).SetUint64(plain2)

c1 := new(big.Int).SetUint64(cipher1)

c2 := new(big.Int).SetUint64(cipher2)

 

// RSA modulus

N := big.NewInt(0)

 

// *modulus extraction*

// exponentiation : (c_i)^e

ce1 := new(big.Int).Exp(c1, e, nil)

ce2 := new(big.Int).Exp(c2, e, nil)

 

// difference : (c_i)^e - p_i

d1 := new(big.Int).Sub(ce1, p1)

d2 := new(big.Int).Sub(ce2, p2)

 

// extraction of the modulus: gcd((c_2)^e - p_2, (c_2)^e - p_2)

N.GCD(nil, nil, d1, d2)

Est alors obtenu un multiple du module RSA. Afin d'extraire celui-ci, une division sera répétée jusqu'à l'obtention d'un nombre d'une taille de 64 bits, fonction k_extraction :

N.Set(k_extraction(N))

3.3 Factorisation

Une fois le module RSA extrait, un algorithme de factorisation peut être utilisé afin de retrouver p et q (les deux nombres premiers à l'origine de celui-ci) permettant ainsi de recalculer la clef privée. Un bon nombre d'algorithmes existent, avec leurs avantages et inconvénients. Les travaux de Daniel J. Bernstein, Nadia Heninger et Tanja Lange présentés lors du 29C3 [4] sous le titre élégant de « FactHacks : RSA factorization in the real world », résument ce dont nous, utilisateurs pressés, avons besoin. L'algorithme utilisé ici sera la crible quadratique dont une implémentation est disponible en golang sur GitHub [5]. Une légère modification a été appliquée à cette dernière afin de pouvoir utiliser directement dans le code le résultat de la factorisation [3]. Une fois le module RSA factorisé, il suffira de calculer l'exposant privé d qui est l'inverse de e (l'exposant public) modulo   (connaissant p et q,   ).

// generation of the private exponent

p_1 := new(big.Int).Sub(primes[1], bigOne)

q_1 := new(big.Int).Sub(primes[0], bigOne)

 

phi := new(big.Int).Mul(p_1, q_1)

d := new(big.Int).ModInverse(e, phi)

3.4 Démonstration

Voici une séquence d'exécution de la preuve de concept, avec verbosité (mettre DEBUG à true) :

% ./poc-voucher -v1 P4qkV2H5snc -v2 asQ1CctSuKa

v1, v2: P4qkV2H5snc, asQ1CctSuKa

N: 11866004645082333679 

N = 3641634287 * 3258428417

d: 6300821847334223873

-----BEGIN RSA PRIVATE KEY-----

MD0CAQACCQCkrIRbHUSB7wIDAQABAghXcQQWQ2CAAQIFANkO7e8CBQDCN6wBAgQu

1OXJAgR+oeQBAgQPxuly

-----END RSA PRIVATE KEY-----

Comme on peut le constater, après avoir extrait le module RSA , le programme s'attaque à la factorisation de celui-ci, pour enfin calculer l'exposant privé en utilisant les deux nombres premiers ainsi trouvés. Il est à noter que l'attaque prend une dizaine de minutes sur un processeur calibré à 2.4Ghz, la partie longue à calculer n'étant pas la factorisation (quelques secondes suffisent avec une crible quadratique pour un module de 64 bits), mais bien le calcul du plus grand commun diviseur (on a effectué une exponentiation non modulaire, les nombres sont donc très grands !). De manière générale, le calcul du   dépend essentiellement de l'exposant public et très peu de la taille de la clef : l'extraction du module RSA sera donc le plus souvent triviale face au temps nécessaire pour la factorisation de celui-ci pour des tailles plus conventionnelles (1024, 2048 bits). Enfin, pour vérifier que l'on a la bonne clef et que tout s'est bien passé, voici les détails de la clef privée utilisée au moment de la génération des vouchers :

% cat key64.private 

-----BEGIN RSA PRIVATE KEY-----

MD0CAQACCQCkrIRbHUSB7wIDAQABAghXcQQWQ2CAAQIFANkO7e8CBQDCN6wBAgQu

1OXJAgR+oeQBAgQPxuly

-----END RSA PRIVATE KEY-----

 

% openssl rsa -inform PEM -text -noout < key64.private 

Private-Key: (64 bit)

modulus: 11866004645082333679 (0xa4ac845b1d4481ef)

publicExponent: 65537 (0x10001)

privateExponent: 6300821847334223873 (0x5771041643608001)

prime1: 3641634287 (0xd90eedef)

prime2: 3258428417 (0xc237ac01)

exponent1: 785704393 (0x2ed4e5c9)

exponent2: 2124538881 (0x7ea1e401)

coefficient: 264694130 (0xfc6e972)

Tous les paramètres sont bons ! Le résultat de la preuve de concept sans les messages de DEBUG donne directement la clef privée dans un format manipulable :

% ./poc-voucher -v1 P4qkV2H5snc -v2 asQ1CctSuKa

-----BEGIN RSA PRIVATE KEY-----

MD0CAQACCQCkrIRbHUSB7wIDAQABAghXcQQWQ2CAAQIFANkO7e8CBQDCN6wBAgQu

1OXJAgR+oeQBAgQPxuly

-----END RSA PRIVATE KEY-----

3.5 Contre-mesures

L'attaque a été l'objet d'un patch chez pfsense [6], qui rend l'extraction du module encore plus difficile en choisissant de manière aléatoire l'exposant public. On notera d'ailleurs que ce dernier est incomplet, car si l'utilisateur décide de regénérer la clef pendant la configuration de pfsense c'est alors l'application openssl qui est lancée pour générer la clef (utilisant par défaut la valeur F4). 

Remerciements

Un grand merci à Renaud Lifchitz pour son retour et ses précieux conseils ainsi qu'à Aurélien pour ses multiples relectures.

Références

[0] http://2014.hackitoergosum.org/slides/day3_A_common_weakness_in_RSA_signatures:extracting_public_keys_from_communications_and_embedded_devices_Renaud_Lifchitz_hes2014.pdf

[1] http://crypto.rd.francetelecom.com/publications/p29

[2] http://svn.m0n0.ch/wall/branches/freebsd8/build/tools/voucher.c

[3] http://dud-t.org/code/poc-voucher.tar.gz

[4] http://facthacks.cr.yp.to/

[5] https://github.com/hydroo/quadratic-sieve

[6] https://redmine.pfsense.org/projects/pfsense/repository/revisions/32837bb4ee1c687e40e0da5abcbce100149f84e1/diff/usr/local/www/services_captiveportal_vouchers.php

 



Article rédigé par

Par le(s) même(s) auteur(s)

Introduction au dossier : Puces sécurisées - À la découverte de la sécurité matérielle

Magazine
Marque
MISC
Numéro
114
Mois de parution
mars 2021
Spécialité(s)
Résumé

Le grand public est familiarisé, ne serait-ce qu’inconsciemment, au concept de puce de sécurité de par l’usage quotidien et depuis de nombreuses années des cartes à puce dans le domaine bancaire ou des cartes SIM dans la téléphonie mobile. Des puces dédiées à la sécurité ont également fait leur apparition dans certains de nos équipements du quotidien (ordinateur portable, smartphone), qu’il s’agisse de microcontrôleur dédié disposant de fonctionnalités liées à la cryptographie (stockage de clef de chiffrement) tel un TPM, ou d’un mode d’exécution sécurisé intégré au processeur principal, à l’instar de SGX pour Intel, de TrustZone chez ARM et de PSP pour AMD.

Édito : Messageries sécurisées - vers la fin d’un règne ?

Magazine
Marque
MISC
HS n°
Numéro
23
Mois de parution
février 2021
Résumé

D’aucuns n’auront loupé l’explosion du nombre d’utilisateurs de l’application de messagerie instantanée Signal, soit au travers de l’actualité, soit car leur infrastructure était tout simplement dans les choux ce 15 janvier 2021, précisément à cause de cette nouvelle charge (on ne connaît pas précisément l’ordre de grandeur). Signal n’a d’ailleurs pas été le seul à connaître ce récent succès, d’autres applications telles que Telegram ont annoncé avoir eu 25 millions de nouveaux utilisateurs en l’espace de 72 heures. Derrière cette migration massive vers des applications de messagerie dites alternatives, une simple, mais non des moindres, annonce d’une future mise à jour des conditions d’utilisation du service WhatsApp, touchant notamment à l’épineuse question des données personnelles.

Entretien avec David Bizeul et Guillaume Arcas, acteurs historiques des CERT francophones

Magazine
Marque
MISC
HS n°
Numéro
23
Mois de parution
février 2021
Spécialité(s)
Résumé

David Bizeul et Guillaume Arcas, tous deux bien connus du monde de la sécurité informatique et notamment de la réponse à incident, vous livrent ici leurs parcours, points de vue et conseils quant aux enjeux de cet incroyable domaine qu’est la sécurité.

Les derniers articles Premiums

Les derniers articles Premium

Quarkus : applications Java pour conteneurs

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Initié par Red Hat, il y a quelques années le projet Quarkus a pris son envol et en est désormais à sa troisième version majeure. Il propose un cadre d’exécution pour une application de Java radicalement différente, où son exécution ultra optimisée en fait un parfait candidat pour le déploiement sur des conteneurs tels que ceux de Docker ou Podman. Quarkus va même encore plus loin, en permettant de transformer l’application Java en un exécutable natif ! Voici une rapide introduction, par la pratique, à cet incroyable framework, qui nous offrira l’opportunité d’illustrer également sa facilité de prise en main.

De la scytale au bit quantique : l’avenir de la cryptographie

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Imaginez un monde où nos données seraient aussi insaisissables que le célèbre chat de Schrödinger : à la fois sécurisées et non sécurisées jusqu'à ce qu'un cryptographe quantique décide d’y jeter un œil. Cet article nous emmène dans les méandres de la cryptographie quantique, où la physique quantique n'est pas seulement une affaire de laboratoires, mais la clé d'un futur numérique très sécurisé. Entre principes quantiques mystérieux, défis techniques, et applications pratiques, nous allons découvrir comment cette technologie s'apprête à encoder nos données dans une dimension où même les meilleurs cryptographes n’y pourraient rien faire.

Les nouvelles menaces liées à l’intelligence artificielle

Magazine
Marque
Contenu Premium
Spécialité(s)
Résumé

Sommes-nous proches de la singularité technologique ? Peu probable. Même si l’intelligence artificielle a fait un bond ces dernières années (elle est étudiée depuis des dizaines d’années), nous sommes loin d’en perdre le contrôle. Et pourtant, une partie de l’utilisation de l’intelligence artificielle échappe aux analystes. Eh oui ! Comme tout système, elle est utilisée par des acteurs malveillants essayant d’en tirer profit pécuniairement. Cet article met en exergue quelques-unes des applications de l’intelligence artificielle par des acteurs malveillants et décrit succinctement comment parer à leurs attaques.

Les listes de lecture

11 article(s) - ajoutée le 01/07/2020
Clé de voûte d'une infrastructure Windows, Active Directory est l'une des cibles les plus appréciées des attaquants. Les articles regroupés dans cette liste vous permettront de découvrir l'état de la menace, les attaques et, bien sûr, les contre-mesures.
8 article(s) - ajoutée le 13/10/2020
Découvrez les méthodologies d'analyse de la sécurité des terminaux mobiles au travers d'exemples concrets sur Android et iOS.
10 article(s) - ajoutée le 13/10/2020
Vous retrouverez ici un ensemble d'articles sur les usages contemporains de la cryptographie (whitebox, courbes elliptiques, embarqué, post-quantique), qu'il s'agisse de rechercher des vulnérabilités ou simplement comprendre les fondamentaux du domaine.
Voir les 66 listes de lecture

Abonnez-vous maintenant

et profitez de tous les contenus en illimité

Je découvre les offres

Déjà abonné ? Connectez-vous