1

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?

5
  • 1
    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
  • 1
    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.
    – Simon G.
    Nov 22, 2013 at 11:26
  • 1
    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?
    – Simon G.
    Nov 22, 2013 at 12:23

1 Answer 1

3

I accept this statement as true: 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.

However, I question the assumption derived from it: This would appear to significantly weaken the cipher. It is not now, nor will it ever be physically possible to test 2^165 possible keys, or to iterate through SHA-1 2^165 times.

Even if a significant breakthrough is made in AES-256 that allows an attacker to reduce the size of their attack, depending on the attack it could still require iterating through 2^165 SHA-1 outputs.

Therefore, I don't fully agree with the qualifier "significant", or that the keys produced are qualitatively "weak". (Yes, they are "weaker" than a 256-bit hash algorithm would produce, I'm only addressing the significance of that difference.) In the real, practical world we live in, the much more probable attacks will be made on the protocols that use this system, or on the security of the endpoints. Instead of trying to guess 2^165 possible random states, I would be trying to learn your internal state, or trying to inject my own state so that your output would no longer be random.

1
  • 1
    As an expert put it: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force......simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised." What I am describing is such a break.
    – Simon G.
    Nov 22, 2013 at 11:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .