Dragonblood: A Security Analysis of WPA3's SAE Handshake

Transcript

1 Dragonblood: A Security Analysis of WPA3’s SAE Handshake Mathy Vanhoef Eyal Ronen New York University Abu Dhabi Tel Aviv University and KU Leuven [email protected] [email protected] design and implementation flaws. For instance, when verifying the ABSTRACT 59 assumptions made by the formal proof of the SAE handshake [ ], The WPA3 certification aims to secure Wi-Fi networks, and provides we discovered both timing and cache-based side-channel vulnera- several advantages over its predecessor WPA2, such as protection bilities in its password encoding method. We empirically confirmed against offline dictionary attacks and forward secrecy. Unfortu- all our findings against both open source and recently-released nately, we show that WPA3 is affected by several design flaws, proprietary implementations of WPA3. and analyze these flaws both theoretically and practically. Most All combined, our work resulted in the following contributions: prominently, we show that WPA3’s Simultaneous Authentication of Equals (SAE) handshake, commonly known as Dragonfly, is af- • We provide a self-contained and high-level description of fected by password partitioning attacks. These attacks resemble WPA3 and its SAE handshake (Section 2 and 3). dictionary attacks and allow an adversary to recover the password • We show that the anti-clogging mechanisms of SAE is un- by abusing timing or cache-based side-channel leaks. Our side- able to prevent denial-of-service attacks (Section 4). In par- channel attacks target the protocol’s password encoding method. ticular, by abusing the overhead of SAE’s defenses against For instance, our cache-based attack exploits SAE’s hash-to-curve already-known side-channels, a resource-constrained device algorithm. The resulting attacks are efficient and low cost: brute- can overload the CPU of a professional Access Point (AP). forcing all 8-character lowercase password requires less than 125$ • We present a dictionary attack against WPA3 when it is op- in Amazon EC2 instances. In light of ongoing standardization ef- erating in transition mode (Section 5). This is accomplished forts on hash-to-curve, Password-Authenticated Key Exchanges by trying to downgrade clients to WPA2. Although WPA2’s (PAKEs), and Dragonfly as a TLS handshake, our findings are also 4-way handshake detects the downgrade and aborts, the of more general interest. Finally, we discuss how to mitigate our frames sent during the partial handshake provide 4-way attacks in a backwards-compatible manner, and explain how minor enough information for a dictionary attack. We also present a changes to the protocol could have prevented most of our attacks. downgrade attack against SAE, and discuss implementation- specific downgrade attacks when a client improperly auto- connects to a previously used WPA3-only network. 1 INTRODUCTION We empirically investigate the feasibility of timing attacks • Alliance recently announced WPA3 as the more secure The Wi-Fi against WPA3’s SAE handshake (Section 6). This confirms successor of WPA2. Unfortunately, it was created without public timing attacks are possible and leak info about the password. review, meaning experts could not critique any of WPA3’s new We present a novel micro-architectural cache-based side- • features before they were released. Moreover, although the new channel attack against the SAE handshake (Section 7). This handshake of WPA3 was designed in an open manner, its security attack leaks information about the password being used. guarantees are unclear. On one hand there is a security proof of Our attack even works against hash-to-curve algorithm im- a close variant of WPA3’s handshake [ 59 ], but on the other hand plementations that include countermeasures against side- another close variant of the handshake received significant criticism channel attacks. This type of attack against hash-to-curve during its standardization [ 68 , 79 ]. These issues raise the question algorithms is of independent interest due to current stan- whether WPA3 is secure in practice. ]. 73 dardization efforts surrounding hash-to-curve methods [ We remark that WPA3 does not define new protocols, but in- • We show both theoretically and empirically how the recov- stead mandates which existing protocols a device must support. ered timing and cache info can be used to perform an offline This means WPA3 is not a specification, but a certification. Put password partitioning attack (Section 8). This enables an differently, devices can now become WPA3-certified, which assures adversary to recover the password used by the victim. they implement certain protocols in an interoperable manner. The Finally, we will discuss related work in Section 9, and we give only novelty in the WPA3 certification is a transition mode where concluding remarks in Section 10. WPA2 and WPA3 are simultaneously supported for backward com- patibility (see Section 2.2). Although WPA3 follows recommended 1.1 Responsible Disclosure practice by using existing standards, we believe more openness to We collaborated with the alternative protocols could have increased its security. Wi-Fi Alliance and CERT/CC to notify all In this paper we perform a security analysis of WPA3’s Simul- affected vendors in a coordinated manner, and helped with imple- taneous Authentication of Equals (SAE) handshake. This hand- menting backwards-compatible countermeasures. An overview of shake is designed to prevent dictionary attacks, and constitutes the affected products and vendors, including allocated Common Vul- biggest improvement over WPA2. We systematically analyzed its nerabilities and Exposures (CVE) identifiers, can be found at [ 17 ]. We hope that our work will influence the deployment of WPA3 security by reading specifications, inspecting formal proofs, and au- diting open-source implementations. This analysis revealed several before it becomes widespread and hard to patch.

2 Mathy Vanhoef and Eyal Ronen Access Point Client 2 BACKGROUND In this section we introduce the (relatively few) new features that Beacons(RSNE with supported ciphers) are defined in the WPA3 certification [ 90 ], and we explain relevant Select cipher aspects of the 802.11 standard [45]. Auth-Commit( 2.1 An Overview of WPA3 scal , elem 1 ) 1 The WPA3 certification was created with two types of networks in ) elem , 2 scal 2 Auth-Commit( mind. The first one is a home network, where users authenticate using a pre-shared password, and the second one is an enterprise Derive PMK Derive PMK network, where more advanced authentication methods can be Auth-Confirm( conf ) 1 used (e.g. certificates, smart cards, and so on). To differentiate both SAE handshake types, the term WPA3-SAE is used for home networks, and the ) conf 2 Auth-Confirm( term WPA3-Enterprise is used for enterprise networks. WPA3-Enterprise uses existing handshakes, but requires that AssocReq(RSNE-Chosen with chosen cipher) ciphers used during authentication provide at least 192 bits of se- curity. That is, the ciphersuites must use at least 384 -bit curves Association Response for elliptic curve cryptography, and use at least 3072 -bit moduli Association when using RSA or DHE. Currently the WPA3 certification does Msg1(ANonce) not mention requirements on the length of session keys or hash ]. However, a security level 90 functions used after authentication [ Derive PTK -bits will likely also be used after authentication [ 18 ]. 192 of at least The WPA3-SAE mode for home networks is more interesting. It Msg2(SNonce, MIC; RSNE-Chosen) mandates support for the existing Simultaneous Authentication of Derive PTK & Verify RSNE Equals (SAE) handshake. This handshake is a Password Authenti- cated Key Exchange (PAKE), meaning authentication is performed Msg3(MIC; RSNE, GTK) based on a password. The SAE handshake provides forward secrecy 4-way handshake and resistance against offline dictionary attacks, and was added to Verify RSNE ]. Several variants of this handshake 47 the 802.11 standard in 2011 [ Msg4(MIC) are also used in other protocols (see Section 3.1). The output of WPA3’s SAE handshake is a Pairwise Master Key (PMK), which connection established handshake to derive a is subsequently used to perform a 4-way Pairwise Transient Key (PTK) (see Figure 1). Note that, even though Figure 1: Connecting to an AP using WPA3. First the SAE handshake, it is not vulnerable to 4-way WPA3 still uses WPA2’s handshake negotiates the master key (PMK), and then the dictionary attacks. This is because the PMK generated by the SAE 4-way handshake derives a session key (PTK). To support handshake has much higher entropy than the password itself. mesh networks, the SAE handshake was made so both par- Finally, in both modes, Management Frame Protection (MFP) ties can initiate it in parallel (hence the crossed arrows). must be used. Most notably, MFP prevents deauthentication attacks where an adversary forcibly disconnects victims from the AP. that are transmitted periodically to advertise the presence of a net- 2.2 WPA3-SAE Transition Mode work. Clients also use the RSNE in association requests to inform Because existing devices may not receive support for SAE of MFP, the AP of the cipher suites they wish to use. Example authentica- they will not be able to use WPA3. To accommodate these older handshake, the 802.1X protocol, the 4-way tion algorithms are the devices, the WPA3 certification defines how a network can simul- SAE handshake, etc. Example encryption algorithms are GCMP or handshake and WPA3’s SAE 4-way taneously support WPA2’s CCMP. Because the RSNE is not authenticated in beacons, an (AES-) handshake. In this transition mode, the AP advertises that MFP is adversary can spoof this element by forging beacons. To detect this, and SAE handshake. optional, and that it supports both the 4-way the received RSNE is cryptographically verified during WPA2’s 4-way handshake Older WPA2 clients can then connect using the handshake. In particular, when the AP receives message 2 4-way without MFP, while new WPA3 clients can connect using SAE with from the client, the AP verifies that the RSNE in the client’s asso- MFP enabled. The only requirement placed on WPA3 clients is that ciation request was not altered (see Msg2 in Figure 1). Similarly, they must use MFP when connecting to a WPA3-capable AP, even when the client receives message 3 from the AP, the client verifies though the AP advertises MFP as optional. 4-way that the RSNE included in beacons was genuine. Since the handshake is always executed at some point when a station (i.e. a 2.3 Downgrade Protection client or AP) connects for the first time to a network, the RSNE is An AP advertises its supported cipher suites, i.e., authentication always verified. In case a mismatch is detected, the handshake is and encryption algorithms, in the Robust Security Network Ele- aborted. This prevents an adversary from spoofing the RSNE, and ment (RSNE). The RSNE is included unauthenticated in beacons thereby tricking the client into using a weaker cipher suite.

3 Dragonblood: A Security Analysis of WPA3’s SAE Handshake Alice (e.g. a client) Bob (e.g. an AP) 3 THE SAE “DRAGONFLY” HANDSHAKE In this section we introduce WPA3’s Simultaneous Authentication of Equals (SAE) handshake, and discuss side-channel defenses that and r Pick random m Pick random r m and A B A B were added in various revisions of the handshake. s mod ) + m + m r ( = ) q s mod = ( r q A B A B B A − = = E E · P P · − m m A A B B 3.1 Background and History Auth-Commit( s The WPA3 certification mandates support for the SAE handshake. , E ) A A 33 This handshake was first introduced by Harkins in 2008 [ ], and ) E , s B B Auth-Commit( was added to the 802.11 standard in 2011 [ ]. Several close variants 47 of the SAE handshake are also used in other protocols. The term Verify E E and s s and Verify A B B A Dragonfly is commonly used to refer to this family of handshakes. E P ) + ) E ·( + P · s s ·( r r = K = K · A B A B A B The SAE handshake is a balanced Password Authenticated Key ) = Hash ( K κ ) κ = Hash ( K Exchange (PAKE). Note that in a balanced PAKE, both endpoints , s ( = tr tr , s ) , E ) E , s , E , s E = ( A A B B B A A B store the password in the same representation (which is in plaintext c tr , κ ( HMAC = = c HMAC ( ) κ , ) tr A B when using SAE). The SAE handshake takes as input a pre-shared secret, and outputs a high-entropy Pairwise Master Key (PMK). Auth-Confirm( c ) After executing SAE, the handshake is used to negotiate 4-way A a session key called the PTK (recall Figure 1). Finally, the SAE ) c B Auth-Confirm( handshake explicitly supports mesh networks, by allowing both endpoints to initiate the handshake concurrently. Verify Verify c c A B 3.2 Protocol Details Figure 2: Details of the SAE handshake. Recall that it sup- The SAE handshake supports both Finite Field Cryptography (FFC) ports mesh networks where two stations may simultane- using multiplicative groups modulo a prime (MODP groups), and it ously initiate the handshake (hence the crossed arrows). We supports Elliptic Curve Cryptography (ECC) using elliptic curve assume elliptic curves are used, since all implementations groups modulo a prime (ECP groups). The 802.11 standard man- of SAE (and hence also WPA3) are required to support it. dates that if a station advertises support for SAE, it must imple- ment the elliptic curve NIST P-256 [45, §12.4.4.1] [ ]. Support 43 , 1 the other participant using a commit frame. On reception of these for other groups is optional, meaning there is no mandated support is within values, each participant verifies that the received scalar s i for MODP groups. Therefore we assume elliptic curves are used, is a valid the range 1 , q [ , and that the received group element E [ i unless mentioned otherwise. 45 point on the curve being used [ , §12.4.5.4]. If one of these checks When describing elliptic curve operations, we use lowercase fails, the handshake is aborted. Forward secrecy is provided by letters to denote scalars (i.e. integers), and uppercase letters to m P and relying on the difficulty of deriving E , i.e., it relies given i i denote elliptic curve points. With SAE, all elliptic curves are defined 3 2 on the hardness of the elliptic curve discrete logarithm problem. x p + ax + = mod p where y over the equation is a prime and b In confirm phase, each participant calculates the shared secret the values a , b , and p depend on the curve being used. We use (see Figure 2). The x-coordinate of this point is processed point K to denote the prime q G to denote the generator of a group, and . Finally, a HMAC over the using a hash function to derive the key κ G . When executing the SAE handshake, the user-readable order of κ is calculated using the key handshake summary . The result of tr password is converted into a group element. For MODP groups this c , is sent to the other participant in a confirm this hash, denoted by i is done using a hash-to-group algorithm, and for elliptic curves c frame. On reception of , the receiver verifies its value. If it equals i using a hash-to-curve algorithm. The resulting password element is the expected value, the handshake succeeds, and the negotiated denoted by , and its generation is described in detail in Section 3.3. P becomes the Pairwise Master Key (PMK). Otherwise the κ key The handshake itself consists of a commit phase followed by a confirm frame is ignored, and the handshake eventually times out. confirm phase. These two phases, along with the accompanying For details on how the SAE handshake negotiates which crypto- elliptic curve operations, are illustrated in Figure 2. Note that the graphic group is used, we refer to Section 5.2. The handshake also handshake can be initiated concurrently by both participants (which has a mechanism to prevent denial-of-service (DoS) attacks, but may happen in mesh networks after connection loss). Nevertheless, unfortunately this defense is flawed (see Section 4). in the more widely-used infrastructure mode, the client will initiate the handshake by sending its commit frame, and subsequently the 3.3 Password Derivation AP will reply using a commit and confirm frame. In turn the client When constructing the commit frame, the pre-shared password is sends its confirm frame, completing the handshake. first converted into a curve point using a hash-to-curve algorithm. In the commit phase, each participant first picks a random num- q , 2 ∈ [ (see Figure 1). The r ber [ q , 2 ∈ [ The specific algorithm used in SAE is based on a try-and-increment m and a random mask [ i i . sum of these numbers (modulo q ) must also lie in the range [ 2 , q [ method, and is shown in Listing 1. Summarized, it first hashes m They then calculate the public group element , after = − E P · the password, together with a counter and the MAC addresses of i i which they send both the scalar E and the group element to s both stations, and uses the output of the hash as the x -coordinate i i

4 Mathy Vanhoef and Eyal Ronen Listing 1: Converting the pre-shared password into an ellip- increase was based on security advice given in a close variant of tic curve point in Python-like pseudocode [45, §12.4.4.2.2]. ]. However, this update was not backported 60 the SAE handshake [ k = to older versions, meaning products using a version that use 1 def password_to_element_ecc(password, MAC1, MAC2, k=40): 2 found = False are vulnerable to timing attacks (see Section 6.5). Intel’s iwd 4 3 counter = 0 client uses the value k = 20 , and the reference implementation of 4 base = password 5 while counter < k or not found: 32 SAE by Harkins uses value 40 [ ]. For comparison, the Dragonfly 6 counter += 1 specification in RFC 7664, which is a close variant of SAE, explicitly 7 seed = Hash(MAC1, MAC2, base, counter) , §4]. The value 40 is k recommends a value of at least [ 40 37 = value = KDF(seed, "SAE Hunting and Pecking", p) 8 9 if value >= p: continue based on a back-of-the-envelope calculation by Igoe [50]. 10 Given the above history of timing side-channels and defenses, if is_quadratic_residue(value^3 + a * value + b, p): 11 one may wonder why an alternative design was not used that avoids 12 if not found: x = value 13 side-channel attacks. In particular, during its review by the CFRG, 14 save = seed suggestions were made to exclude the MAC addresses from the 15 found = True base = random() 16 hash-to-curve algorithm [ ]. With this modification, the , 48 , 49 , 69 80 17 curve point can be generated offline, and can then be reused in every 18 y = sqrt(x^3 + a * x + b) mod p connection attempt. This makes side-channel attacks significantly 19 if LSB(save) == LSB(y): 20 P = (x, y) harder, since the password element is generated only once. else: 21 22 P = (x, p - y) return P 23 3.4 Variants of Dragonfly Several minor variants of the SAE handshake exist, and the resulting . [35, 37–39] family of handshakes is often referred to as Dragonfly Note that the RFCs describing these variants are not standards-track of the curve point. It then tries to find a solution for y over the RFCs, instead, they are either informational or experimental ones. 3 2 x + mod p . In case a solution exists, the point ax equation = + y b This means they are independent submissions, and not officially P . If no solution is found, the ( x , y ) becomes the password element endorsed by e.g. the Internet Engineering Task Force (IETF). For counter is increased, and another attempt is made to find a solution example, there was no consensus in the TLS working group to using the new value for x . Finally, to mitigate timing attacks, for y ]. To the best of our adopt the TLS-PWD variant of Dragonfly [ 71 times, no matter when a solution k the main loop is always executed knowledge, only the 802.11 standard officially adopted Dragonfly. y for is found. In the extra iterations, calculations are based on a In all variants, the password element must be computed online, randomly generated password instead of the real one. because it depends on nonces or on the identities of the participants. Interestingly, this algorithm underwent various changes, and all For example, the TLS variant of Dragonfly specified in RFC 8492 these changes attempt to reduce side-channel leaks. In particular, includes random nonces from the client and server in the hash- the original 802.11s amendment that introduced SAE did not include to-curve algorithm. As a result, the password element must be the additional iterations [ 47 , §8.2a.4.2.2]. Put differently, originally computed online, meaning implementations may be affected by the y the algorithm immediately stops when a solution for is found. An same timing and cache-based side-channel attacks we will present amendment proposed in 2011 added the extra iterations to mitigate in this paper. Similarly, implementations of TLS-PWD will also have 34 ], and this amendment was incorporated into the timing attacks [ a large overhead due to the required side-channel countermeasures. 2012 version of the 802.11 standard [46, §11.3.4.2.2]. Sensitive information can also leak in the Legendre function on 4 ABUSING SAE’S SIDE-CHANNEL DEFENSES line 11 which checks if the left-hand side of the curve equation is a In this section, we show how side-channel defenses of SAE (against quadratic residue. If it is a quadratic residue, a solution for y exists. already-known leaks), introduce overhead that can be abused in a However, depending on how the Legendre function is implemented, denial-of-service (DoS) attack. Simultaneously, we bypass SAE’s its running time may leak information [ ]. To prevent timing at- 44 anti-clogging mechanism that is supposed to prevent DoS attacks. tacks, an amendment to 802.11 recommends (but does not mandate) , 36 ]. This amendment got the use of quadratic residue blinding [ 24 4.1 Background on (Anti-)Clogging Methods incorporated into the 2016 version of 802.11 [45, §12.4.4.2.2]. All versions of the SAE handshake contain an anti-clogging method We also note that the size of the counter value is only 1 byte. However, because the probability of finding a solution for y is to mitigate DoS attacks. This is needed because an AP must per- form costly operations when receiving a commit frame, which an approximately 50%, the chance of the counter overflowing and 255 − adversary can otherwise abuse in a DoS attack by forging commit causing an infinite loop is only 2 . Even an adversary who forges 63 unicast MAC addresses in an attempt to cause an overflow, only . This problem is worse in amended versions of [47, §8.2a.6] frames 2 − 192 has a chance of 2 of triggering an overflow and infinite loop. SAE that contain side-channel defenses against (already-known) Another critical remark is that the 802.11 standard does not information leaks, as these defenses further increase the cost of processing commit frames. More precisely, using quadratic residue . This parameter denotes the total k specify a minimum value for number of iterations that must always be executed to mitigate blinding, and a fixed number of 40 iterations in the hash-to-curve timing attacks. In practice, version 2.1 to 2.4 of wpa_supplicant algorithm, further increases processing time. For example, when , while newer versions use 4 = k and hostapd use . This = k 40 hostapd added quadratic residue blinding, the increased processing

5 Dragonblood: A Security Analysis of WPA3’s SAE Handshake 100% ]. To 42 time even caused timeouts on resource constrained devices [ prevent timeouts, the 802.11 standard was updated to give stations 80% Target CPU 2 seconds (instead of 40 ms) to process commit frames [9]. Attacker CPU 60% The anti-clogging defense of SAE consists of a cookie exchange Total airtime procedure. Simplified, in this procedure the client must reflect a 40% random (secret) cookie sent by the AP, before the AP will process 20% the client’s commit frame. This is inspired by anti-clogging defenses 0% from IP-based networks. More precisely, such a defense was also Utilization of resource used by a precursor of IPsec called Photuris, and a similar variant 0 90 80 70 40 100 10 20 60 30 50 ]. How a cookie 55 of this cookie mechanism is also part of IKEv2 [ is generated is implementation dependent, but it must satisfy the No. of commit exchanges per second 54 following requirements [ ]: (1) the cookie depends on the identities of both parties; (2) only the responder (server) can generate valid Figure 3: Clogging attack against a professional AP from cookies; and (3) the cookie generation and verification must be vendor A using curve P-256. The attacker uses a Raspberry fast. The recommended method to meet these requirements, is to Pi 1 model B+, and its CPU usage is shown in the small generate a secret value, and calculate the cookie as follows: dashed line. The total amount of airtime consumed by all Cookie = Hash(ConnectionID ∥ InitiatorID ∥ secret) SAE frames is shown in the long dashed line. The hash function should be a secure one-way hash such as SHA256. With this cookie exchange, an adversary can no longer initiate hand- shakes using spoofed IP addresses. This prevents an adversary from, . We found experiment, the attack is performed using curve P-256 for example, trigger expensive public key operations by forging that spoofing more than 70 commit exchanges every second causes frames with spoofed IP addresses [ 65 ]. Although the attacker can the CPU usage of the AP to reach 100% (see Figure 3). As a result, still use its real IP address in forged frames, these requests can be clients that try to connect using WPA3 either face long delays, or throttled based on the IP-address. Additionally, because an attacker cannot connect at all. In contrast, the CPU usage of the attacker is must use its real IP address, the threat of attacks is reduced [65]. only 14.2%. Since all APs are required to support NIST curve P-256, this shows an adversary can perform denial-of-service attacks using 4.2 Defeating SAE’s Anti-Clogging cheap resource-constrained devices. In a second experiment, we forged commit exchanges using the The SAE handshake of WPA3 also uses a cookie exchange procedure curve. With this curve the impact is an order of magnitude P-521 to mitigate clogging attacks. More precisely, this mechanism is sup- more catastrophic. Now the target’s CPU can be overloaded by posed to prevent DoS attacks that flood the victim with bogus SAE forging merely 8 commit exchanges every second (see Figure 8 in , §12.4.6]. How- 45 commit messages from forged MAC addresses [ the Appendix). On our Raspberry Pi, this attack consumes 2.7% of ever, in contrast to spoofing IP addresses, it is trivial to spoof MAC the CPU. In other words, a weak adversary is able to clog a high- addresses. Even if the AP employs a cookie exchange mechanism, end AP. We consider it worrying that such a devastating attack is the adversary can trivially capture all cookies (i.e. anti-clogging possible against a modern security protocol. tokens), since everyone within range of the AP can capture and Figure 3 and 8 also show the amount of airtime consumed by the reflect the secret cookies. More generally, a cookie exchange mech- injected frames. We observe that this is just a fraction of the total anism can trivially be defeated in any broadcast network, since available airtime, showing that our attack is more efficient than a everyone will receive the (supposedly secret) cookies. straightforward DoS where an attacker simply jams the channel. 4.3 Experiments 4.4 Attack Optimizations We implemented a Proof-of-Concept (PoC) of a clogging attack Our clogging attack can be optimized if we take into account how where the adversary inject commit frames using spoofed MAC APs generate the anti-clogging token. Note that 802.11 standard addresses, and reflects any cookies (i.e., anti-clogging tokens) it receives. Out tool is written in C for performance reasons, and build recommends to generate anti-clogging tokens by computing a hash on top of aircrack-ng . The tool can forge commit frames using any over a secret value and the MAC address of the sender. All devices we inspected indeed follow hashing-based mechanism. Additionally, elliptic curve supported by SAE. It is essential that the adversary the 802.11 standards recommends to track the number of open and acknowledges all frames sent to forged MAC addresses. Otherwise, unfinished handshakes. When this number hits a given threshold, the AP will retransmit replies up to eight times, making it difficult the secret value should be renewed [45, §8.2a.6]. This implies that for the adversary to inject enough commit frames to overload the target. Fortunately, by relying on the virtual Wi-Fi when the number of open and unfinished handshakes is always interface support above this threshold, the threshold itself will not be hit, meaning of Atheros chips, we can easily make it acknowledge frames sent the secret value is not updated. to any forged MAC address [84, §5.3]. In our clogging experiments, the adversary used a Raspberry If the secret value is infrequently updated, we can reuse previ- Pi Model B+ having a 700 MHz processor. The Raspberry Pi used ously captured anti-clogging tokens. In particular, we were able to a WNDA3200 wireless dongle. Our target was the professional inspect the devices shown in Table 1. The first one is an AP from AP from vendor A, which has a 1200 MHz processor. In our first vendor A, which generates anti-clogging tokens as recommended

6 Mathy Vanhoef and Eyal Ronen Table 1: Renewal interval of the secret that is used to gener- Access Point (adversary) Client (victim) ate anti-clogging tokens for various devices and standards. Beacons(RSNE with only WPA2 support) ○ 1 Renewal time Version Standard or Implementation Select WPA2 AP from vendor A 10.20.0168 threshold reached every 1 minute Hostapd v2.6 AssocReq(RSNE with WPA2 as chosen cipher) Reference Implementation May 2014 never renewed ○ 2 Association Response every 1 minute 1999 Phorious [54] 2014 not specified IKEv2 [55] 802.11 [45] threshold reached 2016 Msg1(ANonce) Derive PTK ○ 3 by the standard, meaning it is easy to bypass. The second imple- Msg2(SNonce, MIC; RSNE-Chosen) mentation we tested is the open source hostapd. It also generates anti-clogging tokens as recommended by the standard, except that Perform dictionary attack it renews the secret value every minute. This means we can reuse anti-clogging token for one minute. Against hostapd we also discov- ered that, if an adversary keeps forging commit frames using the Figure 4: Dictionary attack against WPA3-SAE when it is op- same MAC address, the AP will constantly (re)process the frame erating in transition mode, by attempting to downgrade the without requiring anti-clogging tokens, leading an an efficient DoS. client into directly using WPA2’s 4-way handshake. Harkins’ reference implementation of SAE also follows the 802.11 ]. Table 1 also standard, but it never renews the secret value [ 32 modifies beacons so the client thinks the AP only supports WPA2, shows when other protocols such as IKEv2 renew the secret value. 4-way handshake the client will detect the downgrade and abort the 4-way of WPA2. More precisely, message 3 of WPA2’s handshake 4.5 Countermeasures contains all the supported cipher suites of the AP in the authen- To reduce the impact of an attack, the derivation of the password ticated RSNE element (recall Figure 1). Because this handshake element can be done in a low-priority background thread. Although message is authenticated under the session key (PTK), the adver- legitimate WPA3 clients will be unable to connect during an attack, sary cannot modify it. As a result, the client will detect that RSNE this at least assures other network functionality is not impacted. in message 3 does not match with the RSNE received in beacons, Additionally, larger elliptic curves or MODP groups can be disabled and will subsequently abort the handshake. Hence it is indeed not by default, to reduce the impact of DoS attacks. possible to force a WPA3-capable client and AP to use WPA2. A better solution is to use a constant-time and more efficient The problem is that, although downgrade attacks are detected by 73 hash-to-curve algorithm [ ]. Another solution would be to modify handshake of WPA2, by that point an adversary has cap- 4-way the the SAE handshake such that the password element is independent tured enough data to perform a dictionary attack. This is because an of the MAC addresses. Doing this would allow both the client and adversary only needs a single authenticated 4-way handshake mes- AP to calculate the password element offline, and reuse it in all sage to carry out a dictionary attack [ 62 ]. Therefore, even though handshakes, preventing our attack. However, SAE’s security proof the downgrade is detected, by this point it is too late. Moreover, a ], to verify 59 must then be updated to take this change into account [ man-in-the-middle position is not needed to carry out the attack. whether the protocol would remain secure with this change. The only requirements are that we know the SSID of the WPA3- SAE network, and that we are close to a client (see Figure 4). If 5 DOWNGRADE & DICTIONARY ATTACKS these conditions are met, the adversary can broadcast a WPA2-only In this section we present a dictionary attack against WPA3-SAE in Figure 4). This causes the network with the given SSID (stage ○ 1 when it is operating in transition mode, and discuss an implemen- client to connect to our rogue AP using WPA2. The adversary can tation-specific downgrade attack against WPA3-only networks. We 4-way handshake, since this message forge the first message of the also present a downgrade attack against the SAE handshake itself. in Figure 4). In response, the ○ is not yet authenticated (stage 3 4-way victim will transmit message 2 of the handshake, which is 5.1 Downgrade to Dictionary Attack authenticated. Based on this authenticated handshake message, a Our first attack is against WPA3-SAE transition mode. Recall from dictionary attack can be carried out [62]. We tested the above attack against several client-side implemen- Section 2.2 that in this mode the AP is configured to accept connec- tations of WPA3 (see Table 2). With the first three tested devices, tions using both WPA3-SAE and WPA2. This provides backward compatibility with older clients. Moreover, WPA2’s hand- 4-way the network to connect with must be manually configured. That is, shake detects downgrade attacks, meaning an attacker cannot trick we had to specify the name of the network to connect with, and that a WPA3-capable client into successfully establishing a connection it uses WPA3 in transition mode. We then let this device connect to the WPA3 network, after which we put up a rogue WPA2 AP. using WPA2. Put differently, if an adversary attempts to perform a man-in-the-middle against a WPA3-capable AP and client, and This revealed that these three devices tried to connect to the WPA2

7 Dragonblood: A Security Analysis of WPA3’s SAE Handshake Table 2: Result of downgrade attacks against WPA3 clients Adversary AP Client when the AP operates in transition mode (column Trans) or in WPA3-only mode (column 3-Only). On the first 3 devices E Auth-Commit(group=21, ) s , A A Block the network must be configured manually, while on other ○ 1 devices the network is selected from a list of nearby ones. Auth-Commit(status=unsupported) ′ ′ Software Device Vulnerable? Auth-Commit(group=19, , E ) s A A 3-Only Trans. Auth-Commit(group=19, s , E ) B B AP from vendor A firmware 10.20.0168 ✓✗ ○ 2 RaspBerry Pi 1 B+ OpenWRT r9576 ✓✗ ✓✗ MSI GE60 Laptop wpa_supplicant v2.7 Auth-Confirm( s ) A MSI GE60 Laptop ✓✓ iwd v0.14 ) Auth-Commit( s B ✗✗ NetworkManager 1.17 Dell Latitude 7490 Google Pixel 3 ✗✗ QPP1.190205.018.B4 ✓✓ G975USQU1ASBA Galaxy S10 Figure 5: Downgrade attack against SAE’s group selection: a man-on-the-side can force the client (initiator) into using a different cryptographic group during the SAE handshake. network, allowing subsequent dictionary attacks. With the last four devices in Table 2, the desired network is selected from a list of nearby ones. We found that iwd and the Galaxy S10 are vulnerable. ○ in Figure 5). This can be accomplished by at the AP (see stage 1 However, Linux’s NetworkManager and the Google Pixel 3 refused ], or by forging channel-switch announce- jamming the frame [ 84 to connect to the rogue WPA2 network, preventing our attack. ments [ 83 ]. The adversary then forges a commit frame that indi- We also discovered an implementation-specific downgrade at- cates the AP does not support the request group. In response, the tack when using WPA3-only networks. More precisely, we noticed client will pick its second preferred group, which in our example is that some devices will connect to the rogue WPA2 network, even if group 19 (i.e. curve P-256). From this point onwards, a normal SAE originally the network only supported WPA3 (see column 3-Only in handshake is executed using group 19 (see stage in Figure 5). ○ 2 Table 2). In particular, iwd and the Samsung Galaxy S10 are affected Notice that this negotiation process is never cryptographically vali- by this attack, meaning downgrade to dictionary attacks remain dated, meaning the downgrade attack is not detected. possible even if the network is configured to only support WPA3. It is also possible to perform an upgrade attack, where the victim is forced to use a more secure cryptographic group. That is, if the 5.2 Attacking SAE’s Group Negotiation victim prefers small cryptographic groups, our attack can force the victim into using bigger groups. This may be useful when The SAE handshake can be run using different elliptic curve or mul- performing denial-of-service attacks (recall Section 4), or to amplify tiplicative groups mod (i.e. ECP or MODP groups). The “Group p timing side-channels (see Section 6). ] gives an overview of supported groups. Ad- Description” of [ 43 ditionally, the 802.11 standard allows station to prioritize groups 5.3 Countermeasures [45, §12.4.4.1] . Although this provides in a user-configurable order To mitigate our downgrade to dictionary attack, a client should flexibility, it requires a secure method to negotiate the group that remember if a network supports WPA3-SAE. That is, after suc- will be used. Unfortunately, the mechanism that negotiates which cessfully connecting using SAE, the client should store that the group or curve is used during the SAE handshake is trivial to attack. network supports SAE. From this point onward, the client must With SAE, the used group is negotiated as follows. When a client never connect to this network using a weaker handshake. This connects to an AP, it includes its desired group in the commit trust-on-first-usage idea is similar to the one of SSH, and similar to frame, along with a valid scalar s and element E . In case the AP i i ]. Notice from 63 the Strict-Transport-Security header of HTTPS [ does not support this group, it will reply using a commit frame Table 2 that Linux’s NetworkManager and the Google Pixel 3 al- with a status field equal to “unsupported finite cyclic group” (see stage ready employ a similar defense. Optionally, in case the client notices ○ in Figure 5). In turn the client will attempt to use its next 1 preferred group, and send a new commit frame with this group, and the security configuration of the network changes, the client can E . This process continues corresponding new scalar and element prompt the user for the password of the network. This would pre- s i i until the client selected a curve that the AP supports. Unfortunately, vent automatic downgrade attacks, while still allowing the user to override our defense by reentering the password. To handle net- there is no mechanism that detects if someone interfered with this works where only some APs support WPA3, a flag could be added process. This makes it trivial to force the client into using a different group: simply forge a commit frame that indicates the AP does not to the RSNE that indicates some APs only support WPA2, meaning support the currently selected group. downgrade attacks cannot be prevented against this network. Figure 5 illustrates the resulting downgrade attack. Here the Another possible defense, which requires minimal modifications client first construct a commit frame requesting group 21 (i.e. curve on clients or APs, would be to deploy separate networks with sepa- P-521). However, the adversary blocks this frame from arriving rate passwords for both WPA2 and WPA3.

8 Mathy Vanhoef and Eyal Ronen Table 3: Overview of MODP groups that cause timing side- Listing 2: Algorithm that converts the pre-shared password channels when deriving the password element. The third into a MODP group element [45, §12.4.4.3.2]. The variables column shows the probability that an extra iteration is q ) define the MODP group being used, with p a prime, ( G p , , needed. The last column denotes the average number of it- the (prime) order of . G G a generator, and q p mod erations that are needed to derive the password element. def password_to_element_ffc(password, MAC1, MAC2, k=40): 1 found = False 2 3 counter = 0 ] [ E ] p ≥ value X Pr len(p) Group ID [43] [ while not found: 4 counter += 1 5 30.84% 1024 22 1.44 seed = Hash(MAC1, MAC2, password, counter) 6 value = KDF(seed, "SAE Hunting and Pecking", p) 7 23 2048 32.40% 1.48 8 if value >= p: continue 2048 24 47.01% 1.89 9 1 )/ q − p ( mod p P = value 10 11 if P > 1: found = True 12 return P variant of Dragonfly [ ]. Unfortunately, countermeasures against 23 this timing leak were not incorporated into the SAE handshake. We will now analyze what the practical impact of this decision is, and In principle, group downgrade attacks can also be mitigated by we will determine whether this can be exploited in practice. remembering which groups a network supports. However, the sup- The first cause of extra iterations is when the output of the ported groups of an AP are more likely to change over time, and Key Derivation Function (KDF) on line 7 returns a number bigger therefore we do not recommend such a defense. Instead, the sup- of the MODP group. Note that the number of p than the prime ported groups can be included as a bitmap in the RSNE during the bits returned by KDF is equal to the number of bits needed to handshake. This will enable a station to detect if a downgrade 4-way . That is, the number of bits returned by the KDF function p represent attack took place, and to subsequently abort the handshake. depends on the MODP group being used. This also implies that the depends on the MODP group p is bigger than value probability that 6 TIMING ATTACKS ON MODP GROUPS being used. Fortunately, for most MODP groups this probability In this section we empirically show that the hash-to-group method p is extremely small, because the prime is only slightly smaller that converts a password into a MODP element is vulnerable to than a power of two. However, for the MODP groups shown in timing attacks. The obtained info will later on be used in password is p Table 3, the probability that the output of KDF is bigger than partitioning attacks, allowing one to recover the victim’s password. high. For example, for group 22 this probability equals 30.84%, and for group 24 the probability is 47.01% (see column 3 in Table 3). 6.1 Background Finally, the if-condition on line 11 can in principle also cause an extra iteration to be executed. However, for all supported MODP Up to this point, we assumed the SAE handshake is executed using groups, the probability of this happening is negligible. elliptic curves. Although this is a natural assumption, since any Since the output of the KDF depends on the password, the num- station that supports SAE must implement elliptic curve P-256, the ber of performed iterations also depends on the password being SAE handshake can also be performed using multiplicative groups used. If an adversary learns this number, they learn that passwords mod a prime p (MODP groups). When employing MODP groups, which require a different number of iterations are not used by the the algorithm in Listing 2 is used to convert the password into a victim. Note that the number of executed iterations X follows a group element. In contrast to the algorithm for elliptic curves, the geometric distribution: one for MODP groups does not employ any side-channel defenses such as performing extra iterations [45, §12.4.4.3.2]. 1 n − X [ ]) = p ] = Pr [ value ≥ p ] n (1) Pr ·( 1 − Pr [ value ≥ Although elliptic curves are generally more performant than This means that the average number of iterations required to derive MODP groups, this is not necessarily the case with SAE. In particu- − 1 ( ) 1 ] = . For the password element equals − Pr [ value ≥ p ] E [ X lar, due to the extra iterations needed in the hash-to-curve method, , and for group 24 this equals MODP group 22, this equals 1 . 45 the hash-to-group method for MODP groups may be slightly more 1.89 iterations. In other words, on average one timing measurement efficient. Recall from Section 3.3 that these extra iterations are allows the adversary to learn the result of multiple iterations. Finally, needed to mitigate timing side-channels when using elliptic curves. observe that the MAC address of the client also influences the output As a result, users may prefer MODP groups over elliptic curves, es- of the KDF, and hence also influences the number of executed pecially because this would also reduce the impact of our clogging iterations (line 6 in Listing 2). This means that an adversary can attack of Section 4. Unfortunately, we show that the hash-to-group spoof MAC addresses, and for each address measure the number of method for MODP groups is also affected by timing side-channels. executed iterations. We will show in Section 8 how this information In practice this means that for certain MODP groups, extra itera- can be used to perform a password partitioning attack, allowing an tions must be performed in order to mitigate timing attacks. adversary to recover the target’s password. 6.2 Variable Number of Iterations 6.3 Experiments When converting a password to a MODP element, the algorithm To determine the feasibility of measuring the number of execution in Listing 2 performs a variable number of iterations. In fact, the CFRG already warned about this when they were reviewing a close iterations, we performed the attack in a realistic setting. For the

9 Dragonblood: A Security Analysis of WPA3’s SAE Handshake 66 sent to a spoofed MAC address. This prevents the AP from retrans- mitting frames, making the attack faster and more reliable. More 65.5 traffic influences the timing mea- Wi-Fi importantly, background surements. Additionally, periodic background tasks on the AP also 65 influence the timing measurements. Both sources of noise are prob- lematic because they are not constant throughout the attack. To 64.5 handle this, we interleave the time measurements of all spoofed MAC addresses, instead of performing all measurements for each MAC address one by one. As a result, temporary noise equally in- 64 Average response time (in ms) fluences the measurements of all MAC addresses, instead of only 600 450 750 900 0 150 300 affecting the measurements of one address. With the above setup and optimizations, we carried out an at- No. of timing measurements per spoofed MAC address tack using MODP group 22, and another attack using group 24. We spoofed 20 addresses in each experiment, and performed 1000 mea- (a) Measurements of a timing attack using MODP group 22. surements for each spoofed address. The attack against group 22 took 228 minutes, and the attack against group 24 took 607 minutes. Figure 6 shows the results of these experiments. Each line represents 382 the average timing measurements of one spoofed MAC address. 380 From these timings, it is straightforward to derive the number of executed iterations. For example, the cluster of lines (i.e. spoofed 378 MAC addresses) at the bottom corresponds to one iteration. The cluster above that corresponds to two iterations, and so on. For the 376 highest line in the MODP group 24 attack, careful inspection reveals 374 that this corresponds to 9 iterations. The correctness of these re- Average response time (in ms) sults was confirmed by inspecting the debug output of hostapd. We 600 750 900 450 0 150 300 conclude that timing attacks can accurately determine the number of executed iterations. No. of timing measurements per spoofed MAC address (b) Measurements of a timing attack using MODP group 24. 6.4 Countermeasures and Discussion Ideally, groups 22, 23, and 24 should be disabled. Doing this is in Figure 6: Recovering the number of iterations needed to gen- line with RFC 8247, which recommends that implementations no erate the password element for MODP group 22 and 24. Each longer use these groups due to, among other things, their small line denotes a spoofed MAC address. The lowest cluster of 64 ]. Implementations also should not use MODP 82 , subgroups [ lines corresponds to a single iteration, the second cluster to 64 ]. The other MODP groups use primes that groups 1, 2, or 5 [ two iterations, and so on. The victim device is a Raspberry are slightly smaller than a power of two, meaning it is extremely Pi 1 model B+ running hostapd version 2.6. unlikely that the output of the KDF in line 7 of Listing 2 is bigger or equal to the prime p . Therefore, with these groups the password element is practically always found in the first iteration. Another option is to exclude the MAC addresses from the hash- victim we used a Raspberry Pi 1 model B+ that was running hostapd to-group method used by the SAE handshake. Similar to our defense version 2.6. We used a Raspberry Pi because its 700 MHz CPU from Section 4.5 against clogging attacks, this would allow imple- matches the one in commodity home routers [ 91 ]. The Raspberry mentations to calculate the password element offline. Although the Wi-Fi Pi was equipped with a WNDA3200 dongle. Picking hostapd algorithm would still be insecure, an adversary would no longer be to run the AP was an obvious choice, since it is the most widely able to easily trigger (and measure) executions of it. used wireless daemon in both professional and home routers, and In principle, extra iterations can also be performed after finding is the only one that supports MODP groups at the time of writing. the MODP password element, so a fixed number of iterations are al- The adversary used a MSI GE60 Laptop with a WNDA3200 Wi-Fi ways executed. This is similar to the countermeasure for the elliptic dongle. To perform timing measurements, we wrote a tool on top of curve case. However, we do not recommend this defense, because the aircrack-ng tool suite. It spoofs commit frames, and measures implementations may still be vulnerable to cache-based attacks, how long it takes to receive the corresponding commit reply. After and because groups 22 to 24 should be avoided in general [64]. each individual measurement, a deauthentication packet is injected towards the AP. This causes hostapd to clear all state related to 6.5 Applicability to Elliptic Curves the spoofed MAC address, and enables us to rapidly perform a new In practice, we discovered that version 2.1 to 2.4 of wpa_supplicant timing measurement with the same spoofed address. in the hash-to-curve algorithm, while only Two optimizations were required to make the attack practical. 4 and hostapd use k = First, similar to our clogging attack of Section 4.3, we had to use newer versions use k = 40 . This means that against these older virtual interface support of Atheros chips to acknowledge all frames versions, timing attacks are also possible when elliptic curves are

10 Mathy Vanhoef and Eyal Ronen used. In particular, a random MAC address will have a probability (or application on android). Oren et al. [ 66 ] even showed how to 4 − . 25% of requiring more than 4 iterations, in which case perform such attacks from the browser using JavaScript code (al- = of 2 6 information about the password is leaked. Although most Linux dis- though browsers are now implementing mitigation for these types tributions that used these older versions do not enable SAE in those of attacks). OpenWRT For our password partitioning attack, we need to record several builds, dedicated builds for networking devices (e.g. 15.05.1) did use these older versions with SAE enabled. handshakes with different MAC addresses. We can get handshakes We also conjecture that resource-constrained devices may not with different MAC addresses by targeting multiple clients in the implement the fixed amount of 40 iterations, due to the overhead of same network (e.g. convince multiple users to download the same this countermeasure. Against such implementations, timing attacks malicious application). If we are only able to attack one client, would also be possible against the hash-to-curve algorithm. we can set up rogue APs with the same SSID but a spoofed MAC address. We can force victims into connecting to our rogue AP by 7 CACHE-BASED ATTACKS ON ECC GROUPS using a higher signal strength, or jamming the legitimate AP [84]. In this section we demonstrate that implementations of the hash- 7.3 Attacking the hostap Implementation to-curve algorithm of SAE may be vulnerable to cache-based side- channel attacks. Similar to the timing attack against MODP groups, function sae_derive_pwe_ecc Our target implementation is the this will later on enable an adversary to recover a target’s password. in the latest hostap code (commit 0eb34f8f2 from Sat Jan 26) with the default curve P-256. Our test machine uses a 4-core Intel Core 7.1 Background and Attack Goal i7-7500 processor, with a 4 MiB cache and 16 GiB memory, running Ubuntu 18.04.1. To monitor access to the instruction cache we The goal of our attack is to learn if the Quadratic Residue (QR) test 95 ], as implemented in the Mastik use the Flush+Reload attack [ in the first iteration of the hash-to-curve algorithm succeeded or not. toolkit [94]. This information will be used in the offline password partitioning at- To learn the result of the first QR test, we can either attack the tack of Section 8 to recover the target’s password. Unlike the case of blinded QR test implementation, or the branch in the iteration loop the MODP groups described in Section 6, the implementation of the that checks the result of the test. A simple cache attack against the hash-to-curve algorithm for ECC groups does include mitigations blinded QR test is infeasible as the two possible code paths (see against side-channel attacks. Those mitigations include perform- 1 Listing 4 line 19) are compiled into a single cache line. [45, §12.4.4.3.2] , and ing extra dummy iterations on random data The two code paths of the branch inside the iteration loop (see blinding of the underlying cryptographic calculation of the qua- Listing 5 line 28) are compiled into two separate cache lines. There- dratic residue test [ 36 ]. The resulting code of wpa_supplicant and fore we can monitor cache access to nQR cache line which is the hostapd implementation we reviewed is pseudo-constant time, i.e., target of the conditional jump (see Listing 6 line 9). To differentiate there might be some minor variation in run time, but they are too between the branches taken in the first and subsequent iterations, minute to be measured by an adversary. However, in many cases we created a synchronization “clock” by monitoring another cache such pseudo-constant time implementations are still vulnerable to line that is accessed once every iteration (similarly to what is done different types micro-architectural side-channel attacks [ ]. 51 70 , 2 , in [96]). Modern proces- 7.1.1 Micro-Architectural Side-Channel Attacks. On our test platform, monitoring two cache lines repeatedly sors try to optimize their behavior (e.g. memory access, branch over time caused a high rate of false positives (i.e. false detection prediction) by saving an internal state that depends on the past. of access to cache lines). This error rate increases considerably if Micro-architectural side-channel attacks exploit leaked informa- the monitored cache lines are close. Consequently, for our “clock” tion about the running of other programs due to sharing of this we choose to monitor a cache line far away from the nQR cache state [ ]. Cache-based side-channel attacks exploit the state of the 26 line (in our case the function sha256_prf_bits ). memory case (either instructions or data) and have been widely We want to classify Classification of Cache Access Patterns. 7.3.1 used to break cryptographic primitives [5, 14, 27, 67, 95]. our cache traces as one of two cases depending on the results of , , 30 29 attack [ Flush+Reload In the different variants of the , 95 the QR test in the first iteration (non-QR or QR). The measured 97 ] the attacker starts by evicting (or flushing) a memory location cache access patterns to the two monitored cache lines show a from the cache. After waiting for a predetermined interval, he high variance between different traces of the same case. This might measures the time it takes to reload the flushed location. If during be due to OS related noise, speculative execution, or the way that the interval the victim accesses this memory location, it will be the random dummy iterations affect the branch predictor behavior cached, and the reload time for the attacker will be short. Otherwise, in the next run of the function. To overcome this we perform a the reloading of the flushed memory location will be much slower. , ]. That is, we simplified variant of a cache template attack [ 30 16 In this way, the attacker can trace the victim’s memory access measure a trace of the cache access pattern by monitoring the patterns. two addresses (the “clock” and the non-QR case) in fixed intervals 50000 clock cycles of 200000 clock cycles (each iteration takes ≈ 7.2 Attack Scenario on our test machine). We encode each trace into two bits that Our attack requires the ability to monitor cache access patterns on correspond to the two memory locations. In each trace a bit is set the victim machine. However, unlike many cache attacks against 70 ], we can also target the client side. TLS implementations [ 2 , 51 , 1 More advanced micro architectural attacks targeting the branch predictor [ 2 , 6 , 21 ] We can run our attack from any unprivileged user-mode process will fail due to the extra random iterations.

11 Dragonblood: A Security Analysis of WPA3’s SAE Handshake Listing 3: Password partitioning algorithm in Python-like pseudo code. It eliminates incorrect passwords based on the result of specific element tests for each spoofed MAC ad- dress. It returns a list of remaining candidate passwords. 1 def recover_password(dictionary, testdata, mactarget): # dictionary: Set of possible passwords. 2 3 # testdata: Element test results for each spoofed MAC address and # counter value used in a specific element test. 4 5 # mactarget: MAC address of the target (e.g. a client or AP). 6 7 for macspoof, counter, result in testdata 8 for p in dictionary: if simulate_test(p, macspoof, mactarget, counter) != result: 9 10 dictionary.remove(p) if len(dictionary) <= 1: break 11 return dictionary 12 Figure 7: Probability distribution for attack results Practically, this is implemented by removing incorrect passwords from the dictionary during each partitioning step. If the dictionary to one if its corresponding memory location was accessed, and to becomes empty, this means the target’s password was not in it. zero otherwise. However, if after the partitioning steps only one password remains, In our attack we only keep active measurements with at least then with high probability this is the target’s password. one non-zero bit. Our attack returns the value of the first two active The result of every element test that is performed in a (password- measurements, meaning the return value consists of four bits (re- dependent) iteration of Listing 1 or 2 can be used to partition the dic- sulting in 9 possible return values). Figure 7 shows the distribution to refer to both the quadratic tionary. We use the term element test of these return values when the first iteration of the hash-to-curve residue test for elliptic curves, and the if-test that checks whether algorithm results in a non-QR number (nQR), and when the first the prime of the MODP group is bigger than the hash output. Recall iteration results in a QR number (QR). that with one timing measurement against the MODP algorithm, 20 For our classification we repeat the attack times for each MAC we learn on average the result of multiple (failed) element tests. address. We created a training set for the non-QR and the QR cases Considering element tests separately also has the advantage that, · using 100 traces each. We used this training set to build a simple 20 if for example we are unsure whether a spoofed address resulted in linear classifier that receives 20 traces as an input, and returns the 4 or 5 iterations, this info still enables us to determine that the first input classification, namely either non-QR or QR. We then tested three element tests failed. By representing our timing and cache 400 our attack and linear classifier on a larger test set of · 20 traces attack measurements as a set of element tests, we can now use the for each case. For the non-QR case we have achieved a success 100% same partitioning attack algorithm in both attack scenarios. 99 5% . rate ( ), and for the QR case we have achieved a 400 out of 400 The algorithm illustrated in Listing 3 implements the password 400 ). We can conclude that an adversary out of 398 success rate ( partitioning algorithm. As input it receives a dictionary, the set of can reliably abuse cache-based side-channels to determine whether element tests and their result, and the MAC address of the target. the password element was found in the first iteration or not. The algorithm uses this information to partition the dictionary 7.4 Countermeasures and Discussion by removing passwords that lead to a different result for the ele- ment test compared to the result that we measuring this the timing As in the MODP case, the ideal solution is to modify the SAE or cache-based attack. More importantly, this algorithm can be handshake such that the password element is independent of MAC run offline, i.e., without requiring any interactions with the target addresses, and use a constant-time hash-to-curve algorithm from device. the new standard [ ]. Even if the attacker can attack the one-time 73 offline calculation, and exploit some residual side-channel leak- 8.2 Prerequisites and Success Analysis age, the expected number of password bits leaked is only two. A backwards-compatible countermeasure is to replace the two vulner- To determine the performance of the password partitioning algo- able branches with a constant-time select utility, and use constant rithm, we first calculate how many element tests are required to time Legendre symbol computation as defined in [73]. uniquely recover the password with high probability. Note that every element test is independent, because in each iteration the 8 PASSWORD PARTITIONING hash inputs are different, resulting in independent hash outputs. In this section we show how to perform password partition attacks, p Let denote the probability that the group element is not found, e using the information obtained from our timing and cache attacks. meaning another iteration and element test has to be performed. This enables an adversary to recover the password of a target. For the elliptic curve algorithm, is close to 50%, and for MODP p e 8.1 Partitioning a Dictionary . ≥ ] groups the values for p p are listed in in Table 3 under Pr [ value e incorrect In the first attack variant, our goal is to recover the password from We want to know the probability of eliminating d a given dictionary. We accomplish this by repeatedly partition- passwords, when given the result of n element tests. Let Z denote ing the dictionary into correct and incorrect password candidates. a random variable that equals the number of element tests that are

12 Mathy Vanhoef and Eyal Ronen 28 an adversary needs to obtain . 28 element tests to uniquely recover required to eliminate d incorrect passwords. This means that if a contains the correct password, and we use d + 1 the password. For elliptic curve P-256, the adversary would need dictionary of size n on average 25 . 11 element tests (i.e. quadratic residue test results). element tests, the probability of uniquely recovering the password is n ] Pr . To derive this probability, we first introduce random [ ≤ Z variable Y as being the number of element tests where the password 8.3 Computational Requirements element was found. We have: To estimate the computational costs of running the partitioning al-   n , we derive the expected d gorithm in function of the dictionary size − n k k Pr [ p Y = 1 k ] = ·( ) − (2) · p e e k number of element tests that have to be simulated (see line 9 in Listing 3). From formula 5 we already know the expected number This is because the result of an element test does not eliminate incorrect pass- d of element tests that are needed to eliminate all an incorrect password when the incorrect password has the same words. In other words, the partitioning algorithm will execute on result under the given MAC addresses and iteration count. For iterations. During each of these iterations, a percentage average ℓ example, if the real password in a given iteration did not have a of passwords are eliminated from the dictionary. More precisely, quadratic residue, and the incorrect password also did not, then the when taking a random element test as reference, and comparing it results of this element test does not eliminate the password. Given with an incorrect password, the chance of not being able to remove measured element tests the password element that in out of n k 2 2 the incorrect password as a candidate is ( 1 − p p ) = . Hence, + p e f e was found, the probability that all element tests do not eliminate a the amount of element tests that are performed on average is: k n − k ( ) p · random password equals . Now let random variable 1 p − e e E denote the number of eliminated passwords. The probability that ⌈ ℓ ⌉ p − 1 f are incorrect passwords all eliminated equals: d −⌈ ⌉ ℓ 2 1 = + ... + p d + d d p p + d d (6) f f f   − p 1 d f − k k n p ] Pr [ E = = 1 −( 1 − p d ) · | Y k = (3) e e We again tested the above formula by running 100 000 runs of the n random element tests, the probability Finally, given the result of 1 000 random passwords, partitioning algorithm, with each time that all d incorrect password are eliminated equals: 3084 assuming . Results closely matched the predictions. For 0 . p = e n MODP group 22 and the RockYou dictionary, this would mean that Õ Pr [ Z ≤ Pr [ n = k ]· ] [ E = d | Y = k ] (4) = Y Pr on average we have to perform element tests. With ellip- 33 627 714 0 k = 28 689 748 element tests on average. tic curve P-256 this results in On a laptop with an Intel i7-8650U CPU running at 1.90GHz, runs of the par- 100 000 We tested the above formula by running performing an attack using the RockYou password list takes on passwords. Each run used random 1 000 titioning algorithm on average around 11 minutes. This means ordinary users can perform simulated element test results (i.e. simulated timing measurements). this attack on their existing off-the-shelf hardware. Our experimental results closely matched that of formula 4. We can further optimize the partitioning algorithm if p differs with the RockYou password dump, n By trying various values for e 0 5 from . . That is, when attacking a MODP group, we can first ≥ n we find that for MODP group 22, having 35 element tests process the dictionary using an element test result where the target gives us a probability above 95% of uniquely recovering the correct did not found the password in the given iteration. Recall that this 1 timing 35 password. On average, we need to perform . = 44 24 . 3 / . A random incorrect password then p happens with probability measurements to obtain 35 element tests (recall Table 3). For elliptic e 1 − p has a probability of being eliminated. Since on average curve P-256, an adversary needs to obtain 29 element test results e · p element tests can be used to eliminate an incorrect password ℓ to uniquely recover the password with a probability above 95%. e p , formula 6 can be modified in the with a probability of 1 − Given that our cache-based side-channel attack can detect a QR e obvious way to take our new strategy into account. When using the with 100% accuracy, and a non-QR with 99.5% accuracy, the proba- RockYou dictionary under this new strategy, we need to perform bility of that on average all used non-QR measurement are correct 12 . 5 20 742 225 element tests using MODP group 22, a reduction only . 0 = . The probability of uniquely recovering . 0 equals 995 939 by 38%. 0 the password then becomes at least 939 · 95 . 892 . In other . . 0 = 0 words, using 25 cache-based element test results, the probability of recovering the password from the RockYou dump is close to 90%. 8.4 Brute-Force Attacks in the Cloud Using formula 4, we can also determine the average number of In our second variant of the partitioning attack, we essentially per- d incorrect passwords: element tests that are needed to eliminate all form an offline brute-force attack on the password. More concretely, ∞ ∞ Õ Õ our goal is to test all possible 8-character lowercase passwords. Us- ( ) ℓ = = i ] = i · Pr [ Z ≤ i · Pr [ Z ≤ (5) ] 1 − i i Z [ Pr ]− element ing formula 5 we know that on average this requires 38 . 36 i = 1 = i 1 tests for MODP group 22, and 38 . 92 for elliptic curve P-256. Recall that for the MODP case, this means we need to make on average 100 000 runs of the par- We tested the above formula by running 1 000 random passwords, as- timing measurements. These are relatively mod- titioning algorithm with each time 38 . 36 / 1 . 44 = 26 . 64 p suming . 0 equals est requirements. For example, in our demonstration of the timing 3084 . Results closely matched the predicted e attack we already performed 20 timing measurements. As a result, ones. we must assume an adversary can obtain the required number of Assuming the RockYou dump is used for the dictionary, and MODP group 22 as the target, formula 5 teaches us that on average element test results.

13 Dragonblood: A Security Analysis of WPA3’s SAE Handshake al. designed a variant of Dragonfly that attempts to keep computa- We now calculate the costs of running the offline partitioning tional costs low [8]. phase on Amazon EC2 instances. For both the MODP and elliptic Other types of PAKEs have also been proposed by researchers curve cases, we first performed repeated microbenchmarks where 12 , 10 , 4 , 3 over the years [ 53 , 52 , 75 , 77 , 78 , , 93 ], of which some 13 , we simulated one million element tests on a single EC2 vCPU. On , ]. Finally, 3 . 04 microseconds, and the quadratic 92 , 81 , 76 , 74 , 58 average, the MODP test took 58 , 31 have been submitted as RFCs [ . 23 25 microseconds. In macrobenchmarks of the residue test took there is also research into post-quantum PAKEs [20, 25]. partitioning algorithm on the RockYou dictionary, close to identical running times were observed. We now multiply these timings with 10 CONCLUSION AND RECOMMENDATIONS the result from formula 6. In particular, for MODP group 22 we In light of our presented attacks, we believe that WPA3 does not element tests, and for need to perform on average 301 947 836 620 meet the standards of a modern security protocol. Moreover, we be- 417 654 129 151 curve P-256 we need to perform tests. Fortunately, Wi-Fi Alliance lieve that our attacks could have been avoided if the we can parallelize the code by splitting the brute-force search out created the WPA3 certification in a more open manner. Notable over several workers. Every worker gets access to all the element is also that nearly all of our attacks are against SAE’s password test results, meaning if sufficient element tests were obtained, every encoding method, i.e., against its hash-to-group and hash-to-curve worker will discard all incorrect passwords. Only the real password algorithm. Interestingly, a simple change to this algorithm would will be detected as potentially valid. have prevented most of our attacks. In particular, the peer’s MAC Assuming we rent c5.18xlarge instances having 72 vCPUs, which addresses can be excluded from SAE’s password encoding algo- costs $3.06 an hour, we can perform the brute-force search against rithm, and instead included later on in the handshake itself. This the MODP case for $10.63 on average (within e.g. an hour). The allows the password element to be computed offline, meaning an brute-force attack against elliptic curves would cost $125 on average, adversary can no longer actively trigger executions of the pass- which although more costly, is still a worryingly low amount. word encoding method. Moreover, this would mean that for a given password, the execution time of the password encoding method would always be identical, limiting the amount of information be- 9 RELATED WORK ing leaked. Surprisingly, when the CFRG was reviewing a minor After the introduction of WPA, it was quickly found to be vul- variant of Dragonfly, they actually discussed these type of modifi- nerable to dictionary attacks [ 62 ]. Later, He and Mitchell formally 49 69 , 80 ]. However, to our surprise, this change was , cations [ 48 , analyzed WPA’s 4-way handshake, and discovered a DoS vulner- not incorporated into any of the Dragonfly variants. ability [ 40 , 61 ]. This resulted in the standardization of a slightly We also conjecture that resource-constrained devices may not 4-way ]. He et al. continued to analyze the improved 45 handshake [ implement all the side-channel countermeasures, as these may 4-way handshake, and proved its correctness [ 41 ]. However, imple- be too costly on lightweight processors. Additionally, correctly mentations of the handshake were nevertheless vulnerable 4-way implementing our suggested backwards-compatible side-channel ]. Recently, Vanhoef and Piessens discov- to downgrade attacks [ 85 countermeasures is non-trivial. This is worrisome, because security 86 ]. 87 , ered that WPA2 was vulnerable to key reinstallation attacks [ protocols are normally designed to reduce the change of implemen- Finally, Kohlios and Hayajneh provide an overview of WPA2 and tation vulnerabilities. the differences with WPA3 [56]. Finally, we believe that a more open process would have pre- Wi-Fi Researchers also discovered several DoS attack against vented (or clarified) the possibility of downgrade attacks against ]. 11 networks. The most well-known is the deauthentication attack [ WPA3-Transition mode. Nevertheless, although WPA3 has its flaws, Other DoS attacks exploit weaknesses in TKIP [ 28 ]. Additionally, we still consider it an improvement over WPA2. Könings et al. found several DoS vulnerabilities in the physical ], and other researchers constructed and MAC layer of 802.11 [ 57 72 84 jammers using commodity hardware [ , ]. A detailed survey ACKNOWLEDGMENTS of DoS attacks at the physical and MAC layer is given by Bicakci We thank Yuval Yarom for his helpful comments and insights. We 15 and Tavli [ ]. Aiello et al. show how susceptibility to denial-of- also want to thank Philipp Ebbecke, and an anonymous contributor, service attacks can be balanced with the need for perfect forward for their help in testing downgrade attacks against the Pixel 3 and secrecy [ ]. To the best of our knowledge, our clogging attack 7 Galaxy S10. Mathy Vanhoef holds a Postdoctoral fellowship from against WPA3 is the first that overloads the CPU of the victim. the Research Foundation Flanders (FWO). This work is partially An initial version of Dragonfly was vulnerable to an offline dictio- supported by an ISF grant number 1523/14, and by the Center for ]. nary attack [ 22 ]. A modified variant was then specified in 2008 [ 33 Cyber Security at New York University Abu Dhabi (NYUAD). Several close variants of it have been defined over the years, and – 37 , 35 are commonly referred to as Dragonfly-type handshakes [ REFERENCES 39 ]. Trevor Perrin did a review of an improved draft of the hand- National Institute of 2013. FIPS PUB 186-4: Digital Signature Standard (DSS). [1] ], and later provided an overview of other people’s com- 69 shake [ (2013). Standards and Technology (NIST) 68 ments on the handshake [ ]. Struik reviewed a draft of the hand- [2] 2019. The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Imple- ]. Clarke and Hao discovered a small subgroup attack shake [ 79 . IEEE To appear in the IEEE Symposium on Security and Privacy mentations. In Computer Society. against a draft of the handshake, which was mitigated in a new [3] Michel Abdalla and David Pointcheval. 2005. Simple password-based encrypted draft [ 19 ]. Lancrenon and Skrobot provided a security proof of a key exchange protocols. In Cryptographers’ track at the RSA conference . Springer, ]. Finally, Alharbi et 59 close variant of the Dragonfly handshake [ 191–208.

14 Mathy Vanhoef and Eyal Ronen Michel Abdalla and David Pointcheval. 2005. Simple Password-Based Encrypted [4] Dan Harkins. 2008. Simultaneous Authentication of Equals: A Secure, Password- [33] Key Exchange Protocols. In Topics in Cryptology – CT-RSA 2005 . Springer Berlin The Second International Conference Based Key Exchange for Mesh Networks. In . 839–844. on Sensor Technologies and Applications (SENSORCOMM) Heidelberg, 191–208. Thwarting Side Channel Attacks. Re- Dan Harkins. 2011. Onur Acıiçmez. 2007. Yet Another MicroArchitectural Attack: Exploiting I-Cache. [34] [5] trieved https://mentor.ieee.org/802.11/dcn/ from 2018 September 9 In CSAW . Onur Acıiçmez, Shay Gueron, and Jean-Pierre Seifert. 2007. New Branch Predic- 11-11-1411-01-000m-thwarting-side-channel-attacks.doc. [6] [35] tion Vulnerabilities in OpenSSL and Necessary Software Countermeasures. In Dan Harkins. 2012. Secure Pre-Shared Key (PSK) Authentication for the Internet IMA Int. Conf. Key Exchange Protocol (IKE). RFC 6617. Re- Addressing A Side-Channel Attack on SAE. Dan Harkins. 2014. William Aiello, Steven M. Bellovin, Matt Blaze, John Ioannidis, Omer Reingold, [36] [7] Ran Canetti, and Angelos D. Keromytis. 2002. Efficient, DoS-resistant, Secure trieved 9 September 2018 from https://mentor.ieee.org/802.11/dcn/14/ Key Exchange for Internet Protocols. In 11-14-0640-00-000m-side-channel-attack.docx. . ACM CCS [37] Dan Harkins. 2015. Dragonfly Key Exchange. RFC 7664. [8] Eman Alharbi, Noha Alsulami, and Omar Batarfi. 2015. An Enhanced Dragonfly Dan Harkins. 2019. Secure Password Ciphersuites for Transport Layer Security Key Exchange Protocol against Offline Dictionary Attack. Journal of Information [38] (TLS). RFC 8492. https://doi.org/10.17487/RFC8492 Security 6, 02 (2015), 69. [39] Retrieved Dan Harkins and G. Zorn. 2010. Extensible Authentication Protocol (EAP) Au- [9] Gabor Bajko. 2017. SAE reauthentication timer value. 19 https://mentor.ieee.org/802.11/dcn/17/ from 2018 September thentication Using Only a Password. RFC 5931. [40] 11-17-1030-01-000m-sae-retry-timeout-clarification.docx. Handshake. Changhua He and John C Mitchell. 2004. Analysis of the 802.1 i 4-Way . ACM. In WiSe José Becerra, Dimiter Ostrev, and Marjan Škrobot. 2018. Forward Secrecy of [10] [41] Changhua He, Mukund Sundararajan, Anupam Datta, Ante Derek, and John C International Conference on Provable Security . Springer, 366–384. SPAKE2. In Mitchell. 2005. A modular correctness proof of IEEE 802.11i and TLS. In . CCS John Bellardo and Stefan Savage. 2003. 802.11 denial-of-service attacks: real [11] Masashi Honma. 2015. [PATCH] mesh: Fix mesh SAE auth on low spec de- [42] . vulnerabilities and practical solutions. In USENIX Security vices. Retrieved 19 September 2018 from http://lists.shmoo.com/pipermail/hostap/ Steven M Bellovin and Michael Merritt. 1992. Encrypted key exchange: Password- [12] 2015-July/033304.html. Research in Security and based protocols secure against dictionary attacks. In [43] IANA. 2018. Internet Key Exchange (IKE) Attributes. Last retrieved 12 November . IEEE, Privacy, 1992. Proceedings., 1992 IEEE Computer Society Symposium on 2018 form https://www.iana.org/assignments/ipsec-registry/ipsec-registry.xml# 72–84. ipsec-registry-10. [13] Steven M Bellovin and Michael Merritt. 1993. Augmented encrypted key ex- Thomas Icart. 2009. How to Hash into Elliptic Curves. In [44] Proceedings of the 29th change: a password-based protocol secure against dictionary attacks and pass- . Annual International Cryptology Conference on Advances in Cryptology (CRYPTO) Proceedings of the 1st ACM Conference on Computer and word file compromise. In Wireless LAN Medium Access Control (MAC) and Physical IEEE Std 802.11. 2012. [45] Communications Security . ACM, 244–250. Layer (PHY) Spec . [14] Daniel J. Bernstein. 2005. Cache-timing attacks on AES. IEEE Std 802.11. 2012. Wireless LAN Medium Access Control (MAC) and Physical [46] Kemal Bicakci and Bulent Tavli. 2009. Denial-of-Service attacks and counter- [15] Layer (PHY) Spec . 31, 5 Comput. Stand. Interfaces measures in IEEE 802.11 wireless networks. Amendment 10: Mesh Networking [47] IEEE Std 802.11s. 2011. . (2009). Kevin M. Igoe. 2012. [Cfrg] Status of DragonFly. Retrieved 8 November 2018 [48] Billy Bob Brumley and Risto M. Hakala. 2009. Cache-Timing Template Attacks. [16] from https://www.ietf.org/mail-archive/web/cfrg/current/msg03258.html. In ASIACRYPT (Lecture Notes in Computer Science) , Vol. 5912. Springer, 667–684. Kevin M. Igoe. 2012. [Cfrg] Status of DragonFly. Retrieved 8 November 2018 [49] [17] CERT/CC. 2019. Vulnerability Note VU#871675: Security issues with WPA3. from https://www.ietf.org/mail-archive/web/cfrg/current/msg03261.html. http://www.kb.cert.org/vuls/id/871675 [50] Kevin M. Igoe. 2012. Re: [Cfrg] Status of DragonFly. Retrieved 9 September 2018 Hemant Chaskar. 2019. WLAN Security Enhancements: WPA3, OWE, DPP. [18] from https://www.ietf.org/mail-archive/web/cfrg/current/msg03264.html. Retrieved 9 April 2019 from https://d2cpnw0u24f jm4.cloudfront.net/wp-content/ [51] Gorka Irazoqui, Mehmet Sinan Inci, Thomas Eisenbarth, and Berk Sunar. 2015. uploads/WLPC_2019_WPA3-OWE-and-DDP_Hemant-Chaskar.pdf . Lucky 13 Strikes Back. In . ASIA CCS D. Clarke and F. Hao. 2014. Cryptanalysis of the dragonfly key exchange protocol. [19] ACM [52] David P Jablon. 1996. Strong password-only authenticated key exchange. IET Information Security 8, 6 (2014), 283–289. 26, 5 (1996), 5–26. SIGCOMM Computer Communication Review Jintai Ding, Saed Alsayigh, Jean Lancrenon, RV Saraswathy, and Michael Snook. [20] Stanislaw Jarecki, Hugo Krawczyk, and Jiayu Xu. 2018. OPAQUE: An Asymmetric [53] 2017. Provably secure password authenticated key exchange based on RLWE PAKE Protocol Secure Against Pre-Computation Attacks. Cryptology ePrint for the post-quantum world. In . Springer, Crypto Track at the RSA Conference Archive, Report 2018/163. https://eprint.iacr.org/2018/163. 183–204. P. Karn and W. Simpson. 1999. Photuris: Session-Key Management Protocol. RFC [54] Dmitry Evtyushkin, Ryan Riley, Nael B. Abu-Ghazaleh, and Dmitry Ponomarev. [21] 2522. 2018. BranchScope: A New Side-Channel Attack on Directional Branch Predictor. C. Kaufman, P. Hoffman, Y. Nir, P. Eronen, and T. Kivinen. 2014. Internet Key [55] ASPLOS . In Exchange Protocol Version 2 (IKEv2). RFC 7296. Scott Fluhrer. 2008. Re: [Cfrg] I-D for password-authenticated EAP method. [22] Christopher P Kohlios and Thaier Hayajneh. 2018. A Comprehensive Attack [56] Retrieved 9 November 2018 from https://www.ietf.org/mail-archive/web/cfrg/ Flow Model and Security Analysis for Wi-Fi and WPA3. (2018). current/msg02206.html. [57] Bastian Könings, Florian Schaub, Frank Kargl, and Stefan Dietzel. 2009. Channel [23] Scott Fluhrer. 2012. Re: [Cfrg] Status of DragonFly. Retrieved 8 November 2018 switch and quiet attack: New DoS attacks exploiting the 802.11 standard. In LCN . from https://www.ietf.org/mail-archive/web/cfrg/current/msg03265.html. [58] . Internet-Draft draft- Watson Ladd and Benjamin Kaduk. 2018. SPAKE2, a PAKE Re: [Cfrg] Requesting removal of CFRG co- [24] Scott Fluhrer. 2014. irtf-cfrg-spake2-07. Internet Engineering Task Force. https://datatracker.ietf.org/ chair. Retrieved 7 April 2019 from https://mailarchive.ietf.org/arch/msg/cfrg/ doc/html/draft-irtf-cfrg-spake2-07 Work in Progress. WXyM6pHDjGRZXZzSc_HlERnp0Iw. [25] Xinwei Gao, Jintai Ding, Lin Li, Saraswathy RV, and Jiqiang Liu. 2017. Efficient Jean Lancrenon and Marjan Škrobot. 2015. On the Provable Security of the [59] Implementation of Password-Based Authenticated Key Exchange from RLWE Dragonfly Protocol. In Information Security . Springer International Publishing. and Post-Quantum TLS. Cryptology ePrint Archive, Report 2017/1192. https: [60] Jouni Malinen. 2015. SAE: Increase security parameter k to 40 based on Dragonfly //eprint.iacr.org/2017/1192. 4584b66eaecd recommendation. Hostap commit . [26] Qian Ge, Yuval Yarom, David Cock, and Gernot Heiser. 2018. A Survey of Microar- John Mitchell and Changhua He. 2005. Security Analysis and Improvements for [61] chitectural Timing Attacks and Countermeasures on Contemporary Hardware. . NDSS IEEE 802.11i. In J. Cryptographic Engineering 8, 1 (2018). Robert Moskowitz. 2003. Weakness in Passphrase Choice in WPA Interface. [62] [27] Daniel Genkin, Lev Pachmanov, Eran Tromer, and Yuval Yarom. 2018. Drive-By Retrieved 26 September 2018 from https://wifinetnews.com/archives/2003/11/ Key-Extraction Cache Attacks from Portable Code. In . ACNS weakness_in_passphrase_choice_in_wpa_interface.html. [28] Stephen Mark Glass and Vallipuram Muthukkumarasamy. 2007. A Study of the [63] Strict-Transport-Security - HTTP. Retrieved 3 Febru- Mozilla. 2019. . IEEE. International Conf. on Networks TKIP Cryptographic DoS Attack. In ary 2019 from https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/ Daniel Gruss, Clémentine Maurice, Klaus Wagner, and Stefan Mangard. 2016. [29] Strict-Transport-Security. . Flush+Flush: A Fast and Stealthy Cache Attack. In DIMVA [64] Yoav Nir, Tero Kivinen, Paul Wouters, and Daniel Migault. 2017. Algorithm Daniel Gruss, Raphael Spreitzer, and Stefan Mangard. 2015. Cache Template [30] Implementation Requirements and Usage Guidance for the Internet Key Exchange USENIX Security Attacks: Automating Attacks on Inclusive Last-Level Caches. In Protocol Version 2 (IKEv2). RFC 8247. https://doi.org/10.17487/RFC8247 . USENIX Association, 897–912. Symposium Rolf Oppliger. 1999. Protecting key exchange and management protocols against [65] [31] F. Hao. 2017. J-PAKE: Password-Authenticated Key Exchange by Juggling. RFC Secure Information Networks resource clogging attacks. In . Springer, 163–175. 8236. [66] Yossef Oren, Vasileios P. Kemerlis, Simha Sethumadhavan, and Angelos D. [32] Dan Harkins. [n. d.]. simultaneous authentication of equals. Retrieved 14 No- Keromytis. 2015. The Spy in the Sandbox: Practical Cache Attacks in JavaScript vember 2018 from https://sourceforge.net/p/authsae/wiki/Home/. and their Implications. In CCS . ACM, 1406–1418.

15 Dragonblood: A Security Analysis of WPA3’s SAE Handshake [67] [97] Xiaokuan Zhang, Yuan Xiao, and Yinqian Zhang. 2016. Return-Oriented Flush- Dag Arne Osvik, Adi Shamir, and Eran Tromer. 2006. Cache Attacks and Coun- Reload Side Channels on ARM and Their Implications for Android Devices. In . CT-RSA termeasures: The Case of AES. In . CCS [68] Trevor Perrin. 2013. [TLS] Question regarding CFRG process. Retrieved 29 October 2018 from https://www.ietf.org/mail-archive/web/tls/current/msg10962. html. A EXPERIMENTS Trevor Perrin. 2013. [TLS] Review of Dragonfly PAKE. Retrieved 9 September [69] 2018 from https://www.ietf.org/mail-archive/web/tls/current/msg10922.html. [70] Eyal Ronen, Kenneth G. Paterson, and Adi Shamir. 2018. Pseudo Constant Time 100% Implementations of TLS Are Only Pseudo Secure. In CCS . Target CPU Joseph Salowey. 2013. [TLS] Conclusion of WGLC draft-ietf-tls- [71] 80% pwd. Retrieved 7 April from https://mailarchive.ietf.org/arch/msg/tls/ Attacker CPU Fep2-E7xQX7OQKzfxOoFInVFtm4. Total airtime 60% Matthias Schulz, Francesco Gringoli, Daniel Steinmetzer, Michael Koch, and [72] Matthias Hollick. 2017. Massive reactive smartphone-based jamming using 40% . ACM, 111–121. WiSec arbitrary waveforms and adaptive power control. In Sam Scott, Nick Sullivan, and Christopher A. Wood. 2019. [73] Hashing to Elliptic 20% Curves . Internet-Draft draft-irtf-cfrg-hash-to-curve-03. Internet Engineering Task Force. https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-03 0% Utilization of resource Work in Progress. S. Shin and K. Kobara. 2012. Efficient Augmented Password-Only Authentication [74] 4 3 2 1 0 10 6 7 8 9 5 and Key Exchange for IKEv2. RFC 6628. SeongHan Shin, Kazukuni Kobara, and Hideki Imai. 2010. Security Proof of [75] No. of commit exchanges per second AugPAKE. IACR Cryptology ePrint Archive 2010 (2010), 334. S. Smyshlyaev, E. Alekseev, I. Oshkin, and V. Popov. 2017. The Security Evaluated [76] Standardized Password-Authenticated Key Exchange (SESPAKE) Protocol. RFC 8133. Figure 8: Clogging attack against a professional AP from Stanislav V. Smyshlyaev, Igor B. Oshkin, Evgeniy K. Alekseev, and Liliya R. [77] vendor A using curve P-521. The attacker uses a Raspberry Ahmetzyanova. 2015. On the Security of One Password Authenticated Key Pi 1 model B+, and its CPU usage is shown in the small Exchange Protocol. Cryptology ePrint Archive, Report 2015/1237. https://eprint. iacr.org/2015/1237. dashed line. The total amount of airtime consumed by all [78] Michael Steiner, Gene Tsudik, and Michael Waidner. 1995. Refinement and SAE frames is shown in the long dashed line. extension of encrypted key exchange. ACM SIGOPS Operating Systems Review 29, 3 (1995), 22–30. [79] Rene Struik. 2013. [Cfrg] review of draft-irtf-dragonfly-02 (triggered by [TLS] Working Group Last Call for draft-ietf-tls-pwd). Retrieved 9 November 2018 from B SOURCE CODE https://www.ietf.org/mail-archive/web/cfrg/current/msg03527.html. Re: [Cfrg] small editorial error in and ques- Rene Struik. 2013. [80] Listing 4: Side channel protected quadratic residue test. tion on draft-irtf-cfrg-dragonfly-01 (was: Re: CFRG meeting at IETF 87). 1 static int is_quadratic_residue_blind( Retrieved 10 April 2019 from https://mailarchive.ietf.org/arch/msg/cfrg/ 2 struct sae_data *sae, const u8 *prime, size_t bits, Z-nnOKTA4ddmFd17l5KzlRwWm5Y. const struct crypto_bignum *qr, 3 D. Taylor, T. Wu, N. Mavrogiannopoulos, and T. Perrin. 2007. Using the Secure [81] const struct crypto_bignum *qnr, 4 Remote Password (SRP) Protocol for TLS Authentication. RFC 5054. const struct crypto_bignum *y_sqr) 5 [82] Luke Valenta, David Adrian, Antonio Sanso, Shaanan Cohney, Joshua Fried, { 6 Marcella Hastings, J. Alex Halderman, and Nadia Heninger. 2017. Measuring 7 struct crypto_bignum *r, *num; 24th Annual Network and small subgroup attacks against Diffie-Hellman. In 8 int r_odd, check, res = -1; Distributed System Security Symposium NDSS . 9 Mathy Vanhoef, Nehru Bhandaru, Thomas Derham, Ido Ouzieli, and Frank [83] /* Use the blinding technique to mask y_sqr while determining 10 Piessens. 2018. Operating Channel Validation: Preventing Multi-Channel Man- 11 * whether it is a quadratic residue modulo p to avoid leaking . WiSec in-the-Middle Attacks Against Protected Wi-Fi Networks. In * timing information while determining the Legendre symbol. 12 Mathy Vanhoef and Frank Piessens. 2014. Advanced [84] Wi-Fi attacks using com- * v = y_sqr 13 . ACSAC modity hardware. In * r = a random number between 1 and p-1, inclusive 14 [85] Mathy Vanhoef and Frank Piessens. 2016. Predicting, Decrypting, and Abusing 15 * num = (v * r * r) modulo p USENIX Security WPA2/802.11 Group Keys. In . */ 16 Mathy Vanhoef and Frank Piessens. 2017. Key Reinstallation Attacks: Forcing [86] 17 r = get_rand_1_to_p_1(prime, sae->tmp->prime_len, bits, &r_odd); Nonce Reuse in WPA2. In . CCS 18 ... Mathy Vanhoef and Frank Piessens. 2018. Release the Kraken: new KRACKs in [87] 19 if (r_odd) { the 802.11 Standard. In CCS . 20 /* num = (num * qr) module p Wi-Fi Alliance. 2018. [88] Wi-Fi Alliance introduces security enhancements. 21 * LGR(num, p) = 1 ==> quadratic residue */ Retrieved 6 April 2019 from https://www.wi-fi.org/news-events/newsroom/ if (crypto_bignum_mulmod(num, qr, sae->tmp->prime, num) < 0) 22 wi-fi-alliance-introduces-security-enhancements. goto fail; 23 [89] Wi-Fi Alliance. 2018. Wi-Fi Alliance introduces Wi-Fi certified WPA3 secu- 24 check = 1; rity. Retrieved 6 April 2019 from https://www.wi-fi.org/news-events/newsroom/ 25 } else { wi-fi-alliance-introduces-wi-fi-certified-wpa3-security. 26 /* num = (num * qnr) module p [90] Wi-Fi Alliance. 2018. WPA3 Specification Version 1.0. Retrieved 6 April 2019 * LGR(num, p) = -1 ==> quadratic residue */ 27 from https://www.wi-fi.org/file/wpa3-specification-v10. if (crypto_bignum_mulmod(num, qnr, sae->tmp->prime, num) < 0) 28 [91] WikiDevi. 2018. Semantic search: wireless routers. Last retrieved 14 November 29 goto fail; 2018 form https://wikidevi.com/. check = -1; 30 [92] T. Wu. 2000. The SRP Authentication and Key Exchange System. RFC 2945. 31 } [93] . 1998. The Secure Remote Password Protocol.. In NDSS , Thomas D Wu et al res = crypto_bignum_legendre(num, sae->tmp->prime); 32 Vol. 98. Citeseer, 97–111. ... 33 Yuval Yarom. 2017. Mastik: A Micro-Architectural Side-Channel Toolkit. cs. [94] res = res == check; 34 adelaide.edu.au/~yval/Mastik/Mastik.pdf . 35 ... [95] Flush+Reload: A High Resolution, Low Yuval Yarom and Katrina Falkner. 2014. . Noise, L3 Cache Side-Channel Attack. In USENIX Sec [96] Yuval Yarom, Daniel Genkin, and Nadia Heninger. 2016. CacheBleed: A Timing Attack on OpenSSL Constant Time RSA. In CHES (Lecture Notes in Computer Science) , Vol. 9813. Springer, 346–367.

16 Mathy Vanhoef and Eyal Ronen Listing 6: Assembly output of SAE’s hash-to-curve method. Listing 5: SAE password derivation using hash-to-curve. 1 000000000002efe0 : static int sae_derive_pwe_ecc( 1 ... 2 struct sae_data *sae, const u8 *addr1, 2 2f2c8: e8 f3 17 05 00 callq 80ac0 3 3 const u8 *addr2, const u8 *password, ... 4 size_t password_len, const char *identifier) 4 5 { 5 ... 2f719: e8 f2 fa 04 00 callq 7f210 6 6 7 ... 7 if (random_get_bytes(dummy_password, dummy_password_len) < 0) 8 8 2f751: e8 1a f7 04 00 callq 7ee70 return -1; 9 2f75d: 0f 85 59 01 00 00 jne 2f8bc ... 9 /* Create a random quadratic residue (qr) and quadratic ... /* handle qr case code range */ 10 10 11 * non-residue (qnr) modulo p for blinding purposes during 2f7d2: 0f 86 60 fa ff ff jbe 2f238 11 ... 12 * the loop. 12 13 13 */ /* start nqr case code */ 14 2f8bc: 48 8b 7c 24 40 mov 0x40(%rsp),%rdi if (get_random_qr_qnr(prime, prime_len, sae->tmp->prime, bits, 14 &qr, &qnr) < 0) 2f8c1: be 01 00 00 00 mov $0x1,%esi 15 15 16 2f8c6: e8 a5 f5 04 00 callq 7ee70 return -1; 16 17 ... 17 2f8cb: e9 94 fa ff ff jmpq 2f364 /* end nqr case code */ 18 /* Continue for at least k iterations to protect against 18 19 * side-channel attacks that attempt to determine the number 19 ... 20 * of iterations required in the loop. 21 */ 22 for (counter = 1; counter <= k || !x; counter++) { 23 ... 24 res = sae_test_pwd_seed_ecc(sae, pwd_seed, prime 25 qr, qnr, &x_cand); 26 if (res < 0) 27 goto fail; 28 if (res > 0 && !x) { ... 29 x = x_cand; /* saves the current x value */ 30 ... 31 32 /* Use a dummy password for the following rounds, 33 * if any. */ 34 addr[0] = dummy_password; 35 len[0] = dummy_password_len; 36 } else if (res > 0) { 37 crypto_bignum_deinit(x_cand, 1); 38 } } 39 ... 40

Related documents