0
$\begingroup$

A user of this forum told about ideal and practical hash functions.

What is the difference between them?

Can someone provide examples of ideal and practical hash functions?

$\endgroup$
3
  • 1
    $\begingroup$ The point is that an ideal hash function is a model - it is what we hope a hash function to be in the ideal world. Real world hash functions will deviate from this. The real world example given in the question is exactly what you're after. Merkle–Damgård based constructions. For instance, SHA-256. $\endgroup$
    – Lev
    Oct 19, 2022 at 0:20
  • $\begingroup$ @Lev - What is exactly a real world hash function? Sorry, but I'm in fact a newbie in cryptography. $\endgroup$ Oct 19, 2022 at 1:51
  • 1
    $\begingroup$ What is the "Random Oracle Model" and why is it controversial? $\endgroup$
    – kelalaka
    Oct 19, 2022 at 9:08

1 Answer 1

1
$\begingroup$

At least in the linked context, an ideal (cryptographic) hash function from set $\mathcal M$ (the set of messages $M$, often the infinite set of finite bitstrings $\{0,1\}^*$ ) to finite set $\mathcal H$ (the set of hashes, often the finite set of $b$-bit bitrings $\{0,1\}^b$ ) is a mathematical abstraction. It's a random member of the set of functions from $\mathcal M$ to $\mathcal S$. It can also be modeled as a random oracle (the two are demonstrably indistinguishable). For a finite input set $\mathcal M$, we can make an ideal hash by choosing independently and uniformly at random an output element in $\mathcal H$ for each input element in $\mathcal M$. Problem with this is the storage needed grows exponentially with the bit size of message $M$, which is impractical.

Note: this is not to be confused with perfect hash and universal hash.

A practical (cryptographic) hash function is one that, for a fixed output set $\mathcal H$, can be implemented by an algorithm of size essentially independent of the bit size of message $M$, running in time linear (or near that) with that bit size, and with constant (or modest) temporary storage; yet behaves inasmuch as possible as an ideal hash function/random oracle. Ideally: for one not knowing a certain parameter of the practical hash, it is computationally impossible to distinguish the practical hash from an ideal hash/random oracle.

For a long time, the most standard way to construct practical hash functions was the Merkle–Damgård construction. If mostly does the job (in particular, has collision-resistance and preimage-reistance), but has the unwanted length-extension property: for any $M_0$ (within some huge maximum size constraint) known only by it's size and hash, one can find a short $M_1$ such that for any $M_2$ (within some huge maximum size constraint) one can compute $H(M_0\mathbin\|M_1\mathbin\|M_2)$. An ideal hash would not have that property, and there are some (few) practical cases where that matters. We now have better constructions of practical hashes, such as the sponge construction, that are computationally impossible to distinguish from an ideal hash/random oracle.

$\endgroup$
5
  • $\begingroup$ Can you provide an example of an ideal hash function? Is Blake2 an ideal hash function? $\endgroup$ Oct 19, 2022 at 10:10
  • $\begingroup$ There is no ideal hash function. That is concept! $\endgroup$
    – kelalaka
    Oct 19, 2022 at 10:18
  • $\begingroup$ An "example of an ideal hash function" can be made for small message set, following the answer's principle "by choosing independently and uniformly at random an output element in $\mathcal H$ for each input element in $\mathcal M$.". Blake2 is a practical hash function, that is (believed) computationally indistinguishable from an ideal hash (without knowledge of some Blake2 constants); and is fast. It's believed as good as a practical hash can be. In particular, contrary to SHA-512, it does not have the (undesirable) length-extension property. $\endgroup$
    – fgrieu
    Oct 19, 2022 at 10:34
  • $\begingroup$ @fgrieu "If your definition of "ideal hash" is that it has no collisions with an input larger than the output, that's impossible." ==> crypto.stackexchange.com/questions/12301/… -- Now I understand perfectly, thanks. $\endgroup$ Oct 19, 2022 at 10:38
  • $\begingroup$ No, my definition of an ideal (cryptographic) hash is not that it has no collision. That's the definition of a perfect hash. And that's possible only when $|\mathcal M|\le|\mathcal H|$, which is not typical in cryptographic hashing. Again, my ideal (cryptographic) hash is a fixed function chosen at random among the possible functions from the input set to the output set; equivalently, it's a function that maps an input to a particular output that has been randomly chosen for that particular input. $\endgroup$
    – fgrieu
    Oct 19, 2022 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.