Bug 38417 - gnu.java.security.util.PRNG produces easily predictable values
Summary: gnu.java.security.util.PRNG produces easily predictable values
Alias: None
Product: classpath
Classification: Unclassified
Component: crypto (show other bugs)
Version: 0.97.2
: P3 critical
Target Milestone: 0.98
Assignee: Mario Torre
Depends on:
Reported: 2008-12-05 14:58 UTC by Jack Lloyd
Modified: 2009-02-13 10:53 UTC (History)
3 users (show)

See Also:
Host: x86_64-pc-linux-gnu
Target: x86_64-pc-linux-gnu
Known to work:
Known to fail:
Last reconfirmed: 2008-12-08 17:09:03

Java side of the testcase, creates a PRNG and produces 40 bytes of output (378 bytes, text/plain)
2008-12-05 15:03 UTC, Jack Lloyd
C++ testcase that searches nearby time values (552 bytes, text/plain)
2008-12-05 15:14 UTC, Jack Lloyd

Note You need to log in before you can comment on or make changes to this bug.
Description Jack Lloyd 2008-12-05 14:58:44 UTC
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.
Comment 1 Jack Lloyd 2008-12-05 15:03:53 UTC
Created attachment 16835 [details]
Java side of the testcase, creates a PRNG and produces 40 bytes of output
Comment 2 Jack Lloyd 2008-12-05 15:14:33 UTC
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
$  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.
Comment 3 Jack Lloyd 2008-12-08 10:15:07 UTC
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.
Comment 4 Mario Torre 2008-12-08 11:39:03 UTC
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?

Comment 5 Jack Lloyd 2008-12-08 12:10:19 UTC
Hi Mario. Sure, would be happy to. Should I attach it to this PR or send it to you privately?
Comment 6 Mario Torre 2008-12-08 12:29:59 UTC
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.

Comment 7 Jack Lloyd 2008-12-08 12:51:36 UTC
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.
Comment 8 Casey Marshall 2008-12-08 15:41:41 UTC
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.
Comment 9 Andrew John Hughes 2008-12-19 21:34:57 UTC
Any more news on a fix for this?
Comment 10 Mark Wielaard 2009-01-21 09:00:20 UTC
This is now also: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-5659
Comment 11 Andrew John Hughes 2009-02-03 15:46:24 UTC
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
       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
               * 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?
Comment 12 Jack Lloyd 2009-02-03 16:15:29 UTC

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.
Comment 13 Andrew John Hughes 2009-02-09 13:17:58 UTC
That's my understanding too, but I'd prefer Mario (who wrote the patch) confirm this.
Comment 14 Andrew John Hughes 2009-02-10 21:10:39 UTC
Was released in 0.98.
Comment 15 Andrew John Hughes 2009-02-13 10:53:19 UTC
Fix in 0.98.