The PRNG created in gnu.java.security.util.PRNG by PRNG.getInstance will by default use only the time in milliseconds as the internal seed. This is easily predictable. The algorithm itself seems fine (though with some more or less theoretical flaws, like the fact that it cannot recover from state compromise very well), but the lack of seeding may be a problem. In particular I note that g.j.s.u.PRNG is the PRNG class used by code including SRP, generating seed values for FIPS 186-3 PRNG, the generators for RSA/DSA private keys, and generating DSS signature k values (which is particularly relevant, since a design artifact of the DSA algorithm is that if even a single k value along with the associated signature is leaked or becomes known (or in this case, is easily guessed), it is easy to derive the private key using simple algebra). It seems the convention is for each class to instantiate its own PRNG. While this is in some ways good (at least an attacker might have to guess multiple timestamps), it also prevents the user from doing more thorough seeding (for instance reading some bits from /dev/random) and feeding it into the PRNG. I have written some proof of concept code that easily was able to replicate values produced by the PRNG, using nothing other knowing the current time and searching outward from there. Since there are less than 2**35 milliseconds values in any particular year, it should not be too hard for an attacker to be able to enumerate, for instance, all RSA keys that GNU classpath might possibly have created in 2008. I did testing with whatever version of classpath is included in GCC 4.3.2, but 0.97.2 looks unchanged in this regard.
Created attachment 16835 [details] Java side of the testcase, creates a PRNG and produces 40 bytes of output
Created attachment 16836 [details] C++ testcase that searches nearby time values Here is what I am seeing: $ g++ -Ibuild/include -L. guess_prng_output.cpp -o guess_prng_output -lbotan $ gcj --main=PRNGTest prng.java -o prng $ ./prng Time in ms is 1228509332707 e1bc6ebc96847774a843d3a73086a2f55b0bca86763729bb43fc4f3207966871e0be8a100efd4fc82 $ time ./guess_prng_output | grep -i =e1bc6 seed=1228509332707 hash=E1BC6EBC96847774A843D3A73086A2F55B0BCA86763729BB43FC4F3207966871E0BE8A00EFD4FC82 real 0m0.377s user 0m0.368s sys 0m0.006s Obviously it produces a lot of other guesses, but not nearly as many as one would hope it would take for it to guess a 320 bit long string. Based on some very rough timings and estimates, it looks like it would take about 8-12 hours to enumerate all keys for a year on a reasonably fast desktop machine. Maybe much less with a bit of optimization work, since key search is about the most embarrassingly parallel operation around and multicore chips are cheap.
I have confirmed that DSA private keys can easily be derived from the public key and a single message/signature pair when the app is compiled with gcj. It does not matter if the key was generated by gcj or something else; any DSA key used with gcj is easily compromised as long as the public key, message and signature are known, and the attacker has some starting guess as to what time the message was signed. Tested with 'gcj (Gentoo 4.3.2 p1.2) 4.3.2'. I can attach the victim and attack code, if desired.
We were working on a similar issue and I have some code that may fix this problem, I'll submit it as quickly as I can. Do you have a test case to reproduce all the steps so that I can test the fix? Thanks
Hi Mario. Sure, would be happy to. Should I attach it to this PR or send it to you privately?
Oh, good question :) I don't think security by obscurity does work, but making it a bit harder to crack systems is not a bad thing... You can send me privately for now. Cheers, Mario
I certainly agree now that the issue is known, it would not be terribly hard for someone to recreate the code to do this, but no real reason to make it easier either, at least until a fix can be created and tested. Code and example sent by email.
This is an artifact from GNU Crypto, and it's something I've always hated about that part of the code. We never (I don't think) came up with a good seeding mechanism in GNU Crypto itself -- the PRNG system supports seeding, of course, but we never came up with good, automatic seeding. This is really because it depends a lot on the runtime environment; on *nix, we'd likely go and use /dev/[u]random, and would do something else on Windows. gnu.java.security.util.PRNG is kind of a bad idea; code needing random numbers should use a SecureRandom -- ideally one that can be changed at runtime.
Any more news on a fix for this?
This is now also: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-5659
CVSROOT: /sources/classpath Module name: classpath Changes by: Andrew John Hughes <gnu_andrew> 09/02/03 21:02:59 Modified files: . : ChangeLog gnu/java/security/jce/prng: SecureRandomAdapter.java gnu/javax/crypto/jce/prng: ARCFourRandomSpi.java CSPRNGSpi.java FortunaImpl.java ICMRandomSpi.java UMacRandomSpi.java gnu/javax/crypto/prng: ICMGenerator.java Log message: 2009-01-22 Mario Torre <neugens@aicas.com> PR classpath/38417: * gnu/java/security/jce/prng/SecureRandomAdapter.java: (getSeed(int)): New; retrieve seed from source specified by securerandom.source property or failing that, use VMSecureRandom. * gnu/javax/crypto/jce/prng/ARCFourRandomSpi.java: (engineGenerateSeed(int)): Use SecureRandomAdapter. (engineNextBytes(byte[])): Initialise using new seed. * gnu/javax/crypto/jce/prng/CSPRNGSpi.java: (engineGenerateSeed(int)): Use SecureRandomAdapter. (engineNextBytes(byte[])): Initialise using new seed. * gnu/javax/crypto/jce/prng/FortunaImpl.java: (engineSetSeed(byte[])): Initialise with new seed if unused. (engineGenerateSeed(int)): Use SecureRandomAdapter. * gnu/javax/crypto/jce/prng/ICMRandomSpi.java: (engineGenerateSeed(int)): Use SecureRandomAdapter. (engineNextBytes(byte[])): Initialise using new seed. * gnu/javax/crypto/jce/prng/UMacRandomSpi.java: (engineGenerateSeed(int)): Use SecureRandomAdapter. (engineNextBytes(byte[])): Initialise using new seed. * gnu/javax/crypto/prng/ICMGenerator.java: (setup(Map)): Call fillBlock(). Can someone confirm this fixes the issue?
Andrew: If I am reading the diffs right, the change is that if the PRNG was not seeded with anything at the point output was requested, then 32 bytes are pulled from SecureRandomAdapter (which in turn uses either /dev/random or VMSecureRandom) to use as a seed. (Just want to make sure my understanding is correct). Looks good to me.
That's my understanding too, but I'd prefer Mario (who wrote the patch) confirm this.
Was released in 0.98.
Fix in 0.98.