[Cfrg] (no subject)

["John Kelsey" <john.kelsey at nist.gov>]

Guys,

I have quite a few comments on your draft document, "Randomness
Recommendations for Security."  I'm sorry I haven't gotten this to you
sooner--I know big lists of comments take time to digest, and that
you'd like to get this out the door.  For reference, I'm one of the
people working on the X9.82 random number generation standardization
effort, and this is a pretty major area of research for me, so I hope
I can offer you some pretty meaty comments.  I wish I had time to give you
more--these comments are still a bit unrefined.

General Comments on Organization:

I think the organization of this document could be improved a lot.
You seem to cover enormously relevant things for cryptographic random
number generation (like useful entropy sources in hardware and
software), things of marginal relevance (like the use of FFTs to
"distill" entropy, which seems unlikely to see much real-world use
these days), and things that flat out have no relevance, like
non-cryptographic PRNGs.  At times, you seem to encourage the reader
to roll his own crypto PRNG design, even though this seems like a
disasterously bad idea for most people to do.

I've found it really useful to divide up the discussion of
cryptographic random number generation into two broad chunks:

a.  Entropy sources--the things that are somehow truly unpredictable
to any attacker, or at least that are unpredictable to some subset of
attackers.  These are inherently implementation-specific; you can't
use the same code to pull randomness out of system loading on Windows
as you use on Linux, for example.  You have some nice discussion of
these, and it's probably the part of your document that's most likely
to be directly useful to your readers.

b.  Crypto PRNGs--the deterministic algorithms that, given some
unguessable starting seed, crank out bits that can be used for any
cryptographic purpose, up to the level of security provided by the
algorithm.  These are inherently implementation-independent--if you
and I implement the same algorithm on different computers, and feed
our implementations identical inputs, they will produce identical
outputs.  You discussed this a bit, but not as much as I think you
should have.  Rolling your own crypto PRNG is about as sensible as
rolling your own block cipher, in my opinion.  In X9.82, we've
(preliminarily) published some designs we're pretty confident in, and
I'd be happy to send you text we have on them--the most stable is
probably our cryptographic PRNG based on HMAC.  Alternatively, Peter
Gutmann has a nice design in Cryptlib, which he's analyzed in some
depth, and I published a design with Bruce Schneier and Niels
Fergusson called Yarrow-160, which I think is pretty reasonable.

I think something like this distinction would serve you well in this
document, because it would make it easier for the reader to work out
which parts of this he needs to understand.

It seems to me that most people reading this are going to be trying to
build something, software or hardware or both, which will need to
generate random bits for AES keys or some such thing.  Like, maybe
they're building a router, or a PDA-based secure e-mail application.
They need to walk away from reading the document with some notion of
how they can get entropy, and what they need to do with it to get
random bits they can use as AES keys, HMAC keys, random signature
parameters for ECDSA, etc.

Specific Comments:

Section 1, 4th paragraph, "The lack of generally available...."

I think the thing that's not generally available are reliable entropy
sources--that is, the processes that produce truly unpredictable
results.  There are often things going on in the system that are
probably very hard for an attacker to predict, but it's hard to make
use of them in a way that doesn't depend a lot on details of the
platform the program is running on, and even details of the machine
and its environment.

Crypto libraries routinely provide some way to generate keys, nonces,
etc.  But somehow, you still have to provide some
unguessable-to-the-attacker input to those routines.

Section 1, 5th paragraph, "It is important to keep in mind...."

I think it would help if you distinguished between:

a.  Unguessable values--things that might have all kinds of structure
to them, fail statistical tests, etc., but which cannot be guessed in
their entirety.  This is what we generally want of passphrases, and
it's also (for the same reasons) what we generally want of the seed
for a cryptographic PRNG.  Entropy sources provide unguessable values.

b.  Indistinguishable from random values--things which pass all our
statistical tests, and for all practical purposes, are random.  This
is what we get from the output of a good crypgographic PRNG--ideally,
any way you might have of distinguishing the PRNG outputs from
independent, unbiased, uniform bits from a stable distribution would
also give you a way to break some cryptographic primitive.

The reason to make this distinction is because some protocols need
their random numbers to be indistinguishable from random.  For
example, if I encrypt a random 128-bit block with a four-digit PIN, an
attacker can't learn anything about my PIN from that.  But if I
encrypt a 128-bit block where every 32nd bit is a 0, an attacker can
do a dictionary attack on my PIN.  So, it's important that a general
purpose cryptographic random number generator provide bits which are
indistinguishable from random to any attacker we care about.  These
bits are then automatically okay for every application.

Section 2, Entropy Formula:

Shannon entropy does a terrible job of telling you how hard something
is to guess in various extreme cases.  It's basically an answer to the
question "how many bits, on average, will it take me to transmit this
secret value?"  But we want to ask a different question: "How many
guesses does it take for an attacker to expect to successfully guess
my secret?"  (This ties in with the question of whether something is
unguessable by an attacker.)

The classic example of this is something like:

		    { 161 bits of 0s with probability 1/2
entropy_input =	    {
		    { A 1 bit, followed by 160 random bits with prob = 1/2

This has Shannon entropy of

     1/2 (1) + Sum(1..2^{160})[ 2^{-161} -lg(2^{-161}) ]
=    1/2 + 2^{160} 2^{-161} 161
=    1/2 + 161/2
=    162/2
=    81 bits of entropy

But imagine generating an 80-bit random key with this value--an
attacker could guess your key on his first try, half the time.

The right measure to use is min-entropy--defined as

Min-entropy = -lg( maximum probability )

This usually gives a little more conservative measure than is
absolutely necessary, but if some input string has min-entropy of 128
bits, you can always use it to produce a 128-bit AES key, without
worrying about any other details of the distribution.

The reasoning behind this comes out of something called the "work
function," from a couple of papers by John Pliam.  This says that for
any random variable, there's some work function W(n), that says what
the probability is that you've guessed the variable after n tries.

I don't want to do ASCII art here, but for something like an AES key,
where we expect a uniform, independent, unbiased 128-bit value, the
work function looks like a diagonal line from 0,0 to 1,2^{128}.  For a
password, the work function probably starts out climbing pretty fast
(as you consider all the obvious, common passwords like "fred" or
"albatross"), and then flattens out (as you get into the possible, but
extremely uncommon passwords, like "r$ish7$$" or "08nn17f1").

Suppose we're going to use an input string to derive a 128-bit key.
Then, the only way to make sure that we're not weakening our system by
deriving the key from this string is to ensure that the work function
for that input string never gives a higher probability of success than
the work function for our 128-bit key.  That means that an attacker
can't ever try N guesses, and have a better shot at guessing the input
string than he does at guessing the key.

You obviously have this idea in the next to last paragraph of section
2, but probably never tried running the Shannon entropy of this kind
of seriously asymmetric distribution of inputs.

Section 3:

General Comment: I think you spend *way* too much time here.  Nobody
should be reading this document to learn how to generate non-crypto
random numbers, but if some confused soul does that, you should simply
point them toward Knuth, Numerical Recipes, the Mersenne Twister
design, etc.

There are basically two points you need to get across from this
section:

a.  Don't use rand() to generate random numbers in a security
application, because it will probably blow up in your face.  In fact,
don't use anything that isn't designed for crypto-strength random
numbers.

b.  Passing all the Diehard tests, all the NIST tests, etc., doesn't
mean squat as far as cryptographic strength goes.  It's necessary to
pass these things, but a gazillion designs that are dreadfully weak
also pass them.  (The Mersenne twister passes everything in the NIST
suite with flying colors.)

I think you should kill the section entirely and make those points in
the introduction, because they're probably two of the most important
points you can make, and anyone who gets through page 2 of your
document ought to get them.

Section 4:

General Comment: This is where the meat is for this document!  But
you've split it out in a kind-of odd way.

I think it's a mistake to start by telling them how *not* to do this
stuff (in section 3, and again here), rather than starting by telling
them how to do it, and then pointing out what doesn't work.

I think there are three core points you need to hit in this section,
one of which you've touched on, two of which you've missed:

a.  When you're looking an entropy sources, passing statistical tests
has no relationship to whether the source is unpredictable, which is
what you really want.  (This works both ways:  The sequence of bits
from SHA1 hashing 0,1,2,... has no unpredictability, but will pass any
statistical test you can find.  A sequence of ASCII characters
encoding the rolls of a 6-sided die will fail every statistical test
you can think of, but it's a great source of unpredictability.)

b.  How unpredictable something is usually depends somewhat on the
attacker.  For example, packet arrival times are pretty easy to
predict if I'm on your local network and am monitoring it when you
collect them, but they're a wonderful source of entropy if I am not on
your local network.

c.  The attack we care about is a guessing attack.  That means it
makes sense to do the same kinds of things we do to foil dictionary
attacks on passwords--a combination of requiring good passwords (good
entropy sources), including a salt, and making the hashing from
password to key or secret value expensive.

Once you've made these three points, I think it would be really
valuable to tell the reader enough about these different potential
sources that he could decide if, in his application, they were
useful for anything.

4.1

Time (to the second) and ethernet address are good sources of "salt."
That is, they can and should be fed into the crypto PRNG's initial
state, but you shouldn't assume there's any substantial entropy there
against any attacker.  Very high precision timestamps can be good
sources of entropy, especialy against offline attackers trying to
guess some generated key or something.  But as you point out, the
designer of the system has to find some way to ensure that the
computer his program is running on really has a high-speed counter,
not some low precision clock with software to make it monotonic or
some such horrible thing.


4.2

Wouldn't it make sense to handle these things separately?  Mouse
movements, keystrokes, and network packet arrival times are very
different sources.  Could you give some helpful advice to someone who
needs to use them, in terms of how to estimate entropy?  Something
like:

  Against offline attackers (people attacking the RNG starting state
  long after the state has been generated) and attackers with no
  access to your local network, packet arrival times are a really good
  source of entropy, though naturally, the precision of your clock
  determines how much entropy you can get from each.

I think the other thing you need to get across here is that entropy
sources are implementaton-dependent.  If you're timing packet arrivals
with the cycle counter on your CPU, you're going to get a lot more
entropy than some other guy who's timing them with something driven by
the 18.x times/second external timer interrupt.  If you're designing a
system that needs to collect entropy from these sources, you really
need to know whether you've got a cycle counter you can use for
timing.

Keyboard, mouse, system loading, and packet arrival times are great
sources of entropy, but you have to analyze them on the system they're
to be used for, or at least develop a good model of what they should
look like, and stop trusting them if the model doesn't describe
reality very well.

4.3

I don't see what this adds to the document.  Readers should not
generally be inventing their own cryptographic PRNGs, and so this
shouldn't come up.

4.4

This is nice, but is anyone really thinking of this today?  Would it
make more sense to point out the problem of this in section 2, as part
of the discussion of what entropy is?

5

General Comment: Is the goal here to explain how to build your own
hardware RNG?  I don't think there's a good general guide to doing
that (we're trying to write one, though it will probably specify one
or two standard designs, and then discuss how to validate a specific
instance of one).

If you're pointing people toward how to build their own hardware RNG,
some useful points are:

a.  Nearly all the modern, real-world designs I have seen discussed
are based on either ring oscillators or amplifiers and noisy
electronic components.  (Older designs used unstable analog circuits,
such as, astable multivibrators, in place of ring oscillators.

b.  Doing this kind of design is more of an art than a science.

c.  You can only really give broad ideas about where to look for more
information here.  The designer is going to have to spend a huge
amount of time characterizing their entropy source.

Anyway, there's a fair bit of cryptographic RNG hardware out there.
Intel did a design (which flopped), and VIA has one now.  Several
smartcard/token vendors do special purpose hardware for cryptography.

5.1

Good.  For essentially all real-world cryptography, what we need from
our entropy source is a seed for a cryptographic PRNG.   Then, we can
let the crypto take care of the rest.  It's really important to
clarify that the rate of output of the entropy source is not an
important limit on how many bits per second of keys and such can be
produced, it's a limit on how long it takes before we can start
producing bits.

5.2

All we really need to know about our entropy source is how much
min-entropy we can count on getting from it.  There's probably not
much value in talking about de-skewing techniques in great
depth--maybe you'll want to do some non-cryptographic thing to get
reasonable-looking bits out of your ring oscillator source, but you're
probably just going to shove those bits into a hash function and use
them to derive an AES key or something.

5.2.1

Just a nitpick, but using e as something other than 2.718... in a
probability formula makes my head hurt.

5.2.3
5.2.4

It sure is hard to see where someone is actually going to use the FFT
or LZH to deskew data that they're then going to process with SHA1 or
AES to get a seed for their cryptographic PRNG.  I can definitely see
using either or both to test whether an entropy source is following
its expected behavior, but not really using them to produce
high-quality bits for cryptographic keys and such.  There are just too
many things that can go wrong!

5.3.1

This is extremely hardware and implementation dependent!

5.3.2

This is a nice reference, but it doesn't seem like you see many people
using it in practice, at least not directly.  It's very hard in
software to know how many layers of cache memory are between you and
your hard drive, and sometimes, the drive is virtual, or is a network
drive, or is a flash drive.

Here's another, more recent, reference on the same idea:

M. Jakobsson, E. Shriver, B. K. Hillyer, and A. Juels. A practical
secure physical random bit generator. In Proceedings of The Fifth ACM
Conference on Computer and Communications Security, 1998. 22
http://citeseer.ist.psu.edu/article/jakobsson98practical.html

5.4

Why do you mix the discussion of ring oscillators and amplifiers+noisy
diodes?  They're completely different.

6

It seems like a lot of this discussion of different mixing techniques
doesn't have much practical use to the people you're writing for.  I
see about three choices:

a.  I have one entropy source and it's in hardware, so I'm using some
hardware-friendly, low-gate-count mixing function such as a big CRC.

b.  I have lots of software entropy sources and they have to be
handled fast, so I do some kind of fast mixing like /dev/random does,
and periodically hash it.

c.  I have lots of software entropy sources but don't need blinding
speed.  I hash them as needed.

6.1.1
6.1.3
6.1.4

There's no point even discussing these techniques that I can
see--who's going to use them?  Either you can use a hash function (in
which case you will), or you need something faster (in which case, you
need some fast linear checksum).  Could you get the mixing polynomial
thing from /dev/random, and discuss using a big CRC circuit to do
mixing in dedicated hardware?  That plus a discussion of using a hash
function would cover everything people are likely to need in the real
world.

6.2

How about some advice on how to assess these sources in a given
environment.

6.3.1

Why go into how to do it wrong?  Just tell people that they can use
any strong block cipher in OFB or counter mode, and reference the NIST
special publication on block cipher chaining modes.

8.2.2

This is kind-of pointless, isn't it?  You just shouldn't use
algorithms known to be vulnerable to meet-in-the-middle attacks.  It's
usually a pretty obvious feature of an algorithm, so it's not like
this is some subtle thing.



_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg