Re: generic crypto

[Simon Josefsson]

Paul Eggert <address@hidden> writes:

> Simon Josefsson <address@hidden> writes:
>
>> * Perhaps the /dev/*random reading should be separated into a separate
>>   module?  It might be useful outside of the gc layer too.
>
> Absolutely.  I've been meaning to do that for months (for a "shuffle"
> program I want to add to coreutils), but hadn't gotten around to it.
> It would have to be generalized a bit.  I'd like to have the file
> descriptor cached, for example.

I'll write a separate module for that part.

I think we should even add a good PRNG that is re-seeded from
/dev/*random frequently.  GnuTLS can need a lot of random data on a
big server, more than /dev/random can supply.  And /dev/urandom might
not be strong enough.  Further, the security of /dev/*random can also
be questionable.

>>   I'm also not sure about the names of those functions, they suggest
>>   a more higher-level API than what is really offered (i.e., the
>>   names "nonce" and "pseudo_random" and "random" imply certain
>>   cryptographic properties).
>
> Could you expand a bit more on that?  What is the relationship between
> nonce/pseudorandom/random and the /dev/ values you are using?

There is none, that is the problem.

Applications generally need different kind of "random" numbers.
Sometimes they just need some random data and doesn't care whether it
is possible for an attacker to compute the string (aka a "nonce").
Sometimes they need data that is very difficult to compute (i.e.,
computing it require inverting SHA1 or similar).  Sometimes they need
data that is not possible to compute, i.e., it wants real entropy
collected over time on the system.  Collecting the last kind of random
data is very expensive, so it must not be used too often.  The second
kind of random data ("pseudo random") is typically generated by
seeding a good PRNG with a couple of hundred bytes of real entropy
from the "real random" data pool.  The "nonce" is usually computed
using the PRNG as well, because PRNGs are usually fast.

Pseudo-random data is typically used for session keys.  Strong random
data is often used to generate long-term keys (e.g., private RSA
keys).

Of course, there are many subtleties.  There are several different
kind of nonce:s.  Sometimes a nonce is just an ever-increasing
integer, starting from 0.  Sometimes it is assumed to be unlikely to
be the same as previous nonces, but without a requirement that the
nonce is possible to guess.  MD5(system clock) would thus suffice, if
it isn't called too often.  You can guess what the next value will be,
but it will always be different.

The problem is that /dev/*random doesn't offer any kind of semantic
guarantees.  But applications need an API that make that promise.

I think we should do this in several steps:

1) Write a module that can read from /dev/*random.

2) Add a module for a known-good PRNG suitable for random number
   generation, that can be continuously re-seeded.

3) Add a high-level module that provide various different randomness
   functions.  One for nonces, perhaps even different kind of nonces,
   one for pseudo random data, and one for strong random data.  It is
   not clear whether we can hope to achieve the last one in a portable
   way.

Further, it would be useful to allow users to provide their own
entropy source as a file, used to seed the PRNG or initialize the
strong randomness pool.  This is used on embedded platforms that
doesn't have enough interrupts to hope to generate good random data.

> For example, why not use OpenBSD's /dev/arandom?

I don't trust ARC4.  For example, recent cryptographic efforts
indicate that you must throw away the first 512 bytes generated from
the PRNG for it to be secure.  I don't know whether OpenBSD do this.
Further, I recall some eprint paper on RC4 security that didn't
inspire confidence.

While I trust the random devices in OpenBSD more than
Solaris/AIX/HPUX/etc, I think that since we need something better on
Solaris/AIX/HPUX we'd might as well use it on OpenBSD or even Linux
too.

> Here is one thought.  The user could specify a desired quality level
> range, and the implementation then would supply random data that is at
> least as good as the lower bound of the range.  I.e., ihe
> implementation refuses to produce any random data if it can't generate
> data that is at least as good as the lower end of the range.  The
> upper bound of the range is advice from the user not to be any more
> expensive than that, but the implementation can ignore the advice if
> it doesn't have anything cheaper.

I'm not sure this is a good idea.  Users can't really be expected to
understand this.  Further, applications need many different kind of
random data.  Selecting the randomness level for each by the user will
be too complicated.

I think it is better if the application decide, from its cryptographic
requirement, what entropy quality it require, and call the proper API.
Meeting the implied semantic properties should be the job for gnulib.

>> Perhaps gc_dev_random and gc_dev_urandom?
>
> To some extent.  I'd rather insulate the user from the details of
> where the random numbers come from.  On the other hand we need to
> provide a way for applications to specify a file that contains
> random bits, so that people can override the defaults.

Agreed.

This may require some thinking before it is finalized.  Is it ok to
install the GC module as-is meanwhile?  Then I can continue to add the
stuff that GnuTLS need, and then come back to re-working the
randomness module.  That way, we have two different projects that use
the code.  GnuTLS includes the same randomness code that was in GNU
SASL and that is in the current gc module.  I feel much more
comfortable working in small steps at a time, rather then working on
this for a long time in gnulib and only later integrate the stuff in
GnuTLS.

Thanks,
Simon