[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