Java's SecureRandom & plaintext attack?

Java's SecureRandom is meant to be cryptographically secure, and I know part of that means that the output should not be usable to predict further output. Though, admittedly, my knowledge in the area is limited, and I'd like to test the limits to get an idea of how secure Java's SecureRandom really is.

So let's say I do this: I seed a SecureRandom with a secret long value (8 bytes) and then use it to encrypt 100 bytes of data by generating 100 bytes with the SecureRandom (right after seeding) and adding them to the original 100 bytes. Very silly of me, however, the original 100 bytes are all zeros, and you know this. Could you use some variant of a known-plaintext attack (or anything similar) to break my encryption? That is, could you determine the initial seed or predict the next values?

Okay, I need to specify it a bit more. I'm going to assume - as a worst case scenario - the SecureRandom implementation uses SHA1PRNG (that is SHA-1) as a mixing function. I know that this algorithm is considered to have some flaws, so then my question is whether - in the given circumstance - these flaws would allow for an easy break on the encryption; meaning one could determine the initial seed without great difficulty from the output. Meanwhile -in a better scenario - the mixing function would be SHA-256, and I still wonder if this situation would allow for vulnerabilities with that algorithm as well, other than brute force.

-
so your top secret original 100 bytes is your plaintext or some other value? Plus 8 bytes isn't that hard to brute-force. –  rath Jan 15 at 23:36
"Plus 8 bytes isn't that hard to brute-force" 2^64 is approximately 18.45 Quintilian (10^18) possibilities, so if your method of brute force is to try them all I'd say that's significantly above the capability to be brute forced...? –  user11424 Jan 17 at 8:10
@user11424: $2^{64}$ operations is no longer considered infeasible. Back in 1998, brute-forcing DES and its $2^{56}$ keys was a matter of 3 days with the EFF DES cracker, and Moore's law has allowed progress by more than $2^8$ since then. $2^{80}$ is still hard, but not inconceivable. $2^{128}$ is safe for a long time. –  fgrieu Jan 17 at 8:19
"operations is no longer considered infeasible" ahh I see you're probably right. I had forgotten about the ease with which encryption cracking can be run in parallel, using large numbers of processors to drastically reduce the time. Well at least that gives me one weakness, but I'd still like to know about whether it can be done much quicker or easier as in the original question. –  user11424 Jan 17 at 8:28
@user11424: Now that the challenge is removed and the question tidied, it is acceptable to me. However, are you aware that, as pointed in my first comment (now deleted), your encryption scheme is impractical, for it does not allow decryption with the key, if Java's SecureRandom obeys its own specification, which states that "SecureRandom must produce non-deterministic output" ? Also: it should be stated that the default SecureRandom generator of Java 7 is used, as I assume it is. –  fgrieu Jan 17 at 8:51

This answer has been updated a lot, again, after being accepted. I now base my analysis on simple functional equivalent source code to the deterministic PRNG used.

The cryptosystem proposed works, in the sense that it allows decryption. The best cryptanalytic method there is to predict further output is enumerating the 64-bit key by brute force. That's in the realm of feasible for a governmental organization: testing a key guess merely requires computing the SHA-1 of the key; then the SHA-1 of that; and comparing to the first 20 octets of known pad. Modern suitable resources are GPUs, FPGAs, or ASICs. I'm told that some commercial GPUs do 2.6G SHA-1 per second. That allows testing like 1.3G keys per second per GPU. On a farm of 1000 such GPUs, an attack is expected to last less than 3 months. I expect that a competent standard-cells ASIC design allows to improve that by a factor like 100 at constant power and cost, disregarding NRE that can be amortized over multiple other projects with similar requirements, such as password search, an industry that siphons untold budgets and power.

On first reading of Java's specification for SecureRandom, I thought that the proposed scheme would not allow decryption by the legitimate key holder, because of the "SecureRandom must produce non-deterministic output" fragment of that specification. However it turns out this is not a promise to a user, but a constraint, implying that "any seed material passed to a SecureRandom object must be unpredictable". My guess is now that the design intend is that the generator is deterministically seedable for conformance testing, and is seeded with true random in normal use, including automatically when not explicitly seeded.

SecureRandom does not by itself define either an algorithm or implementation, it is designed to support various named algorithms and allow access to various crypto-providers (such as HSMs, Smart Cards, or native OS implementations), with a default software-only crypto-provider implemented by an unspecified combination of Java bytecode on top of a JVM and possibly native primitives. As documented, SecureRandom's constructor "traverses the list of registered security Providers, starting with the most preferred Provider. A new SecureRandom object encapsulating the SecureRandomSpi implementation from the first Provider that supports the specified algorithm is returned".

I have experimentally verified that on a default installation of jdk-7u51-windows-x64, new SecureRandom() and SecureRandom.getInstance("SHA1PRNG") are the same deterministic generator when deterministically seeded before having produced any output (and appear non-deterministic whenever they have been used unseeded). The pseudo-random pad used in the question (which first 100 octets are known in the context) are as produced by:

// Produce a pseudo-random pad from a key using "SHA1PRNG" of the default provider,
// (which also is the default SecureRandom algorithm)
private static void orgSHA1PRNG (byte key[], byte pad[]) throws GeneralSecurityException {
SecureRandom rng = SecureRandom.getInstance("SHA1PRNG"); // or: = new SecureRandom();
rng.setSeed(key);
}


Based on the source code available here, I wrote a minimal piece of Java code that I verified produces the same output:

// On a default install of jdk-7u51-windows-x64, the following is equivalent to
// orgSHA1PRNG above, with reference only to SHA-1. Distilled from code found at
// http://www.docjar.com/html/api/sun/security/provider/SecureRandom.java.html
private static void eqvSHA1PRNG (byte key[], byte pad[]) throws GeneralSecurityException {
// initial state is the SHA-1 hash of the key
byte state[] = MessageDigest.getInstance("SHA").digest(key);
// while there is output to produce..
for(int j=0; j<pad.length+19; j += 20) {
// compute new output as the SHA-1 hash of the current state
byte hash[] = MessageDigest.getInstance("SHA").digest(state);
// copy the hash (possibly truncated) to the pad
// The documented INTEND is to perform
//    state = (state + output + 1) % 2^^160,
// with an increment of the first octet of state if the whole state is unchanged.
// This is performed considering variables as little-endian, and with a minor
// mess in carry propagation, due to the signedness of the  byte  type in Java.
int c = 1<<8;     // turns into the + 1 of the above formula
boolean z = true; // true when state is unchanged
for (int i = 0; i < 20; i++) {
c = (c >> 8) + state[i] + hash[i];  // partial result; can be negative !
byte t = (byte)c;                   // truncation to byte
z &= state[i]==t;                   // z becomes false when state changes
state[i] = t;
}
if (z)          // occurs with low odds
++state[0];
}
}


Simplified pseudo-code:

• compute state = SHA-1(key)
• while output is needed
• compute hash = SHA-1(state)
• use hash as up to 20 additional output octets
• state = state $\boxplus$ hash
• if the previous operation did not modify state, then
• increment the first octet of state.

where $\boxplus$ is some internal law on the set of 20-octet strings, remotely similar to addition $\bmod 2^{160}$ (the neutral element is the all-0xFF octet string, and most importantly a = x $\boxplus$ b always has a unique solution; $\boxplus$ is commutative; I'm uncertain about if $\boxplus$ is associative, but that's of secondary importance). More precisely, $\boxplus$ is addition performed by scanning octets from first to last (that's the reverse of addition within 4-octet words in SHA-1), and with a carry that is initially 1 then either -1, 0, or 1 (because the octets are considered signed two's complement). This is odd, but unlikely to introduce a cryptanalytic weakness.

There are two obvious weaknesses (none of them really exploitable in the context of the question):

• the generator enters a cycle with odds $p\approx(b/20)^2\cdot2^{-161}$ after $b\ll2^{84}$ octets;
• there is an attack recovering the state (thus allowing prediction of future output) with odds $p$, from $b\ll2^{84}$ octets of output, with expected effort less than $p\cdot2^{161}\cdot20/b$ hashes, and less than $b$ octets of memory.

The attack sketch goes:

• from the $b$ octets of output get $\lfloor b/20\rfloor$ values of hash and organize that for quick search
• repeat
• choose an arbitrary state (an incremental counter works)
• if SHA-1(state) is among the hashes
• if SHA-1(state $\boxplus$ SHA-1(state)) is among the hashes
• stop and output the guess state, which is correct with overwhelming odds.

I'm critical on the rationality of testing that state did not change (except, perhaps, when considering the possibility of malicious reseeding, using means not shown here), for that test and associated action does not significantly decrease the odds of entering a cycle (it only makes it impossible to enter a cycle of length 20, 10, 5, 4, 2, or 1 octets).

Even accounting for the known weaknesses of SHA-1, brute force for keys significantly less than $16$ octets might remain the least inefficient purely cryptanalytic attack for decades, considering $b=100$ in the question's statement. I'm discounting attacks on implementation, like compromise of the software integrity, side channels, and induced faults.

A quick search on SHA1PRNG returned an analysis report of 2009 (in French) hosted by usually serious officials, studying Java SE 6, with mention of substandard cryptographic post-processing and unexplained statistical anomalies in SHA1PRNG of the default Sun provider, reportedly detected using a standard entropy test of 500 MB output; leading to a JAVASEC rule #36 intended to mean: the developer should not use SHA1PRNG of the Sun Provider. I second the substandard cryptographic post-processing, but conjecture that the unexplained statistical anomalies are an artifact of the test method (the other option is that a standard entropy test managed to distinguish SHA-1 from a random function, which is next to unbelievable).

-
very nice updates - thanks for the great answer! –  user11424 Jan 20 at 18:38