In the ever-changing landscape of security protocols, standards continually adapt to address emerging threats and enhance security measures. Several years ago, Wi-Fi Protected Access 3 with Simultaneous Authentication of Equals (WPA3-SAE) underwent an update with the method of deriving the Password Element (PWE). This change involved the adoption of Hash-to-Element (H2E), a cryptographic technique also known as hash-to-curve, aimed at strengthening security against certain types of timing and side-channel attacks. This post will delve into the reasons behind this transition.

Simultaneous Authentication of Equals

One of the problems with WPA2-Personal is Pre-Shared Key (PSK) security scheme. The scheme is solely based on the complexity of the provisioned password (thus a more complex is “better” when using PSK) and also involves sending password-derived data over-the-air (OTA). In other words, the PSK approach is non-robust and is prone to offline dictionary attacks. All the attacker needs to do is capture the handshake.

WPA3-Personal addresses these problems with a protocol called Simultaneous Authentication of Equals (SAE). SAE was originally defined in IEEE Std 802.11s™-2011:

SAE authentication uses finite field cryptography to prove knowledge of a shared password

SAE introduces a more secure handshake mechanism that mitigates the risks associated with PSK and doesn’t require a long complex password to provide “better” security. SAE utilizes a mechanism called a Zero Knowledge Proof (ZKP). SAE ensures that even if an attacker captures the handshake, the attacker cannot perform an offline dictionary attack to guess the password. This is because the ZKP requires interaction (mutual authentication) with the Access Point (AP) for each guess. Additionally, because interaction is required APs can implement rate limiting and other countermeasures to thwart online dictionary attacks. This provides a significantly better defensive advantage than WPA2-Personal.

Zero Knowledge Proof

A Zero Knowledge Proof (ZKP) is a cryptographic method where a client (the prover) can prove to the AP (the verifier) that a password is true, without revealing any information beyond the validity of the password itself. This means the client can demonstrate they know a password without actually disclosing the password itself.

A classic example of a Zero Knowledge Proof is the “cave” analogy, where a prover (client) claims to know the password to pass through a magical door in a circular cave. The verifier (AP) can repeatedly ask the prover (client) to emerge from either side of the cave, proving they can pass through the door without ever revealing the password. This is the essence of ZKPs: verifying the truth of a claim without knowing the actual content of the claim.

The Zero Knowledge Proof (ZKP) implemented in SAE is called the Dragonfly Key Exchange by author Dan Harkins and is defined in RFC 7664. Importantly, Dragonfly is an unpatented ZKP and is such that vendors across the Wi-Fi industry could implement it without the risk of lawyers and patent wars. Dragonfly is a Password Authenticated Key Exchange (PAKE) that provides mutual authentication with forward secrecy and prevents offline dictionary attacks.

Password Element (PWE)

In this key exchange, the Password Element (PWE) plays a key role functionally serving as the shared secret between two devices attempting to authenticate with each other without relying on a Pre-Shared Key (PSK) like we did with WPA2-Personal.

In Dragonfly, both the client and the AP convert the provisioned password to an element. During the commit phase, they both negotiate the shared key. After the commit phase, the confirm phase confirms the peer negotiated the same key.

The PWE is derived from a user-provisioned password and is used in conjunction with other parameters and operations during the authentication process as described above.

What you need to know is that the PWE is a transformed representation of the password that facilitates secure authentication between devices without exposing the original password itself.

Hunting-and-Pecking (HNP)

How do we get an element from a password in an unpatented manner that the industry can use and implement?

The original method to derive the PWE was via a looping mechanism called hunting-and-pecking (HNP) where the verifier (AP) does an interactive search to select a random element from a predefined set and perform operations to check whether the selected element meets the desired criteria.

Basically, hash the password (and some other stuff) and get a number. That number is then used to see if the equation for the elliptic curve produces something valid. If not, try incrementing, hash again, and try again.

Once the verifier (AP) finds an element that satisfies the requirements, the verifier (AP) uses the element to derive the Password Element (PWE). Conceptually this seemed sufficient during protocol design.

It turned out that security researchers quickly found that the implementation of hunting-and-pecking (HNP) for Password Element (PWE) derivation was not robust. Mathy Vanhoef and Eyal Ronen quickly found vulnerabilities coining them Dragonblood.

The HNP method is a simple process that ended up leaking information. Primarily the number of times taken to find a valid element. This presented a dictionary partitioning attack where each connection attempt shaves down the number of possible passwords. A dictionary partitioning attack divides up a large dictionary of possible passwords into smaller subsets called partitions. The attacker then tests the partitions one by one, rather than trying each password individually. The idea is to identify which partition contains the correct password by observing the response to each subset. A dictionary partitioning attack is effective against APs that do not properly implement rate-limiting and lockout.

The solution to this problem is to loop a bunch of times even if the element is found on the first try, making guessing much harder. However, vendor implementations of the Dragonfly Key Exchange were also vulnerable to a side-channel attack. An attacker with device access could determine if the device found the element or not regardless of the number of loops.

Additionally, there was a side-channel attack against Brainpool curves, which are a set of elliptic curves defined over finite fields. Brainpool curves are often used in cryptographic applications due to their efficiency and security properties. Attacks against Brainpool curves are typically around exploiting information leaked through side channels (hence side-channel attack) during the execution of the cryptographic algorithm. Attackers analyze the side channels to potentially deduce information about the operations being performed, like deriving shared secrets. The attack on Brainpool curves was largely possible because code implementation was not written in constant time, which is fundamental in cryptographic algorithms to mitigate side-channel attacks.

The next few sections will provide some background on constant time coding and Brainpool curves.

Constant Time Coding

Let’s talk about constant time coding. Imagine you have a magic toy chest that holds many toys of different sizes and shapes. Imagine you want to find your specific favorite toy. Let’s say your magic toy chest has a rule that no matter how many toys are inside, your toy will be found in the same amount of time. Thus if you have 10 toys or 1000 toys in the chest, the chest will find your special toy in the same amount of time. That’s like constant time.

In code, when something is done in “constant time”, this means no matter how much data we have to work with, the same amount of time is taken to do the thing.

Why is constant time coding important? Imagine the magic toy chest requires guessing a secret word to operate. Suppose you have a sneaky friend who is trying to open your toy chest to steal one of your toys. If the chest takes longer to say “Nope, your guess is wrong” when the guess is closer to the secret word, your sneaky friend might figure out the secret word by paying attention to how long the toy chest takes to answer.

This analogy illustrates a side-channel attack where the sneaky friend exploits indirect information - the time the chest takes to respond - to infer the secret word. Your friends’ method of listening to how long the chest takes to respond mirrors an attacker observing the time it takes for a device to process each key exchange attempt. Like your friend observing the response timing of the chest to narrow down the correct secret word, an attacker could determine if a device successfully found the correct element in the Dragonfly Key Exchange based on processing times, even without directly seeing the number of attempts or the exchanged data. The unintended leaking of information through processing times allowed attackers to indirectly infer the correct passphrase through the side-channel attack.

Vendors must implement SAE with constant time coding to protect against side-channel attacks.

Uniform Execution Paths

In addition to execution timing, constant time coding also must ensure that the execution path does not vary based on input.

Imagine you’re navigating a maze to get to a treasure chest, and you have an observer watching from above, trying to guess the path you’ll take based on your movements.

In a non-constant time scenario, the path you take changes depending on the secret instructions you received before entering the maze. If the instructions are complex, you take longer routes with more turns; for simpler instructions, your path is shorter and more direct. The observer could deduce the complexity of your instructions based on these variations in your path.

In a constant time scenario, no matter the instructions, you always take the same amount of time and follow the same path to reach the treasure chest, performing some dummy loops or turns if necessary to make up the time when the instructions are too simple. To the observer, your path and the time it takes are always the same, making it impossible to infer anything about your secret instructions. This uniform execution path, much like in constant time coding, ensures that no external patterns or variations give away the secret, protecting the treasure chest (or password) from being inferred by watchers.

Vendors must implement SAE in a way that avoids conditional branches based on the password. The algorithm should not make decisions based on different password values that lead to different execution paths. For example, this means avoiding if-else conditions that depend on the passphrase contents.

Brainpool Curves

Now that we’ve covered constant time coding and uniform execution paths. What on earth are brainpool curves? Imagine you have a very big, squishy playdough ball. You can squish, stretch, and shape the ball into all sorts of shapes. In computers, cryptographers like to play with something similar, but instead of playdough, they use math to create special shapes called curves. These curves have special and precise rules about how they look.

A Brainpool curve is a special type of curve that cryptographers agreed to use for creating and keeping secrets safe. Just like you might have a secret handshake or secret language with a friend, computers use these curves to make sure their secrets can be shared without anyone else finding out. Brainpool curves are just one set of these curves that are known to be particularly good at keeping secrets. These curves make sure that when you send a secret over a technology communications medium, the secret is as safe as if you were to put the secret in a locked chest.

The security provided by Brainpool curves can be undermined by side-channel attacks, such as those that analyze the time it takes to perform cryptographic operations. Constant time coding ensures the operations take the same amount of time to execute, regardless of input values. If the execution time or execution path varies with different inputs, an attacker could potentially use the differences to infer secret keys.

Hash-to-curve (H2C)

The solution to making SAE resistant to side-channel attacks was to find a way to directly obtain an element without hunting and pecking. A patent-free hash-to-curve algorithm from the Internet Research Task Force (IRTF) was found that could directly obtain an element, given a password.

This hash-to-curve PWE derivation method produces a valid point on an elliptic curve satisfying the criteria by the curve’s equation. Hash-to-curve is implemented in constant time which solves the side-channel attacks on hunting-and-pecking and works with all of the curves used by the Dragonfly Key Exchange.

Hash-to-elemenet (H2E)

WPA3-SAE was then modified to address Dragonblood replacing HNP with H2C, removing unnecessary looping, and implemented in constant time to combat side-channel attacks.

The Wi-Fi Alliance ended up branding hash-to-curve (H2C) as hash-to-element (H2E). In the context of WPA3-SAE, the direct hashing, hash-to-curve cryptographic technique is called hash-to-element (H2E).

How is H2E advertised?

So, how does the AP interoperate with clients that support WPA3 and HNP, but are not updated to support H2E?

In the legacy bands of 2.4 GHz and 5 GHz, AP vendors are mostly allowing the use of either HNP or H2E. Some vendors like Cisco make this configurable allowing administrators to disable use of HNP in legacy bands. Others like Aruba do not expose knobs and handle PWE options automatically.

Note that HNP is not allowed in 6 GHz or with Wi-Fi 7 connectivity. I’ll touch on that a bit later.

Beacons and Probe Responses

The AP advertises Hash-to-Element (H2E) capability through Beacons and Probe Responses with the RSN Extension IE (RSNXE).

Authentication

Clients indicate which PWE method they are using during the first message of the SAE commit exchange. If the client sends status code 126 in the authentication frame, the client is using H2E for PWE derivation.

Client support for H2E

The majority of client vendors began supporting H2E in 2021.

• Android 12+
• Linux wpa_supplicant v2.10+
• Windows 10 21H2+
• Windows 11+

I’m not sure when Apple started supporting H2E, but their 6 GHz capable products support H2E due to the explanations in the following sections. If you know when and which versions across their product line, please shoot me an email so I can update this post.

Wi-Fi Alliance Role in H2E

The Wi-Fi Alliance decided to make H2E mandatory for certified devices in the following bands of operation and Wi-Fi iterations. This is because the vulnerabilities highlighted by Dragonblood demonstrate without proper protocol implementation and countermeasures in place, attackers could potentially exploit side-channel attacks to compromise Wi-Fi security.

Wi-Fi 6E

Because there are no legacy (Wi-Fi 5 or older) clients in 6 GHz, when using WPA3-SAE in 6 GHz operation, clients must use H2E. HNP is not allowed.

Wi-Fi 7

Wi-Fi 6 (802.11ax) and Dragonblood were released in the same year. The next iteration of Wi-Fi with version 7 presented the opportunity to make H2E mandatory for certified devices. When using WPA3-SAE with Wi-Fi 7 in any band of operation, clients must use H2E to obtain the PWE. HNP is not allowed.

Conclusion

The transition from Hunting-and-peeking and adoption of Hash-to-Element for PWE derivation in WPA3-SAE represent a step forward in improving Wi-Fi security. The WPA3-SAE protocol with H2E and proper implementation is resistant to side-channel attacks, providing users with better confidence in the integrity of their Wi-Fi networks. In this era of increasing security concerns, protocols like WPA3-SAE play a critical role in safeguarding Wi-Fi communications. The transition to Hash-to-Element for PWE derivation underscores the industry’s commitment to continuous improvement.

---

Thanks to Guillaume (GG) and Colin Vallance for reading drafts of this and providing feedback.

↑ Top