WPA3 Dragonfly Handshake

In June 2018, Wi-Fi Protected Access 3 (WPA3) was published by the Wifi Alliance as successor of WPA2. WPA3 will not supersede WPA2, since WPA2 can still be used and manufacturers can continue producing WPA2 devices. Both standards will be in use in parallel and the transition phase is believed to be equally long to the coexistence of WPA2 and WEP that lasted for several years.

The major improvement of WPA3 is a improved handshake (Dragonfly-Handshake) that makes it impossible for attackers to record the 4-Way Handshake and launch a offline dictionary attack. WPA3 also introduces perfect forward secrecy which prevents attackers from decrypting past traffic after a key breach.

Implementation and Presentation

A implementation of the rfc7664 dragonfly key exchange using ECC can be found here: https://github.com/NikolaiT/Dragonfly-SAE/blob/master/dragonfly_implementation.py

The presentation slides can be downloaded here: https://github.com/NikolaiT/Dragonfly-SAE/blob/master/dragonfly.pdf

What is new in WPA3

As the name suggest, WPA3 is the successor of WPA2. WPA3 is a certification program and it supports four major features of which only one is mandatory: The new dragonfly handshake. Those four features are the following:

A new handshake called dragonfly (also called Simultaneous Authentication of Equals) that is resistant against dictionary attacks and provides forward secrecy. Makes use of Zero knowledge proofs.
A straightforward method to securely add devices to a network. Refereed to as Wi-Fi CERTIFIED Easy Connect program.
Protective mechanisms in open networks based on unauthenticated encryption. Opportunistic Wireless Encryption.
Increased key sizes with 192-bit sized keys. Only mandatory when certified as WPA3-Enterprise

Additionally, WPA3 supports Protected Management Frames (PMF) which makes it impossible to launch de-authentication attacks. WPA2 already supports this, therefore this is not a novelty of WPA3. However with WPA, PMF are included from the start in the certification program.

It's up to the vendors to decide which of those three voluntary features they are going to implement in their products. Either way, they must use the new dragonfly handshake such that they can use the label WPA3.

What is a zero knowledge proof (ZKP)?

A zero knowledge proof is a cartographic protocol that enables one party to to prove to another party that they know a value x without conveying any information other than the fact that they know the value of x.

WPA3 makes use of such a zero knowledge proof to ensure that no secrets of the passwords are transmitted in the SAE handshake, but both handshake participants can be sure that the other party knows that they possess the same and correct password.

In fact both parties prove that they have knowledge over the same password.

Dragonfly handshake (Simultaneous Authentication of Equals)

The dragonfly handshake is a key exchange using discrete logarithm cryptography that is authenticated using a password or passphrase. It is resistant to active attack, passive attack, and offline dictionary attack.

WPA3 has perfect forward secrecy (which WPA2 lacks), and protects from offline brute force attacks.

In contrast to WPA2, WPA3 is only allowed to use the "Advanced Encryption Standard" (AES) and no longer legacy protocols like the "Temporal Key Integrity Protocol" (TKIP) or "Wired Equivalent Privacy" (WEP).

The Pre-Shared Key (PSK) method of WPA2 is replaced by Simultaneous Authentication of Equals (SAE), which offers a more robust password-based authentication. The passphrase itself is no longer used for key derivation (keyword: Pairwise Master Key (PMK)), the key derivation is based on Elliptic Curve Cryptography (ECC) or a special form of ECC with integer numbers only called Finite Field instead.

Simultaneous Authentication of Equals (SAE)

In SAE, it is now possible to authenticate each other at the same time and independently of any role. It is of none importance who is client (STA) and access point (AP). SAE makes use of the Diffie-Hellman (DH) key exchange.

Establishing a Pairwise Master Key in SAE with ECC

The scenario is that two clients want to connect to each other in a mesh network. This handshake is called the dragonfly key exchange and is described in full extent in rfc7664.

Both access points create a mutual hashed password such that

if MAC1 > MAC2:
    hashed_password = H(MAC1 | MAC2 | Password | i)
else:
    hashed_password = H(MAC2 | MAC1 | Password | i)

where MAC1 and MAC2 are the mac addresses of the clients and i is a integer counter value. The Password is the piece of secret which both parties do share.

x = ((KDF(hashed_password, len)) mod (p-1)) + 1
y = sqrt(E(x))
P = (x, y)

Then this password is used as a point to derrive a point on a elliptic curve using a so called hunting and pecking technique. A key derivation function (KDF) extends the size of the hashed_password to a certain length and the result is taken modulus a prime p.

Then y is calculated by entering x into the elliptic curve function E. The square root is taken and we have our y value. Algorithmically, you can use the tonelli_shanks algorithm to compute the square root of a point.

If the generated point (x, y) is not a valid point on the elliptic curve, the counter i is increased by one and the algorithm is computed again until a valid point has been found.

Then two random numbers are chosen by both parties: private and mask in order to compute a new point and a scalar:

scal = (private + mask) mod r
new_point = inverse(mask • P)

Each party sends the scalar and new_point to the other party and thus both parties are in possession of scal_AP1, scal_AP2, new_point_AP1 and new_point_AP2.

Then a new point K is computed which is the shared secret between AP1 and AP2.

On AP1:

K = private_AP1 * ( scal_AP2 * P(x, y) o new_point_AP2 ) = private_AP1 * private_AP2 * P(x,y)

On AP2:

K = private_AP2 * ( scal_AP1 * P(x, y) o new_point_AP1 ) = private_AP2 * private_AP1 * P(x,y)

where o is the point operation that is point addition in ECC.

Then a function B is used to create a number from the Point K such that k = B(K) and then two tokens for each party can be computed as follows:

tok_AP1 = H(k | scal_AP1 | scal_AP2 | new_point_AP1 | B(new_point_AP2) | AP1-MAC)
tok_AP2 = H(k | scal_AP2 | scal_AP1 | new_point_AP2 | B(new_point_AP1) | AP2-MAC)

tok_AP1 != tok_AP2 because order of input matters. However, both parties can compute the token of the other party. If the tokens were found to be confirmed, the Pairwise Master Key is computed as follows:

PMK = H(k | scal_AP1 + scal_AP2 mod r)

The Pairwise Master Key is based on random numbers and not on the passphrase itself. The Point P(x, y) used in the computation of K however is based on the passphrase. But because of the Discrete Logarithm Problem in ECC, the private key (one random number, namely the private in computation of scal) can be kept secret and both parties can establish a shared secret based on random numbers (Elliptic Curve Diffie Hellman Key Exchange).

Offline-Dictionary: Although an attacker can sniff the scalars, it is infeasible to calculate private or mask and therefore is unable to use the transmitted tokens to check if a guessed passphrase is correct.

When the random numbers change, a new PMK is used which results in perfect forward secrecy. Then with the established PMK, the Personal Transition Key (PTK) can be set up during the EAP 4-Way handshake.

Other attacks such as DOS or side channel attacks

As soon as an AP notices too many SAE connection requests, it will use tokens to limit the amount of simultaneous attempts and thus makes it harder to bruteforce or DoS.

Side channel attacks (timing attacks) are prevented by computing always a fixed amount of iterations in each algorithm (upper threshold).

Big advantage:

As the password/passphrase is no longer part of the PMK, the complexity of it does no longer play an important role. Therefore, it is suitable to use passwords that are easy to enter and remember (But not so easy that they can easily be guessed by an attacker).

This improvement has also its downside: Users are going to reuse their main password for their wlan device. This means that an attacker who finds the main password of an victim in turn can guess the password for his WLAN device.

Dictionary attacks are no longer feasible.

Deploying WPA3 on the home network

The hostap project is split in two components:

hostapd, which lets you run a WiFi access point, and
wpa_supplicant, which lets you connect to an existing WiFi network

Is there support for WPA3? http://lists.infradead.org/pipermail/hostap/2018-July/038700.html

This article explains how to use WPA3 in your home network stack: https://gist.github.com/est31/d92d17acbb4ea152296f9b38764cd791

Offline dictionary attack against WPA2 handshake

The main reason the Dragonfly handshake is plugged in before the 4-way handshake is the following attack against the 4-way handshake:

The attacker...

goes in range
launches a deauthentication attack by sending deauthentication frames
records the 4-way handshake that is issued by the deauthenticated devices
now the attacker has everything he needs, he can go offline
the attacker can use one or more computers to try multiple passwords against the recorded handshake until he finds one that matches. Attackers can use amazon cloud computing or multiple gpus to increase computational force.

Criticism of the Dragonfly Handshake

Discussion about the problems and challanges of the Dragonfly handshake can be found here:

The use of the dragonfly PAKE has significant disadvantages:

There are known timing side channels on the protocol which already defeat the password protection.
There are several known active attacks on the protocol which already defeat the password protection, some under the assumption of non-robust implementations and others unconditional properties of the protocol.
The implication of the protocol is that passwords must be stored in a format which make them brute forceable, again defeating the password protection.
The parameter negotiation can be used to force malicious parameters, which is even more dangerous given how the protocol can be initiated by any side.
The implementation of the crypto is fragile (easy to exclude checks which subvert the security of the scheme). It is not clear that the specification includes all checks necessary for a robust implementation.

NSA backdoor?

This is on top of there being no formal security proofs and a lack of crypt-analysis, while there are other already standardized alternatives. To note that these protocols are typically very difficult to design.

I question the IETF's decision, believe this standard to contain significant cryptographic weaknesses that probably amount to an NSA backdoor, and will attempt to use VPN over WPA3 wifi connections.

Problems have also been noted here: https://news.ycombinator.com/item?id=17403697

Personal project from Dan Harkings?

I couldn't possibly speculate as to why, but one does feel inclined to agree that the people behind wireless LAN security haven't always generally chosen high quality methods in the past, and this feels to me like it could well be a continuation of that pattern.

Promoting Patents of Daniel Harkings? https://patents.justia.com/inventor/daniel-harkins

Dan Harkings reacts: https://www.schneier.com/blog/archives/2018/07/wpa3.html -> ctr-f: @Some Guy, do I know you? Have we worked together?

Harkings responds:

Regarding the weaknesses of dragonfly:

there is _one_ known side channel attack if one chooses to do the "hunting-and-pecking" version of PWE assignment. One could, alternatively, use any of the techniques in draft-sullivan-hash-to-curve that are not susceptible to side channel attack. In any event, there is a mitigation against side channel attack in the specification anyway so I don't think this is an issue.
what are the "several known active attacks"? I'm very curious to learn of these.
not quite right. It's a balanced PAKE so the implication is that the credential is stored in a format that is directly usable by the protocol. Even asymmetric PAKEs store a password-derived credential in a manner that is brute force-able. That's just the nature of the PAKE. If you have a better idea please describe it.
what malicious parameters are you talking about? Please let me know as this issue should be addressed if it really is an issue.
what is the crypto fragility you are talking about? Validating received elements? That is prudent for every protocol that does public key crypto. On the other hand, if there's some issue other than element verification then please do bring it to my attention!

Dragonfly - RFC 7664 Summary

Contents directly taken from RFC 7664

Resistance to dictionary attack means that any advantage an adversary can gain must be directly related to the number of interactions she makes with an honest protocol participant and not through computation.

This allows Dragonfly to be used in traditional client-server protocols and also in peer-to-peer applications in which there are not fixed roles and either party may initiate the exchange (and both parties may implement it simultaneously).

Prior to beginning the Dragonfly exchange, the two peers MUST derive a secret element in the chosen domain parameter set.

The Dragonfly exchange consists of two message exchanges, a Commit Exchange in which both sides commit to a single guess of the password, and a Confirm Exchange in which both sides confirm knowledge of the password.

A side effect of running the Dragonfly exchange is an authenticated, shared, and secret key whose cryptographic strength is set by the agreed-upon group.

Derivation of the Password Element

Prior to beginning the exchange of information, the peers MUST derive a secret element, called the Password Element (PE), in the group defined by the chosen domain parameter set.

The deterministic process to select the PE begins with choosing a secret seed and then performing a group-specific hunting-and-pecking technique -- one for FFC groups and another for ECC groups.

To thwart side-channel attacks that attempt to determine the number of iterations of the hunting-and-pecking loop used to find the PE for a given password, a security parameter, k, is used that ensures that at least k iterations are always performed.

Alice, Bob are the Mac Addresses of Alice and Bob.

base = H(max(Alice,Bob) | min(Alice,Bob) | password | counter)

The base is then stretched using the technique from Section B.5.1 of [FIPS186-4]. The key derivation function, KDF, is used to produce a bitstream whose length is equal to the length of the prime from the group's domain parameter set plus the constant sixty-four (64) to derive a temporary value, and the temporary value is modularly reduced to produce a seed:

n = len(p) + 64

temp = KDF-n(base, "Dragonfly Hunting and Pecking")

seed = (temp mod (p - 1)) + 1

The seed is then passed to the group-specific hunting-and-pecking technique.

If the protocol performing the Dragonfly exchange has the ability to exchange random nonces, those SHOULD be added to the computation of the base to ensure that each run of the protocol produces a different PE.

Hunting and Pecking with ECC Groups

The ECC-specific hunting-and-pecking technique entails looping until a valid point on the elliptic curve has been found. The seed is used as an x-coordinate with the equation of the curve to check whether x^3 + a*x + b is a quadratic residue modulo p.

If it is not, then the counter is incremented, a new base and new seed are generated, and the hunting and pecking continues.

If it is a quadratic residue modulo p, then the x-coordinate is assigned the value of seed and the current base is stored.

When the hunting-and-pecking loop terminates, the x-coordinate is used with the equation of the curve to solve for a y-coordinate.

An ambiguity exists since two values for the y-coordinate would be valid, and the low-order bit of the stored base is used to unambiguously determine the correct y-coordinate. The resulting (x,y) pair becomes the Password Element, PE.

Checking whether a value is a quadratic residue modulo a prime can leak information about that value in a side-channel attack.

The Commit Exchange

In the Commit Exchange, both sides commit to a single guess of the password. The peers generate a scalar and an element, exchange them with each other, and process the other's scalar and element to generate a common and shared secret.

First, each peer generates two random numbers, private and mask that are each greater than one (1) and less than the order from the selected domain parameter set:

1 < private < q
1 < mask < q

These two secrets and the Password Element are then used to construct the scalar and element:

scalar = (private + mask) modulo q
Element = inverse(scalar-op(mask, PE))

If the scalar is less than two, the private and mask MUST be thrown away and new values generated. Once a valid scalar and Element are generated, the mask is no longer needed and MUST be irretrievably destroyed.

The peers exchange their scalar and Element and check the peer's scalar and Element, deemed peer-scalar and Peer-Element. If the peer has sent an identical scalar and Element -- i.e., if scalar equals peer-scalar and Element equals Peer-Element -- it is sign of a reflection attack, and the exchange MUST be aborted.

ss = F(scalar-op(private,
                         element-op(peer-Element,
                                    scalar-op(peer-scalar, PE))))

To enforce key separation and cryptographic hygiene, the shared secret is stretched into two subkeys -- a key confirmation key, kck, and a master key, mk. Each of the subkeys SHOULD be at least the length of the prime used in the selected group.

kck | mk = KDF-n(ss, "Dragonfly Key Derivation")

where n = len(p)*2.

The Confirm Exchange

In the Confirm Exchange, both sides confirm that they derived the same secret, and therefore, are in possession of the same password.

The Commit Exchange consists of an exchange of data that is the output of the random function, H(), the key confirmation key, and the two scalars and two elements exchanged in the Commit Exchange. The order of the scalars and elements are: scalars before elements, and sender's value before recipient's value. So from each peer's perspective, it would generate:

confirm = H(kck | scalar | peer-scalar |
            Element | Peer-Element | <sender-id>)

The two peers exchange these confirmations and verify the correctness of the other peer's confirmation that they receive. If the other peer's confirmation is valid, authentication succeeds; if the other peer's confirmation is not valid, authentication fails.

If authentication fails, all ephemeral state created as part of the particular run of the Dragonfly exchange MUST be irretrievably destroyed. If authentication does not fail, mk can be exported as an authenticated and secret key that can be used by another protocol, for instance IPsec, to protect other data.

Resistance to dictionary attack means that an adversary must launch an active attack to make a single guess at the password. If the size of the dictionary from which the password was extracted was d, and each password in the dictionary has an equal probability of being chosen, then the probability of success after a single guess is 1/d. After x guesses, and removal of failed guesses from the pool of possible passwords, the probability becomes 1/(d-x).

Due to the problems with using groups that contain a small subgroup, it is RECOMMENDED that implementations of Dragonfly not allow for the specification of a group's complete domain parameter to be sent in-line, but instead use a common repository and pass an identifier to a domain parameter set whose strength has been rigorously proven and that does not have small subgroups.

The technique used to obtain the Password Element in Section 3.2.1 addresses side-channel attacks in a manner deemed controversial by some reviewers in the CFRG. An alternate method, such as the one defined in [hash2ec], can be used to alleviate concerns.

Fuzzing dragonfly

It is very easy to make a non-robust implementation of dragonfly, since the RFC lacks concrete implementation details. Timing attacks become easily possible when not implemented properly.

Fuzzing: Parameter negotiation with the random values is interesting. What is exactly checked? Race conditions? When is state aborted when handshake attempts overlap?

Protocol can be initiated by any site. Can this lead to other problems?

It is easy to exclude security checks in dragonfly in crypto stuff.

Resources

This article builds on the knowledge found in the following resources:

Very good practical article that attempts to deploy WPA3 for a home network: https://gist.github.com/est31/d92d17acbb4ea152296f9b38764cd791
Introduction to WPA3: https://wlan1nde.wordpress.com/2018/09/14/wpa3-improving-your-wlan-security/
RFC7664: RFC behind the dragonfly handshake that is used in WPA3: https://tools.ietf.org/html/rfc7664
Good visual introduction for Elliptic Curve Cryptography: http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
Update of the most recent changes in the WPA3 certification program: https://www.mathyvanhoef.com/2018/06/wpa3-missed-opportunity.html
Good article on protected management frames: https://wlan1nde.wordpress.com/2014/10/21/protected-management-frames-802-11w/
Bruce Schneier on WPA3: https://www.schneier.com/blog/archives/2018/07/wpa3.html
Discussion on problems with dragonfly: https://news.ycombinator.com/item?id=17403697
Author of Dragonfly on WPA3 himself: https://blogs.arubanetworks.com/industries/wpa3-the-next-generation-in-secure-mobility/
WPA2 4-Way Handshake: https://wlan1nde.wordpress.com/2014/10/27/4-way-handshake/

Template:Reflist