3
$\begingroup$

The "birthday paradox" places an upper bound on collision resistance: if a hash function produces $N$ bits of output, an attacker who computes only $2^{N/2}$ (...) hash operations on random input is likely to find two matching outputs. If there is an easier method than this brute-force attack, it is typically considered a flaw in the hash function.

Is it mathematically possible that a hash function without the easier method exists?

$\endgroup$
9
  • 4
    $\begingroup$ @kelalaka: actually, universal hash functions aren't hash functions :-). The reason: a 'hash function' (at least, when we talk about it in cryptography) doesn't have a key; a universal hash function does have a key (which needs to be secret in order to preserve its properties) $\endgroup$
    – poncho
    Dec 6, 2021 at 17:27
  • 2
    $\begingroup$ @kelalaka: I'm still not convinced that a universal hash function meets the criteria to be a cryptographical hash function. Even if there is a secret key, as long as you have oracle access to the universal hash function, it is easy (at least, with the universal hash functions I know) to find a collision (or even find the secret key) with a handful of oracle queries - that is far less than what we'd expect from a cryptographical hash function. $\endgroup$
    – poncho
    Dec 8, 2021 at 15:37
  • 1
    $\begingroup$ @kelalaka: not quite: in GCM, the key to the universal is a function of the GCM key (hence the same universal hash key is used for all messages encrypted with the same GCM key) - however, the universal hash output is masked by (a function of) the nonce - that's why repeating nonces is deadly (because that allows us to effectively unmask the universal function output) $\endgroup$
    – poncho
    Dec 8, 2021 at 15:50
  • 1
    $\begingroup$ Does the question ask for an efficiently computable hash function, or just any mathematical construction? $\endgroup$
    – Fleeep
    Dec 13, 2021 at 17:44
  • 2
    $\begingroup$ I don't understand the question. If it's not possible, then all hash functions are "broken". Is it what is asked? What is "mathematically"? $\endgroup$
    – Fractalice
    Dec 16, 2021 at 8:10

1 Answer 1

-2
$\begingroup$

Let's consider what the statement "birthday paradox" means:

Def: Suppose the length of a digest is N. How many messages and relevant digests should be produced on the attacker side, in order to find two messages which have equal digests (collision happens) with the probability of finding these two messages is higher than 50%?

The answer is $ c*\sqrt{N} $. This means the attacker should collect at least $ c*\sqrt{N} $ number of messages among N messages in order to find two identical digests and find a collision. More clearly, in $ c*\sqrt{N} $ number of messages, there should be two messages m and $ \acute{m} $ that H(m) = H($ \acute{m}$) where the likelihood of finding these two messages is approximately 50% (which is an acceptable probability). In this formula, $c$ is a constant and it is approximately equal to 1.2 and ignored in most of the papers and calculations. Furthermore, this statistic is correct just for theoretical hash functions which are designed correctly and are flawless. In this case, we just find these two messages just by brute force and not any other attacks, as the hash function is flawless and designed based on pure theoretical mathematics.

If we want to give a simple example to clarify this, suppose U = {0,1} 128 is the length of digest, then the number of messages that the attacker should choose from U, in order to find two identical digests and find a collision( this incident have a the probability of almost 50%), should be : $$ 1.2 * \sqrt{2^{128}} \cong 1.2 * (2^{64} ) \cong 2^{64} $$ This is an upper bound on collision resistance based on a proven mathematical probability paradox and it is correct just if the designed hash function is theoretically and mathematically correct. If we want to find collisions in the number of lower than $2^{64}$ messages, based on this theory, the probability reduces to less than 50%, in other words, it is less likely to find two messages with identical digests.

Now if I want to answer the question regarding " easier method than brute-force attack", this would happen if we could find a flaw in the design of the hash function that the attacker exploits in order to find two messages which they have identical digests in the lower number of $ c*\sqrt{N} $ messages. As I mentioned above, based on the birthday paradox, we should at least test the $ c*\sqrt{N} $ number of messages to find a collision ( in this number of tests, the probability of finding a collision is approximately equal to 50%). However, if there is a flaw in the design of the hash function, the attacker exploits that flaw and never uses brute force in order to find a collision. Moreover, here "easier method" is a type of attack that can be applied to hash functions rather than brute force attack.

The cryptographers, design their schemes based on computational security rather than perfect security; that is, they prove the security of their scheme based on computational powers. On the other hand, designed schemes without robust mathematical background which could not resist common theoretical attacks are not acceptable at all. Nowadays secure hash functions, are computationally resistant against common computational attacks as well as mathematically proven to be robust. In a theoretical way, it is possible to design a secure hash function, but in practice, there are many factors such as implementation that impact the designed scheme.

$\endgroup$
1
  • 1
    $\begingroup$ This answer is not a response to the particular question in the post. $\endgroup$
    – Wilson
    Dec 12, 2021 at 16:54

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.