L’aléatoire en programmation

De nombreux algorithmes nécessitent des caractéristiques imprévisibles pour fonctionner de manière efficace et/ou optimale. Il arrive parfois que l’on veuille éviter d’avoir la possibilité de deviner qu’elle sera l’issue de l’exécution de notre programme, par exemple dans le domaine de la sécurité ou certaines données ont besoin de rester imprévisibles aux yeux de programmes malfaisants.

Les jeux de rôle sur ordinateur utilisent souvent l’aléatoire pour simuler des jets de dés. Prenons l’exemple des statistiques d’une arme légendaire :

Si vous êtes observateur ou connaisseur, vous apercevrez les différents types de dommages (physique, magique, feu) de l’arme, chacun représenté par des intervalles. Pour un coup donné avec cette arme, trois nombres aléatoires sont tirés pour chaque plage de dégât, et leur somme correspond au total de dommage sur le monstre frappé. D’autres utilisations très utiles de l’aléatoire se retrouvent dans de nombreux domaines de l’informatique, notamment pour les réseaux de neurones, ou dans l’algorithmie répartie…

Typiquement, en programmation un entier aléatoire s’obtient par un simple appel de fonction :

int random_number = random(0,9);

La fonction random retourne un chiffre entre 0 et 9 et met cette valeur dans la variable entière random_number. Avec cette fonction, on peut faire fonctionner notre algorithme de calcul de dégâts et optimiser notre réseau de neurones.

Cependant, comment pourrait-on être certain que les nombres retournés par une fonction random soient réellement dus au hasard ? Les programmes sont des automates, leurs exécutions sont causales et déterminées par un programmeur. Théoriquement, il n’y a donc aucune chance qu’un code puisse nous retourner un résultat réellement aléatoire.

La méthode simple n’est pas toujours la meilleure

D’une manière générale, le hasard naît toujours d’une série d’événements, et lorsqu’ils sont suffisamment nombreux et tortueux, alors on peut considérer le hasard comme du hasard. Dans le cas d’un programme écrit sur une machine, on pourrait récupérer le nombre de nanosecondes écoulées depuis le début de la seconde courante et s’en servir comme “événements suffisamment imprévisibles” pour générer de l’aléatoire :

struct timespec spec;
clock_gettime(CLOCK_REALTIME, &spec);
// nanoseconds contient le nombre de nanosecondes dans la seconde courante 
time_t nanoseconds = spec.tv_nsec; 
// On veut tirer un chiffre aléatoire entre 0 et 9
int random_number = nanoseconds % 10;

Le reste de la division par 10 nous donnerait un résultat situé entre 0 et 9. Etant donné qu’il est impossible pour un humain de suivre l’écoulement des nanosecondes, la variablerandom_number serait un candidat bien assez crédible en tant que nombre aléatoire. Du moins, elle pourra piocher un neurone parmi 10, ou calculer des dégâts magiques de 1 à 10. Elle pourrait également être utilisée pour générer le secret d’une méthode d’encryptage… À vos risques et périls.

“Good random numbers”

Le fichierrandom.c du code source de linux contient les fonctions permettant de produire des nombres aléatoires, qui ensuite sont encodés puis stockés, afin d’être utilisés par la suite dans un programme. Le commentaire explicatif au début du fichierrandom.c affirme que les nombres générés seraient des “good random numbers”, c’est à dire des nombres aléatoires étant supposé sûr pour être employé dans le domaine de la sécurité. Et si l’on parle de “good random”, il existe aussi des “bad random number” tel que celui récupéré par la variablerandom_number ci-dessus.

L’exemple précédent produit de l’aléatoire crédible pour un humain, mais pas pour un programme. En effet, l’écoulement des nanosecondes suit un cycle. Une simple méthode de brute force permettrait de parcourir toutes les nanosecondes (10^9 possibilités) et rendrait ce procédé de génération de nombre inefficace pour une utilisation cryptographique.

Pour éviter qu’un programme malicieux puisse remonter le fil de la causalité, il faut… davantage de cause à l’origine de notre nombre. Donc récupérer plus d’informations que seul le cycle des nanosecondes.

Toujours plus d’entropie

Dans un premier temps, un octet aléatoire devrait être sourcé par une quantité raisonnable d’information. En effet, plus la fréquence d’information qui génère cet octet est importante, plus l’octet a de chance d’être crédible en tant qu’octet aléatoire. Une autre manière de voir cela serait de compter le nombre de façon différente d’obtenir un 4 avec un dé, puis avec deux dés.

Forcément, on a plus de possibilités avec deux dés. On désigne ces variations de la fréquence d’information comme étant l’entropie. Donc une entropie assez importante pourrait assurer la création de bon octets aléatoires ! On pourrait prendre des éléments comme le pid du programme courant, l’adresse MAC de la machine, le nombre de cycles, etc… Et les ajouter dans nos calculs de nouveaux nombres aléatoire.

Seulement, on a pu voir qu’un programme malicieux pouvait toujours faire des suppositions, puis appliquer la brute force en prenant en compte des caractéristiques que la machine génère. La qualité des informations à une très grande importance pour ce qu’il s’agit de sécuriser le processus de création de bytes aléatoire. Par qualité, on entend des informations très difficiles à estimer, comme des interactions homme-machine.

Les bruits extérieurs

random.cfait appel aux interfaces/dev/randomet/dev/urandom, ils contiennent des bruits extérieurs récupérés par le programme. La différence fondamentale entre ces deux interfaces réside dans la tolérance à l’entropie./dev/randombloque lorsque la requête demande une entropie plus grande que celle présente dans l’interface, alors que/dev/urandomne bloque jamais. Les bruits récupérés provenant des interfaces sont ajoutés via plusieurs fonctions à une structure appelée une “entropy pool”. Cette structure contient ces données sous une forme encodées afin d’éviter qu’une source extérieur puisse interpréter le contenu de l’entropy pool.

Plusieurs fonctions permettent d’incrémenter cette structure :

• void add_device_randomness(const void *buf, unsigned int size): Ajoute des données (probablement) uniques à la machine, comme l’adresse MAC, ou des numéros de série
• void add_input_randomness(unsigned int type, unsigned int code,unsigned int value): Ajoute les intervalles entre les entrées du clavier.
• void add_interrupt_randomness(int irq, int irq_flags): Ajoute les intervalles entre les déclenchements de certaines interruptions.
• void add_disk_randomness(struct gendisk *disk) : Ajoute des données liées aux utilisations du disque dur.

Ces événements ne sont pas déterministes et quasi impossibles à mesurer, ce qui les rend efficace pour un programme supposé sécurisé.