6
$\begingroup$

What would be a way to prove that both you and I know the same dictionary word? If we both hashed the word, then we could compare the hashes, but anyone who saw the hash could find the original word by hashing all the words in the dictionary. What would be a better way?

$\endgroup$
2
  • $\begingroup$ Not very into crypto, but wouldn't Zero Knownledge Proof be a good fit here ? (en.wikipedia.org/wiki/Zero-knowledge_proof) $\endgroup$ Aug 2 at 6:26
  • $\begingroup$ Who are you proving it to, each other or a third party? Is it the fact that you both know the definition, or that you both are thinking of the same word? How is the word communicated? $\endgroup$ Aug 2 at 15:21

2 Answers 2

10
$\begingroup$

The problem of testing whether two low-entropy strings are equal is called private equality test or the socialist millionaires problem. It is also the main challenge in password-authenticated key exchange (PAKE). You have correctly observed that simply sending a hash is not a good approach, when the strings have low entropy --- it exposes an offline dictionary attack.

The Wikipedia page for socialist millionaires problem provides an example protocol, but I don't think it's a very good example (it is made much more complicated by avoiding a random oracle, which I don't think is the most important criterion for a Wikipedia example). There is a much simpler approach -- actually the first PAKE protocol ever proposed: EKE from Bellovin & Merrit. The idea is simple: just wrap Diffie-Hellman key agreement it in a layer of an ideal cipher, with the input string as the key:

  • Alice holds $x$ and Bob holds $y$. They agree on a public Diffie-Hellman group with generator $g$.
  • Alice chooses a random exponent $a$ and sends $A = E(x, g^a)$ where $E$ is an ideal cipher.
  • Bob chooses a random exponent $b$ and sends $B = E(y, g^b)$.
  • Alice can compute $K = (E^{-1}(x, B))^a$
  • Bob can compute $K' = (E^{-1}(y, A))^b$
  • When $x=y$, then $K=K'$ too (you can check that $K=K'=g^{ab}$). But when $x \ne y$, $K$ looks random to Bob and $K'$ looks random to Alice (with high entropy!). So they can simply compare $K$ and $K'$ in the clear.

If you want to implement EKE in practice, then you will have to deal with the slight mismatch between the key agreement (happening in a cyclic group, presumably an elliptic curve group) and the block cipher (which expects a string of bits as input). This can indeed be dealt with but it makes things slightly messier.

$\endgroup$
1
  • $\begingroup$ Thanks! Is there an easy way to do this with OpenPGP or similar? $\endgroup$ Aug 1 at 6:41
2
$\begingroup$

If we can share a secret key by some method (e.g. pre-shared out of band, or using some cryptographic key establishment) then we can both compute a keyed HMAC. We would be able to check the hash value, but anyone without the key would be unable to exhaust possible inputs.

$\endgroup$
5
  • $\begingroup$ Diffie-Hellman is an easy way to establish a shared key over a reliable (and not necessarily secure) channel. $\endgroup$
    – iBug
    Aug 1 at 18:16
  • $\begingroup$ @iBug DH also requires a pre-shared key to prevent MITM. $\endgroup$
    – AndreKR
    Aug 2 at 13:12
  • $\begingroup$ @AndreKR By "reliable" I mean an attacker cannot change what's transmitted, only see it. $\endgroup$
    – iBug
    Aug 2 at 14:36
  • $\begingroup$ In this scenario, if Alice gives her hash to Bob first, couldn't Bob compute the hash for all dictionary words? $\endgroup$ Aug 2 at 15:18
  • $\begingroup$ @JasonGoemaat It's not clear whether or not Alice are Bob are mutually untrusting in this question, but if so note that the checking can be done by a third party without knowledge of the key. $\endgroup$
    – Daniel S
    Aug 2 at 18:06

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.