1
$\begingroup$

I'm trying to design a protocol where hashing can involve some public and private components. The idea is that Alice hashes a value with minimal computation and sends the hash to Bob. For Bob it should be exponentially harder to re-create / verify the hash against a given value with the hash he received from Alice.

The hash function Alice is going to use will be something like this, with constant time:

$$H_A = \text{hash_generate}(\mathit{input}, \mathit{private\_component}, \mathit{public\_component})$$

The hash / verification function Bob is going to use will be something like this, with exponential time:

$$\text{hash_verify}(H_A, \mathit{input}, \mathit{public}\_component)$$


What I have devised is the following:

This is what Alice does, (this is constant time)

  1. Alice creates random $n$ bits as $\mathit{public\_component}$
  2. Alice creates random $n$ bits as $\mathit{private\_component}$
  3. Alice salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component} \mathbin \| \mathit{public\_component}))$
  4. Alice sends the $\mathit{public\_component}$ and the hash result $H_A$ to Bob

And what Bob does in order to verify is the following:

  1. Bob creates random $n$ bits as (replacement) $\mathit{private\_component}^{rand}$
  2. Bob salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component^{rand}} \mathbin \| \mathit{public\_component}))$
  3. If the hash result is the same as Alice's hash result, he has verified it
  4. If the hash result is the not same as Alice's hash result, goto 1 (or fail with a given repeat count based on $n$, guaranteeing we have done enough permutations to prove that we can't verify the hash)

So the expected complexity of Bob's operation should be around $\mathcal{O}(2^n)$

This protocol is what we have came up with; it's similar to proof of work in a way.


Are there protocols for such a use-case? If yes, how are they called?

$\endgroup$
  • 1
    $\begingroup$ I'm not sure how to describe the result of a hash verification in math notation (or anything close to it). Please edit if you know how. $\endgroup$ – Maarten Bodewes Jul 20 '18 at 13:43
  • $\begingroup$ @Maarten Bodewes thank you for the edit, I'll try to use the math notation from now on. $\endgroup$ – zetaprime Jul 20 '18 at 15:01
1
$\begingroup$

What you are describing here looks like a thing, indeed. For instance, in the case of passwords, you have human-created password, whose entropy is generally weak and who are often found in dictionaries...

So, suppose you'd like to store the user's password in your database in a way that would prevent an attacker obtaining the database to deduce the actual password used by any given user, the simplest way around it might be to simply hash the passwords and store the hashes, right?

Well, if you just hash the passwords, then an attacker could simply take a dictionary and hash its content and compare it to the hashes he found in your database... So it wouldn't prevent the adversary to possibly find some passwords.

So, the next step is obviously to salt the hashes you are storing, in order to increase the cost of the dictionary attack for your adversary. And you can even use a different salt for each password, thus increasing the cost of a dictionary attack even more.

Note that modern hash functions, such as Blake2, sometimes includes support for salted and even for keyed hashing out of the box.

Modern password hashing algorithm, such as Argon2 are actually very similar to "proof of work", as you noticed, since you want to make your adversary consume as much time and power as possible.

There are also other cases where you'd want something like this (see how HMAC works, for instance.)

$\endgroup$
  • $\begingroup$ thanks for the pointers, I wasn't aware of Argon2; i'll look into it. When you say that, it looks like a thing, did you mean something novel, or something that already exists? As you have pointed out, this is definitely about increasing the cost of the dictionary attacks (exponentially). I think Bcrypt is pretty close to what I'm describing, however the increasing cost is for both parties. In this case, it's more about increasing costs for a specific party. $\endgroup$ – zetaprime Jul 20 '18 at 23:38
  • $\begingroup$ @zetaprime I meant "something that already exists". When you're adding a salt and/or a pepper to your password hashes, the cost asymmetry holds, IMO, since the dictionary attack becomes really expensive for the attacker, while the "good ones" are just negligibly impacted. And as I noted at the end of my answer, the same kind of method is used for HMAC, to produce Message Authentication Codes in a way an attacker can not spoof. $\endgroup$ – Lery Jul 23 '18 at 13:18

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.