1
$\begingroup$

(I cleaned up the question a bit, It was previously titled "extracting entropy without hashing" .. thus some of the comments / answers)

I'd like to extract the entropy of data without injecting "pseudo" entropy. For example, let's say I have a series of bytes, but only the low bit is changing (or something is changing that I'm not aware of beforehand) - how can I just output that low bit?

Is there a known way to extract the random part of the data without doing custom programming for each different type of data series?

edit: To clarify, I'm looking to extract only the random part. Eg, assuming F is the magical function, I want:

Length (F(X)) = # of bits of min-entropy in X.

As has been pointed out elsewhere, this is probably impossible to do automagically with any reasonably assured level of confidence in its real accuracy.

$\endgroup$
7
  • 1
    $\begingroup$ Why do you want to avoid hashes? $\endgroup$ Sep 23, 2013 at 8:49
  • $\begingroup$ Because it injects pseudo entropy. I'm looking for an alg which just extracts the entropy. $\endgroup$
    – Blaze
    Sep 23, 2013 at 11:02
  • 1
    $\begingroup$ If you manage to estimate entropy, then you can still simply truncate the hash to the estimated entropy. Entropy estimation and extraction are mostly independent. $\endgroup$ Sep 23, 2013 at 12:33
  • $\begingroup$ Ok, so now we just need an alg to estimate the entropy. $\endgroup$
    – Blaze
    Sep 23, 2013 at 19:42
  • $\begingroup$ I don't know what you mean by "inject pseudo entropy". A hash does not inject entropy. I'm not familiar with "pseudo entropy" as a technical term. Can you tell us more about what your real problem is? You might want to edit the question to provide more context and to explain the particular application setting and what you're trying to achieve or what problem you're trying to fix. $\endgroup$
    – D.W.
    Oct 2, 2013 at 6:09

3 Answers 3

3
$\begingroup$

For randomness extraction, in some cases, you could use alternatives to hash functions. However, mostly hash (or hmac) is preferable, because hash and hmac are very good in extracting randomness.

RFC 5869 describes HKDF, HMAC-based extract-and-expand key derivation function, with randomness extraction and expansion phase. NIST has made equivalent standard from HKDF, NIST SP 800-56C, which also allows AES-CMAC as alternative to HMAC. Thus, NIST SP 800-56C compliant randomness extraction can be done without hash functions by using AES-CMAC instead.

However, NIST SP 800-56C is only usable when there is a good reason to expect that input contains sufficient entropy to meet the intended entropy of the output.

Another obvious approach is that you could create NIST SP 800-90A Deterministic Random Bit Generator using AES-CTR algorithm with derivation function. The randomness you want to extract could be input entropy to the algorithm.

Estimate entropy

However, for both of uses described above, you need good means to estimate how much entropy you have within the input. If you use something like NIST SP 800-56C and you did not have enough entropy in input, you don't have lot of entropy in output either. For this reason, it is critical you can correctly estimate how much entropy you have.

Usual compression functions, for example, like CodesInChaos mentioned above are not good enough, for determining the amount of entropy. They can give pointers. Just never expect a compression function to produce full entropy.

Linux kernel's /dev/random uses various mathematical means to estimate amount of entropy present in the events in information theoretic sense. This is in fact something pretty close to compression. However, it does not actually compress anything, but instead selects entropy estimate which is strictly smaller than any compression approach it could have used. A lot of information about Linux /dev/random is in this analysis. The analysis is old, and the issues found are largely fixed, but the basic structure remains the same.

For estimating the amount of entropy, it is necessary to understand what kind of input materials you have. Software like ent are useful to make estimate, but it is not at all hard to find materials where ent will overestimate entropy. For instance, try estimate entropy of AES-CTR(128 x 0 bit, 1024 x 0 bit). This input has around zero bits of input, but ent will estimate it to have nearly 1024.

I would almost say that if you cannot indicate what the input material is (unfortunately commonly the case), and you feel ent or compression are good enough, you're very likely to end up with system that is not very strong (because you most likely will overestimate entropy).

$\endgroup$
1
  • $\begingroup$ Yeah, though perhaps there is some middle ground. Wish there were more tools I could use to crunch the data. $\endgroup$
    – Blaze
    Oct 2, 2013 at 20:07
3
$\begingroup$

The best answer is almost certainly to use a cryptographic hash.

Your reason for avoiding a cryptographic hash makes no sense to me. Your problem does not explain the motivation for your question, but I suspect you've fallen prey to the XY problem (see also here).

You haven't told us what you're ultimately trying to accomplish, but I suspect the right answer in practice is ultimately going to be:

  1. Use /dev/urandom to generate cryptographic-quality pseudorandom numbers.

  2. If you have a source of entropy, feed it into /dev/urandom (e.g., cat somekindarandombits > /dev/urandom), then see step 1 above.

Internally, this effectively uses a hash.

I also recommend you read the following:

$\endgroup$
10
  • $\begingroup$ The answer I suspect is what codes in chaos said above in his comments. What I'm really looking for is a way to estimate entropy. And, what I've come to realize, is that there is no "ent" utility you can run that magically does this, but rather it's a combination of heuristic + statistical analysis. Painful, but necessary because of the hidden patterns in seemingly random data that can't be pried out by mere software. Automated entropy estimation simply fails (which is why dev/random is no good) $\endgroup$
    – Blaze
    Oct 2, 2013 at 9:23
  • $\begingroup$ As for the reason I want to do this, I'm under NDA sadly! Still, the problem of entropy estimation I think is something everyone might be interested in. $\endgroup$
    – Blaze
    Oct 2, 2013 at 9:35
  • 1
    $\begingroup$ @Blaze could you edit your question to contain the actual problem, instead of hiding it in a comment? $\endgroup$ Oct 2, 2013 at 18:50
  • $\begingroup$ @Blaze, careful there. There is no good way to do accurate entropy estimation (at least not in general, without knowing anything about the source). But be careful about what inferences you draw. That doesn't mean /dev/random is no good. In general, there's a lot of work on this sort of topic; I encourage you to read up on it before drawing too many conclusions. $\endgroup$
    – D.W.
    Oct 2, 2013 at 19:27
  • $\begingroup$ I have read up on it, and the entropy estimator is often the root of its problems. It's why Fortuna, Barak and Halevi, etc have been advocated. $\endgroup$
    – Blaze
    Oct 2, 2013 at 19:47
2
$\begingroup$

Yes, this can be done with strong extractors and strong blenders.

$\endgroup$
7
  • $\begingroup$ I looked at that stuff, my concern was that the fixed length of the output would be greater than the amount of entropy in the input. $\endgroup$
    – Blaze
    Sep 22, 2013 at 23:33
  • 1
    $\begingroup$ You need to assume something about the data. $\:$ Would you prefer to assume that the data is divided $\hspace{.12 in}$ into independent blocks, or even iid blocks, rather than a lower bound on its smoothed min-entropy? $\hspace{.27 in}$ $\endgroup$
    – user991
    Sep 23, 2013 at 0:29
  • 1
    $\begingroup$ @Blaze It's impossible to estimate the entropy of an input without context, so you can't limit the output size to the entropy, no matter which extractor you use. $\endgroup$ Sep 23, 2013 at 8:51
  • $\begingroup$ I disagree that it's impossible. To get something completely accurate, yes, that's probably impossible. But I can think of one rough method - compression. What if I take a large byte stream and run a compression utility on it. That should give me a rough idea of the entropy bits in the input. $\endgroup$
    – Blaze
    Sep 23, 2013 at 10:42
  • 2
    $\begingroup$ Compression gives you an upper bound, but for security you need a lower bound. Generic compression routines will probably overestimate entropy so much that they're useless. $\endgroup$ Sep 23, 2013 at 11:22

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.