Projects/PRNG Cleanup - Revision history

Ghudson at 18:42, 18 May 2011

2011-05-18T18:42:14Z

TomYu: add release info

2011-03-08T00:02:45Z

add release info

TomYu: approve

2011-03-08T00:01:50Z

approve

TomYu: add vote section

2011-03-08T00:01:27Z

add vote section

Ghudson at 16:45, 23 February 2011

2011-02-23T16:45:37Z

Ghudson at 16:43, 23 February 2011

2011-02-23T16:43:36Z

Ghudson: /* Implementation Details */

2011-02-23T16:39:04Z

‎Implementation Details

Ghudson at 16:35, 23 February 2011

2011-02-23T16:35:27Z

Ghudson: /* Problem Analysis */

2011-02-22T00:49:29Z

‎Problem Analysis

Ghudson: /* Background */

2011-02-22T00:48:55Z

‎Background

← Older revision		Revision as of 18:42, 18 May 2011
Line 1:		Line 1:
−	{{project-~~approved~~}}	+	{{project-rel\|1.10}}
−
−	{{project-target\|1.10}}

	==Overview==		==Overview==

← Older revision		Revision as of 00:02, 8 March 2011
Line 1:		Line 1:
−	{{project-~~review\|March 2, 2011~~}}	+	{{project-approved}}
		+
		+	{{project-target\|1.10}}

	==Overview==		==Overview==

← Older revision		Revision as of 00:01, 8 March 2011
Line 69:		Line 69:

	===Approvals===		===Approvals===
		+
		+	# [[User:TomYu\|TomYu]] 00:01, 8 March 2011 (UTC)

	===Discussion===		===Discussion===

← Older revision		Revision as of 00:01, 8 March 2011
Line 59:		Line 59:

	http://mailman.mit.edu/pipermail/krbdev/2010-September/009561.html		http://mailman.mit.edu/pipermail/krbdev/2010-September/009561.html
		+
		+	==Review==
		+
		+	This section documents the review of the project according to [[Project policy]].
		+	It is divided into multiple sections. First, approvals should be listed. To list an approval type
		+	:<nowiki>#~~~~</nowiki>
		+	(hash mark followed by four tilde characters) on its own line.
		+	The next section is for summarizing discussion, which should take place on krbdev@mit.edu. Provide links to the archive at http://mailman.mit.edu/pipermail/krbdev/ if appropriate. Blocking objections can be noted with <nowiki>{{project-block}}</nowiki>.
		+
		+	===Approvals===
		+
		+	===Discussion===

← Older revision		Revision as of 16:45, 23 February 2011
Line 51:		Line 51:

	The OS-only PRNG implementation will always use /dev/urandom. Currently we make some effort to seed the PRNG with values from /dev/random when creating a Kerberos database or starting kadmind; a note will be made to only select the OS-only PRNG when /dev/urandom is not significantly stronger than /dev/random. (The alternative is to revise our APIs so that each request for random data carries a "strong" flag; currently that flag only exists in krb5_c_random_os_entropy, an API to contribute OS entropy to the PRNG.)		The OS-only PRNG implementation will always use /dev/urandom. Currently we make some effort to seed the PRNG with values from /dev/random when creating a Kerberos database or starting kadmind; a note will be made to only select the OS-only PRNG when /dev/urandom is not significantly stronger than /dev/random. (The alternative is to revise our APIs so that each request for random data carries a "strong" flag; currently that flag only exists in krb5_c_random_os_entropy, an API to contribute OS entropy to the PRNG.)
		+
		+	==Testing==
		+
		+	Using internal interfaces to avoid gathering OS entropy, a test program will ensure that the values created by the Fortuna PRNG are stable across code changes, exercising all of the code paths.

	==Relevant Mailing List Threads==		==Relevant Mailing List Threads==

← Older revision		Revision as of 16:43, 23 February 2011
Line 1:		Line 1:
−	{{project-~~early~~}}	+	{{project-review\|March 2, 2011}}

	==Overview==		==Overview==

@@ Line 50: / Line 50: @@
 The corrected Fortuna PRNG will attempt gather entropy from the OS at initialization time.  If this fails, and no TRUSTEDPARTY or OSRAND entropy is contributed, subsequent calls to obtain random values will fail.
-The OS-only PRNG implementation will always use /dev/urandom.  Currently we make some effort to seed the PRNG with values from /dev/random when creating a Kerberos database or starting kadmind; a note will be made to only select the OS-only PRNG when /dev/urandom is not manifestly stronger than /dev/random.
+The OS-only PRNG implementation will always use /dev/urandom.  Currently we make some effort to seed the PRNG with values from /dev/random when creating a Kerberos database or starting kadmind; a note will be made to only select the OS-only PRNG when /dev/urandom is not significantly stronger than /dev/random.  (The alternative is to revise our APIs so that each request for random data carries a "strong" flag; currently that flag only exists in krb5_c_random_os_entropy, an API to contribute OS entropy to the PRNG.)
 ==Relevant Mailing List Threads==

@@ Line 6: / Line 6: @@
 * Correct (probably rewrite) the Fortuna PRNG implementation and make it the default.
-* Make the Fortuna implementation immediately reseed the generator on inputs likely to contain an interesting amount of entropy (OSRAND and TRUSTED).  Use the pool logic for other entropy inputs.
+* Make the Fortuna implementation immediately reseed the generator on inputs likely to contain an interesting amount of entropy (OSRAND and TRUSTEDPARTY).  Use the pool logic for other entropy inputs.
-* Make the Fortuna implementation fail out if it cannot gather OS entropy and does not receive an OSRAND or TRUSTED entropy input.
+* Make the Fortuna implementation fail out if it cannot gather OS entropy and does not receive an OSRAND or TRUSTEDPARTY entropy input.
 * Eliminate the Yarrow PRNG implementation.
 * Add a PRNG implementation which just gathers OS entropy.
@@ Line 40: / Line 40: @@
 The Yarrow PRNG implementation requires callers to estimate the entropy of unreliable-entropy events.  This requirement has been recognized by the creators of Yarrow as unrealistic and a flaw in the Yarrow architecture.
-The Fortuna-like PRNG implementation was written by someone without access to Schneier's description of Fortuna.  As a result, it implements something completely different from the Fortuna accumulator which is unlikely to be of benefit.  Its generator logic also has subtle differences from the Fortuna generator.
+The Fortuna-like PRNG implementation was written without direct access to Schneier's description of Fortuna.  As a result, it implements something completely different from the Fortuna accumulator.  Its generator logic also has subtle differences from the Fortuna generator.  These differences carry significant risk of compromising the PRNG's design goals.
 When entropy from a parent key or master key is contributed to the PRNG, it is not guaranteed to trigger a reseed.  If the PRNG was previously in a guessable state, we will generate a guessable subkey unnecessarily.
 The Yarrow implementation is complicated and delicately integrated with the rest of the crypto library, making it an obstacle to simplifying the organization of the library.

@@ Line 30: / Line 30: @@
 # When generating subkeys, we contribute the parent key as PRNG entropy.  Similarly, when operating on a KDC database, we supply the master key as PRNG entropy.
 # We produce values using a cryptographic generator.  A cryptographic generator, once seeded with input not known to the attacker, produces an indefinite sequence of random values which, without an infeasible amount of computational power, cannot be used to determine the internal state of the generator.
-# We implement a pool system which allows a stream of unreliable entropy events to be pooled together and used to reseed the generator.  The goal is that even if the internal state of the PRNG is known to an attacker at some point in time, the attacker will eventually be unable to recover the state after one of the reseed operations.
+# We implement an accumulator which allows a stream of unreliable entropy events to be pooled together and used to reseed the generator.  The goal is that even if the internal state of the PRNG is known to an attacker at some point in time, the attacker will eventually be unable to recover the state after one of the reseed operations.
-These countermeasures are not completely reliable at resolving the problem cases.  If the operating system cannot produce non-guessable initial entropy and we have no parent key to contribute, we cannot generate non-guessable values.  The pool logic is only useful for long-running callers such as the KDC which can generate a stream of unreliable entropy events.
+These countermeasures are not completely reliable at resolving the problem cases.  If the operating system cannot produce non-guessable initial entropy and we have no parent key to contribute, we cannot generate non-guessable values.  The accumulator is only helpful for long-running callers such as the KDC which can generate a stream of unreliable entropy events.
-The generator and pool system we use are from Yarrow, a creation of Schneier and others.  As of krb5 1.9, we also offer a compile-time choice of a "Fortuna-like" implementation of the generator and pools, based loosely on more recent work of Schneier and others.
+The generator and accumulator we use are from Yarrow, a creation of Schneier and others.  As of krb5 1.9, we also offer a compile-time choice of a "Fortuna-like" implementation of the generator and accumulator, based loosely on more recent work of Schneier and others.
 ==Problem Analysis==