1
$\begingroup$

I have 32-byte Keccak hashes and I have some maximum number, for example 500, how to uniformly convert those hashes to pseudo-random positive numbers up to that maximum?
I mean I have for example 100 quite random hashes and I want to distribute them so the result would be something like 80 numbers hit once, 19 twice and 1 hit three times (I guess something like that), somehow uniform distribution.
The maximum can be over 32-bits, so I need to use 64-bit integers.

Some approaches come to my mind:
a) always take first 8 bytes, convert them to 64-bit integer and use modulo 500 on them,
b) sum 1st 8 bytes, 2nd 8 bytes, 3rd 8 bytes and 4th 8 bytes to 64-bit integer and use modulo 500,
c) something better?

I know that modulo is not the best for uniform distribution, because it slightly prefers numbers at the beginning of the range, but I think I google how to overcome that by myself and I think it's not even a big deal.

The other thing I am not sure about is whether all the bits in Keccak hashes are quite uniformly distributed, but I guess they should be. I hope that some bit doesn't favor 0s or 1s so some numbers don't get an advantage during my conversion.

$\endgroup$
  • 2
    $\begingroup$ Is this question basically "how can I decode a base 64 string (which happens to be produced by keccak) then deserealize that into some set of ints?"? $\endgroup$ – Thomas M. DuBuisson Jun 22 '18 at 13:32
  • 1
    $\begingroup$ I don't know what is inside Keccak, I use it as 32 bytes. I put some example hash that could be shown, but I thought that inside every byte, there could be 0-255. $\endgroup$ – Salda Jun 22 '18 at 13:39
  • 1
    $\begingroup$ So your question is "what is the optimal strategy to get as many values sampled uniformly at random from my target range out of a given random string with bitwise uniformly random distribution"? $\endgroup$ – SEJPM Jun 22 '18 at 17:10
  • 1
    $\begingroup$ If you're asking how to get a uniform distribution from values which may not be uniformly distributed... Have you looked at en.wikipedia.org/wiki/Universal_hashing#Hashing_integers? $\endgroup$ – jadb Jun 22 '18 at 18:19
  • $\begingroup$ The input should be clear, it's 32-byte Keccak hash and I want to uniformly distribute it over a range of numbers. Edited question. $\endgroup$ – Salda Jun 23 '18 at 8:55
5
$\begingroup$

Your "32-byte Keccak hash" doesn't look like a canonical, binary Keccak output, but rather appears to be encoded with some Base64 variant—to me it appears to be the MIME version. Your comments on the matter confuse me whether that is the case or not; you should check your language or library's documentation.

If it's Base64 then it appears to be encoding a 18 bytes of raw binary output, which is 144 bits. This is a unusual output size. I would double check how your software is generating that output, and verify that all of that Base64 string really reflects a 144-bit Keccak output, and that there aren't some constant bytes being prefixed or suffixed to it. Again, your description and comments are not helpful in this regard.


Taking the modulo is fine in practice if you do it over a large enough input set. Appendix B of NIST SP 800-185 contains a recommendation that uses modulo to convert the output of an extendable output or variable length hash function into a near-uniform natural number $0 ≤ n < R$ for arbitrary $R$. The trick is that they make sure to do it over a hash output that is at least 128 bits longer than the number of bits needed to encode values in the output range:

  1. Compute $k = \lceil\log_2(R)\rceil + 128$, where $\lceil\log_2(R)\rceil$ is the number of whole bits needed to encode $R$ distinct values. For $R = 500$, this is $k = 9 + 128 = 137$.
  2. Hash your input to an output $Z$ with length of at least $k$ bits. Since your outputs are at least 144 bits, they meet this requirement.
  3. Convert $Z$ to some "bigint" data type (arbitrary precision integers, check library support in your language; e.g., in Java it's BigInteger). The bits_to_integer algorithm they detail in the document just parses $Z$ as a binary numeral with least significant bits first, although that later detail is not critical (e.g., Java BigInteger parses them in the opposite order, and that's just fine).
  4. Take $N = \mathit{bits\_to\_integer}(Z) \mod R$ as your result.

The trick that allows them to use modulo is that they're willing to accept a biased distribution if they can guarantee the bias is astronomically small. That's why they insist on taking a hash output 128 bits longer than the number of bits needed to encode $R$. Suppose we used $R = 500$ but $k = 9$ (instead of the recommended $k = 137$). The problem here is that since $2^k = 2^9 = 512$, when you take the modulo, 488 of the values have a probability of $1/512$ but 12 of them have a probability of $2/512$—they're twice as likely as the others.

Now suppose we take $k = 10$ instead, so $2^k = 1,024$. Now when you take modulo 500, there are 476 values in the range have a probability of $2/1,024$ but 24 of them have probability of $3/1,024$—they're only 50% more likely than the rest. For $k = 11$, $2^k = 2,048$ so you get 452 values with probability $4/2,048$ and 48 with $5/2,048$ (only 25% more likely), and so on. By the time you get to $k = 137$ the bias is negligible; footnote 12 of the appendix gives:

$$ |\mathrm{Prob}(N=t) - 1/R| ≤ 2^{-w} $$

...where $w ≥ \lceil\log_2(R)\rceil + 128$.

$\endgroup$
  • $\begingroup$ I updated the question, it is 32-byte Keccak hash, just the example was not good enough (I wanted it to look humanly readable..). $\endgroup$ – Salda Jun 23 '18 at 9:01
-3
$\begingroup$

Why not use method in the format keeping encryption. Sorry, it is format-preserving encryption. This is the wiki. https://en.wikipedia.org/wiki/Format-preserving_encryption
Its method can make the probability of each number be the same.

$\endgroup$
  • 2
    $\begingroup$ I'm pretty sure you mean "format-preserving encryption". Either way, you should try to go into more detail in your answer, or at least include a link to the relevant technique. $\endgroup$ – Ella Rose Jun 24 '18 at 0:56
  • $\begingroup$ Please edit your question to make the changes suggested by Ella or your post will keep accumulating downvotes. $\endgroup$ – SEJPM Jun 24 '18 at 9:44
  • $\begingroup$ Sorry, it is format-preserving encryption. This is the wiki. en.wikipedia.org/wiki/Format-preserving_encryption $\endgroup$ – Felix LL Jun 25 '18 at 9:43

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.