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

Quoi de neuf depuis 6 mois ?

Le dernier article en date sur le sujet date un peu, et le projet s’est entre temps finalisé (du moins dans le cadre des objectifs qu’on s’étaient fixés). C’est donc le bon moment pour voir quelles sont les dernières évolutions.

Retournons au coeur du projet

Si à la dernière partie de cette série d’articles, tout l’aspect de génération de nombres pseudo-aléatoires avait été abordée, le sujet principal du projet quant à lui n’avait été évoqué que brièvement.

La génération de nombres aléatoires n’est en fait qu’une brique essentielle à la génération de clés de chiffrement RSA. Le projet a pour but de générer des clés RSA sur un système embarqué, soit pour les utiliser directement dans un projet embarqué, soit pour se servir de la carte comme un moyen de générer ses clés en minimisant les attaques qui pourraient être conduites pour les voler lors de la génération (par exemple éviter les cache attacks, les timing attacks, etc).

Soyons honnête, le projet constitue plus un proof-of-concept que quelque chose de réellement utile. Cependant, il nous tenait à coeur avec Julien d’aboutir à un résultat assez probant, à savoir avoir une interface minimaliste sur sur l’écran tactile de la carte pour la gestion de la quantité d’aléatoire et la création des clés, et une interface USART pour transmettre les clés nouvellement générées.

Génération des clés RSA

Avec l’implémentation de Miller-Rabin et une source de nombres aléatoires, nous étions prêt pour affronter l’algorithme RSA. Première étape : les nombres premiers.

En effet, la tout première étape de RSA consiste à trouver \(p\) et \(q\), deux nombres premiers de très grande taille. Plus la taille de ces nombres est grande, plus la sécurité est forte, d’un point de vue purement mathématiques, c’est à dire en faisant abstraction des potentielles failles d’implémentations de l’algorithme.

Nombres premiers

Nous avions déjà évoqué Miller-Rabin dans la première partie de cette suite d’articles, cet algorithme permettant de vérifier qu’un nombre est pseudo-premier, c’est à dire qu’on est sûr à X % que le nombre est effectivement premier, avec X variable.

Cependant, bien que cet algorithme soit beaucoup plus rapide que le véritable test de primalité, il demeure néanmoins trop long pour trouver un nombre pseudo-premier en se contentant de le faire vérifier par Miller-Rabin.

L’algorithme que nous avons mis en place pour déterminer un nombre premier est donc le suivant (en pseudo-python pour la simplicité de lecture) :

def generate_prime(size):
    def basic_prime_test(x):
        """
            This function asserts that x is not a multiple of the first prime
            numbers (3 to 79)
        """
        first_primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
                        61, 67, 71, 73, 79]
        for i in first_primes:
            if x % i == 0:
                return False
        return True

    def medium_prime_test(x):
        """
            This function asserts that x respects the fermat pseudoprime theorem
            against small values
        """
        first_primes = [2, 3, 5, 7]
        for i in first_primes:
            if not fermat_pseudoprime(x, i):
                return False
        return True

    x = random_number(size) # Using our CSPRNG

    # Asserting x being odd
    if x % 2 == 0:
        x += 1

    while True:
        if not basic_prime_test(x) or not medium_prime_test(x):
            x += 2
            continue
        # At this point, x a good candidate for the slow Miller-Rabin test
        if not miller_rabin(x, size, iterations=4):
            x += 2
            continue
        # We did some iterations of Miller-Rabin, we must assert a second time
        # with more tests. Since the witness is randomly selected, it cannot hurt
        if not miller_rabin(x, size, iterations=(8 if size / 4 > 8 else size / 4)):
            x += 2
            continue
        break

    return x

Cette fonction prends donc en argument la taille (en bits) du nombre que l’on souhaite obtenir, génère un nombre aléatoire de cette taille, l’incrémente de 1 s’il est pair, et le soumet à une batterie de tests.

Tous ces tests sont de plus en plus lents, et assurent de plus en plus que le nombre est effectivement premier. Si un test échoue, on incrémente notre nombre de 2 (pour toujours avoir un nombre impair), et on recommence.

Le nombre est ainsi testé pour le modulo avec les premiers nombres premiers, donc ceux qui ont la probabilité la plus forte d’être un multiplicateur de x.

En effet, il est facile de se convaincre que 50% (1/2) des nombres sont divisibles par 2, 33% (1/3) divisibles par 3, etc. Ces tests sont rapides, et éliminent beaucoup de candidats facilement.

Ensuite, on utilise le test de pseudoprimalité de Fermat, moins efficace que celui de Miller-Rabin, mais qui possède les mêmes propriétés (voir le premier article). Ainsi, on élimine de nouveau les candidats les plus probables avec un test un peu plus lent que le précédent, mais néanmoins suffisament rapide.

Ensuite, les choses sérieuses commencent. On dispose à cet instant de l’algorithme un nombre qui a de fortes chances d’être premier, du moins un nombre qui mérite notre attention, et qui mérite le temps que vont durer les test de Miller-Rabin.

On en lance un premier, avec 4 témoins, puis un second avec un nombre de témoins dépendant de la taille désirée du nombre. Pour des raisons de performances, on a mis une limite à 8, mais celle-ci peut être augmentée.

Si le nombre passe tous les tests, c’est qu’il est considéré comme pseudo-premier avec une confiance suffisante.

Cet algorithme fonctionne sur un principe de “glissière” : le nombre aléatoire n’est sélectionné qu’une seule fois, et à chaque fois qu’il échoue un test, il est incrémenté. Cette technique pourrait apparaitre comme problématique, puisque plusieurs nombres aléatoires vont donner le même nombre premier en résultat, puisqu’ils vont utiliser la même “glissière”. Cependant, ce n’est pas un problème, puisque l’on ne connait pas la fonction de répartion des nombres aléatoires. Ainsi, toujours dans le cas où l’on génère des nombres de très grandes tailles, puisque l’on ne connait pas la répartition de ces nombres premiers, on ne peut pas y associer leur probabilité d’apparition respective. Cette technique peut néanmoins devenir obsolète, notamment si des avancées conséquentes se font sur l’hypothèse de Riemann

RSA

Avec l’algorithme décrit ci-dessus, on peut donc implémenter RSA.

On génère avec cet algorithme \(p\) et \(q\), deux nombres premiers très grands, dont la taille est la moitié de la taille de la clé souhaitée (en bits).

On calcule \(n = p \times q\) le module de chiffrement, et \(\varphi(n) = (p - 1) \times (q - 1)\) (noté \(pm1\_qm1\) dans notre code).

On choisi ensuite un nombre \(e\), l’exposant, qui doit être premier, et premier avec \(pm1\_qm1\). Beaucoup d’implémentations utilisent 65537, qui est le \(5^{ième}\) nombre de fermat (noté \(F_4\)) et qui possède des propriétés intéressantes, rendant les implémentations moins vulnérables à des attaques par padding par exemple. Cependant, le fait d’utiliser un nombre aussi gros conduit à des temps de calcul plus long, et il s’avèrent que 3, aussi simple qu’il est, fonctionne très bien la plupart du temps. Notre implémentation utilise donc un \(e\) parmi les premiers nombres premiers (< 100), le premier qui rempli les critères de primalité avec \(pm1\_qm1\).

Il est à noté qu’un nombre \(e\) de taille réduite le rend vulnérable à des attaques telle que celle d’Håstad (basée sur le théorème des restes chinois), mais il existe en réalité beaucoup d’attaques exploitant des faiblesses sur les nombres \(p\),\(q\) et \(e\) choisi qui n’ont pas été pris en compte pour ce projet, faut de temps et de puissance de calcul. Citons par exemple l’algorithme de p-1 de Pollard ou l’algorithme p+1 de Williams.

On calcule \(d\), l’exposant de déchiffrement, le modulo inverse de \(e\;mod\ \varphi(n)\)

Le couple \((n, d)\) est la clé privée, et \((n, e)\) la clé publique. La sécurité repose entre autres sur le fait qu’il n’est pas possible de déterminer facilement \(d\) à partir de \(n\) et \(e\) sans connaitre ni \(p\) ni \(q\).

Notre fonction en ADA renvoie alors tous les nombres utiles, pour traitement ultérieur.

Interface graphique et USART

Une fois la fonction pour obtenir un couple de clés RSA achevée, nous avons mis en place une interface graphique minimaliste sur l’écran tactile de la carte.

Cette interface indique la quantité d’entropie dans la pool, et via des boutons de configuration, permet de choisir la taille de la clé que l’on souhaite générer, et de la générer.

La clé générée est envoyée par USART sur le PC sur lequel la carte est connectée, au format ASN.1.

Enfin, plutôt au format de configuration pour ASN.1. En effet, le format ASN.1 est particulièrement complexe, et difficile à mettre en oeuvre. Nous avons plutôt opté pour le format de configuration, format textuel, qui donné à un programme adapté comme openssl, peut être transformé en véritable ASN.1 (et donc en PEM, ou DER).

Voilà un exemple de clé telle que renvoyée par la carte :

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:37477350045613351057385588413797341577818008774786266332685817476996829238649795191048242559827572814382384476961157054475196464330381984106266957099057849
pubExp=INTEGER:3
privExp=INTEGER:24984900030408900704923725609198227718545339183190844221790544984664552825766271948720770608795840345052921525277482746393685348052725607521859645987484043
p=INTEGER:189538920998910343421661850948063780678255779528125127227650900184477066206253
q=INTEGER:197729046087736290390634952054125264254679105140317124065921923293011051625533
e1=INTEGER:126359280665940228947774567298709187118837186352083418151767266789651377470835
e2=INTEGER:131819364058490860260423301369416842836452736760211416043947948862007367750355
coeff=INTEGER:119387985172943203969466914625888991715770146158161796912531923651123504483796

Cette clé, de 512 bits, est dans un format reconnaissable par openssl par exemple, qui permet d’obtenir simplement la clé au format PEM, utilisable partout, en 1 commande.

On retrouve les nombres mentionnés dans la section ci-dessus, avec des noms légèrement différents pour certains.

Cette clé a été générée par notre carte, et est une clé RSA valide de 512 bits . Je vous conseille très fortement d’utiliser cette clé, elle ne comporte aucun risque.

…

(bon ok, la sécurité n’est certes pas optimale, mais au moins c’est une clé valide)

Par ailleurs, tout au long de la génération d’une clé, l’affichage est mis à jour pour tenir compte de l’avancé de l’algorithme, notamment sur l’étape la plus longue, la recherche de deux nombres premiers de grande taille.

La carte STM32 et son interface graphique pour la génération des clés. Size ouvre un nouveau menu pour choisir la taille de la clé, RSA la génère et print l’affiche sur l’USART

Tentative d’interfaçage avec un compteur Geiger

L’étape ultime de ce projet, et celle qui nous avait beaucoup motivé tout au long de la réalisation des étapes préliminaires, était l’utilisation d’un compteur Geiger comme source de véritable aléatoire. L’algo pour générer les clés RSA n’est pas parfait et comporte de nombreuses failles d’implémentation ? Qu’à cela ne tienne, nous aurions des nombres nucléaires.

Malheureusement, le compteur s’est perdu à Albany et Watterbury (merci USPS), et n’est arrivé que très tard, c’est à dire la veille de la deadline.

Nous avons donc tenté en vitesse de l’interfacer avec notre carte et de réussir à communiquer avec lui, malheureusement sans succès.

Tant pis, on trouvera une autre utilisation pour ce jouet.

Et on en parlera ici …

Concours Make it with ADA

Nous avons néanmoins soumis notre projet au concours Make it with ADA, et après quelques mois de délibération, nous avons gagné la seconde place du concours avec notre projet si étrange !

Les sources du projet

Le projet est consultable sur github.