File:  [NetBSD Developer Wiki] / wikisrc / projects / project / scalable-entropy.mdwn
Revision 1.1: download - view: text, annotated - select for diffs
Tue Feb 23 16:45:42 2016 UTC (3 years, 9 months ago) by riastradh
Branches: MAIN
CVS tags: HEAD
Add scalable entropy pool project.

[[!template id=project

title="Scalable entropy gathering"

contact="""
[tech-kern](mailto:tech-kern@NetBSD.org)
"""

mentors="""
[Taylor R Campbell](mailto:riastradh@NetBSD.org)
"""

category="kernel"
difficulty="medium"
duration="2-3 months"

description="""
The kernel entropy pool provides unpredictable secrets via the
 [/dev/urandom](http://netbsd.gw.com/cgi-bin/man-cgi?rnd++NetBSD-current)
 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:

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

2. 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.
"""
]]

[[!tag gsoc]]

CVSweb for NetBSD wikisrc <wikimaster@NetBSD.org> software: FreeBSD-CVSweb