# On the security definition of password-authenticated key exchange

I found in all PAKE papers, the security is defined as something like this:

Let $Succ(A)$ be the probability that an attacker $A$ successfully distinguished the session key from a random string. Then the advantage of $A$ is $Adv(A) = 2 \times Succ(A)-1$. Then a PAKE protocol is secure if $Adv(A) \leq n_{se}/|PW| + neg$. where $n_{se}$ is the number of queries made by the attacker, and $|PW|$ is the size of the password dictionary.

From this definition, it seems that the session key is semantically secure only if $|PW|$ is large enough to make $n_{se}/|PW|$ negligible. Does this contradict the definition of PAKE that supports low-entropy passwords? I mean if |PW| is small, then the session key generated by PAKE is not indistinguishable from a random key, so we cannot use it for encryption and so on, isn't it?

Let's approach the question from this direction.

PAKE tries to solve this problem: Alice has a password $PW_{a}$, and Bob has a password $PW_{b}$; consider a protocol where Alice and Bob exchange messages, and generate encryption keys $E_{a}, E_{b}$ where $E_{a} = E_{b}$ if $PW_a = PW_b$ (and unrelated if $PW_a \ne PW_b$); if they're the same, Alice and Bob can use the common key to protect traffic.

In this scenario, one thing that an attacker Eve can do is pretend to be Alice, create a guess at the password $PW'$, and then run through the protocol with Bob (who knows the real password); if Eve picked the same password as Bob ($PW' = PW_b$), she knows her guess at the password was correct.

This (and the obvious related one where Eve pretends to be Bob) are inherent within the scenario; what a PAKE attempts to do is ensure that there is no significantly better attack; that going through the plausible passwords, and trying them one-by-one is about Eve's best option.

The formalism $Adv(A) \leq n_{se}/|PW| + neg$ attempts to capture this idea in a manner that we can make mathematical statements about; if Eve gets $n_{se}$ attempts, and she knows the size of the dictionary $|PW|$ of possible passwords, she can try $n_{se}$ entries with her attempts, and succeed with probability $n_{se} / |PW|$ (assuming that each entry in the password is equiprobable); the $neg$ term is there because no real protocol can actually achieve this.

What does this mean to you? If the risk that an attacker might guess the password successfully is too high for you, then yes, a PAKE in not applicable; you'll need to find some other authentication method that relies on something stronger than a low entropy secret.

That at least does not contradict "the definition of PAKE that supports" sets $PW$ which
are known, since the adversary can just try an element of $PW\hspace{-0.03 in}$. ​ However, that does not

give meaningful assurance against, for example adversaries who have information which uniquely determines the password without letting the adversary find the password
or
restrict the adversary's ability to make its successes against
[parties with independent passwords] [correlated or anti-correlated]

.

• I mean if $|PW|$ is small, then the session key generated by PAKE is not indistinguishable from a random key, so we cannot use it for encryption, isn't it? – Jan Leo Apr 22 '16 at 10:32
• If it has the a right length, then we can use it for encryption. ​ If the underlying encryption scheme is secure then the adversary's ability to distinguish different conversations under the combined scheme will be at most negligibly more than $n_{se}/|PW|$. ​ ​ ​ ​ – user991 Apr 22 '16 at 10:50
• Suppose we use a secure encryption scheme $E()$ and a $n$-bit key $k$ which is outputted by PAKE to encrypt a bit $m$. Then the adversary's advantage to distinguish $m$ is $n_{se}/|PW| + neg(n)$. Suppose |PW| is small and is roughly equal to $n_{se}$, then the adversary's advantage is about 1, which is certainly insecure. – Jan Leo Apr 22 '16 at 11:00
• Oh yeah, I guess the basic definition also doesn't account for the ideal functionality having an even smaller probability of revealing more than one key to the adversary. ​ ​ – user991 Apr 22 '16 at 11:27
• Sorry, what do you mean by "evealing more than one key to the adversary". If the above is true, then what is the point to use PAKE? – Jan Leo Apr 22 '16 at 11:38