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 2008/12/09 13:20 [category: bitbashing / security]
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 2008/12/06 11:11 [category: bitbashing / security]
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 2008/12/05 11:54 [category: bitbashing / security]
Sat, 25 Oct 2008
Robot packs will hunt 'non-cooperative' humans
A new Pentagon project proposal for a "Multi-Robot Pursuit System" will allow soldiers and police to "search for and detect a non-cooperative human".
posted 2008/10/25 15:46 [category: bitbashing / security]
Sun, 12 Oct 2008
Interesting W3C Workshop - Security for Access to Device APIs
Thomas Roessler posted a call for papers for a W3 workshop on secure device access for web applications:
posted 2008/10/12 14:25 [category: bitbashing / security]
Mon, 23 Jun 2008
Steve Dekorte asks DRM opponents how they would feel about the bits representing their fingerprints, genome, car keys, and mental state (I would add also personal finances and cryptographic keys) being copied around willy-nilly, and suggesting that perhaps these people really do want DRM, just not for things they want to copy.
Getting DRM to actually work seems to imply replacing our current computers and networks with essentially closed systems. This seems like trading something for nothing, because frankly, the only entities that I would really worry about trafficking in my fingerprints and genome (and my mental state, if that turns out to be readable outside of an MRI tube) is the federal government, who would just write the rules to suit their needs. If there is anything in our modern era that trumps Disney, it's "national security".
posted 2008/06/23 09:03 [category: bitbashing / security]
Mon, 16 Jun 2008
The bond insurers MBIA and Ambac are going bankrupt because they wrote insurance for mortgage backed securities which are now failing at rates far higher than they had estimated. This is a pretty common problem with insurance; humans tend to be really bad at estimating or pricing risk.
posted 2008/06/16 12:18 [category: bitbashing / security]
Thu, 15 May 2008
A post on Ben Laurie's blog is among the more frightening things I've read recently:
I've reached my goal of writing a totally transparent firewall bypass engine for those firewalls which are PC-based: you simply overwrite the firmware in both NICs and then perform PCI-to-PCI transfers between the two cards for suitably formatted IP packets (modern NICs have IP "offload engines" in hardware and therefore can trigger on incoming and outgoing packets).
From the report, it seems some Ethernet cards will allow for firmware updates that arrive over the wire!
More details in Ben's post.
And if anyone knows how one subscribes to the Robust Open Source mailing list, let me know. That there are no hits on Google, and the lack of public archives, suggests it is by-invite only...
posted 2008/05/15 12:58 [category: bitbashing / security]
Wed, 14 May 2008
Reading the documentation for Java's File object, I was astounded to find that the Java designers managed to replicate one of the best known file system race conditions for no good reason: the functions canRead and canWrite are essentially the Java equivalents of the access function, which is so well known to be a security hole that the Linux man page actually warns that:
Using access() to check if a user is authorized to e.g. open a file before actually doing so using open(2) creates a security hole, because the user might exploit the short time interval between checking and opening the file to manipulate it.
While OpenBSD provides the less ambiguous caveat that:
access() is a potential security hole and should never be used.
This comes up in several contexts, including when trying to allocate a temporary file. A classic (flawed) pattern for this task is to generate a random filename (usually situated in a shared directory like /tmp), call access to see if the file exists, and if not, open up that filename and use the returned file object as a scratchpad. The problem is if someone else is racing you: in between the time access returns and the file is opened, an attacker can create that file and "capture" your open call. One common (if not particularly inventive) attack is to create the file as a symbolic link to a file owned by the victim. The victim's process will (on ACL-based systems like Windows, MacOS X, or Unix) have full access rights to all of their files, so it will happily stomp on something important without ever realizing it. This is a great example of the confused deputy problem: a non-malicious program is tricked by a third party into using its authority in unintended ways.
I don't believe there is any situation where an application can use these functions safely. At best, they can provide "early failure" to additional user friendliness, in the same way that doing input validation of a web form in JavaScript can. But in both cases, in the end you can't trust the results.
An additional comment: these functions will throw a SecurityException if the security manager forbids read or write access to the files. But this is in direct violation of the semantics of the functions: if attempts to actually read or write the file will be forbidden by the security manager, then a function that "Tests whether the application can read[/write] the file denoted by this abstract pathname." should simply return false (because the application cannot read/write that file), not fail with an exception. Bizarre!
posted 2008/05/14 14:56 [category: bitbashing / security]
Thu, 01 May 2008
Microsoft has developed a 'forensics tool' named COFEE (Computer Online Forensic Evidence Extractor), with some interesting capabilities:
The device contains 150 commands that can dramatically cut the time it takes to gather digital evidence, which is becoming more important in real-world crime, as well as cybercrime. It can decrypt passwords and analyze a computer's Internet activity, as well as data stored in the computer.
The article itself is not terribly interesting, spending most of its word count discussing the terrible dangers of "anonymous predators or those with false identities" on social networks - something which COFEE seems completely unrelated to. But I did find it interesting, because the existence of COFEE raises the question: did Microsoft intentionally backdoor their own systems, or is the authentication and authorization model in Windows so weak that anyone else could do the same thing without special privileges? Given the existence of USB autorun hacks, and that most users still run as full-rights Administrators, I lean towards the latter.
But the ability to decrypt passwords seems curious. While both the LM and NTLM password hashing schemes are pretty terrible, I don't see how they could be easily decryptable without a fairly huge back door (or unless they somehow managed to fit a Rainbow table on the flash drive). However since the article never states explicitly what sorts of passwords are under discussion, it's possible COFEE only attacks IE passwords or something like that. But, again, this implies that either Microsoft left themselves a backdoor, or that the password hashing scheme used in IE (or whatever it is COFEE can recover passwords from) is quite fatally weak.
Meandering somewhat off the main topic - while writing this, I came across an article on Microsoft's TechNet magazine that set off a lot of red flags for me. If a "senior security strategist in the Microsoft Security Technology Unit", who has access to the source code, spent years not understanding how Microsoft's authentication systems work (versus how they are documented to work), and finally had to go read Samba documentation to figure it out, what hope is there for anybody else? I'm pretty convinced that nobody really understands Windows; even the best Windows sysadmins I've known, and indeed several Microsoft system engineers I've met, really had very little insight into how the whole thing works, but still... damn. I suspect this effect is partially due to their strongly silo'd development and security review model.
posted 2008/05/01 14:06 [category: bitbashing / security]