TIMING ATTACKS ON MODP GROUPS

In this section we empirically show that the hash-to-group method that converts a password into a MODP element is vulnerable to timing attacks. The obtained info will later on be used in password partitioning attacks, allowing one to recover the victim’s password. 6.1 Background Up to this point, we assumed the SAE handshake is executed using elliptic curves. Although this is a natural assumption, since any station that supports SAE must implement elliptic curve P-256, the SAE handshake can also be performed using multiplicative groups mod a prime p (MODP groups). When employing MODP groups, the algorithm in Listing 2 is used to convert the password into a group element. In contrast to the algorithm for elliptic curves, the one for MODP groups does not employ any side-channel defenses such as performing extra iterations , §12.4.4.3.2]. Although elliptic curves are generally more performant than MODP groups, this is not necessarily the case with SAE. In particular, due to the extra iterations needed in the hash-to-curve method, the hash-to-group method for MODP groups may be slightly more efficient. Recall from Section 3.3 that these extra iterations are needed to mitigate timing side-channels when using elliptic curves. As a result, users may prefer MODP groups over elliptic curves, especially because this would also reduce the impact of our clogging attack of Section 4. Unfortunately, we show that the hash-to-group method for MODP groups is also affected by timing side-channels. In practice this means that for certain MODP groups, extra iterations must be performed in order to mitigate timing attacks. 6.2 Variable Number of Iterations When converting a password to a MODP element, the algorithm in Listing 2 performs a variable number of iterations. In fact, the CFRG already warned about this when they were reviewing a close variant of Dragonfly . Unfortunately, countermeasures against this timing leak were not incorporated into the SAE handshake. We will now analyze what the practical impact of this decision is, and we will determine whether this can be exploited in practice. The first cause of extra iterations is when the output of the Key Derivation Function (KDF) on line 7 returns a number bigger than the prime p of the MODP group. Note that the number of bits returned by KDF is equal to the number of bits needed to represent p. That is, the number of bits returned by the KDF function depends on the MODP group being used. This also implies that the probability that value is bigger than p depends on the MODP group being used. Fortunately, for most MODP groups this probability is extremely small, because the prime p is only slightly smaller than a power of two. However, for the MODP groups shown in Table 3, the probability that the output of KDF is bigger than p is 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). Finally, the if-condition on line 11 can in principle also cause an extra iteration to be executed. However, for all supported MODP groups, the probability of this happening is negligible. Since the output of the KDF depends on the password, the number of performed iterations also depends on the password being used. If an adversary learns this number, they learn that passwords which require a different number of iterations are not used by the victim. Note that the number of executed iterations X follows a geometric distribution: Pr[X = n] = Pr[value ≥ p] n−1 · (1 − Pr[value ≥ p]) (1) This means that the average number of iterations required to derive the password element equals E[X] = (1 − Pr[value ≥ p]) −1 . For MODP group 22, this equals 1.45, and for group 24 this equals 1.89 iterations. In other words, on average one timing measurement allows the adversary to learn the result of multiple iterations. Finally, observe that the MAC address of the client also influences the output of the KDF, and hence also influences the number of executed iterations (line 6 in Listing 2). This means that an adversary can spoof MAC addresses, and for each address measure the number of executed iterations. We will show in Section 8 how this information can be used to perform a password partitioning attack, allowing an adversary to recover the target’s password.

Experiments

To determine the feasibility of measuring the number of execution iterations, we performed the attack in a realistic setting. For the victim we used a Raspberry Pi 1 model B+ that was running hostapd version 2.6. We used a Raspberry Pi because its 700 MHz CPU matches the one in commodity home routers. The Raspberry Pi was equipped with a WNDA3200 Wi-Fi dongle. Picking hostapd to run the AP was an obvious choice, since it is the most widely used wireless daemon in both professional and home routers, and is the only one that supports MODP groups at the time of writing. The adversary used a MSI GE60 Laptop with a WNDA3200 Wi-Fi dongle. To perform timing measurements, we wrote a tool on top of the aircrack-ng tool suite. It spoofs commit frames, and measures how long it takes to receive the corresponding commit reply. After each individual measurement, a deauthentication packet is injected towards the AP. This causes hostapd to clear all state related to the spoofed MAC address, and enables us to rapidly perform a new timing measurement with the same spoofed address. Two optimizations were required to make the attack practical. First, similar to our clogging attack of Section 4.3, we had to use virtual interface support of Atheros chips to acknowledge all frames sent to a spoofed MAC address. This prevents the AP from retransmitting frames, making the attack faster and more reliable. More importantly, background Wi-Fi traffic influences the timing measurements. Additionally, periodic background tasks on the AP also influence the timing measurements. Both sources of noise are problematic because they are not constant throughout the attack. To 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 influences the measurements of all MAC addresses, instead of only affecting the measurements of one address. With the above setup and optimizations, we carried out an attack using MODP group 22, and another attack using group 24. We spoofed 20 addresses in each experiment, and performed 1000 measurements 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 the average timing measurements of one spoofed MAC address. From these timings, it is straightforward to derive the number of executed iterations. For example, the cluster of lines (i.e. spoofed MAC addresses) at the bottom corresponds to one iteration. The cluster above that corresponds to two iterations, and so on. For the highest line in the MODP group 24 attack, careful inspection reveals that this corresponds to 9 iterations. The correctness of these results was confirmed by inspecting the debug output of hostapd. We conclude that timing attacks can accurately determine the number of executed iterations. 6.4 Countermeasures and Discussion Ideally, groups 22, 23, and 24 should be disabled. Doing this is in line with RFC 8247, which recommends that implementations no longer use these groups due to, among other things, their small subgroups. Implementations also should not use MODP groups 1, 2, or 5. The other MODP groups use primes that are slightly smaller than a power of two, meaning it is extremely 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 hashto-group method used by the SAE handshake. Similar to our defense from Section 4.5 against clogging attacks, this would allow implementations to calculate the password element offline. Although the algorithm would still be insecure, an adversary would no longer be able to easily trigger (and measure) executions of it. In principle, extra iterations can also be performed after finding the MODP password element, so a fixed number of iterations are always executed. This is similar to the countermeasure for the elliptic curve case. However, we do not recommend this defense, because implementations may still be vulnerable to cache-based attacks, and because groups 22 to 24 should be avoided in general. 6.5 Applicability to Elliptic Curves In practice, we discovered that version 2.1 to 2.4 of wpa_supplicant and hostapd use k = 4 in the hash-to-curve algorithm, while only newer versions use k = 40. This means that against these older versions, timing attacks are also possible when elliptic curves are used. In particular, a random MAC address will have a probability of 2 −4 = 6.25% of requiring more than 4 iterations, in which case information about the password is leaked. Although most Linux distributions that used these older versions do not enable SAE in those builds, dedicated builds for networking devices (e.g. OpenWRT 15.05.1) did use these older versions with SAE enabled. We also conjecture that resource-constrained devices may not implement the fixed amount of 40 iterations, due to the overhead of this countermeasure. Against such implementations, timing attacks would also be possible against the hash-to-curve algorithm.