How can two parties compare whether a simple (5 letter) shared word matches, without disclosing their word to each other?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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)