[OTR-dev] solution for slow key generation

Greg Troxel gdt at ir.bbn.com
Tue May 20 07:45:49 EDT 2008


Thorsten Glaser <tg at mirbsd.de> writes:

> Jonathan complained that OTR key generation took about an hour on his NetBSD
> computer (he’ll probably provide specs if desired). I dug into the code and
> found out that this is because libgcrypt (sucky code…) uses /dev/srandom¹ for
> key generation entropy, which uses blocking reads.

Do you really mean srandom?  NetBSD provides

  /dev/random  (bits with actual entropy, will block until available)

  /dev/urandom (bits with entropy if available, and keep hashing if not
               available)

> While it didn’t take that long for me on MirOS – less than one minute – I’ve
> written a tool intended to be used as a contributed script, not to replace
> the code inside of libotr. This script² uses openssl for key generation, so
> Debian users should take care ☺ as not even using -rand helps with the bug
> they had. Other dependencies are mksh³, chmod, cat, and of course the openssl
> command-line tool. Add some suitable entropy source (can optionally be given
> as command line argument) or pull 32 (additional) bytes from me⁴ (this is a
> slow box on a slow ADSL connection, but it has good entropy quality⁵).

I'm not sure this is a good idea.  openssl ought to be using /dev/random
too.  If one wants to take bits that might not have adequate entropy,
one can just use /dev/urandom.

What I do is kick off a 'du /' to get lots of disk activity, which
replenishes the pool.

It really depends on whether you want to wait for good quality key bits,
or to get lesser quality bits faster.



RND(4)                  NetBSD Kernel Interfaces Manual                 RND(4)

NAME
     rnd -- in kernel entropy collection and random number generation

SYNOPSIS
     pseudo-device rnd

DESCRIPTION
     The rnd pseudo-device uses event timing information collected from many
     devices, and mixes this into an entropy pool.  This pool is stirred with
     a cryptographically strong hash function when data is extracted from the
     pool.

INTERNAL ENTROPY POOL MANAGEMENT
     When a hardware event occurs (such as completion of a hard drive transfer
     or an interrupt from a network device) a timestamp is generated.  This
     timestamp is compared to the previous timestamp recorded for the device,
     and the first, second, and third order differentials are calculated.

     If any of these differentials is zero, no entropy is assumed to have been
     gathered.  If all are non-zero, one bit is assumed.  Next, data is mixed
     into the entropy pool using an LFSR (linear feedback shift register).

     To extract data from the entropy pool, a cryptographically strong hash
     function is used.  The output of this hash is mixed back into the pool
     using the LFSR, and then folded in half before being returned to the
     caller.

     Mixing the actual hash into the pool causes the next extraction to return
     a different value, even if no timing events were added to the pool.
     Folding the data in half prevents the caller to derive the actual hash of
     the pool, preventing some attacks.

USER ACCESS
     User code can obtain random values from the kernel in two ways.

     Reading from /dev/random will only return values while sufficient entropy
     exists in the internal pool.  When sufficient entropy does not exist,
     EAGAIN is returned for non-blocking reads, or the read will block for
     blocking reads.

     Reading from /dev/urandom will return as many values as requested, even
     when the entropy pool is empty.  This data is not as good as reading from
     /dev/random since when the pool is empty, data is still returned, degen-
     erating to a pseudo-random generator.

     Writing to either device will mix the data written into the pool using
     the LFSR as above, without modifying the entropy estimation for the pool.

RANDOM SOURCE STRUCTURE
     Each source has a state structure which the kernel uses to hold the tim-
     ing information and other state for that source.

           typedef struct {
                   char            name[16];
                   uint32_t       last_time;
                   uint32_t       last_delta;
                   uint32_t       last_delta2;
                   uint32_t       total;
                   uint32_t       type;
                   uint32_t        flags;
           } rndsource_t;

     This structure holds the internal representation of a device's timing
     state.  The name field holes the device name, as known to the kernel.
     The last_time entry is the timestamp of the last time this device gener-
     ated an event.  It is for internal use only, and not in any specific rep-
     resentation.  The last_delta and last_delta2 fields hold the last first-
     and second-order deltas.  The total field holds a count of how many bits
     this device has potentially generated.  This is not the same as how many
     bits were used from it.  The type field holds the device type.

     Currently, these types are defined:

     RND_TYPE_DISK  The device is a physical hard drive.

     RND_TYPE_NET   The device is a network interface.  By default, timing
                    information is collected from this source type, but
                    entropy is not estimated.

     RND_TYPE_TAPE  The device is a tape device.

     RND_TYPE_TTY   The device is a terminal, mouse, or other user input
                    device.

     RND_TYPE_RNG   The device is a random number generator.

     flags is a bitfield.

     RND_FLAG_NO_ESTIMATE  Do not assume any entropy is in the timing informa-
                           tion.

     RND_FLAG_NO_COLLECT   Do not even add timing information to the pool.

IOCTL
     Various ioctl(2) functions are available to control device behavior,
     gather statistics, and add data to the entropy pool.  These are all
     defined in the <sys/rnd.h> file, along with the data types and constants.

     RNDGETENTCNT    (uint32_t) Return the current entropy count (in bits).

     RNDGETSRCNUM    (rndstat_t)

                           typedef struct {
                                   uint32_t       start;
                                   uint32_t       count;
                                   rndsource_t     source[RND_MAXSTATCOUNT];
                           } rndstat_t;

                     Return data for sources, starting at start and returning
                     at most count sources.

                     The values returned are actual in-kernel snapshots of the
                     entropy status for devices.  Leaking the internal timing
                     information will weaken security.

     RNDGETSRCNAME   (rndstat_name_t)

                           typedef struct {
                                   char            name[16];
                                   rndsource_t     source;
                           } rndstat_name_t;

                     Return the device state for a named device.

     RNDCTL          (rndctl_t)

                           typedef struct {
                                   char            name[16];
                                   uint32_t       type;
                                   uint32_t       flags;
                                   uint32_t       mask;
                           } rndctl_t;

                     Change bits in the device state information.  If type is
                     0xff, only the device name stored in name is used.  If it
                     is any other value, all devices of type type are altered.
                     This allows all network interfaces to be disabled for
                     entropy collection with one call, for example.  The flags
                     and mask work together to change flag bits.  The mask
                     field specifies which bits in flags are to be set or
                     cleared.

     RNDADDDATA      (rnddata_t)

                           typedef struct {
                                   uint32_t       len;
                                   uint32_t       entropy;
                                   u_char          data[RND_POOLWORDS * 4];
                           } rnddata_t;

FILES
     /dev/random    Returns ``good'' values only
     /dev/urandom   Always returns data, degenerates to a pseudo-random gener-
                    ator

SEE ALSO
     rndctl(8), rnd(9)

HISTORY
     The random device was first made available in NetBSD 1.3.

AUTHORS
     This implementation was written by Michael Graff <explorer at flame.org>
     using ideas and algorithms gathered from many sources, including the
     driver written by Ted Ts'o.

NetBSD 4.0_RC1                 October 12, 1997                 NetBSD 4.0_RC1




More information about the OTR-dev mailing list