4
$\begingroup$

After reading about UHFs from different sources (From Algorithm books to Crypto books), I am still thoroughly confused about them.

How is a UHF different from other cryptographically secure hashing functions? Is the only difference that it's a keyed hash function while other secure hash functions need not be keyed?

Also, Boneh defines a UHF as a keyed hash function which satisfies a very weak notion of collision resistance and he goes ahead he defines this notion by saying that the adversary must not be able to find a collision with no information about the key at all. Other than the mention of the key - this seems similar to the adversary having to find a collision where he can pick both m1 & m2 such that there is a collision. If the user can pick both messages to find a collision, then Christof Paar defines that as strong collision resistance rather than weak collision resistance. Paar's definition of weak CR is that user is given m1 & it's tag & he must find a m2 with a collision.

So I am confused here about a couple of things

  1. Is UHF just a cryptographically secure hash function which is keyed?

  2. What Collision Resistance property does a UHF need to possess - Weak or Strong CR & how do you define that type of CR?

$\endgroup$
1
  • $\begingroup$ Here is a clear explanation of universal hashing over a prime field. $\endgroup$
    – Patriot
    Feb 17, 2021 at 21:28

2 Answers 2

4
$\begingroup$

The usual definition for a hash function - to avoid hard coded collisions, i.e. trivial formal adversaries have a collision as part of their description and just output it- is as a pair of algorithms $(\operatorname{Gen},\operatorname{Hash})$. In this definition $\operatorname{Gen}$ typically picks a "key" for the hash function, which for the "keyless" ones can usually be seen as the details of the description, like the exact structure and constants.

The advantage of an adversary $\mathcal A$ against the collision resistance of a scheme $H$ is then defined using the following experiment:

  1. $k\gets \operatorname{Gen}(1^\kappa)$
  2. $(m,m')\gets\mathcal A(1^\kappa,k)$
  3. $\mathbf{Adv}_H^{\text{CR}}(\mathcal A;\kappa)=\Pr[\operatorname{Hash}(k,m)=\operatorname{Hash}(k,m')\land m\neq m']$

A scheme is then called collision-resistant if for all polynomial-time adversaries $\mathcal A$ the advantage $\mathbf{Adv}_H^{\text{CR}}(\mathcal A;\kappa)$ is negligible in $\kappa$.

This definition essentially amounts to "give the adversary a full description of the scheme and then they win if they find a collision". The key serving the role of the definition of the hash function having only existed for so long in the real world, i.e. the key being given to the adversary the moment the hash function design was finalized.

Now for a UHF on the other hand the security definition is much weaker. The advantage of an adversary $\mathcal A$ against the universal hashing security of a scheme $H$ is then defined using the following experiment:

  1. $(m,m')\gets\mathcal A(1^\kappa)$
  2. $k\gets \operatorname{Gen}(1^\kappa)$
  3. $\mathbf{Adv}_H^{\text{UHF}}(\mathcal A;\kappa)=\Pr[\operatorname{Hash}(k,m)=\operatorname{Hash}(k,m')\land m\neq m']$

A scheme is then called universal hashing secure if for all polynomial-time adversaries $\mathcal A$ the advantage $\mathbf{Adv}_H^{\text{UHF}}(\mathcal A;\kappa)$ is negligible in $\kappa$.

As you can see for the UHF security, the adversary doesn't get a full description of the scheme. They don't even get oracle access - i.e. they can't query values to get their hashes. So they have to come up with a collision that works for a non-negligible amount of instantiations ("keys") of $H$. Obviously this definition is much easier to satisfy. In cryptographic practice dedicated UHF schemes actually even break down in security if an adversary learns a single input-output pair, allowing an adversary to completely recover the key $k$ and produce collisions at will.

$\endgroup$
3
  • $\begingroup$ In cryptographic practice dedicated UHF schemes actually even break down in security if an adversary learns a single input-output pair, allowing an adversary to completely recover the key k and produce collisions at will. - in real life - is it possible to prevent this - i.e. adversary getting just one input/output pair? $\endgroup$
    – user93353
    Feb 16, 2021 at 4:04
  • $\begingroup$ They don't even get oracle access - i.e. they can't query values to get their hashes. - how is this prevented as compared to other Hashing schemes? $\endgroup$
    – user93353
    Feb 16, 2021 at 4:04
  • 1
    $\begingroup$ @user93353 for UHFs the key is usually actually kept secret, e.g. as part of a MAC key. Without the key and no direct way to learn inputs and outputs, you can't evaluate the concrete instance in question. As for preventing learning input / output pairs, adversaries typically do learn inputs, however the UHF's output is usually encrypted or otherwise cryptographically post-processed, preventing the adversary from learning the actual output. $\endgroup$
    – SEJPM
    Feb 16, 2021 at 11:01
2
$\begingroup$

The main difference is as you noted: Cryptographic hash functions need not be keyed. So intuitively the weak collision resistance guarantee for UHFs is indeed weaker that what we ask for cryptographic hash functions. Namely for UHFs the attacker has to find a collision for a hash function that the attacker doesn't really know(Not really but the UHF key is kept secret), this is a easier to satisfy compared to the case where the adversary knows the key. Indeed for UHFs based on polynomial that would be trivial.

Additionally: It is worth noting that technically a keyless hash function cannot be collision resistant in the sense: No efficient adversary is able to find a collision. The reason being that there exists such an efficient adversary: the one that has the collision hardcoded.

The way out is to actually define parametrized family of hash function $\{H\}_k$. Therefore the attacker cannot simply hardcode the collisions anymore.

But when comes to collision for such a family, in some books, the key $k$ is also given to the adversary.

$\endgroup$
7
  • $\begingroup$ What do you mean by "Collision Hardcoded"? $\endgroup$
    – user93353
    Feb 15, 2021 at 9:55
  • $\begingroup$ About collision resistance, is the attacker only allowed to choose m2 or is he allowed to choose both m1 & m2? $\endgroup$
    – user93353
    Feb 15, 2021 at 9:56
  • $\begingroup$ What I meant was that since for any $H$ such that the input space is larger that the output space therefore there exists $(m_1,m_2)$ that is a collision for $H$. Therefore an efficient adversary is the one with $(m_1 ,m_2)$ hardcoded. This does not mean that we actually know such an adversary! i.e: we don't know the colliding messages so we cannot really write the adversary formally but it 'exists' $\endgroup$ Feb 15, 2021 at 9:59
  • 2
    $\begingroup$ But CR doesn't mean that collisions don't exist, it just means the adversary can't find them. So in this context, I still don't get what "hardcoded" means. $\endgroup$
    – user93353
    Feb 15, 2021 at 10:25
  • 1
    $\begingroup$ Indeed, for hash functions that we are considering collision resistance do exist, but this doesn't mean that we know them! But this fact doesn't contradict the fact that we can have an adversary which trivially breaks collision resistance by hardcoding the collision which we don't know about but that exists. $\endgroup$ Feb 15, 2021 at 10:47

Your Answer

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

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