Cryptographie maison sur carte embarquée en ADA / C - Partie 1

Un projet d’études

Présentation de la problématique

Dans le cadre des études, on m’a imposé un projet à faire en ADA sur carte embarquée. Les contraintes n’étaient pas beaucoup plus précises que ça, et du coup je pouvais choisir un peu le sujet que je voulais, qui m’intéressait.

Étant un fan de cryptographie, je trouve ce domaine passionnant, j’ai eu la (mauvaise) idée de me dire qu’un projet où je coderais une lib de crypto en ADA sur la carte embarquée semblait être une bonne idée :

• Sujet qui m’intéresse (la crypto)
• Pas trop avoir affaire avec des drivers relous, lire des specs et tout
• Pas vraiment (voire pas du tout) de projet similaire en ADA
• Suffisament complexe pour taper une bonne note si ça fonctionne
• Permet de voir des internals de la crypto, et pas uniquement la manière de s’en servir

Le projet est réalisable à plusieurs, et donc on s’est mis à 2 pour le faire, principalement en peer-programming (on connait ni l’ADA, ni la carte embarquée. Et la crypto, pas franchement plus).

Actuellement (fin décembre 2019), le projet est toujours en cours, mais suffisament avancé pour faire un billet de blog et raconter 2-3 trucs potentiellement intéressants, car, comme prévu, ça n’a pas été facile.

Scope du projet

L’idée “crypto sur carte embarquée” est assez vague, mais fort heureusement on n’avait pas besoin de donner un sujet plus précis. L’idée était donc de commencer par faire un truc “facile”, c’est à dire être capable de générer des clés RSA (et juste les générer), en re-implémentant toutes les primitives nécessaires pour cette tâche.

En regardant rapidement, et sans surprise, la première étape était d’avoir un mécanisme pour gérer des nombres de (très) grande taille, pour avoir des clés de taille suffisante (impossible de générer une clé RSA 4096bits si on a pas un moyen de faire des calculs avec des nombres possédant plusieurs dizaines de chiffres).

Une fois cette étape passée, il était nécessaire pour nous d’avoir un moyen de tester la primalité des nombres qu’on allait manipuler, les nombres premiers étant un peu la clé de voute de la sécurité de RSA.

Pour la suite … ben on allait voir plus tard, hein ?

Des BigNums maison

BigNums et ADA

La première étape donc était d’avoir des bignum, aka une structure de données capable de représenter un nombre arbitrairement grand, et avec les opérations nécéssaires :

• addition/soustraction
• multiplication/division
• modulo
• puissance
• décalage de bits et opérations bitwise

On a donc regardé du côté des bibliothèques pré-existantes en ADA, mais rien de probant. La solution qu’on nous a conseillé, c’était d’utiliser la bibliothèque des BigNums de la GNU, la GMP. Après quelques tatônnements (pas mal en réalité, encore une fois on ne sait pas faire d’ADA et encore moins linker du C à de l’ADA), on nous a conseillé plutôt de nous orienter vers une bibliothèque plus minimaliste, en C, sans aucune dépendance (pas même d’allocateur de mémoire), tiny-bignum.

Après avoir réussi à linker notre projet avec la lib, et réussi à faire la passerelle en ADA, nous étions capables d’avoir des bignums en ADA.

Miller-Rabin

Pour déterminer la primalité d’un nombre avec des dizaines de chiffres, le test classique qui consiste à tester pour un nombre n tous les nombres impairs de 3 à sqrt(n) est clairement inutilisable tant il est lent. Même avec les optimisations, sur un ordinateur “puissant” comme peut être mon laptop, on perd beaucoup trop de temps, le faire sur une carte embarquée n’est même pas envisageable.

Ce problème est évidemment bien connu, et en pratique on s’oriente plutôt vers des tests de pseudo-primalité, comme celui de Miller-Rabin. Le test de pseudo-primalité de Miller-Rabin a ces propriétés :

• Il garantit qu’un nombre marqué comme non-premier est forcément non-premier
• Il est beaucoup plus rapide qu’un test de primalité
• Il garantie avec une probabilité supérieure à un nombre (configurable) qu’un nombre marqué comme premier l’est.

Cette dernière propriété est très intéressante, car cela signifie que selon le nombre de tests que l’on veut effectuer, on va augmenter nos chances que le nombre soit effectivement premier, jusqu’à un certain point qui est un bon compromis entre temps d’execution et pourcentage de garantie. Évidemment, plus on veut augmenter cette garantie, plus l’algorithme met du temps à s’executer.

Miller-Rabin fonctionne sur un concept de “témoin de Miller-Rabin”, qui sont des nombres à tester vis-à-vis du nombre dont on veut déterminer la pseudo-primalité. Plus on test de témoins (en respectant certaines règles évidemment), plus nos chances que le nombre soit effectivement premier augmentent.

Quelque chose d’intéressant sur les témoins de Miller-Rabin est le fait qu’il a été déterminé pour tous les nombres inférieurs à un nombre donné, qu’une selection de témoins suffisent à donner une réponse sûre à 100%. Par exemple, pour tester la pseudo-primalité d’un nombre inférieur ou égal à 25 326 001, il est suffisant et necéssaire de tester qu’avec 2, 3 et 5 comme témoins pour avoir une réponse fiable à 100%.

Cette liste de témoins sûrs existe (du moins sur wikipédia) jusqu’au nombre 3 317 044 064 679 887 385 961 981, avec 13 témoins à vérifier.

Au dela, la probabilité est donnée selon la formule présentée ici.

Implémentation de Miller-Rabin

L’implémentation de Miller-Rabin, bien que l’algorithme soit assez simple, a été assez longue pour plusieurs raisons :

• On sait toujours pas faire d’ADA
• Il y a bien évidemment eu des bugs à corriger, ce qui n’est pas trivial quand le code s’execute sur la carte embarquée (en pratique on a un peu galéré à avoir GDB fonctionnel, et encore plus à avoir un moyen d’afficher des choses sur l’écran de la carte pour le traditionnel debug au print, parfois plus efficace)
• La lib est pas si évidente à prendre en main dans son utilisation à travers de l’ADA

Les ennuis commencent

Les broutilles auxquelles ont a du faire face n’étaient en réalité que des petits problèmes facilement surmontables. Un truc plus ennuyeux cependant s’est manifesté : la lenteur. Pour calculer la primalité d’un nombre petit (genre qui tient encore dans un uint64_t), la carte mettait plusieurs secondes. En cause : la bibliothèque des tiny-bignum qui faisait des opérations pas forcément optimisées.

Mais le vrai problème s’est manifesté peu après, quand on a commencé à vouloir coder la fonction pour RSA, qui à un moment implique de devoir potentiellement représenter un bignum négatif. Ce qui est impossible pour la bibliothèque que l’on a choisie. Argh.

Pas le choix, on a mis les mains dans le camboui, et on a tenté d’adapter la lib. Bon au final on s’est retrouve à tout recoder et optimiser. Vu que c’était en C, l’opération s’est retrouvée ne pas être si longue finalement.

Résultats

Après donc plusieurs jours de taf, on avait enfin un moyen de vérifier qu’un nombre était pseudo-premier (et avec notre nouvelle implémentations des bignum, l’opération est déjà sensiblement plus rapide), notre bibliothèque des BigNums est prête pour toutes les opérations dont on aura besoin, et on a un début de RSA qui marchote.

Et là, nouveau côté rigolo, on découvre que littéralement la première étape de notre implem de RSA ne peut pas fonctionner. Pourquoi ? Car il faut choisir 2 nombres aléatoires p et q, et qu’on a pas d’aléatoire sur la carte.

Ah.

Bah va falloir gérer ça alors :)

La suite dans la partie 2