- Contact: tech-kern
- Mentors: Taylor R Campbell
- Duration estimate: 2-3 months
IMPORTANT: This project was completed by Taylor R Campbell. You may still contact the people above for details, but please do not submit an application for this project.
Update: This project was completed in 2020 by Riastradh.
The kernel entropy pool provides unpredictable secrets via the rnd(4) (/dev/urandom) device for applications doing cryptography, Monte Carlo simulations, etc. To provide unpredictable secrets, the kernel observes various physical hardware devices attached to it and combines the individually low-entropy observations into a high-entropy pool. Sources include
- hardware random number generators,
- keystrokes and their timing,
- disk seek times,
- network packet timing,
- page fault times,
and various others.
Currently, the observations are put into a single global queue, and then mixed with an ad-hoc array of 128 linear feedback shift registers, which is hashed with SHA-1 to produce outputs. There are two problems with this:
The single global queue is a point of contention for gathering observations: every disk seek, every network packet, every page fault must acquire a global lock to enter data into the global queue for processing.
The cryptographic construction of the pool -- array of 128 linear feedback shift registers fed into SHA-1 -- is ad hoc, has never been analyzed by a cryptographer, and uses questionable components.
Using a queue instead of entering into the pool directly reduces the latency of each operation, but the contention over a single global resource remains, and as computers become more parallel, the cost of that contention grows. Entering entropy should be cheap; extracting entropy can be expensive because once you have a single 256-bit unpredictable secret, you can efficiently expand that into an arbitrarily long unpredictable secret.
The entropy pool should be replaced by a per-CPU collection of Keccak sponges, the primitive inside SHA-3. Entering data into the poolcan be a matter of xoring into a buffer on the local CPU, and occasionally permuting the 1600-bit state; extracting data from the pool requires a CPU cross-call to extract data from all the per-CPU pools.
This project has an untested draft to start with. Subtle issues in the project include avoiding deadlocks in the protocols for gathering entropy on demand and waking readers waiting for entropy before the system has gathered enough.