6 ms·

Last year my wife and I suspected we might have gotten each other the same Christmas gift, but didn’t want to spoil the surprise in case we didn’t. So we compar

by Liron 4y ago

Last year my wife and I suspected we might have gotten each other the same Christmas gift, but didn’t want to spoil the surprise in case we didn’t. So we compared SHA256 hashes... and sure enough they both came out cb17007d (theragun)

garaetjjte 4y ago
Doesn't work, because you can reasonably brute-force possible gifts.
- Liron 4y ago
  Yeah I'm not sure what's the best protocol that's actually zero-knowledge here, but since we both trusted each other to only want to find out whether or not our gifts were the same, and otherwise to not spoil the surprise, this did the job.
  - kevinventullo 4y ago
    You could write a script that does the hash comparison for you and simply outputs “Yes” or “No” for whether the hashes are identical.
    - soonerroadie 4y ago
      You could just write a script that lets you write an input and your spouse writes an input and then compares the two inputs without showing them - no need for hashing at all.
- lights0123 4y ago
  You could reveal the hash letter-by-letter and stop as soon as a letter differs so there's more possibilities.
  - teaearlgraycold 4y ago
    > stop as soon as a letter differs Oops - you just exposed a timing attack side channel
- mbauman 4y ago
  You can similarly brute force mutual acquaintances in TFA
- 10000truths 4y ago
  Sure, but the example is contrived, as it serves to illustrate the point in an easily digestible (heh) way. In real world applications, both the possible messages and the possible hashes would be way too large to brute force.
- xigoi 4y ago
  But why would you do it?
  - kjeetgill 4y ago
    I think the point is just that this is a misleading example of zero-knowledge proofs which are meaningful different cryptographically.
PascLeRasc 4y ago
This explained zero knowledge so much easier than that parable about the caves, thank you.
- vintermann 4y ago
  But it isn't zero-knowledge. If it was zero-knowledge, you would be able to know what you had the same gift/crush, but it would be impossible to prove to someone else. Mere hashing doesn't do that. For the crush example (This site), your crush could show everyone the link and their name. For that matter, someone could enter the names of everyone you knew in turn, until you were outed.
  - josephcsible 4y ago
    An actual zero-knowledge way to do that would be the Socialist Millionaires' Protocol.
  - sangel 4y ago
    Non interactive zero knowledge allows one proof to be checked by many verifiers. I think folks would still consider that to be a zero knowledge proof no? That said, yeah this hashing example is not zero knowledge because, among other things, the hash is not hiding.
    - vintermann 4y ago
      It's been a while since I read about zero-knowledge proofs, so I wasn't aware of the non-interactive kind. But I read up on them, and as I understand, you have to pre-commit to a finite set of participants in the protocol who can verify that you have the proof. Which makes sense: If the evidence (that you have a mathematical proof) could be convincingly shared with absolutely everyone, it wouldn't be zero-knowledge any longer. The whole point of zero-knowledge proof is that the evidence is only useful for the recipient(s).
  - tylersmith 4y ago
    It is n-bit knowledge which is a more complete and valuable concept.
avg_dev 4y ago
What did you hash? The name of the product? Or the UPC or something? I am curious.
- Liron 4y ago
  We both hashed "theragun" in all lowercase. We actually bought each other two different models of Theragun but it was pretty natural to refer to them with that string.
nullc 4y ago
Not technically zero knowledge, since you could brute force search her non-matching hash later. A true ZK comparison[1] would just return a true or false without exposing any other information such as the hash of the item. I'm sure the hash was good enough for your purpose, however! [1] https://en.wikipedia.org/wiki/Socialist_millionaire_problem https://en.wikipedia.org/wiki/Socialist_millionaire_problem
hinkley 4y ago
There are a couple of science and science fiction authors that started posting hashes or signatures for their predictions for the future, and then post it after events played out. I think the idea is that unlike pundits predicting the future, you don't want your particularly clever friend speculating out loud ten minutes into the suspense movie what they think is going on because they either guess the ending, or their guess makes you figure out the ending, and then it's 70 minutes of sitting there reading all of the other foreshadowing and not getting to enjoy any of it.
- Thorrez 4y ago
  >unlike pundits predicting the future Isn't your example pundits predicting the future? So why are hashes useful to those pundits in your example?
heroHACK17 4y ago
Relationship goals
deleted 4y ago
[deleted]

by Liron 4y ago

garaetjjte 4y ago

Doesn't work, because you can reasonably brute-force possible gifts.

Liron 4y ago
Yeah I'm not sure what's the best protocol that's actually zero-knowledge here, but since we both trusted each other to only want to find out whether or not our gifts were the same, and otherwise to not spoil the surprise, this did the job.
- kevinventullo 4y ago
  You could write a script that does the hash comparison for you and simply outputs “Yes” or “No” for whether the hashes are identical.
  - soonerroadie 4y ago
    You could just write a script that lets you write an input and your spouse writes an input and then compares the two inputs without showing them - no need for hashing at all.
lights0123 4y ago
You could reveal the hash letter-by-letter and stop as soon as a letter differs so there's more possibilities.
- teaearlgraycold 4y ago
  > stop as soon as a letter differs Oops - you just exposed a timing attack side channel
mbauman 4y ago
You can similarly brute force mutual acquaintances in TFA
10000truths 4y ago
Sure, but the example is contrived, as it serves to illustrate the point in an easily digestible (heh) way. In real world applications, both the possible messages and the possible hashes would be way too large to brute force.
xigoi 4y ago
But why would you do it?
- kjeetgill 4y ago
  I think the point is just that this is a misleading example of zero-knowledge proofs which are meaningful different cryptographically.

PascLeRasc 4y ago

This explained zero knowledge so much easier than that parable about the caves, thank you.

vintermann 4y ago
But it isn't zero-knowledge. If it was zero-knowledge, you would be able to know what you had the same gift/crush, but it would be impossible to prove to someone else. Mere hashing doesn't do that. For the crush example (This site), your crush could show everyone the link and their name. For that matter, someone could enter the names of everyone you knew in turn, until you were outed.
- josephcsible 4y ago
  An actual zero-knowledge way to do that would be the Socialist Millionaires' Protocol.
- sangel 4y ago
  Non interactive zero knowledge allows one proof to be checked by many verifiers. I think folks would still consider that to be a zero knowledge proof no? That said, yeah this hashing example is not zero knowledge because, among other things, the hash is not hiding.
  - vintermann 4y ago
    It's been a while since I read about zero-knowledge proofs, so I wasn't aware of the non-interactive kind. But I read up on them, and as I understand, you have to pre-commit to a finite set of participants in the protocol who can verify that you have the proof. Which makes sense: If the evidence (that you have a mathematical proof) could be convincingly shared with absolutely everyone, it wouldn't be zero-knowledge any longer. The whole point of zero-knowledge proof is that the evidence is only useful for the recipient(s).
- tylersmith 4y ago
  It is n-bit knowledge which is a more complete and valuable concept.

avg_dev 4y ago

What did you hash? The name of the product? Or the UPC or something? I am curious.

Liron 4y ago
We both hashed "theragun" in all lowercase. We actually bought each other two different models of Theragun but it was pretty natural to refer to them with that string.

nullc 4y ago

Not technically zero knowledge, since you could brute force search her non-matching hash later. A true ZK comparison[1] would just return a true or false without exposing any other information such as the hash of the item. I'm sure the hash was good enough for your purpose, however! [1] https://en.wikipedia.org/wiki/Socialist_millionaire_problem https://en.wikipedia.org/wiki/Socialist_millionaire_problem

hinkley 4y ago

There are a couple of science and science fiction authors that started posting hashes or signatures for their predictions for the future, and then post it after events played out. I think the idea is that unlike pundits predicting the future, you don't want your particularly clever friend speculating out loud ten minutes into the suspense movie what they think is going on because they either guess the ending, or their guess makes you figure out the ending, and then it's 70 minutes of sitting there reading all of the other foreshadowing and not getting to enjoy any of it.

Thorrez 4y ago
>unlike pundits predicting the future Isn't your example pundits predicting the future? So why are hashes useful to those pundits in your example?

heroHACK17 4y ago

Relationship goals

deleted 4y ago

[deleted]