3
$\begingroup$

Let msg be some data we want to hash using an arbitrary digest size algorithm such as blake2b. From that hash, we would like to compute a checksum field with n decimal digits.

If we suppose that the hash algorithm has a perfect distribution, we would like to design the checksum with a probability of collision as low as possible, ideally 1/10n.

Let n be in the range 1..10 (1 digit checksum to 10 digits checksum).

For each value of n, what would be the safest way to calculate a checksum of size n?

More specifically, what size of digest should we aim for every size of n and how should we reduce the value of the hash h to a decimal number.

E.g.: For n = 2 (2 checksum digits):

a) digest_size = 1, checksum formula = h mod 100

b) digest_size = 4, checksum formula = h mod 97

If the formula used to reduce the hash h to a checksum is h mod p, are there optimal values of p and digest_size for each value of n?

$\endgroup$
  • $\begingroup$ If "an arbitrary digest size algorithm" is a digest algorithm with output a bitstring (or bytestring) digest of size $b$: consider a mapping $f$ of such digests to $n$-digit checksum, compute odds that $f(h)=f(h′)$ under assumption $h$ and $h′$ are random, from the number of digests reaching each given checksum; show that if $f$ is such that any two of these numbers differ by more than 1, there exists a better $f$ (with less odds of collisions); conclude that $f(h)=h\bmod p$ is optimum for some choice(s) of $p$, and which; compute the odds of collision and the influence $b$ has on that. $\endgroup$ – fgrieu Jan 9 '17 at 12:41
  • $\begingroup$ Since you're reducing a power-of-two number of bits to a decimal number via a module, your results will be non-uniformly distributed. This can have security implications in some scenarios. A better method is to re-hash if the output of the first hash is greater than $floor(2^h/10)*10$ where $h$ is the length of the hash and perform a modulo operation over the same value. $\endgroup$ – rmalayter Jan 10 '17 at 12:39
  • $\begingroup$ @rmalayter: Thanks for your insight. I think is a great idea. I suppose the formula is floor(2^hashlen/10)*10 with hashlen measured in bits ? $\endgroup$ – User314 Jan 11 '17 at 9:54
  • $\begingroup$ @User314 yes, in bits, but you might need a big number library or calculator to handle hashes larger than 2^64. It must be exact integer math; floating point rounding won't work. You could always truncate the hash to whatever bit length your environment can handle first before applying that formula. $\endgroup$ – rmalayter Jan 11 '17 at 22:41
  • $\begingroup$ Obviously you should amend the input to the hash before re-hashing it, and you should always do this otherwise you would get collisions. E.g. you could use a 128 bit counter and add that to the end of the calculation; this would foil an adversary that lets you run out of e.g. $2^{32}$ rounds of calculation. Often you can determine how many bits is best beforehand so you can minimize the amount of times you're overrunning the max value. Note that this problem is very much like calculating a number 0..X from a random number generator, and there are multiple methods described to do that. $\endgroup$ – Maarten Bodewes Jul 11 '19 at 12:59

Your Answer

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

Browse other questions tagged or ask your own question.