Entropy

In IT, specifically in IT security, the entropy’s system is very useful. This concept is very important for encryption and others applications using random data. Entropy are qualified like a data structure and represent the randomness in the system.

For generating random datas, your system use many extern or intern factors:

Disk interrupt
Disk I/O
Reading/writing time in disk
Users interactions: mouse and keyboard
Components RNG (Random Number Generator)
etc.

The RFC 4086(1) is very interesting, because, it give many solutions for generate the random data in the system, like using sound from microphone or using disk drive interrupts, but it given some examples of bad technicals for generate random data.

The entropy represent the disorder in your system, but, with that, we can generate numbers. In Linux, it exists an algorithm which called PRNG (Pseudorandom Number Generator) and use the entropy in your system for generate the numbers. With this algorithm, some applications can have a random numbers, like application of cryptography and to have a stronger key of encryption.

For exploiting these values, linux provides the peripherics /dev/random and /dev//urandom and their use the PRNG for generate the random values. The figure below show the process for generating the random values:

Entropy

Entropy: a necessity for the security

As we say above, the entropy is very useful, especialliy for the cryptography, because we improve the security with a lot of random datas, however, if a system haven’t generated enough datas, that will impact on the communications. For instance, during the SSL handshake phase - process for establishing the session between two SSL users - that can take some times to establishe the session or that can fail. Also, when we generate a key for encryption, if the entropy is poor, an attacker can insert data in input interface and like that, he cans assume the output of the PRNG algorithm and to identify the key of the encryption (See the section 3.1 of the article An Analysis of OpenSSL’s Random Number (2)).

Chosen-Plaintext attacks there are method who an attacker may know in advance the key of encryption, because he has plaintext message and encrypted messages. If the encryption key is not very strong, it will be easy for an attacker to find the key. An article very interesting(3), explain to us the weaknes of SSL encryption when the entropy is very weak. It’s for this reason we may change often the key to ensure a high secure of our data.

Recently, a bug was implemented in Linux kernel and the system was very slow during the boot sequence and that impacted the system Ubuntu 18.04 and the processes was stucked, because not enough of entropy(4).

We can ask a question to ourself: how to improve the entropy on the system ? For doing that, we can use tools, like Haveged (5), but we won’t talk about this tool in this article.

Use the entropy with Linux

In Linux environment; it’s possible to display the number of entropy on the system. For doin that, read the file /proc/sys/kernel/random/entropy_avail and we will see the number of entropy available.

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

The devices /dev/random and /dev/urandom use the entropy on the system. For testing the entropy, we will create a small file of 500Mb with the tool dd and add random block with the device /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

As you see in the example above, I used the commande pv which can have a state of progress during the dd process. When the dd process is done, we consumed a lot of entropy, because the device /dev/random use the entropy on the system.

Benchmarking linux kernel

As we see above, the devices /dev/random and /dev/urandom use the entropy on the system for generating random numbers, however, the linux kernel provide to us a function which can get these values. This function is defined in the file random.c: get_random_bytes(void *, int).

For using this function, we need to create a module and to load into the kernel. The program below will create a module for testing this function:

#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");

The program is very simple. For the benchmark, I made a module with two functions: int init_module(void) et void cleanup_module(void). During the initialisation of module, the program will create an kobject, which is a representation of sysfs, called bench_entropy in the directory /sys/kernel/.

The program will create the file results in this directory with the function sysfs_create_file(struct kobject *, const struct attribute **). When the user will display this file, the program will call the function random_show and will execute the function getRandomBytes(char*) and put the result in this file. To understand how kobject works, I will invite you to see kobject-example.c.

The function getRandomBytes(char*) will create a dynamic variable with a size of 200bytes in our buffer char *nbuf. This buffer will be fill with our random values get from the function get_random_bytes(void *, int). The size of this buffer is put in the variable char buffer. This buffer will be copy in the variable char *nbuf which is returned in the file results.

After that, we can compile our module. For doing that, create the Makefile and put these lines:

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

We can now compile: make. Then, if we have no errors, we have the file bench_kernel.ko which is created:

$ 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

We can load this module in our kernel, and we can display our results file:

$ 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
...

Sometimes, the buffer is not full (200 bytes). For illustrated, I made a graphic with the results:

Bench diagram

I used this python program for make that diagram:

#!/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()

Entropy: a necessity for the security

Use the entropy with Linux

Benchmarking linux kernel

Referencies