9

I was wondering if generation of sequential hashes from random seed can be considered "random enough" to be used in cryptographic operations?

By sequential hashes I mean the following:

First we create a hash using e.g. SHA512 from a strong random seed number -> we get a first hash. Then we calculate the next hash using the previously calculated hash, then the next hash from that hash and so on...

Can the data generated this way be considered "random" enough to use in cryptographic operations where strong randomness is required, provided that the initial seed is random?

5
  • 1
    Do you mean you want to create a pseudorandom stream where the first 512 bits are SHA512(seed), the next 512 are SHA512(SHA512(seed)) and so on?
    – nobody
    Jul 30 at 8:25
  • @nobody basically yes, this was my idea Jul 30 at 8:40
  • 2
    Try instead SHA512(seed + n) where seed is a secret (it is very important to ensure its confidentiality) of at least 128 bits generated by a cryptographically secure PRNG (like /dev/urandom) and n is an integer incremented for each new block. Here, the symbol + is the concatenation operator, but it can be an addition if the seed is at least 256 bits long.
    – A. Hersean
    Jul 30 at 12:58
  • But if you have access to /dev/urandom, just use it directly instead.
    – A. Hersean
    Jul 30 at 13:00
  • Why not use PBKDF2 instead ? Jul 31 at 7:18
33

No this is cryptographically completely insecure

This construction violates a very important property of cryptographically secure PRNGs, namely that knowing one part of the PRNG's output does not help an attacker predict any other part of the output. However, in your construction, knowing one block of output allows the attacker to accurately predict all the the subsequent blocks of output.

Consider the case where the first block of the output is leaked to an attacker. Knowing the first 512 bytes of the stream means they know the output value of SHA512(seed). They can now compute the SHA512 on these 512 bits and derive SHA512(SHA512(seed)), which is the second block of output. Then they can compute another iteration of SHA512 on this second block, and derive SHA512(SHA512(SHA512(seed))), which is the third block, and so on.


Some people seem to be trying to improve this scheme to remove this vulnerability. Unless you are doing this purely as a thought experiment, please stop. Hash-DRBG/HMAC-DRBG already exist. While your improvement may plug this particular hole, cryptography is an incredibly difficult subject, and unless you are a professional cryptographer, you cannot tell if you are still introducing other subtle weaknesses into your scheme. Remember Schneier's Law:

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis.

6
  • 4
    But this assumes that the PRNG outputs the entire 512 bits of its internal state. What if it doesn't?
    – dan04
    Jul 30 at 19:20
  • @dan04 Any block will allow us to know all subsequent blocks. If we know SHA512^n(seed) we can calculate SHA512(SHA512^n(seed)).
    – Taemyr
    Jul 31 at 12:14
  • 3
    What about f(seed), f(g(seed)), f(g(g(seed))), ...? Jul 31 at 14:30
  • 1
    The sentence you quote is a little subtle and at first glance, appears to encourage "anyone" to create cryptography algorithms. The complete quote is "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis."
    – Stef
    Aug 1 at 21:55
  • 1
    @SolomonUcko That one doesn't have any really obvious vulnerabilities, but as the last quote says, that doesn't mean we should just use it. But for example, Dual_EC_DRBG uses this structure, so it may be interesting to note that it's relatively easy to add a backdoor by making f secretly invertible.
    – user253751
    Aug 2 at 10:21
8

No, a hash function can not be used directly to create cryptographically secure random data in general, even from a strong random seed. That being said, there might be hash-functions that also have this property.

The problem in inherent in the definition of a hash function, a hash function does not require the output to be pseudorandom in the first place. A cryptographic hash function must only fulfill the following properties:

  • Pre-image resistance
  • Second pre-image resistance
  • Collision resistance

These properties are not sufficient for creating a pseudorandom number generator. Using a hash-function h one can create the hash function g like: g(x) = 0^64 || h(x) where || denotes concatenation.

The function g will then also be considered to be a hash function because all three of those properties are fulfilled, but the first 64 bit are not random.

Also, as nobody mentioned, knowing the first 512 bit of your stream will allow an attacker to calculate all bits of the data stream, not a property you want from a pseudorandom number generator.

8
  • 3
    +1, while I agree with the point you are making, your first sentence seems a little inaccurate. Most common cryptographically secure hash functions can be used to make a CSPRNG. It's just that not all hash functions can be used for constructing a CSPRNG, which, as you say, is why we shouldn't try rolling our own crypto.
    – nobody
    Jul 30 at 15:05
  • 1
    @nobody Thank you for pointing that out, I added "in general" to the first sentence to make the statement more accurate.
    – Gamer2015
    Jul 30 at 16:05
  • 1
    @erickson I understand what you mean but you could also argue that you can use a feistel network to build a block cipher from a hash function and then use this block cipher in gcm or ctr mode to act as a stream cipher, which has the desired property. I said that hash functions can not be used for creating pseudorandom data, not that they can not act as a primitive to build upon. I will add the word 'directly' to the first sentence if this is a little ambiguous.
    – Gamer2015
    Jul 30 at 19:44
  • 1
    That helps. While their use must be qualified, saying hash functions generally can't be used for random generation struck me as misleading. Their use for this purpose is standardized and widely accepted, and the algorithm specifications stop at the level of abstraction of "hash function," just as block-cipher based DRGB specifications are not interested in the cipher implementation, only its properties.
    – erickson
    Jul 30 at 19:57
  • 1
    Your example g(x) is a hash function but not a cryptographic hash function; the three properties are not satisfied. Resistance is relative to the hash size... if a pre-image of a 128-bit hash can typically be found in 2**64 attempts, that is not considered resistant.
    – Ben Voigt
    Jul 30 at 21:27
6

Others have covered the flaws in your proposed solution, and why you should not roll your own crypto, so I won't rehash that.

If you do decide not to roll your own, and to use an existing algorithm, Hash_DRBG from NIST SP 800-90A Rev. 1 is a well-vetted deterministic random bit generator, that is built upon SHA-family hash functions. If you want a hash-based random bit generator, use that.

Using existing implementations (such as /dev/urandom) is an even better idea than using existing algorithms. Existing implementations of Hash_DRBG also exist, but I'm not familiar enough with them to recommend one.

6

The crucial test of the security of a proposed cryptographic PRNG is the next-bit test. That means, given some of the output of the PRNG, it should be impossible for someone to determine the next bit of the output with a probability better than 1/2 (that is, better than just guessing).

In your case, if we've seen 512 bits of the output, we can guess the next bits with probability 1: they'll be the SHA-512 hash of the bits we've seen.

There are two common designs that use cryptographic hash functions that are secure, and they're outlined in NIST's SP 800-90A Rev 1. These are the HMAC DRBG and the Hash DRBG.

I'll refer you to the documentation for the complete implementation, but roughly, the Hash DRBG works like this:

  1. Derive a seed from the input, and set V to the seed. Derive a variable C from V preceded by a zero byte. Set the reseed counter to 1.
  2. To generate data, set D to V. Hash D and put that in the output. Then add one to D, and hash it again for the next block of output, continuing until you've produced the desired amount of output.
  3. To update the state, hash V preceded by a byte with value 3, and call it H. Set V to V + H + C + the reseed counter. Increment the reseed counter.

Note that in this approach, the attacker doesn't ever see D, so they cannot determine the next output data from the previous data. This is ultimately the "hash of a hash", but the difference is that D is secret, not something we've output to the attacker.

There is also the HMAC DRBG, which in my opinion is easier to implement, because it uses a hash function with HMAC and doesn't require bignum arithmetic, which is error prone and may not be constant time. It's described in the same document. It's also used in RFC 6979 as part of deterministic DSA and ECDSA, and is widely considered to be strong.

In general, though, you should use the system's CSPRNG: getentropy, getrandom, arc4random, /dev/urandom, or RtlGenRandom, as appropriate. This will almost always be the right option and will be secure. Only if you are sure that you cannot use it or have other requirements should you implement one of these algorithms yourself.

5

It all depends on only the randomness (entropy) of the first random number (seed) only, in this case. So the answer is no.

You do not get more entropy by using more (deterministic) math.

6
  • So the answer is that the entropy of the output data is as good as the input seed? Is this also the case with any key expansion algorithm? Jul 30 at 7:09
  • Yes, this is also the case with any key expansion algorithm. An attacker just needs to go through the input space and calculate whatever you are doing. To get this into perspective though, a block cipher in CTR or GCM mode also creates a pseudorandom stream that is then used for encryption. The security is still as much as the key size in this case.
    – Gamer2015
    Jul 30 at 9:03
  • @Gamer2015 So does this mean, that I'm not losing anything by using this kind of algorithm provided that entropy of the initial input is sufficient for the purpose, attacker cannot see the previous hash result, and the hash algorithm has equal or more entropy (e.g. 512 bits in case of SHA512) compared to the input? Jul 30 at 9:50
  • 1
    It seems like what you are looking for is a CSPRNG. Cryptography is a dangerous area for doing stuff yourself, you might want to rely on implementations that have been tested and attacked for a long time. In the section "Designs based on cryptographic primitives" you can read more about using hash functions as a primitive for a CSPRNG.
    – Gamer2015
    Jul 30 at 10:24
  • It does not look like there are any well established CSPRNG's based on hash functions as opposed to using block ciphers as I mentioned above. I would guess your construction does not hold up to modern standards as this would have been an obvious design choice, I do not know where it would fail. One thing to consider though is that hash functions have do not necessarily have random outputs. Take SHA-256 and construct hash(x) = 0^256 || SHA-256(x) and you still get a hash function that is clearly not random, but fulfills collision resistance, pre-image resistance and second pre-image resistance.
    – Gamer2015
    Jul 30 at 10:25
3

What you describe is a sequence of deterministic operations based on some single initial random seed. The more pseudo random values you derive from the initial true random value, the less usable it gets for cryptographic operations (assuming that the attacker has some kind of visibility into all the values you derive). Thus "random enough" is not a yes or no but it depends on how much values you derive and what security you actually need for your specific purpose.

4
  • Could this kind of sequential hashing data generation be somehow improved to make it less "pseudo random" especially when large amount of random data is needed? Is this effectively a expansion algorithm? Jul 30 at 7:12
  • @Theamateurprogrammer: no deterministic method will magically add more randomness. You need to add true randomness for this. It is common to regularly add true randomness when large amounts of sufficiently random data are needed. Jul 30 at 7:19
  • Would SHA512(SHA512(SHA512(seed) + x) + x) and so on be a good idea where x is strong enought random number? Would this add entropy? Jul 30 at 8:43
  • @Theamateurprogrammer: "where x is strong enough random number" - you basically ask if enough is enough. Sure. "Would this add entropy?" - if entropy is part of "enough" then yes. For example, if each new x would be a new truly random number than this would add new randomness. If x is instead a predictable number than it would not. Jul 30 at 18:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.