# Can SHA-1 PRNG still create secure cipher keys?

I am concerned that a SHA-1 PRNG cannot produce an AES-256 cipher key with the expected 256 bits of security, or indeed any secure cipher key where over 165 bits of security are expected.

The SHA-1 PRNG is the only pure-java secure random number generator provided by Java without third-party libraries. (I am fully aware third party libraries exist that offer other algorithms.) An implementation can be seen here. The algorithm starts with a state consisting of 160 bits drawn from an external source. As the algorithm uses this data it keeps track of which byte was last used, a number between one and twenty and requiring another 5 bits of information to represent.

Once the 160 bits are all used up, the next 160 bits are derived by calculating:

state(n+1)= state(n) + SHA1(state(n)) + I(SHA1(state(n))

where I(x)=1 if x=0 and I(x)=0 if x!=1

This is wholly determined by the existing 160 bits of state.

This means that if you give someone 165 bits of information, they can calculate the output from the SHA-1 PRNG at any future time. Therefore if I have an AES-256 cipher and I know the key was generated using SHA-1 PRNG I only have to test 2^165 possible combinations, not 2^256. This would appear to significantly weaken the cipher.

As the law of conservation of information says information can never be created, I see no way an algorithm whose internal state consists of only 165 bits of information can ever output 256 bits of information.

If this is true, and the SHA-1 PRNG as shipped with Java can only generate weak keys, what should one do?

Is there a resource that lists the number of bits of information a Secure PRNG function embodies so one can ensure the algorithm has more bits that the cipher key?

• If you really want 256 bits or security, use a stronger PRNG. But the difference between 160 and 256 bits is pretty theoretical since 160 bits is already far out of brute-force range. You should be far more concerned about 1) a badly seeded PRNG 2) Weaknesses in other parts of the system. Nov 21, 2013 at 21:21
• NSA might be able to break 90 bit keys (even that's very expensive), 160 bits is 10^21 times as expensive. Moore's law will break down long before we reach 2^160. It'd take a radical change in our understanding of nature to achieve that kind of computational power. Nov 21, 2013 at 21:28
• @CodesInChaos "A stronger PRNG"? Such as? Where can one find accepted definitions of such strengths? Cryptographers refer to a security system as broken if its strength is significantly reduced. This is such a reduction. The fact that 2^165 is still huge is irrelevant in cryptographic-speak, the security system is broken as its effective strength has been reduced. Nov 22, 2013 at 11:26
• It's only "broken" if you claim a higher security level than you achieve. A system using a SHA-1 based PRNG and AES-256 is not broken if you claim a security level of roughly 160 bits, but is broken if you claim 256 bits. Nov 22, 2013 at 11:34
• And how would anyone know that what strength to claim? Nov 22, 2013 at 12:23