Entropie · Bucchino Geoffrey

Dans cet article, nous allons voir un concept fondamental dans un système informatique: l’entropie. Cette notion est très utilisée dans des applications de chiffrements et autres qui nécessite l’utilisation de données aléatoire. L’entropie représente le désordre dans un système.

Pour permettre au système de générer de l’entropie, il utilise différents élément que ce soit externe ou interne:

Les interruptions disques
Les entrées/sorties disques
Le temps de lecture/écriture sur disques
Les intéractions utilisateurs: clavier et souris
Les composant RNG (Random Number Generator)
Le temps d’accès d’un paquet réseau pour accéder aux couches bases
etc.

La RFC 4086(1) est assez intéressante, puisqu’elle donne des préconisations pour générer l’aléatoire dans un système, comme l’utilisation du fond sonore d’un micro ou utiliser les interruptions des disques dur mais fournit aussi des conseils sur des mauvaises techniques pour générer de l’aléatoire.

L’entropie va simplement générer du “désordre” dans un système, mais ne va pas générer des nombres. Sous Linux, il existe un algorithme que l’on nomme PRNG (Pseudorandom Number Generator) et qui s’appuie sur l’entropie pour les générer. Les données retournées par cette algorithme va permettre aux applications nécessitant ces nombres d’en faire usages, comme des solutions cryptographiques puisqu’elle nécessite des valeurs aléatoires pour éviter qu’un attaquant ne puisse identifier une clé de chiffrement.

Pour permettre d’exploiter ces valeurs, linux fournit les périphériques /dev/random et /dev/urandom qu’ils s’appuient sur l’algorithme PRNG pour générer les valeurs aléatoires. Nous pouvons schématiser ce fonctionnement de cette manière:

Fonctionnement de l’entropie

L’entropie: un fondamental pour la sécurité

Comme nous l’avons vu plus haut, l’entropie est très utilisé dans le millieu de la cryptographie car grâce à ces propriétés pour générer des valeurs aléatoires, elle améliore la sécurité, cependant, dans le cas où le système n’a pas généré assez de valeurs, cela aura des conséquences sur les communications. Par exemple, durant la phase du SSL handshake - procéssus qui permet d’établir une connexion sécurisée entre deux entités - cela met du temps à s’établir où échoue, car il n’y a pas assez d’entropie pour générer des clés de chiffrement. Par ailleurs, lorsque nous générons ces clés de chiffrement, si l’entropie est faible, un attaquant peut facilement insérer des données dans les interfaces d’entrées et de supposer les valeurs de sorties de l’algorithme PRNG et permettre ainsi de retrouver la clé de chiffrement, et rendre les connexions faibles (Voir la section 3.1 de l’article An Analysis of OpenSSL’s Random Number (2)).

Les attaques par texte claire sont des méthodes qui permettent aux attaquant de déduire la clé de chiffrement, puisqu’ils possident des messages clair ainsi que leurs versions chiffrées. Si la clé de chiffrement, ne possède pas assez de valeurs aléatoires, il sera plus facile pour un attaquant de deviner cette clé. Un article très intéressant(3), nous explique les faiblesses du chiffrement SSL lorsque l’entropie dans un système est faible. C’est l’une des raisons pour changer régulièrement sa clé de chiffrement pour assurer une haute sécurité des données.

Récemment, un bug dans le noyau Linux à causé un ralentissement du système Ubuntu 18.04 lors du démarrage et les procéssus entraient en pause, car il n’y avais pas assez d’entropie (4). Cela ne concerne en rien la sécurité, mais j’ai trouvé intéressant d’en faire part.

Ces problématiques détaillées plus haut, nous font poser la question suivante: comment augmenter l’entropie dans un système et garantir une plus forte sécurité dans nos communications de tous les jours ? Il existe des outils, comme Haveged (5), cependant, nous ne verrons pas dans cet article la mise en place de ces outils car ils existent une multitude de tutoriels sur le Web.

Utilisation de l’entropie sous Linux

Dans les environnements Linux, il est possible d’afficher le nombre d’entropie disponible sur le système. Pour cela, linux fournit le fichier /proc/sys/kernel/random/entropy_avail et retourne le nombre d’entropie disponible.

$ cat /proc/sys/kernel/random/entropy_avail 
3803

Les périphériques /dev/random et /dev/urandom sont les principaux consommateurs d’entropie. Pour tester l’utilisation de l’entropie, nous allons créer un fichier d’une taille de 500Mo via l’utilitaire dd et lui affecter des blocs aléatoires via le périphérique /dev/random:

# cat /proc/sys/kernel/random/entropy_avail
3426
# touch test-entropy
# dd if=/dev/random | pv | dd of=/dev/test bs=1024 count=512000
# cat /proc/sys/kernel/random/entropy_avail
36

Vous pouvez-voir que j’utilise la commande pv qui va me permettre d’avoir un état d’avancement puisque la commande dd, ne fournit aucun retour durant son exécution. Au début, nous pouvons remarquer que j’ai 3426 entropie et à la fin, j’ai n’ai plus que 36 d’entropie. Cela nous indique que le périphérique /dev/random est bien consommatrice d’entropie. Je vous conseil durant l’exécution de la commande dd de vérifier de temps-en-temps l’entropie disponible. Vous remarquerez que cette dernière va fluctuer.

Benchmarking linux kernel

Comme nous l’avons vu plus haut, les périphériques /dev/random/ et /dev/urandom s’appuient sur l’entropie pour générer les valeurs aléatoires, cependant, il existe une fonction intégré dans le kernel linux qui permet de récupérer ces valeurs. Cette fonction est définie dans le fichier random.c: get_random_bytes(void *, int).

Pour pouvoir bencher une fonction utilisé dans le kernel, il est nécessaire de créer un module et le charger dans le kernel. Le script ci-dessous va permettre de créer un module qui servira à bencher cette fonction:

#include <linux/vmalloc.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/kobject.h>
#include <linux/random.h>

#define COUNT 100
#define BUF_SIZE 200
#define BUF_SIZE2 1024

static struct kobject *kobj_kernel;
static struct attribute attr;
static struct kobj_attribute kobj_attr;
static ssize_t random_show(struct kobject*, struct kobj_attribute*, char *);
int getRandomBytes(char *);


/* 
 * https://www.kernel.org/doc/Documentation/filesystems/sysfs.txt
 * https://elixir.bootlin.com/linux/v4.14.5/source/samples/kobject/kobject-example.c
 */
static ssize_t random_show(struct kobject *d, struct kobj_attribute *attr, char *buf) {
	return getRandomBytes(buf);
}

int getRandomBytes(char *buf) {
    int i,pos;
    char *nbuf = vmalloc(sizeof(char) * BUF_SIZE);
    char buffer[BUF_SIZE2];
    pos = 0;

    for(i = 0; i < COUNT; i++) {
        /* Reinitalize buffer */
        memset(nbuf, 0, BUF_SIZE);

        get_random_bytes(nbuf, BUF_SIZE);
        pos += snprintf(buffer+pos, BUF_SIZE2-pos, "%ld\n", strlen(nbuf));
    }
    vfree(nbuf);
    return scnprintf(buf, PAGE_SIZE, "%s", buffer);

}

int init_module(void) {
	/* Create sysfs 'bench_entropy' in /sys/kernel/	*/
	kobj_kernel = kobject_create_and_add("bench_entropy", kernel_kobj);	
	
	if (!kobj_kernel)
		return -1;
		
	/* Create file */
	attr.name = "results";
	attr.mode = 0644;

	kobj_attr.attr = attr;
	kobj_attr.show = random_show;
	kobj_attr.store = NULL;

	if (sysfs_create_file(kobj_kernel, &kobj_attr.attr)) {
		printk(KERN_INFO "Error to create file in sysfs kernel");
		return -1;
	}
	return 0;
}

void cleanup_module(void) {
	kobject_put(kobj_kernel);
}

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Benchmarking module for linux kernel entropy");
MODULE_AUTHOR("Geoffrey Bucchino");

Le script est assez simpliste. Pour faire les tests de benchmark, je vais créer un module en implémentant deux fonctions: int init_module(void) et void cleanup_module(void). Lors de l’initialisation du module, le programme va créer un objet kobject, qui est l’abstraction derrière le sysfs, nommé bench_entropy dans le répertoire /sys/kernel/.

Le programme va ensuite créer le fichier results dans ce répertoire grâce à la fonction sysfs_create_file(struct kobject *, const struct attribute **). Lorsque l’utilisateur va afficher ce fichier, le programme va faire appel à la fonction random_show et exécuter la fonction getRandomBytes(char*) pour retourner le résultat dans ce fichier. Pour mieux comprendre le fonctionnement de kobject, je vous invite à regarder un exemple d’utilisation de kobject.

La fonction getRandomBytes(char*) va créer une variable dynamique d’une taille fixe (200) dans notre buffer: char *nbuf. Ce buffer sera remplis par les valeurs aléatoires récupérées via la fonction get_random_bytes(void *, int). La taille du buffer est mise dans la variable char buffer. Cette dernière sera ensuite copié dans la variable char *buf qui sera retournée dans le fichier results.

Nous devons ensuite compiler notre module. Pour cela, créer le fichier Makefile et ajouter les directives suivantes:

obj-m += bench_kernel.o

bench_kernel.ko:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

On lance ensuite la compilation: make. Puis, si aucune erreur ne survient, nous avons le fichier bench_kernel.ko qui est créé:

$ sudo modinfo bench_kernel.ko
filename:       /home/geoffrey/Documents/{...}/entropy/bench_kernel.ko
author:         Geoffrey Bucchino
description:    Benchmarking module for linux kernel entropy
license:        GPL
depends:        
retpoline:      Y
vermagic:       4.9.0-6-amd64 SMP mod_unload modversions

On charge notre module dans le kernel, puis on affiche le résultat de notre test:

$ sudo insmod bench_kernel.ko
$ ls -l /sys/kernel/bench_entropy/
-rw-r--r-- 1 root root 4096 Apr 14 14:29 results
$ cat /sys/kernel/bench_entropy/results
200
200
3
200
200
200
123
200
59
35
...

On peut voir que la taille de notre buffer n’est pas remplis complètement (200). Pour illustrer le résultat, j’ai fait un graphique grâce aux résultats précédents:

Graphique du résultat du bench

Et voici le programme python qui m’a permit de faire ce graphique:

#!/usr/bin/python
# coding: utf-8

import matplotlib.pyplot as plt
import numpy as np

with open("results", "r") as f:
	y = f.readlines()
y = [int(tmp.strip()) for tmp in y]

x = [tmp for tmp in range(0, len(y))]

width = 0.5
plt.barh(x, y, width)
plt.show()

Mes sources

//: # (https://en.wikipedia.org/wiki/Entropy_(computing)) //: # (http://www.deltasight.fr/entropie-linux-generation-nombres-aleatoires/) //: # (https://blog.seboss666.info/2015/06/augmenter-lentropie-pour-accelerer-ssh-pas-que/) //: # (https://en.wikipedia.org/wiki/Known-plaintext_attack) //: # (https://www.rocq.inria.fr/secret/Andrea.Roeck/pdfs/article_majecstic.pdf)