Fixing Wi-fi … Meet Dragonfly … and a bit of ECC

It has been known for a while that the core of Wi-fi — WPA-2 (IEEE 802.11i) — is weak in its implementation of security. While its…
Ref [here]

Fixing Wi-fi … Meet Dragonfly … and a bit of ECC

It has been known for a while that the core of Wi-fi — WPA-2 (IEEE 802.11i) — is weak in its implementation of security. While its cryptography is sound — using AES encryption — its main weakness focuses on the flawed 4-way handshake.

Within this, the client and access point pass a hashed value of the SSID and the password, and this can be seen by an intruder. Its saving grace is that the hashing method used — PBKDF2 — is a relatively slow method, and when it was initially rolled-out it would have been relatively expensive to crack it. Unfortunately, these days, cloud crackers can now run at high speeds, and even PBKDF2 can be cracked within reasonable time limits and for a minimal cost.

The great worry, though, is that once it is cracked, it is cracked for the whole network. With 16-GPU clusters available to rent within AWS for less than $10 per hour, the opportunity exists for the core of wi-fi to fundamentally fail within the next few years.

And so, the Wi-Fi Alliance has addressed this fundamental problem with the release of WPA-3, and where the 4-way handshake is replaced by a zero-knowledge proof method named Simultaneous Authentication of Equals (SAE). Its roots derive from mesh networks and of the Dragonfly protocol, and have since been defined in IEEE 802.11s.

SAE

The focus for SAE is to properly authenticate a device onto a network and using a password and MAC addresses to authenticate. An intruder should not be able to connect to a network unless they known password that the access point uses. Also, an intruder should not be able to guess either the password or the long-term authentication element of the password. In WPA-2 an intruder can listen to the 4-way handshake and can then brute force the password from hashed value created (see the section below for details).

With SAE — and which is based on a zero-knowledge proof known as dragonfly — we use the Diffie-Hellman key exchange method but adds an authentication element. With this we create a shared key with elliptic curve methods (NIST curves), and then use a pre-shared key and MAC addresses. When the client connects to the access point, they perform an SAE exchange. If successful, they will each create a cryptographically strong key, of which the session key will be derived from. If one session key is cracked it will only affect one key, and not all of the key used, as with WPA-2.

The basic method

Basically a client and access point goes into phases of commit and then confirm. Once we have a commitment, the client and access point can then go into the confirm states each time there is a session key to be generated. The method uses forward secrecy, where an intruder could crack a single key, but not all of the other keys.

The core security comes from the power of discrete logarithms and where it is difficult to find the value of x, even though we have Y, G and p:

Y = Gˣ mod q

and where q is a prime number. We make q a prime number as it allows us to perform maths functions, while constraining the value between 0 and q-1 [finite fields].

In the commit phase, Alice (the client) generates two random values (a,A), and then computes a scalar value (a+A). The value that Alice will pass is the PE (Password Equivalent — such as hashed value of the password that Bob and Alice know) raised to the power of -A. As the values will get large, the operations are done with (mod q) and where q is a large prime number.

Bob does the same, and then they exchange values. In the end they will have the same shared commit key (PEªᵇ). They will only have the same shared value, if they have both used the same password. This password is thus used to validate Bob and Alice, and they will only have the shared shared commit value if they both have the same password. The intruder cannot determine either the original password or the final shared value.

Dragonfly protocol for zero knowledge proof

To perform the -A power, we perform an inverse mod q function (and which uses the extended euclidean algorithm) [inverse mod function]:

elementA = inverse_of(pow(PE,A),q)
elementB = inverse_of(pow(PE,B),q)

In the confirm phase we then use the long-term key to generate a unique session key. An attacker cannot determine the password used or the long-term master key (PMK). The cracking of one session key will also not reveal the rest of the keys which have been used (forward security). This is not the case for WPA-2.

Implementation

I have previously implemented Dragonfly with discrete logs:

https://asecuritysite.com/zero/dragonfly

So, let’s implement it with ECC (Elliptic Curve Cryptography), and where we convert exponents (g^x) to multiplication (xG), and multiplication (g^x . g^y) to adding ((x+y).G). Overall, ECC is much more efficient that discrete logs. We can now convert this into elliptic curves. Bob will generate random scalars of b and B and compute:

sB := b.Add(B)

Bob will generate random scalars of a and A and compute:

sA := a.Add(A)

Bob and Alice will generate the PE elliptic curve point from the password:

msg := []byte(pass)
	h := sha256.New()
	h.Write(msg)
	msg1, _ := curve.Scalar.SetBytes(h.Sum(nil))
	PE := G.Mul(msg1)

Bob will compute the shared secret as:

ss_b := PE.Mul(sA).Add(PE.Mul(A.Neg())).Mul(b)

and Alice with:

ss_a := PE.Mul(sB).Add(PE.Mul(B.Neg())).Mul(a)

This is:

ss_a=b.(sA.PE−A.PE)

ss_b=a.(sB.PE−B.PE)

This works because:

ss_a=b.sA.PE−b.A.PE=b(a+A).PE−b.A.PE=a.b.PE+b.A.PE−b.A.PE=a.b.PE

ss_b=a.(sB.PE−B.PE)=a.sB.PE−a.B.PE=a.(b+B).PE−a.B.PE=a.b.PE

In the confirm phase we then use the long-term key to generate a unique session key. An attacker cannot determine the password used or the long-term master key (PMK). The cracking of one session key will not reveal the rest of the keys which have been used. Which is not the case for WPA-2.

Here is a simple implementation of the Dragon method:

A sample run is:

Password= hello123
=== Bob generates ====
b (Bob)= 4fd0f5f392ee19f20f7501e6e629db454c45126717314674d0602ed1e5ca3d16
B (Bob)= 7c1a1da01fc785931ea40c5b8258a801a2a38a8b139a40899a6a332f1047ad7b
== Alice generates ===
a (Alice)= 235c3e2d65866ddfc02212dd5cbf3a2a7bfab4c615c7dfe5e7af4217e970f07f
A (Alice)= 4fd0f5f392ee19f20f7501e6e629db454c45126717314674d0602ed1e5ca3d16
== PE of password (SHA256) ==
H(password)= 27cc6994fc1c01ce6659c6bddca9b69c4c6a9418065e612c69d110b3f7b11f8a
PE(password)= 02570dc43c510a5102a8e94d2a029cdb61a8beeb6c59017f509870a37ec99dac93
=== After key exchange ===
Shared Secret (Bob)= 028c55265ca1edb7cdc4bb5a80bb1a7f5bef1e6cb0f66b4b1ad7249d1cc6efac47
Shared Secret (Alice)= 028c55265ca1edb7cdc4bb5a80bb1a7f5bef1e6cb0f66b4b1ad7249d1cc6efac47
Bob and Alice have a shared secret

With a compressed point, we get a 32 byte compressed value (64 hex characters), and then add a 02 or a 03 to represent when y is even (02) or odd (03). So “028c55265ca1edb7cdc4bb5a80bb1a7f5bef1e6cb0f66b4b1ad7249d1cc6efac47” is a compressed point, and is only the x-axis point, and where the y-axis point is even.

Conclusions

WPA-2 is flawed, and is not really fit for purpose. Our core protection is built around something that — given time — can be cracked. As GPUs and ASIC advance we need to move away from hashed passwords, as they are fundamentally flawed, and implement zero-knowledge proof methods. A user should not be asked to show their password, but should be asked if they can prove that they know it. Hashed passwords are typically the weak point in data breaches, and where millions, if not billions (as in the case of Yahoo) can be released into the wild, and where hackers can easily pick-off the passwords that users have used.