0
$\begingroup$

The following is a representative example of a common hash function:-

sha1

The asymmetry is clear, and I would expect additional edge effects in the A and E output words. So I'd be surprised if the probability distributions between words A to E are identical to the nth degree. The same asymmetric construction argument clearly applies to all other hash architectures.

In general cryptography and as NIST does, it's common to treat a bias $\epsilon < 2^{-64}$ as negligible. So an $\epsilon$ is expected of some degree as our constructions are imperfect.

The question therefore is: is there any estimate of the theoretical bias across the block width of hash function outputs? Assume the limiting case of an infinite number of hash inputs. Would the output probability distributions be (say for the above example) $P_{\infty}(A) = P_{\infty}(B) = P_{\infty}(C) = P_{\infty}(D) = P_{\infty}(E)$ exactly, and $\epsilon = 0.0$?

I won't be accepting the current answer as that deals with empirical measures, but I'm asking about theoretical expectations. There is no computationally bounded adversary. I'm just curious.

NB. I take "bias" to mean the standard NIST definition (SP 800-90B) as "A random process (or the output produced by such a process) is said to be biased with respect to an assumed discrete set of potential outcomes (i.e., possible output values) if some of those outcomes have a greater probability of occurring than do others."

I'm really not sure if Is any group of bits in a SHA-1 hash more/less unique than another? is similar or not.

|improve this question
$\endgroup$
  • 1
    $\begingroup$ The most practical estimate, which only indirectly relates to your question, is if it's computationally feasible to distinguish a hash output from random. Modern strong hashes are computationally indistinguishable given reasonable limits (the adversary is capable of less than somewhere around 2^100 evaluations). However, they are almost certainly not perfectly unbiased. Presumably some simple hash functions still have some mathematical description of their bias, but even then the computational limit above will usually prevent you from detecting it. $\endgroup$ – Natanael Feb 17 '19 at 17:28
  • 1
    $\begingroup$ And to add to the above, I doubt there's any reasonably complete mathematical description of the bias of a complex function like SHA256. Evaluating the exact bias can be harder than regular cryptoanalysis. $\endgroup$ – Natanael Feb 17 '19 at 17:33
  • $\begingroup$ @Natanael Do you think that there might be an algebraic assessment somehow, given that empirical measures are infeasible? $\endgroup$ – Paul Uszak Feb 17 '19 at 17:38
  • 1
    $\begingroup$ @PaulUszak I'm not sure why the asymmetry matters. The diagram you are displaying is just one of 80 rounds. As you can see, each word "shifts" at the end of the round. Each round has every word affecting one word before they all shift, and this happens many times. Also, Whirlpool looks nothing like this. MD4, MD5, SHA-1, and SHA-2 look a bit like this (and a few slightly more obscure hashes like those of the RIPEMD family), but Whirlpool is based on AES and looks nothing like this. And SHA-3 (which uses the Keccak sponge function) also looks totally different. It's not even ARX. $\endgroup$ – forest Feb 18 '19 at 10:29
  • 2
    $\begingroup$ The definition of bias you gave is a binary property: either a distribution is uniform, in which case it is unbiased by this definition; or it is nonuniform, in which case it is biased. Is there a continuous measure of bias that you're asking about? If not, it is almost certainly the case that for any ‘cryptographic hash function’ the output is technically ‘biased’ in this sense, but that almost-certainly-true property is of no practical consequence whatsoever—we have no idea in which way it might be biased. $\endgroup$ – Squeamish Ossifrage Feb 18 '19 at 16:40
3
$\begingroup$

If there were any detectable bias, I wouldn't be posting about it on a forum of pseudonymous wackos like me on the internet—I would be getting top billing (or beaking, as the case may be) in a top-tier cryptography conference, and the champagne would be popping, and Twitter would be abuzz with speculation, and Hacker News would be extra insufferable.

Specifically, with the exception of 2-pass Snefru[1][2], no major hash function with advertised preimage and collision resistance has ever seen its preimage resistance broken[3] (archive). (Yes, there's a paper that everyone and their dog cites on an MD5 preimage attack[4], but it's not cheaper than the best generic attack[5].)

P.S. The formula $\epsilon = 2^{-(s n - k)/2}$ appears to be a quotation from an ID Quantique marketing whitepaper with a garbled definition which Paul read out of context to draw a nonsense conclusion in the self-accepted answer of his own that he cited.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ @fgrieu Thomsen: ‘The total complexity of the attack is about $2^{73}$ compression function evaluations. Memory requirements are about $2^{73}$ message blocks.’ (p. 8) Muller: ‘[I]t will cost about $2^{104}$ applications of the compression function. In addition, a memory of $2^{71}$ is required. This is much faster than a naive exhaustive search.’ (p. 14) These are not cheaper than generic search. $\endgroup$ – Squeamish Ossifrage Feb 17 '19 at 18:50
  • $\begingroup$ There is a report of a preimage attack of cost $2^{73}$ evaluations on MD2: Søren S. Thomsen's An improved preimage attack on MD2 (2008). It improves Lars R. Knudsen and John E. Mathiassen's Preimage and Collision Attacks on MD2 (in proceedings of FSE 2005) with a claimed $2^{97}$, improving on Frédéric Muller's The MD2 Hash Function is Not One-Way with $2^{104}$ [fixed]. Indeed memory cost is high. $\endgroup$ – fgrieu Feb 17 '19 at 18:50
  • 1
    $\begingroup$ Hey, the $\epsilon$ formula is a standard NIST formula widely accepted by all TRNG architects. I'm sorry that you can't understand it, but the implication of your self labelled 'wacko' answer is that $\epsilon = 0.0$ which is unlikely isn't it? $\endgroup$ – Paul Uszak Feb 17 '19 at 21:24
  • $\begingroup$ @SqueamishOssifrage, nice answer, including the ones in the links I followed from here. What is beaking at a crypto conference? I get the image of a verbose bird shaking its head. $\endgroup$ – kodlu Feb 17 '19 at 21:27
  • 1
    $\begingroup$ @PaulUszak No one's questions are being ridiculed. Squeamish Ossifrage is pointing out only that you took the equation from a marketing whitepaper out of context and, as a result, drew a nonsense conclusion. $\endgroup$ – forest Feb 18 '19 at 23:38

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.