# How does Dragonfly key exchange work, in non-white-paper terms?

I'm trying to understand WPA3, whose Simultaneous Authentication of Equals is supposedly similar to Dragonfly Key Exchange.

Dragonfly is resistant to dictionary attacks, meaning that rather than an attacker being able to identify the use of a password in their dictionary with passive computation, they are forced to interact with one of the parties to make guesses.

I'm having trouble understanding the description of Dragonfly in the link, which is the only one I can find. How do Dragonfly's properties arise from the arithmetic? Is it some property of the "hunting-and-pecking" that only the non-attacker parties can perform the computation?

Dragonfly is resistant to dictionary attacks, meaning that rather than an attacker being able to identify the use of a password in their dictionary with passive computation, they are forced to interact with one of the parties to make guesses.

Actually, the goals are a bit more than that; even if you have an active attacker that can either modify the exchanges taking place, or can impersonate one of the end points (and attempt to negotiate with someone who does know the password), the best they can do from $$N$$ exchanges is to test $$N$$ entries from their dictionary.

We know that such an adversary can do at least that much; with a single exchange, they can take an entry from the dictionary, and (assuming that entry is the password) perform the exchange honestly with the valid endpoint, and see if the exchange fails or not. The goal of a PAKE (such as Dragonfly) is that they can't do any better than that generic attack.

How do Dragonfly's properties arise from the arithmetic? Is it some property of the "hunting-and-pecking" that only the non-attacker parties can perform the computation?

No, the hunting-and-pecking procedure $$P = \text{HuntAndPeck}(\text{Password})$$ is a public method of mapping a password to a 'group element' so that:

• The group element $$P$$ generates a prime sized subgroup; that is (using Finite Field terminology) the values $$P^x \bmod p$$ (for various values of $$x$$) can take up exactly $$q$$ values (where $$q$$ is a large prime).

• For two different passwords $$\text{Password1}$$ and $$\text{Password2}$$, the two values $$P1 = \text{HuntAndPeck}(\text{Password1})$$ and $$P2 = \text{HuntAndPeck}(\text{Password2})$$ are unrelated; that is, no one knows the value $$x$$ for which $$P1^x \equiv P2 \pmod p$$.

Instead, the PAKE properties arise from the actual protocol.

The RFC format is a horrid way to describe cryptography, and so here is the protocol in a nutshell in the honest case (still using the Finite-Field terminology, and eliminating sanity tests both sides run):

Alice and Bob run the Hunt-and-Peck procedure to convert their password into a group member $$P$$ (and since this is the honest case, we'll assume they have the same password). Then, Alice picks random values $$p, m$$, and transmits the values $$s = p + m \bmod q$$ and $$E = P^{-m}$$, and sends those to Bob. Bob also selects values $$p', m'$$ and sends $$s' = p' + m' \bmod q$$ and $$E' = P^{-m'}$$ to Alice.

Alice then computes $$(E' \times P^{s'})^p$$; this is $$(P^{-m'} \times P^{p' + m'})^p = P^{p p'}$$. Bob does the same computation, and gets $$P^{p' p}$$, which is the same value, and so we have our shared secret.

Now, why is this secure? The attacker is allowed to submit any $$s', E'$$ value it wants to Alice (subject to the sanity test that Alice runs); however (because of how the hunt-and-peck procedure works), he does not know a value $$E'$$ where he knows the values $$x, y$$ for $$E' = P1^x$$ and $$E' = P2^y$$ for two different passwords; hence if he can predict the value $$(E' \times P1^{s'})^p$$ for $$P1$$, he cannot know the value $$(E' \times P2^{s;})^p$$, and so he is effectively limited to testing one password (which we know he can do).

One final note: reviewing the Dragonfly RFC, I see that it would (as written) leak some information if you run in on an elliptic curve that doesn't have a prime number of points (that is, has a cofactor $$h > 1$$). If you're using (say) the NIST curves, that's not an issue; if you try to adapt it to run over (say) Curve25519, that would need to be addressed...

• That final note is fascinating! – forest Dec 5 '18 at 2:27
• I think we should absolutely stop using those curves, they are clearly insecure :P – Maarten Bodewes Dec 5 '18 at 7:04
• FWIW, I opened a question about that final footnote. – forest Jan 4 '19 at 2:24