NetBSD Security Advisory 2013-003: RNG Bug May Result in Weak Cryptographic Keys (REVISED)

[NetBSD Security-Officer <security-officer%netbsd.org@localhost>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


                 NetBSD Security Advisory 2013-003
                 =================================

Topic:          RNG Bug May Result in Weak Cryptographic Keys (REVISED)

Version:        NetBSD-current:         affected prior to Mar 29th, 2013
                NetBSD 6.0.1:           affected
                NetBSD 6.0:             affected
                NetBSD 5.2.*:           not affected
                NetBSD 5.1.*:           not affected

Severity:       Cryptography Weakness

Fixed:          NetBSD-current:         Mar 29th, 2013
                NetBSD-6-0 branch:      Mar 29th, 2013
                NetBSD-6 branch:        Mar 26th, 2013

NetBSD 6.1 will contain the fix.  NetBSD 6.0.2 will contain the fix.

Please note that NetBSD releases prior to 5.1 are no longer supported.
It is recommended that all users upgrade to a supported release.


Abstract
========

Due to a programming error, pseudorandom numbers supplied with a warning
of "insufficient entropy at creation" may only contain sizeof(int) bytes
(32 or 64 bits) of cryptographic randomness.

The first attempt to fix this bug, on January 26, 2013, contained a
different programming error with the same effect.


Technical Details
=================

The NetBSD kernel uses an entropy pool to gather entropy from
system events, hardware random number generators, environmental
sensors, and other sources.  This pool is never directly accessed
by user processes nor by most kernel subsystems.  Instead, the
pool is used to key individual instances of a random stream
generator based on the NIST SP 800-90 CTR DRBG, per-consumer.

Each instance of the random stream generator itself mixes in local
data believed to contain additional entropy, or at least to be
difficult for an adversary to predict.  As each stream generator
runs, some additional such data are mixed in each time data are output.
This additional entropy consists of kernel-private statistics such as
per-thread context switch count and ticks on-cpu, as well as cpu
cycle counter timestamps.

When the kernel boots, it creates several instances of the random
stream generator very early.  Additional random number
generator instances may be created relatively early by, for example,
the sshd script generating keys when it first runs.

Because generators created very early may be keyed when the system
has very little entropy available, the system rekeys those generators
as soon as a "minimum entropy" threshold is passed, where the entropy
collection pool has enough bits to provide bits which are random in the
cryptographic sense: computationally infeasible to distinguish from
actual random noise.

However, internally, the pool has an "entropy estimator" which counts
how many bits have ever been put into the pool, for entropy consumers
who care about information-theoretic randomness rather than cryptographic
randomness.  If a consumer asks for "GOOD" bits rather than "ANY" bits,
the consumer will get only entropy-estimate worth of bits -- no more.

The code for keying the stream generators which actually supply bits to
kernel and user consumers requests GOOD bits and then, if it does not
get as many as it wanted, and the user has indicated that cryptographic
randomness is sufficient (for example, by opening /dev/urandom rather
than /dev/random) requests ANY bits for the remainder.

Other random-number-generator bugs have resulted in generators' output
having a very small number of possible states.  This bug is different:
the stream generator's output has the expected range of possible states,
but under some conditions, enough of the stream generator's input may
be guessable that it might be practical to reproduce its output by brute
force.

    The Original Bug
    ----------------

    Due to a misplaced parenthesis, if insufficient GOOD bits were
    available to satisfy a request, the keying/rekeying code requested
    either 32 or 64 ANY bits, rather than the balance of bits required
    to key the stream generator.

    The result of this bug is that even after the minimum entropy
    threshold was reached, the generators for in-kernel and userspace
    consumers could in the worst case be keyed, or re-keyed, with as
    few as 32 bits (on 32 bit platforms) or 64 bits (on 64 bit
    platforms) of data, plus a 32-bit cycle counter value, plus the name
    of the generator (an LWP ID for userspace, a fixed string for kernel
    consumers), two 32-bit cycle counter snapshots, a count of context
    switches, and a count of LWP ticks on-CPU, plus stack noise.

    The most conservative estimate is that cryptographic keys produced
    in this way contain only 32 bits (on 32-bit platforms) or 64 bits
    (on 64-bit platforms) of entropy.  A more optimistic estimate would
    assume that from an attacker's point of view, additional entropy
    (unpredictable bits, which must be guessed by brute force) are
    contained in the two cycle counter values and the LWP statistics.

    An additional consideration is that most consumers (including the
    OpenSSL and OpenSSH key-generation functions and utilities) access
    /dev/urandom via OpenSSL's RAND_bytes() function.  This function
    itself mixes in two addtional timestamp values (though these are
    in seconds, not cycles), and also due to its implementation imposes
    a variable delay between the two in-kernel cycle-counter
    measurements mentioned above.
    
    Nonetheless, we urge users to proceed according to the conservative
    estimate, but provide the optimistic estimate in the interest of
    full disclosure.

    The Mistaken Fix (code from 2013-01-26 until 2013-03-29)
    --------------------------------------------------------

    To fix the original bug, multiple instances of the code for
    keying stream generators were replaced by a single new function,
    cprng_entropy_try().  This function took a flag argument indicating
    whether the consumer wanted "hard" (information-theoretic) or "soft"
    (cryptographic) randomness.  If "hard" randomness was requested, the
    function returned only GOOD bits, leaving the remainder of the
    caller-supplied buffer untouched.  If "soft" randomness was requested,
    the function filled the rest of the caller-supplied buffer with ANY
    bits.  The function always returned a count of only as many bytes of
    GOOD data as it could obtain.

    The code calling the new cprng_entropy_try() function, however,
    reversed the sense of the flag argument.  This was missed by the
    original author and in code review.

    This could cause keying attempts originating from /dev/random device
    node opens to receive buffers with some GOOD and some ANY bits, but
    since the count of GOOD bits was correctly returned, the keying
    operations were retried before any data were output, and the result
    was merely less-efficient operation.

    However, keying attempts originating from /dev/urandom device node
    opens could receive only partially-filled buffers (with only as
    many GOOD bits as were available).  The code for this case did not
    force an immediate rekey of the generator, but rather scheduled it
    for rekey as soon as bits were available in the entropy pool (but
    in any event, after its next use, since use of the generator invokes
    the rekeying code).

    Rekeying would occur with full entropy, but in the worst case, the
    next generator output might contain *only* entropy from the
    generator name (process ID) two cycle counter values, and
    kernel-private LWP statistics.  If output was through OpenSSL's
    RAND_bytes function, additional entropy would come from that
    functions' implementation as discussed above.

    We do not know how to precisely quantify this entropy and urge
    that any keys generated on NetBSD-current or NetBSD 6 systems
    between 2013-01-26 and 2013-03-29 be regenerated, unless those
    systems are known to have not been in an "insufficent entropy"
    condition when the keys were generated (see discussion below).

    The correct fix always overwrites the entire caller-supplied buffer
    with output from the entropy pool and should be more robust against
    programmer error.
    
Systems which never experience an "insufficient entropy" condition
(for example, systems with hardware random number generators supported
by NetBSD) are not impacted by this bug.

All cryptographic keys generated on NetBSD 6 or NetBSD-current (prior to
2013-03-29) systems should be regenerated, unless it is certain that
the system in question cannot have suffered a low-entropy condition
when the keys were generated.

In particular, since ECDSA ssh host keys are new in NetBSD 6 and
are generated by /etc/rc.d/sshd at system boot if not yet present, it
is likely that for systems that have been updated to NetBSD 6.0 or a
netbsd-6 branch kernel before the fix date, ECDSA host keys have been
considerably weakened by lack of actual randomness, especially since
with little system uptime stack contents will be more predictable than
later.

For systems newly set up with NetBSD 6, all SSH host keys are suspect.

Other persistent cryptographic secrets (for example, SSH or SSL keys of
any type) generated using /dev/urandom on NetBSD 6 systems which may have
had insufficient entropy at key generation time may be impacted and should
be regenerated.

Signature algorithms based on the discrete logarithm problem can
disclose the private signing key if the nonce 'k' is predictable.
However, DSA and ECDSA keys used (but not generated) on systems with
this bug are believed to be safe.  This is because the OpenSSL
implementation of DSA signing feeds the digest of the message signed to
the OpenSSL random-number generator as ancillary input, with the result
that the nonce depends on the output of /dev/urandom, additional input
used to seed the OpenSSL RAND_bytes() generator, and the message itself,
and all bits from all inputs are well diffused across all bits output.

Solutions and Workarounds
=========================

Workaround:

Don't generate cryptographic keys, and don't use random numbers for
critical applications, on NetBSD 6 or NetBSD-current systems prior
to 2013-01-27, unless the system has sufficient "GOOD" entropy.  In
practice, this means reading from /dev/random rather than /dev/urandom
when using system entropy to generate cryptographic keys.

Fix:

Install a kernel containing the fix.

The fastest way to do that, if you are running or can run a standard kernel
built as part of the NetBSD release process, is to obtain the corresponding
kernel from the daily NetBSD autobuild output and install it on your system.

You can obtain such kernels from http://nyftp.netbsd.org/pub/NetBSD-daily/
where they are sorted by NetBSD branch, date, and architecture.  To fix
a system running NetBSD 6.0 or the stable NetBSD 6.0 branch, the
most appropriate kernel will be the "netbsd-6-0" kernel.  The "netbsd-6"
kernel can also be used; this is the branch that will become NetBSD 6.1.
To fix a system running NetBSD-current, the "HEAD" kernel should be used.
In all cases, a kernel from an autobuild dated 20130329 or newer must be
used to fix the problem.

If you cannot use the autobuilt kernels, then for all affected NetBSD
versions, you need to obtain fixed kernel sources, rebuild and install
the new kernel, and reboot the system.

The fixed source may be obtained from the NetBSD CVS repository.
The following instructions briefly summarise how to upgrade your
kernel.  In these instructions, replace:

  ARCH        with your architecture (from uname -m), and
  KERNCONF    with the name of your kernel configuration file.
  NEWVERSION  with the CVS version of the fix

Versions of src/sys/kern/subr_cprng.c:
        Branch          NEWVERSION
        ---------------------------
        HEAD            1.16
        netbsd-6        1.5.2.8
        netbsd-6-0      1.5.2.3.4.2

To update from CVS, re-build, and re-install the kernel:

        # cd src
        # cvs update -rNEWVERSION sys/kern/subr_cprng.c
        # ./build.sh kernel=KERNCONF
        # mv /netbsd /netbsd.old
        # cp sys/arch/ARCH/compile/obj/KERNCONF/netbsd /netbsd 
        # shutdown -r now

For more information on how to do this, see:

   http://www.NetBSD.org/guide/en/chap-kernel.html


Thanks To
=========

Ben Bucksch and Joachim Kuebart for discovering that the first attempt
to fix the bug in fact didn't.

Gregory Maxwell for pointing out that a discussion of ECDSA key use
was needed in addition to the discussion of key generation.

Thor Lancelot Simon for causing, finding, "fixing", and fixing the bug
and helping with this advisory.


Revision History
================

        2013-02-26      Initial release
        2013-03-07      Title change; stronger cautionary text; fix improved.
        2013-03-29      Initial fix wasn't.  Say so.  Improve technical
                        discussion.  Add discussion of ECDSA/DSA key use.


More Information
================

Advisories may be updated as new information becomes available.
The most recent version of this advisory (PGP signed) can be found at 
  http://ftp.NetBSD.org/pub/NetBSD/security/advisories/NetBSD-SA2013-003.txt.asc

Information about NetBSD and NetBSD security can be found at
http://www.NetBSD.org/ and http://www.NetBSD.org/Security/ .

Copyright 2013, The NetBSD Foundation, Inc.  All Rights Reserved.
Redistribution permitted only in full, unmodified form.

$NetBSD: NetBSD-SA2013-003.txt,v 1.5 2013/03/29 23:18:18 christos Exp $

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (NetBSD)

iQIcBAEBAgAGBQJRViMTAAoJEAZJc6xMSnBubd4QAJkAfHnu4omuVvtSQL68QA0J
au7CX8VbLFdLT25pfUq5Sm8KBC5Kh9mSltA+nFfjEmSFG67jc32thZMre4DKj7Sf
6UuAYjWPT0PU0LCgCuPA4iytcIk9kXmrW82Ozki7DrWOX4z456KUdwedbL5fhzFl
hbvaetm8KAtT27hM70uM6gsBQxa+HvdmSV5QZGgh3DRPpNGQC9f+oa9HyanqQMyM
g/tuQbmf3mUOsiiRjDXphkvKjioqr9k3G8/yC8fNAo12yS3ZEq/LD+rQ3sKcf6lk
L/Ja8AQ7nKGowu5ANtb/o0K6COil2oA60dkakvhMSYaX4MNnevwvScbVgN52RCuJ
fL3uSZ38J9q/3SBm4cEf1ASE6sdHUzl7jhTZf2J2ZUw+rH3jjKAPtvFAYfRxRCUZ
OsVL8NnGi592Y3ki0CVwNGfiHl8KnKDe+f+4fPI442/rWDsBO9/5qNGJdDaxx3Km
6a5q2CTwI8s9JaH71BZROnvAeD6NkoXL3SOSgNJi3UImE8fdL71ErmL7iHGBk9Uf
Y7MLz9tfCWCU5B5Jp5y/38eF2iQFiiAccaJG5hGR+I3XwO975Ym4ZvtOhFmD0oal
wDgP0PlLXb/Amo2ikOTfeuGXU/xhsh3z2tASUpKhaCruqcziYR/lRvn8b7ApSxNg
NcTCy2lcAhJNiMBT82/X
=yb+Y
-----END PGP SIGNATURE-----