# 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 as 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

## 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:

1. 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.
2. A straightforward method to securely add devices to a network. Refereed to as Wi-Fi CERTIFIED Easy Connect program.
3. Protective mechanisms in open networks based on unauthenticated encryption. Opportunistic Wireless Encryption.
4. 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.

## Zero knowledge proof (ZKP) and WPA3

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.

## Cryptographic overview of Dragonfly and SPEKE

The Dragonfly handshake is essentially a SPEKE protocol. SPEKE stands for Simple Password Exponential Key Exchange.

Such a protocol implements more than the typical Diffie-Hellman Key Exchange. Remember that the typical Diffie-Hellman Key Exchange using ECC (which is called ECDH) looks like this.

### ECDH

Both Alice and Bob chose the following domain parameters:

• A prime ${\displaystyle p}$ and the elliptic curve ${\displaystyle E:y^{2}=x^{3}+ax+b\;{\bmod {p}}}$
• A primitive element (generator) `P = (x_P, y_P)`

Then ECDH is essentially the following exchange of messages:

Alice chooses a private key `a` in the domain `{2,3, #E-1}` Alice computes the public key `A = (x_A, y_A) = aP` Alice sends her public key `A` to Bob

Bob chooses a private key `b` in the domain `{2,3, #E-1}` Bob computes the public key `B = (x_B, y_B) = bP` Bob sends his public key `B` to Alice

Alice computes `K = aB` Bob computes `K = bA`

Both parties have the same shared secret Key `K`, since `aB = a(bP)` and `bA = b(aP)` and point addition is associative.

### SPEKE

Alice and Bob agree to a prime `p` and the elliptic curve `E: y^2 = x^3 + ax + b mod p`

Alice and Bob also agree to a hash function `H`

Alice and Bob agree to a shared password `P`

They both compute a generator `G` from the hashed password `G <- H(P)`

This is usually done with a so called hunting and pecking technique that uses a counter until a valid point on the curve was found. Each valid ECC point is a generator of the curve `E`

Alice chooses a secret random integer in the curve domain `a` and computes `aG mod p` and sends it to Bob

Bob chooses a secret random integer in the curve domain `b` and computes `bG mod p` and sends it to Alice

Alice and Both both compute their shared key similarly to the plain ECDH.

### Dragonfly

The Dragonfly handshake is essentially a SPEKE handshake. Here the Dragonfly handshake using ECC is discussed.

Both parties Alice and Bob agree to a ECC `E` and to a prime `p`

Alice and Bob have a same password `P`

They derive a `x` coordinate out of this password `P` with a hash function `H` and a key derivation function `KDF`. They repeat this step until this `x` coordinate is a valid quadratic residue mod p. This results in a valid point on the curve which is used as a generator `G`. In the dragonfly RFC this generator is also called `PE` password element.

Then Alice and Bob generate two random numbers, `private` and `mask`.

These two random numbers and the password element are then used to construct the `scalar` and `element`:

``` scalar = (private + mask) modulo q ```

```Element = inverse(mask o PE) ```

Alice and Bob exchange their `scalar` and `Element` and check that their peers `scalar` and `Element` are valid.

Then Alice and Bob compute a shared secret similarly as in the ECDH:

``` K = private o (peer-Element * (peer-scalar o PE)) ```

In the confirm exchange both parties confirm that they computed the same key `K`.

This is essentially done with the hash function `H()` that is used to hash a part of the key `K` and confirming that both parties have the same hash.

### Dragonfly/SPEKE simplified

Both parties Alice and Bob shared a password `P`.

They use a known transformation to derive a point `G` on the elliptic curve `E` (Using hash functions and key derivation functions and hunting and pecking techniques).

Then Alice and Bob each randomly pick a value in the domain of the prime `p`.

Alice randomly picks `a` and Bob randomly picks `b`.

They exchange `aG` and `bG`

Then both parties compute `K` as usual in the Diffie-Hellman Key exchange.

An offline dictionary attack is NOT FEASIBLE BECAUSE:

Attacker can guess `G` but he cannot find `aG` and `bG` because

1. The hardness of the discrete logarithm problem

2. Because `a` and `b` were randomly chosen!

Therefore the key `K` cannot be computed!

Even if the password guess is correct, you cannot confirm the correctness of your guess, because its very unlikely that the attacker also picked the random values correctly (those random values are in the range of at least 2^128 or more)

## 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:
else:
```

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
```

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.

## DOS and side channel attacks

As soon as an Wifi 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 launch DOS attacks against devices.

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

Because 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 which are easy to enter and remember (But not so easy that they can easily be guessed by an attacker).

This improvement has 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.

## 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:

1. There are known timing side channels on the protocol which already defeat the password protection.
2. 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.
3. The implication of the protocol is that passwords must be stored in a format which make them brute forceable, again defeating the password protection.
4. 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.
5. 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:

1. 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.
2. what are the "several known active attacks"? I'm very curious to learn of these.
3. 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.
4. what malicious parameters are you talking about? Please let me know as this issue should be addressed if it really is an issue.
5. 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 partially 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.

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
```

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

```scalar = (private + mask) modulo q
```

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 the Dragonfly/SAE handshake

What is fuzzing? https://en.wikipedia.org/wiki/Fuzzing

Fuzzing or fuzz testing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program. The program is then monitored for exceptions such as crashes, failing built-in code assertions, or potential memory leaks. Typically, fuzzers are used to test programs that take structured inputs. This structure is specified, e.g., in a file format or protocol and distinguishes valid from invalid input. An effective fuzzer generates semi-valid inputs that are "valid enough" in that they are not directly rejected by the parser, but do create unexpected behaviors deeper in the program and are "invalid enough" to expose corner cases that have not been properly dealt with.

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.

Parameter negotiation with 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 cryptographic primitives.

When a fuzzer for the dragonfly handshake is built, it would be advisable to create a smart/protocol-aware fuzzer and not a generic fuzzer that just creates any kind of package randomly.

### Reasons that make fuzzing promising

Often the source code is not available for wireless drivers. Reverse engineering and black box testing is to strenuous. Therefore, fuzzing might be the easiest approach to find vulnerabilities.

Fuzzers should be smart and have deep knowledge of the Dragonfly/SAE protocol to create semi valid frames/packets in order to reach deep into the logic of driver implementations.

Each vendor uses his own chipset, his own implementation, his own programming language and framework. This leads to a heterogeneous landscape of implementations of the new dragonfly handshake. There will be vulnerable implementations. Fuzzers can help discover them.

Maybe the biggest reason why fuzzing Wifi drivers is promising, because

• 1. Exploits can be triggered over the air
• 2. When code execution is achieved, it usually runs with kernel privileges
• 3. A wide array of manufactures creating device drivers heightens the possibility that bugs arise

### Which parts of the Dragonfly handshake might be candidates for vulnerable implementations?

• Length of exchanged parameters.
• Encoding of those parameters.
• Curve parameters in ECC implementations. May all curves be used?
• Length of PMK?

### Use monitor or master mode for fuzzing?

The 802.11 finite state machine has essentially three different states:

• State 1: initial state, not authenticated, not associated. Client probes for AP
• State 2: authenticated, not associated. Client is authenticated to the AP
• State 3: authenticated, associated. Client is authorized to send and receive data from the wired network through the AP.

There are many other internal states in the driver, but those three are the most fundamental. Fuzzing State 1 is much easier than the other states, because they require successful authentication/association. Additionally, 802.11 frames must be acked within very short delays, which makes it very hard to achieve fuzzing in monitor mode with a wireless card. Another difficulty is that there no verbose information/logging from the firmware to the operating system.

In order to increase the likelihood that beacon and probe response frames are parsed by the fuzzed AP, a fuzzer client can flood the network with those packets on various channels.

For fuzzing it's optimal to use Python3 as programming language in combination with the Scapy network package manipulation library.

WPA States
• Monitor mode for unauthenticated and unassociated states
• Master mode for authenticated/unassociated
• Master mode for authenticated/associated

Only fuzzing in state 1 is easy, because raw packet injection is easy. Other states require interaction with drivers.

### 802.11 candidate frames for fuzzing

What are some of the most important 802.11 frames that are interesting to tinker with?

• 802.11 Frame with MAC addresses and frame body
• 802.11 Frame control header with type and subtype fields
• 802.11 Beacon and probe response header with timestampt and beacon interval fields
• 802.11 Information element with information element type and length with value up to 1 Byte length

All fields of frames with variable type, length and value attributes seem to be promising regarding overflow vulnerabilities. For example the SSID takes up to 32 Bytes memory, but it might be interesting to check whether we can overflow a statically allocated memory location.

It's also possible to fuzz outside of the 802.11 specification to test whether the standard is correctly parsed and useful error handling is incorporated.