Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Let's say Alice wants to prove to Bob that she knows a secret S that Bob is also supposed to know. Alice can't be sure Bob is really who he pretends to be, so she needs to make sure Bob can't deduce S from their interaction. Additionally, S could be weak (e.g. "abc123"), so she can't simply send a hash of S to Bob, or any f(S) really since that could be brute-forced.
What are your thoughts on this? Is this even possible?
What you want is the https://en.wikipedia.org/wiki/Socialist_millionaires Problem. This problem is orignally phrased as two people want to verify if they have the same amount of money without revealing anything more. Alice has a value $A$ and Bob has value $B$ and they want to verify $A =? B$ without either side revealing anything more than the result of the check. See the wiki page for algorithm description.
A simple solution can involve Nestor: a trusted third party. Both Alice and Bob send the secret to Nestor and he will verify if they both have the same secret.
In real life this solution is not optimal (what if Nestor is Bob's partner? How can Bob verify that Nestor is not on Alice side?) but can be acomplished if both party trust Nestor enough to stay Neutral.
You could use a password-authenticated key agreement protocols, e.g. EKE.
Basically, those aim exactly at your scenario with the goal of establishing a proper key to communicate securely. If you use that key to established a secure channel(e.g. with AES-GCM), and then verify both parties have the same key, you can ensure they both used the same password. Example: Alice sends a random x and Bob answers with x+1 over the established channel.
You can use Password-Based Key Derivation Function (PBKDF2). However, not even this can save you for weak secrets.
Although a bit outdated, you can view some recommended parameters here
What are your thoughts on this? Is this even possible?
This is not possible as long as the varification algorithm runs in polynomial time. Even you have said it yourself:
..., or any f(S) really since that could be brute-forced ...
Unless the complexity (time or space) of your verification algorithm doesn't belong in $P$ - that is, it cannot end in polynomial time (deterministically). I'm not entirely certain, but one may be able to devise a verification algorithm that 1) takes a secret parameter, 2) ends quickly when correct secret is given, and 3) runs in super-polynomial time (or ideally, exponential time) when wrong secret is given.
But then again, the compromised Bob may abort the verification algorithm if he believes that the algorithm had been running for too long due to wrong input.
You have the answer. It's hashing. Even if S is weak, it's not possible to determine S from the hash value if the algorithm used is secure enough. Alice can send a SHA-256 hash of S to Bob. If Bob knows S, he can confirm it and Alice has convinced him. Else, we know it's just someone pretending to be Bob.
