From: Stephan Mueller Subject: [RFC][PATCH] Entropy generator with 100 kB/s throughput Date: Fri, 08 Feb 2013 23:04:54 +0100 Message-ID: <51157686.9000404@chronox.de> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 7bit Cc: lkml To: Ted Ts'o , linux-crypto@vger.kernel.org Return-path: Sender: linux-kernel-owner@vger.kernel.org List-Id: linux-crypto.vger.kernel.org Hi crypto hackers, [1] patch at http://www.chronox.de/jitterentropy-0.1.tar.gz The Linux kernel RNG which we all use via /dev/random or /dev/urandom received a lot of merits over the long years it exists. In particular it was subject to countless researches and assessments and was determined to deliver appropriate entropy to the caller. However, we all know that the RNG also has deficiencies, which makes the appropriate use not entirely clear to everybody. In the past we heard about weak keys in embedded systems and the like. It is not the RNG's fault, but rather the problem of designers of such systems. Nonetheless, things could be easier with the use of the Linux RNG . In particular I met the following shortcomings over the years: * /dev/random is regarded as high-quality RNG as it is constantly reseeded, but suffers from its blocking nature * there is no in-kernel equivalent for /dev/random -- i.e. how can you really seed the DRNG that is present in the kernel crypto API with high quality entropy? * at boot time the data /dev/random or /dev/urandom spits out is questionable which requires a reseed during reboot. Also, that seed file must first be written, which may not be trivial in all circumstances. For example, in embedded systems or live CDs, this may be a challenge. Or what about system outages -- there is no clean shutdown and no new seed file. * in virtual environments (i.e. the Linux kernel operates as guest), /dev/random does not have access to all the devices to collect entropy. * when generating the key for full disk encryption configuration, there may be limited entropy in the entropy pools * random.c contains complex processing which enlarges the device event processing for every event In the patch, I try to provide an entropy collector without these shortcomings. The patch offers an entropy generator based on CPU timing jitter. The entropy collector has the following properties: * it does not maintain any state and therefore does not need any seed * it delivers entropy on demand with a throughput of about 100 kB/s and does not block -- it performs a synchronous entropy generation for the caller * it should work well in virtualized environments * the heart of the entropy collector is about 10 lines of code and does not use cryptography * an array of statistical test suites pass the output of the entropy collector (again, the output is not mangled with cryptography) The design and concepts are documented in source code comments. The source code is available at [1]. The code can be compiled as kernel module as well as user space application. In case the code finds its way to the kernel, the user space code will be removed -- currently it remains to ease the analysis. To compile as kernel module, just run make. To compile as user space application, run make -f Makefile.user. Note, the user space part can also be used in user space libraries to avoid /dev/random. Is such entropy collector of interest for the kernel? Do you see weaknesses in the design or its implementation? In a recent discussion about the Linux RNG Theodore Ts'o indicated that in the long run, he would like to see an RNG based on AES (see http://lkml.org/lkml/2012/12/15/162). In addition to the entropy collector, the kernel module also includes a link to the kernel crypto API X9.31 DRNG based on AES. Two instances of the DRNG are maintained. The first instance is reseeded once in a while (after 1024 bytes of random data) with the CPU jitter entropy. The second is reseeded with 16 bytes of entropy when 16 bytes are read from the DRNG. The first DRNG therefore is a fast delivering DRNG which is information theoretical weaker than the second DRNG (which is much slower, but the information theoretical entropy equals about 1 bit per 1 bit of output). For testing purposes, debugfs interface files are implemented to read from the entropy collector and the two DRNGs. The test mode is triggered with the parameter "insmod jitterentropy.ko testmode=1". The interface files are /sys/kernel/debug/jitterentropy/[seed|drng|strong-drng]. Detailed design description is given as comments in the source code file. Thanks Stephan