Return to scalable-entropy.mdwn CVS log

Up to [NetBSD Developer Wiki] / wikisrc / projects / project

Annotation of wikisrc/projects/project/scalable-entropy.mdwn, revision 1.2

1.1       riastrad    1: [[!template id=project
                      2: 
                      3: title="Scalable entropy gathering"
                      4: 
                      5: contact="""
                      6: [tech-kern](mailto:tech-kern@NetBSD.org)
                      7: """
                      8: 
                      9: mentors="""
                     10: [Taylor R Campbell](mailto:riastradh@NetBSD.org)
                     11: """
                     12: 
                     13: category="kernel"
                     14: difficulty="medium"
                     15: duration="2-3 months"
                     16: 
                     17: description="""
                     18: The kernel entropy pool provides unpredictable secrets via the
1.2     ! kim        19:  [[!template id=man name="rnd" section="4"]] (/dev/urandom)
1.1       riastrad   20:  device for applications doing cryptography, Monte Carlo simulations,
                     21:  etc.
                     22: To provide unpredictable secrets, the kernel observes various physical
                     23:  hardware devices attached to it and combines the individually
                     24:  low-entropy observations into a high-entropy pool.
                     25: Sources include
                     26: 
                     27: - hardware random number generators,
                     28: - keystrokes and their timing,
                     29: - disk seek times,
                     30: - network packet timing,
                     31: - page fault times,
                     32: 
                     33: and various others.
                     34: 
                     35: Currently, the observations are put into a single global queue, and
                     36:  then mixed with an ad-hoc array of 128 linear feedback shift
                     37:  registers, which is hashed with SHA-1 to produce outputs.
                     38: There are two problems with this:
                     39: 
                     40: 1. The single global queue is a point of contention for gathering
                     41:  observations: every disk seek, every network packet, every page fault
                     42:  must acquire a global lock to enter data into the global queue for
                     43:  processing.
                     44: 
                     45: 2. The cryptographic construction of the pool -- array of 128 linear
                     46:  feedback shift registers fed into SHA-1 -- is ad hoc, has never been
                     47:  analyzed by a cryptographer, and uses questionable components.
                     48: 
                     49: Using a queue instead of entering into the pool directly reduces the
                     50:  latency of each operation, but the contention over a single global
                     51:  resource remains, and as computers become more parallel, the cost of
                     52:  that contention grows.
                     53: *Entering* entropy should be cheap; *extracting* entropy can be
                     54:  expensive because once you have a single 256-bit unpredictable secret,
                     55:  you can efficiently expand that into an arbitrarily long unpredictable
                     56:  secret.
                     57: 
                     58: The entropy pool should be replaced by a per-CPU collection of Keccak
                     59:  sponges, the primitive inside SHA-3.
                     60: Entering data into the poolcan be a matter of xoring into a buffer on
                     61:  the local CPU, and occasionally permuting the 1600-bit state;
                     62:  extracting data from the pool requires a CPU cross-call to extract
                     63:  data from all the per-CPU pools.
                     64: 
                     65: This project has an untested draft to start with.
                     66: Subtle issues in the project include avoiding deadlocks in the
                     67:  protocols for gathering entropy on demand and waking readers waiting
                     68:  for entropy before the system has gathered enough.
                     69: """
                     70: ]]
                     71: 
                     72: [[!tag gsoc]]