1
$\begingroup$

I want to transform a semi random input to a shorter, uniformly random bit string. Assuming there is enough entropy in the semi random input, can I use a collision resistant hash function to extract randomness?

Update
After the first answer pointed out that the body of the question is not correctly asking the intended question, I didn’t want to edit the question, so that the answer given wouldn’t be confusing for the other readers. But the linked question, that is said to be duplicate, definitely does not answer my question.

$\endgroup$
5
  • 2
    $\begingroup$ Does this answer your question? I believe it does with detailed analysis of collision resistance and other hash function properties, if present. Can we assume that a hash function with high collision resistance also means a highly uniform distribution? $\endgroup$
    – kodlu
    Commented Nov 23, 2022 at 12:08
  • $\begingroup$ Collision resistance is not enough. Another example, $H(x) = x$ for 128 bits inputs. A hash function can be an extractor if you are willing and comfortable to see it as a random oracle. Which technically SHA256 is not in the general case. Alternatively, the HMAC construction is shown to be indifferentiable from a RO (even with fixed salt). So that's might be better assumption-wise. $\endgroup$ Commented Nov 23, 2022 at 13:11
  • 1
    $\begingroup$ To all who closed the question: the designated duplicate only answers the question in the body, not the question in the title; which is what the OP wanted to ask, if you look at comments to my answer. $\endgroup$
    – fgrieu
    Commented Nov 23, 2022 at 16:53
  • 1
    $\begingroup$ I also agree with fgrieu that the linked answer isn't relevant for the title of the question. $\endgroup$ Commented Nov 23, 2022 at 21:46
  • 1
    $\begingroup$ I posted a new question hopefully asking what the OP wanted to ask in the title of the present question. $\endgroup$
    – fgrieu
    Commented Nov 23, 2022 at 22:25

1 Answer 1

1
$\begingroup$

It's asked different things in title and body, leading to radically different answers.

Can I use a cryptographic hash function such as sha256 for Randomness Extraction ?

Yes for standard cryptographic hash functions including SHA-256, any SHA-2 or SHA-3 function, Blake2b (even SHA-1 or MD5 if one does not care giving a poor first impression), and any of their truncation. They are suitable to transform a semi random input into a shorter, uniformly random bit string, assuming there is enough entropy in the semi random input, and assuming that this input is not prepared with knowledge of hash function. To illustrate why that last condition is required: if the input $x$ was filtered or tweaked so that $\operatorname{SHA-256}(x)$ has it's first bit $0$, then $\operatorname{SHA-256}(x)$ would be easily distinguishable from random.


I want to transform a semi random input to a shorter, uniformly random bit string. Assuming there is enough entropy in the semi random input, can I use a collision resistant hash function to extract randomness?

No, in general. Collision resistance is not a sufficient property. E.g. the function defined by $F(x)=\operatorname{SHA-256}(x)\mathbin\|\operatorname{SHA-256}(x)$ is just as collision-resistant as SHA-256 is, but is not suitable for randomness extraction as it's output is easily distinguishable from random.

Collision resistance is not a necessary property either. E.g. SHA-256 truncated to it's first 8 bytes is not collision-resistant, but is suitable for randomness extraction.


Security is met if the entropy extraction function is a random member of a computationally secure Pseudo-Random Function Family (PRF).

Again, it's critical that the "semi random input" is not somewhat biased with knowledge related to the function used for randomness extraction. For example: no matter how large and random most of the input is, if one input bit is prepared with knowledge of the rest of the input and of the otherwise ideal extraction function, then it's easy to get the first bit of the output equal to 0 with probability near 75%.


Update following comment:

I found some (direct academic source of the "yes") for HMAC, but if the hash function is not keyed, would this still be the case?

Yes for any standard cryptographic hash function, if it's usable to instantiate a PRF (when the kind of length-extension property SHA-256 has does not matter). But I'm afraid I can't point a source, because my "not somewhat biased with knowledge related to the function used for randomness extraction" condition is both necessary, and hard to formalize other than as without knowledge of the key of a PRF, and there's no key in a hash. Hence the formal statement using HMAC, which has a key input and is an archetypal PRF.

We can rightly argue that the constants in the definition of a hash like SHA-256 in practice (and proof of the Merkle-Damgård construction used in SHA-256) plays the role of a key. It's widely believed that SHA-256 passes the PRF experiment when we use the 32-byte IV as key; and that's even provable under an ideal cipher model for the cipher underlying the Davies-Meyer compression function. But that's not part of the design goals of SHA-256, nor a very standard result, and we need lesser hypothesis to prove that HMAC is a PRF.

$\endgroup$
14
  • $\begingroup$ Could you point me to a source for your ‘yes’ answer? That was also my intuition but, I couldn’t find any direct academic sources, I found some for HMAC but if the hash function is not keyed, would this still be the case? $\endgroup$ Commented Nov 23, 2022 at 13:14
  • $\begingroup$ @ONUR EREN ARPACI: I can't point a source; see update. $\endgroup$
    – fgrieu
    Commented Nov 23, 2022 at 14:53
  • $\begingroup$ @fgrieu, couldn't you make a case for a generic case that in the random oracle model we have an extractor using a hash function? So we could use lemma 2 of eprint.iacr.org/2010/264.pdf? As you point out, SHA2 is not really a good generic random oracle. Hence, we require HMAC that can be proven indefferentiable from a RO. $\endgroup$ Commented Nov 23, 2022 at 15:24
  • $\begingroup$ @Marc Ilunga: yes, a random oracle can easily be proven to be a perfect random extractor function in the question's sense. But any hash is distinguishable from a random oracle when you know the hash's definition (just submit any particular message and compare the outcome to what the hash's definition imply). Thus we need a formalization of "the random input is not somewhat biased with knowledge related to the function used for randomness extraction", and the standard such formalization is a keyed PRF with key unknown to what generates the input of the random extractor. And hashes have no key. $\endgroup$
    – fgrieu
    Commented Nov 23, 2022 at 16:54
  • 1
    $\begingroup$ I would like to add that many CSPRNG's (or, rather, the better named DRBG's) within NIST SP 800-90Ar1 are based on hash functions, see section 10.1: DRBG Mechanisms Based on Hash Functions. The hash function used is commonly the only cryptographic primitive used to create the function. So if you have a hash and don't need top performance, you can just create an official DRBG out of it, possibly including things as reseeding and whatnot. For top security, base it off of HMAC (i.e. a PRF, see the answer), one of the options. $\endgroup$
    – Maarten Bodewes
    Commented Nov 24, 2022 at 14:16

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