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

L’aléatoire cryptographique

Pour des besoins de cryptographie, il est fréquent d’avoir besoin d’aléatoire et de valeures aléatoires, parfois de grande taille. Sur un ordinateur qui est par nature déterministe, cette tâche peut se révéler être complexe, surtout si l’on cherche à avoir un aléatoire qui soit de suffisamment bonne qualité pour ne pas être prédictible (ne serait-ce que partiellement) par un potentiel attaquant.

En l’occurrence, la fonction pour obtenir de l’aléatoire en ADA sur la carte embarquée repose sur un PRNG.

PRNG

Un PRNG, ou PseudoRandom Number Generator, est une construction mathématique qui permet de générer une séquence de nombres qui s’apparente à du hasard.

C’est souvent un algorithme assez simpliciste, une suite mathématique. À chaque fois qu’un nombre “aléatoire” est demandé, on applique une itération de la suite et on renvoit la valeur obtenue.

Exemple de PRNG fait main

Prenons un exemple fait-maison :

#include <stdio.h>
#include <stdint.h>

int main(void)
{
    uint32_t n = 4242; // On initialise notre PRNG avec 4242
    for (int i = 0; i < 20; ++i)
    {
        n ^= (n << 3) | (n >> 5);
        printf("%u\n", n);
    }
    return 0;
}

Ici on va demander 20 nombres “aléatoires” à notre PRNG, en commençant avec la valeur 4242 (qui s’appelle la seed). On obtient le résultat suivant :

$ gcc a.c && ./a.out
37894
274614
2462979
17316283
155317350
1125014485
1500816683
2459633746
105370240
880372756
2542962676
724449355
1918356369
3790157133
4003913383
2580621658
1461641856
3990951316
2190391608
2533049585

C’est un bon début. Chaque itération de cet algorithme maison nous donne une nouvelle valeur, et à vue de nez il ne semble pas y avoir de répétition. On peut cependant constater que les nombres sont tous à peu près de la même taille, on ne va donc pas avoir une bonne répartition des nombres tirés sur l’ensemble des possibilités.

Essayons de déterminer au bout de combien de temps ce PRNG va boucler, et nous ressortir la même séquence :

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    uint32_t n = 4242;
    for (int i = 0; i < atoi(argv[1]); ++i)
    {
        n ^= (n << 3) | (n >> 5);
    }

    uint32_t witness = n;
    printf("Témoin : %u\n", witness);
    int iter = 0;
    while (1)
    {
        n ^= (n << 3) | (n >> 5);
        iter++;
        if (n == witness)
            break;
    }

    printf("Cycle détecté : %d\n", iter);
    return 0;
}

Le concept de ce petit bout de code crado est de faire tourner le PRNG un certain nombre de fois avant de chercher un cycle. En effet, avec un PRNG sorti de mon chapeau comme celui là, il est fort à parier que ce PRNG va boucler sur un cycle réduit au bout d’un moment, mais qu’il est potentiellement long à atteindre.

Ainsi, si je commence avec la valeur 4242, je ne vais pas nécessairement retomber sur la valeur 4242. Cependant, si je fais tourner l’algorithme un certain nombre de fois, il est possible que je l’ai fait tourner suffisamment longtemps pour tomber dans la boucle. Si c’est le cas, mon algorithme va m’indiquer combien de nombres sont présents dans la boucle.

Essayons :

$ ./a.out 1000
Témoin : 3674165384
^C #Interrompu. 1000 tours préalables ne sont pas suffisant pour tomber dans le cycle
$ ./a.out 10000
Témoin : 2432314554
^C
$ ./a.out 100000
Témoin : 3532233727
Cycle détecté : 16
# Tentons de trouver une valeur plus proche en fixant witness = 3532233727
$ ./a.out 0
Témoin : 3532233727
Cycle détecté : 42720

On déduit donc que ce PRNG sorti du chapeau n’est pas très performant, car bien qu’il soit capable de donner 42720 valeurs différentes sur ses 42720 premières itérations (en partant de 4242, toujours !), une fois ce nombre d’itérations atteint (toujours pour 4242), le PRNG devient inutile.

Un vrai PRNG

Il parait évident que ce PRNG pourrait être amélioré. Si l’on est capable de trouver un algorithme qui produit tous les nombres exprimables sur 32 bits, et dans le désordre, on aurait un PRNG qui s’approcherait de quelque chose de raisonnable par exemple (plus ou moins, hein, restons souples).

En pratique, des gens bien plus compétents que moi se sont penchés sur la question, et ce depuis plusieurs dizaines d’années, et ces gens ont été capables de trouver des algorithmes bien plus efficaces.

Par exemple, le Mersenne Twister est capable de générer des nombres “aléatoires” sur une période de 2^19937 - 1, ce qui est pas dégeu il faut l’avouer.

Mais pourquoi ?

Ce concept de PRNG est bien rigolo, mais en quoi est-il applicable à notre problème ? Même si les nombres d’un PRNG peuvent sembler aléatoire, il suffit de savoir l’algorithme utilisé et le dernier nombre sorti pour pouvoir calculer manuellement la suite et donc les nombres “aléatoires” qui vont être produits par le PRNG.

De plus, comment déterminer la seed, la valeur de départ ? Idéalement, il faudrait le faire de manière aléatoire, du coup on utilise un autre PRNG pour ça ?

Bien entendu un PRNG seul ne constitue pas un élément suffisant pour générer de l’aléatoire. C’est pourtant le mécanisme derrière la fonction pour obtenir de l’aléatoire que nous avions à disposition en ADA, et aussi la fonction rand() en C !

Pour obtenir de l’aléatoire de piètre qualité (comprendre suffisant pour beaucoup d’utilisations, sauf la cryptographie), il n’est pas nécessaire de chercher plus loin : on prend ce PRNG, et on le seed avec l’heure actuelle. Ainsi, d’une exécution à une autre les valeurs seront différentes, et c’est good. Je pense par exemple à l’aléatoire pour le machine learning, des IA de jeux vidéos, etc.

Plus loin que le PRNG : le CSPRNG

Si on veut un truc un peu plus robuste (et potentiellement utilisable pour de la cryptographie), il faut regarder du côté des Cryptographically Secure PseudoRandom Number Generator.

Le concept du CSPRNG est assez similaire à celui du PRNG : une suite mathématique qu’on fait itérer pour générer des nombres. Cependant, il doit respecter 2 contraintes supplémentaires :

• Il doit respecter le Next-bit test, c’est-à-dire qu’il n’existe pas de moyen, connaissant k bits donnés par le CSPRNG, de calculer le bit k+1 avec une probabilité supérieure à 50%
• Si l’état interne du CSPRNG est dévoilé, il ne doit pas être possible d’être capable de remonter dans la génération des nombres et de retrouver les nombres précédemment générés.

Quel est le sens de la seconde règle ? Expliquons la par un exemple :

Narvalo génère une clé privée RSA sur le PC du CDI (il est pas malin, Narvalo). Pour générer la clé, il a besoin d’aléatoire, et demande au kernel des nombres aléatoires.

Une fois sa clé générée, transférée et supprimée du disque définitivement, Narvalo s’en va sans redémarrer la machine.

Frelon, le responsable du CDI qui a un PHD en crypto, se connecte sur le PC de Narvalo et grace à un tour de passe-passe, réussi à récupérer l’état interne du CSPRNG du kernel.

Comme le CSPRNG du kernel est CS (Cryptographically secure), Frelon n’est pas capable de remonter l’algorithme et de retrouver les nombres générés et donnés à Narvalo pour sa clé. Du coup Frelon ne peut pas retrouver la clé privée de Narvalo, on a encore eu de la chance.

Comment je rajoute le CS devant mon PRNG ?

Pour créer un PRNG, il faut plusieurs éléments :

• Un bon PRNG
• Une fonction d’output
• De l’entropie
• Une fonction de mélange

Que signifie ces termes ?

Fonction d’output

On l’a évoqué précédemment, si l’état interne du PRNG est dévoilé, alors il est facile de prédire la suite de nombres qui va être générée. Pour éviter de tomber dans cette faiblesse, le nombre généré par notre PRNG ne sera pas directement envoyé à l’utilisateur, mais passera auparavant par une fonction d’output.

Imaginons un cas simple où cette fonction n’est qu’un simple hash, genre sha256. Ainsi, plutôt que de renvoyer le nombre directement à l’utilisateur, on lui renvoit son hash, pour éviter qu’il puisse connaître l’état actuel interne du CSPRNG (le hash étant par nature une fonction mathématique à sens unique donc irreversible).

En pratique, simplement hasher la sortie est loin d’être suffisant (faiblesse aux attaques par rainbow table pour ne citer qu’un exemple), mais les constructions des fonctions de sortie s’en approchent.

L’entropie

L’entropie est une valeur qui peut représenter la “quantité d’aléatoire” contenu dans une donnée. On parle ici d’entropie de Shannon, d’entropie de Rényi, ou de Min-Entropie, à distinguer de l’entropie utilisée en physique par exemple.

L’entropie de Shannon (la plus commune quand on parle d’entropie en informatique sans préciser), est une valeur numérique que l’on peut interpréter par le nombre de questions à poser pour déterminer le symbole suivant.

Si on prend par exemple un message qui ne peut être composé que de deux lettres, A ou B. La répartition de composition est équiprobable, c’est à dire que A et B ont autant de chance d’apparaître. Ainsi, déterminer le caractère suivant d’un message ainsi défini revient à poser une question : “Est-ce que le prochain char est un A ?”. Si la réponse est oui, c’est bingo, si la réponse est non, alors c’est un B. L’entropie de Shannon dans une telle situation vaut donc 1.

C’est cette notion d’entropie qui intervient dans la force de vos mots de passe par exemple :

Un mot de passe composé de caractères aléatoires aura selon notre définition une force plus élevée qu’un mot de passe avec uniquement des chiffres. Cette notion est cependant parfois plus complexe que de simples probabilités sur l’univers des possibilités. Si l’on parle de mot de passe, et que l’on a déterminé que les premiers caractères d’un mot de passe que l’on souhaite casser sont passwor, le d a une probabilité plus forte d’apparaître, même s’il est tout à fait possible d’avoir n’importe quel autre caractère.

Dans le cadre de notre CSPRNG, l’entropie est une mesure de l’aléatoire “pur”. Il va nous falloir une source d’aléatoire “pur”, qui va nous servir à nourrir notre CSPRNG d’une certaine manière.

Si l’on prends le CSPRNG de linux par exemple, des sources d’aléatoire “pur” (donc d’entropie) sont utilisées. Ces sources sont par exemple les mouvements de la souris, les frappes du clavier, les latences du disque, etc.

Ces évènements sont difficiles à déterminer, et si on est capable de les transformer en valeur numérique, et de quantifier la “quantité d’aléatoire qu’ils portent”, leur entropie, on peut rajouter cet aléatoire dans notre CSPRNG pour le rendre, bah plus aléatoire.

Fonction de mélange

C’est précisement le rôle de la fonction de mélange (ou d’input) de rajouter cette entropie dans notre CSPRNG, en “diffusant” l’aléatoire, sans pour autant remplacer notre “aléatoire” pré-existant.

Elle va souvent de pair avec une fonction capable d’estimer l’entropie que l’on ajoute, et qui donc sert à maintenir un état de la quantité d’entropie disponible.

Et le rapport avec le projet d’ADA ?

Si j’évoque tout ces éléments, c’est pour la simple et bonne raison qu’il m’a fallu les comprendre (du moins suffisamment) pour pouvoir implémenter un CSPRNG pour mon projet de cryptographie en ADA.

La présentation de mon CSPRNG fera l’objet d’un nouveau billet de blog, celui-ci est déjà bien assez long comme ça.