Timeline for Can I use a cryptographic hash function such as sha256 for Randomness Extraction
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2022 at 14:16 | comment | added | Maarten Bodewes♦ | 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. | |
| Nov 24, 2022 at 8:37 | comment | added | ONUR EREN ARPACI | Thank you for the discussion, this has been helpful. people.seas.harvard.edu/~salil/pseudorandomness/extractors.pdf In page 174 section 6.1.3, it says that you can’t have deterministic extractors for k-sources. And then there is this huge literature for deterministic extractors for specific source models (such as, link.springer.com/book/10.1007/978-3-642-14903-0 ) so even if the source is not adversarial (for example, radiation waves coming from sun), I am still not sure if using a specific cryptographic hash function solves the problem. | |
| Nov 23, 2022 at 22:24 | comment | added | Paul Uszak | Not really that hard. Left over hash Lemma, Piling up Lemma and von Neumann. I was generalising on the bit dropping, but there are papers featuring chaotic lasers that just take the lower bits. Didn't know that you were a fan of ENT. I've developed ent2 :-) | |
| Nov 23, 2022 at 22:13 | comment | added | Paul Uszak | @MarcIlunga I think that Mr. Grieu was suggesting that a cryptographically secure, non invertible extraction function is required. That's not the case. TRNG security comes from the underlying raw entropy stream. Entropy $\equiv$ security. The extractor function only has to change a wiggly wobbly distribution into a uniform one. E.g. von Neumann creates a 100% secure TRNG if the input is IID. HMACs are unnecessary. | |
| Nov 23, 2022 at 22:05 | comment | added | fgrieu♦ | @PaulUszak: an example of "semi random input" that no amount of bit dropping will turn "to a shorter, uniformly random bit string" is bits from a biased coin toss. And if I know that the output is conditioned by MD5, I can arrange that for "semi random inputs" with all bits truly random and a single apparently random other that I craft, the MD5 output consistently fails a thorough ENT test. The condition for robust randomness extraction when only "assuming there is enough entropy in the semi random input" is far from trivial! | |
| Nov 23, 2022 at 21:45 | comment | added | Marc Ilunga | @PaulUszak "Absolutely anything works that provides a uniform(ish) output", wouldn't this be a characterization of some notion of security? | |
| Nov 23, 2022 at 21:37 | comment | added | Paul Uszak | Re: "Security is met if..." There is no concept of security in randomness extraction functions. Absolutely anything works that provides a uniform(ish) output. XOR, bit dropping, CRC16, Pearson, MD5, anything that you've written yourself, e.t.c. It's one of the counter examples of why you can't roll your own algorithm in cryptography. | |
| Nov 23, 2022 at 21:19 | comment | added | Marc Ilunga | @fgrieu, yeah, that's a good point regarding independence. But if the keying material can be assumed to be independent, my question remains then: If H was shown indifferentiable from a RO, can't it then be a good extractor? With that said, in practice, I would always use a salted HKDF. | |
| Nov 23, 2022 at 18:07 | comment | added | fgrieu♦ | @Marc Ilunga: yes, a true random function is vulnerable. Lemma 2 in your reference succinctly repels that with "and independent from H", then discusses why that's necessary and what that means in no less than two paragraphs below the lemma. It ends up with "model H as a family of random functions indexed by a key rather than as a single deterministic function", so we are essentially back to what HMAC with a fixed key does, only it's not named HMAC. | |
| Nov 23, 2022 at 17:13 | comment | added | Marc Ilunga | @fgrieu, "just submit any particular message and compare the outcome to what the hash's definition imply", a true random function would be "vuneralbe" to this attack as well right? After all, even a random function is still deterministic for a fixed randomness. Correct me if I am wrong, but an indifferentiability (not indistinguishability) result on a given hash function would capture the fact that we could use it in place of a RO (modulo assumptions on the internals). | |
| Nov 23, 2022 at 16:54 | comment | added | fgrieu♦ | @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. | |
| Nov 23, 2022 at 15:24 | comment | added | Marc Ilunga | @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. | |
| Nov 23, 2022 at 15:11 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Nov 23, 2022 at 15:05 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Nov 23, 2022 at 14:57 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Nov 23, 2022 at 14:53 | comment | added | fgrieu♦ | @ONUR EREN ARPACI: I can't point a source; see update. | |
| Nov 23, 2022 at 14:52 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Update following comment
|
| Nov 23, 2022 at 13:14 | comment | added | ONUR EREN ARPACI | 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? | |
| Nov 23, 2022 at 13:08 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Nov 23, 2022 at 12:34 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Nov 23, 2022 at 12:24 | history | answered | fgrieu♦ | CC BY-SA 4.0 |