2

I'm having some trouble with this scenario, some advice would be great. The context is that a group of people have each been give a simple 5 letter word - for example:

  • Alice: ACTOR
  • Bob: JEANS
  • Dan: SAUCE
  • Erin: ACTOR
  • Fred: RELAX

How could a person within the group identify whether or not another member has the same word as them, without sharing the word itself? Is this even possible? My first instinct was to use some kind of hashing algorithm, but that would be simple to brute force. Is there some kind of neutral web service out there that could facilitate this?

Improve this question
  • does it matter if Bob, Dan or Fred can find out that Alice and Erin have the same word, assuming one or more of them can see the exchange or be a MitM? – Skaperen Jun 15 '15 at 10:47
4

The problem you are asking about is called the Socialist Millionaire problem and has been discussed in research before; as far as I know there is a protocol to do this comparison without disclosing any of the two secrets and without involvement of a third party. I will edit my answer with a full explanation as soon as possible.

Improve this answer
  • That's great, thanks! Wasn't aware there was a name for this problem – ICV Jun 8 '15 at 12:57
0

Hashing is definitely the way. If brute-forcing is an issue then there is no secure way to do this, as any algorithm which compares two 5-letter strings and returns equivalence could be trivially brute-forced in a maximum of 26^5=11881376 comparisons. The only feasible way of defending against brute-forcing in such a low-entropy environment is to use a variably slow hashing algorithm like bcrypt.

Improve this answer
  • Sorry, but you're not correct. The correct method here is to use a zero-knowledge proof protocol. – Steve Dodier-Lazaro Jun 8 '15 at 21:14
  • @SteveDL, you're both wrong. "The correct method here is to use" multi-party computation, which might involve "a zero-knowledge proof protocol." – user49075 Jun 9 '15 at 1:20
  • @RickyDemer please give reasons, or at least sources, as to why an answer is wrong. With all due respect, it seems that both SteveDL and myself are at least partially correct, in that an ideal hashing algorithm is a type of zero-knowledge proof protocol, which itself is used in multi-party computation. – CrazyCryptoNonsense Jul 21 '15 at 12:39
0

I would say;

A

  • generate a pseudo random token
  • encrypt using the word as the key
  • send result

B

  • decrypt
  • generate next token using predefined method
  • encrypt it
  • send it back

A

  • decrypt
  • check received token (now A has authentificated B) if not ok then stop here
  • generate next token
  • encrypt it
  • send to B

B

  • decrypt
  • check

With this you don't have to share the word and you can't guess someone password when he try to authentificate you if brute forcing decryption with all possible key you can't know if decryption succeed cause the message has a random form.

you are still vulnerable to:

  • Intercepting two message of the same sucessful authentification process then use brute force to check with which word the echange make sense
  • brute forcing by trying to authentificate using all possible password (this one seem inevitable but can be detected easily)
Improve this answer

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.