3
$\begingroup$

The dragonfly key exchange scheme (as used by WPA3) received criticism because the way it chooses a generator of the elliptic curve group ('hunting and pecking') is a non-constant time algorithm making it vulnerable to side-channel attacks.

My question is: Why is hunting and pecking used at all?

Assume there is a known generator $G$ for a group of prime size, then $G^P$ would also be a generator of the same group (if $P$ is not a multiple of the group size). With $P$ being a password-derived number (as with the dragonfly scheme as is), this way one would obtain a generator just as random and unpredictable as with hunting and pecking, no?

Where is the mistake in that reasoning?

$\endgroup$

1 Answer 1

4
$\begingroup$

Where is the mistake in that reasoning?

The problem is that would allow an attacker to test multiple passwords with the same exchange, hence losing the PAKE properties that we were trying to achieve.

With dragonfly, the honest side selects a secret values $p, m$, and outputs the values $s = p+m$ and $P = -m \cdot SKE$, where $SKE$ is the 'secret key element', that is, the one that you suggest to be derived $SKE = [password]G$ (I'm writing it in additive notation because hunt-and-peck comes into play in Dragonfly only if you're using elliptic curves).

Then, the honest party receives values $s'$ and $P'$ from the other side (the adversary), and then computes the secret key:

$$H( p( P' + s' \cdot SKE ))$$

and then sends an encrypted message based on that key (that is, if the adversary somehow obtains a guess to the same key, he can decrypt the message, and thus validate the key).

With your proposal, the attacker will know the discrete log of any SKE, that is, the value $x$ s.t. $xG = SKE$. So, what the attacker can do (after receiving the honest peers's $s, P$ values) is select arbitrary $s', P'$ values (for which he knows the discrete log of $P' = p'G$) and send those, and then receive the encrypted password based on the value the honest party computed.

Then, for every password in his dictionary, computes the corresponding $SKE$ and $xG = SKE$ and then computes:

$$H( (p'+s'x)(sG + x^{-1}P))$$

If the guess for SKE was correct, this is the same secret key that the honest party computed, and that can be validated.

This can be seen to be the same because, if the SKE is the value the honest party used, then $pG = sG + x^{-1}P$ and $p' + s'x$ is the discrete log of $P' + s' \cdot SKE$

The attacker can perform all this computation for every password in his dictionary, hence he can test every password as the result of a single exchange.

Now, DragonFly doesn't have to use hunt-and-peck; there are other known hash-to-curve transforms that convert a password to an EC point in a way that you can't compute the discrete log. However, DragonFly needs to use some such method...

$\endgroup$
3
  • $\begingroup$ Ah, I see. It must be impossible for the attacker to find the discrete log of $P'$ (the one he sent to the honest party) to the base $SKE$. Otherwise he can find a $p'$ consistent with the $P'$ and $s'$ he sent and use the regular equation to find the key. Thanks a lot. $\endgroup$
    – omgold
    Aug 21, 2020 at 8:26
  • $\begingroup$ Not quite obvious to me how the two hashed terms are equal. Perhaps somebody knows a source that could clarify? $\endgroup$
    – Sam
    Feb 4, 2021 at 12:39
  • 1
    $\begingroup$ @Sam: well, if $SKE = xG$ (that is, his guess is correct), then $p(p'G+s'SKE) = p(p'+s'x)G$. On the other side, then $(p'+s'x)(sG+x^{-1}P) = (p'+s'x)( (p+m)G + x^{-1}(-mxG))$, that is, $(p'+s'x)(pG + mG - mG) = (p'+s'x)pG$, which is the same value (and hence hash to a common value) $\endgroup$
    – poncho
    Feb 4, 2021 at 13:31

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.