# Is this a valid scheme to authenticate through a 'human-readable' certificate?

Let's say Alice wants to talk securely to Bob over the internet, and Eve is not only eavesdropping, but has managed to get into a MITM position.

In this scheme Alice and Bob exchange $n$ (example $n = 2$) plaintext questions, at least one for both parties (these are toy example questions):

Alice, what brand of car did I ride you to the airport with last December?

Bob, what's the serial number of the flashlight I gave you yesterday?

Is it then secure for Alice and Bob to attempt to use authenticated encryption under key $H(A_1 || \dots ||\ A_n ||\ S)$ where $A_n$ is the answer to the $n$th question (both parties will include the answers to their own questions), $S$ is a cryptographically strong salt, and $H$ is a slow key derivation function like scrypt?

This will only work if the answers are the exact same, so let's assume the answers have exact unambiguous answers.

Then, using this (seemingly temporarily secure) authenticated channel, can Alice and Bob exchange long-term proper crypto authentication certificates to foil Eve's future attempts at MITM?

Obviously, security can only be as good as the quality of the questions, so let's assume that Eve does not know the answer to any of the questions until the long-term exchange has completed, but we must assume Eve will be able to figure out the answers at a later time.

• No, since that would let Mallory check her guesses for the concatenations of the answers. $\hspace{1.03 in}$ – user991 Mar 27 '15 at 23:29
• @RickyDemer If bruteforce on the answers is the strongest attack on this scheme, that would qualify it as 'secure', wouldn't it? Your argument could also be used to say public signatures are insecure, because it allows you to check your guesses for the private key. – orlp Mar 27 '15 at 23:32
• That wouldn't "qualify it as 'secure'". $\:$ Similarly, my "argument could also be used to say public" key encryption is "insecure, because it allows you to check your guesses for the private key." $\:$ (Both of those sayings would hopefully be incorrect, since it's supposed to be infeasible to guess the private key.) $\hspace{.33 in}$ – user991 Mar 27 '15 at 23:45
• @RickyDemer Just like it's infeasible to guess the private key, I assume the questions are of sufficient quality it's infeasible to guess them, at least within the timeframe of the exchange. The questions I used as an example are weak toy questions. $H$ is a slow hash function, like scrypt. – orlp Mar 27 '15 at 23:47
• You should put that into your opening post. $\;$ – user991 Mar 27 '15 at 23:48

No, it is not. There are several misconceptions with your scheme.

First, your question/answer pairing does simply not contain enough entropy. This is much less entropy than your common "please choose a password" input, because you can't just use all words/numbers/common symbols. You have to stick to answers that make sense. This is what Ricky Demer hinted at in his comments. Even using scrypt or another password based KDF will be able to negate this fundamental issue.

Secondly, your 'salt' is entirely pointless. Salts are used to prevent attacks (multi user setting, rainbow tables), which are not considered in your scenario. You assume Eve to have only access to the communication network.

Thirdly (and most important): Your scheme mixes key exchange and authentication, but has vulnerabilities with both regards: Neither Bob nor Alice have a way to determine, if a question is from the other partner or was actually modified by Eve. She can just swap out the questions to those she is knows the answers to (possibly from a previous exchange, where she researched the correct answers). The question/answer format is not a suitable challenge-response mechanism, because there is no intractable computational problem (e.g. Diffi-Hellman) involved.

From a computational point of view, this has no security at all, because the questions are sent in the clear, knowledge of a question almost immediately implies knowledge of the possible answers, and then you just throw a hash function on top. And Eve can do that all by herself as well. And even worse, she can just take her time, find out the correct answers to the easy questions and decrypt everything afterwards.

The only way to use this would probably be to use the "unique serial number" from the pen you mentioned, and limit its usage to a single time. That means, basically you got something like a one-time-password and use it to seed a CSPRNG. But if you limit yourself to that, you can just leave out the clunky non-secure question/answer game.

• You have no idea how much entropy there is with question/answers, it could be an arbitrary amount. Could you elaborate on your replay attack? I don't fully understand what Eve would replay, and how it would affect security. – orlp Mar 30 '15 at 14:18
• I changed the third part a lot. Replays are gone, because actually you don't have an authentication scheme (my bad, sorry), but just a key exchange protocol without any computational hardness assumptions. – tylo Mar 30 '15 at 15:11
• While I do not 100% agree with your notions in point #1 and #2, I did not consider the attack where Eve swaps out questions for those she knows the answer with. Do you know of any secure scheme where two human users can prove their identity to eachother through some means without having shared a cryptographical certificate/secret beforehand? Is it possible at all? – orlp Mar 30 '15 at 15:23
• "will be" $\: \mapsto \:$ "will not be" $\;\;\;$ ? $\;\;\;\;\;\;\;\;$ – user991 Mar 31 '15 at 2:50
• His salt is far from "entirely pointless". $\:$ Salts can be used to defend against time-memory tradeoffs. $\hspace{.2 in}$ How could Eve "decrypt everything afterwards"? $\;\;\;\;$ – user991 Mar 31 '15 at 2:57