Tue, 09 Dec 2008
Inspired by the recent FreeBSD arc4random vulnerability, I've been taking a look at the random number generators used by various libraries and operating systems. So far, problems in the JUCE C++ library and in the GNU Classpath PRNG have been identified. (I also checked out Mozilla's NSS, but did not spot any major flaws in that implementation.)
Syllable is a desktop OS based on AtheOS that provides what seems like a pretty decent desktop experience along with POSIX APIs and the GNU toolchain. My initial interest in the project was to get it installed under KVM and port my project botan to it.
Posted in security at 2008/12/09 13:20; 0 comments
Sat, 06 Dec 2008
Serious Weakness in GNU Classpath/gcj PRNG; DSA keys are compromised
GNU Classpath is an open source implementation of the Java class libraries used by gcj, the GNU Compiler for Java. One component of the Java library is JCE, the Java Cryptography Extensions (so called because originally it was not bundled with the JVM due to United States export restrictions), which provides the basic crypto features one would expect (ciphers, hashing, signatures) for Java applications.
For many RNG purposes, including creating private keys, DSA
k values, and SRP session ids, GNU Classpath uses
gnu.crypto.security.util.PRNG.
This PRNG uses a hash function, which by default is SHA-1 though others can be used instead. It is initialized with a random seed, and then values are generated by the recurrence
V(0) = H(seed) V(i) = H(seed || V(i-1))
The PRNG has an interface allowing the addition of new seed material at a later time, for instance a GUI application might seed it with mouse click event information.
Unfortunately there are two problems with how this PRNG is used in Classpath that in combination cause serious problems. One is a convention where each object, most of the time, gets its own PRNG. It seems that it is possible in some but not all cases to override the PRNG to be used, and there seem to be at least three different conventions for how to do it in Classpath. A representative example, from the RSA key pair generator code:
/** The optional {@link SecureRandom} instance to use. */
private SecureRandom rnd = null;
/** Our default source of randomness. */
private PRNG prng = null;
[...]
private void nextRandomBytes(byte[] buffer)
{
if (rnd != null)
rnd.nextBytes(buffer);
else
getDefaultPRNG().nextBytes(buffer);
}
private PRNG getDefaultPRNG()
{
if (prng == null)
prng = PRNG.getInstance();
return prng;
}
This class will use nextRandomBytes to choose starting
points for the RSA p and q values. Note that all
access to the prng itself is private, so an application developer
cannot, for instance, add new seed data to the PRNG.
The other problem is that by default the only seed used in
gnu.crypto.security.util.PRNG is the current timestamp in
milliseconds. This can be extended by setting a property
named "gnu.crypto.prng.md.seed", but I could not find out much more
about this because it does not seem to be used by any code at all
within Classpath.
Many cryptographic algorithms require a source of cryptographically
secure random numbers. For instance, DSA
requires choosing a new random 160-bit integer k for each
signature that is generated. If this k value is ever
revealed, the private key is immediately compromised, since it is
equal to (((s*k) - H(m)) * r-1) mod q (using the notation
from FIPS 186). Since GNU Classpath (in effect) chooses k
values by simply hashing the current timestamp in milliseconds with
SHA-1, it is quite simple to search for and find k.
Experiments confirmed that the output of
gnu.crypto.security.util.PRNG, as it is returned by
PRNG.getInstance(), is easily guessable using only the local
clock as the starting point for the search. This usage matches exactly
how this class is used throughout the GNU Classpath source.
There are less than 235 millisecond values in a year, which puts an upper bound on the security of any keys generated by this RNG, assuming an attacker can guess the year, which seems a reasonably safe bet. Even a decade contains barely 238 milliseconds. These values are far less than even the toughest export restrictions the United States ever imposed, which were typically 40 to 56 bits of security.
Classpath contains a number of other RNGs including
gnu.crypto.security.util.CSPRNG, which seems (at least at
first glance) to be somewhat safer. I would recommend adding
additional seed material, which would probably be sufficient, except
it seems in many cases that is not even possible. Unfortunately since
g.c.s.u.PRNG's use is hardcoded in nearly everywhere, it may be
difficult for applications to switch.
Update 2008-12-08: I've confirmed that the private half of a DSA keypair can be derived from the public key and a single signature/message pair, simply starting with a guess of the time the signature was generated. This basically means that every DSA key which has been used in an application compiled with gcj or using GNU Classpath/GNU crypto is (or at least can easily be, at any time) compromised. Based on the CVS history, it appears this flaw was originally introduced in GNU Crypto about 6 years ago, and was then imported into Classpath without alteration.
I've entered a bug report for Classpath describing the problem, but no response yet. After this is resolved (hopefully soon), I'll post the private key derivation code for examination.
An example vulnerable application is DSASigGen.java, which uses only the normal stock Java/JCE API calls to generate a random DSA key, sign an empty string (the exact value doesn't matter, as long as the message is known), and prints the public key and signature (the private key is printed to stderr by the Java code, just so I could confirm that the search code was in fact finding the correct key).
(motoko)$ gcj --version gcj (Gentoo 4.3.2 p1.2) 4.3.2 Copyright (C) 2008 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. (motoko)$ gcj --main=DSASigGen DSASigGen.java (motoko)$ ./a.out > pubkey_and_sig Private key is 286340495355822070335047169143648712734886086939 (motoko)$ cat pubkey_and_sig 308201b83082012c ... [(DSA public key truncated for readability / not screwing up formatting)] 302c02140f22be1f12e4c5950e1a4ff4cb7e269f3cd5b6f60214060ae0e5013a05ee2b1f719b49926b394424bde0 (motoko)$ g++ -O2 find_dsa_key.cpp -lbotan -o find_dsa_key (motoko)$ time ./find_dsa_key < pubkey_and_sig Found private key 286340495355822070335047169143648712734886086939 real 0m0.716s user 0m0.634s sys 0m0.054s
Update #2: According to the Wikipedia entry, other JVMs including Kaffe and JikesRVM use GNU Classpath. I have not checked if they are vulnerable (Kaffe is not building on my machine), but the odds are good. This may be a bigger issue than I first thought.
Update #3: I should emphasize that while DSA keys are the easiest target of this flaw, it is quite likely that all private keys (RSA, DSA, Diffie-Hellman, etc) generated by Classpath can be easily found, simply by guessing PRNG seeds and running through the key generation procedure until a private key corresponding to the known public key is produced.
Posted in security at 2008/12/06 11:11; 0 comments
Fri, 05 Dec 2008
"Anyone who considers arithmetic methods of producing random digits is, of course, in a state of sin." - John von Neumann, 1951
On an Ubuntu forum I caught a reference to a C++ library called JUCE, which is one of those all-inclusive C++ libraries along the lines of POCO or GNU Common C++. One thing I noticed was that it includes a few cryptographic operations, including RSA key generation, so I decided to take a peek at the latest release as of this writing, 1.46.
Tracing through the code, we find the primes for the RSA keys are
created by calling Primes::createProbablePrime, which
generates a random starting point and then uses a sieve to find the
nearest prime number. The random starting point is chosen on line 131
of juce_Primes.cpp, using
BitArray::fillBitsRandomly. This function in turn calls
Random::getSystemRandom() to actually get random data. So far
so good.
From the name "getSystemRandom", I assumed this would in turn use
an OS specific RNG like /dev/random on Linux/OS X or CryptGenRandom on
Windows. So you can imagine my horror to find that JUCE's 'system RNG'
is a linear
congruential generator, seeded with the constant value 1:
static Random sysRand (1);
Random& Random::getSystemRandom() throw()
{
return sysRand;
}
There are flaws at multiple levels here.
Posted in security at 2008/12/05 11:54; 0 comments
Wed, 03 Dec 2008
Thanksgiving 2008 Recipe Wrapup
Amanda and I made Thanksgiving dinner pretty much from scratch this year, and happily everything turned out very well!
Posted in food at 2008/12/03 17:16; 0 comments
Thu, 20 Nov 2008
Switching to Pyblosxom, and a colophon
Until recently I had been using on bitbashing blosxom, a minimalist blog system which stores each entry as a flat file on disk. My existing workflow relies heavily on tools like emacs for editing and merging and monotone for revision control, and it is nice to have a blog system that plays well with these other tools, rather than using, say, a MySQL database as the storage layer and an AJAX widget as editor. However over time blosxom has seemed less and less maintained, and I started looking for alternatives.
Today I switched to pyblosxom, which started as a clone of blosxom, and still has much the same philosophy, but seems to have many advantages and useful features as compared to blosxom. A description of the upgrade process along with a site colophon are after the jump.
Posted in about at 2008/11/20 19:53; 1 comment
[1] 2 3 4 5 6 7 8 >>