The Dragonfly zero-knowledge proof method is used in WPA-3 for Simultaneous Authentication of Equals (SAE). In this case we will implement using the secp256k1 curve [Discrete log version].
Dragon Fly - Zero Knowledge Proof with ECC |
Theory
Security in Wi-Fi has had a difficult route. In its current form (WPA-2) a password can be cracked by listening to the 4-way handshake between a client and the access point. This will then crack all the keys that have been used or will be used in the future. WPA-3 addresses this by securing the password, and uses zero-knowledge proof to make sure that no elements of the password are transmitted over the network. Both sides then pass their knowledge of the password, and then both can prove that each of them knows the secret password.
With WPA-2 we hash the SSID and the password and use this to create a master key (and which is used to derive session keys). The intruder can then use a dictionary or a brute force attack on the hash to discover the password and thus the long-term key (to which all other keys are derived). A PBKDF2 hash is used to make the hash difficult to crack, but if an intruder has GPU crackers, it can make the cracking fairly inexpensive. A weak password is also easily crackable, especially if it comes from a standard dictionary. This happens for an offline crack, and where an intruder can use Cloud-based crackers to crack the password on the system, and then crack all the keys derived from it.
The upgrading of wi-fi security has often been driven more by keeping compatibility with legacy devices than in driving forward improvements. With WEP we had a standard which broke almost every rule in the good cryptography book. It had a small IV value (24-bits), and which meant that it rolled-over after a relatively show time. This then cracked the global key for the whole network, and an intruder could listen to all of the encrypted traffic. It also supports a flawed stream cipher and key size: 40-bit RC4.
So the fix was WPA which integrated a new encryption method (TKIP) and where the IV and key size was increased to safer levels. In 2004, WPA-2 brought a block cipher: AES and improved authentication, and introduced the 4-way handshake. This handshake has since been the source of a number of vulnerabilities.
So with WPA-2 (802.11i) seen as flawed, the Wi-Fi Alliance has released WPA-3 [here], and which introduces almost seamless protection against brute-force attacks for network passwords. The protection only allows for one change to crack a password. As with WPA-2, it is available in two forms:
- WPA3-Personal: This replaces the 4-way handshake with Simultaneous Authentication of Equals (SAE) [1] and which is defined in the IEEE 802.11s standard. SAE was initially defined for mesh networks, but is now scaling to infrastructure wireless networks.
- WPA3-Enterprise: This integrates a back-end authentication infrastructure, such as with a RADIUS server. Elliptic Curve Diffie-Hellman (ECDH) exchange and Elliptic Curve Digital Signature Algorithm (ECDSA) using a 384-bit elliptic curve are used to a strong authentication.
Along with these changes, WPA-3 brings the integration of QR codes to gain the network connection details.
The focus for Simultaneous Authentication of Equals (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.
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.
In the commit phase, Alice (the client) generates two random values (a,A), 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. 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^{ab}\)). The password has been 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.
We can now convert this into elliptic curves. Bob first creates to random scalar values of \(b\) and \(B\):
b := curve.Scalar.Random(rand.Reader) B := curve.Scalar.Random(rand.Reader)
Bob will then compute:
sB := b.Add(B)
Alice will generate random scalars of \(a\) and \(A\):
a := curve.Scalar.Random(rand.Reader) A := curve.Scalar.Random(rand.Reader)
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 pass \(sB\) and \(-B.PE\) to Alice. Alice will pass \(sA\) and \(-A.PE\) to Bob. 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:
package main import ( "crypto/rand" "crypto/sha256" "fmt" "os" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { curve := curves.K256() G := curve.Point.Generator() // argCount := len(os.Args[1:]) pass := "hello" argCount := len(os.Args[1:]) if argCount > 0 { pass = os.Args[1] } a := curve.Scalar.Random(rand.Reader) b := curve.Scalar.Random(rand.Reader) A := curve.Scalar.Random(rand.Reader) B := curve.Scalar.Random(rand.Reader) sA := a.Add(A) sB := b.Add(B) msg := []byte(pass) h := sha256.New() h.Write(msg) msg1, _ := curve.Scalar.SetBytes(h.Sum(nil)) PE := G.Mul(msg1) ss_b := PE.Mul(sA).Add(PE.Mul(A.Neg())).Mul(b) ss_a := PE.Mul(sB).Add(PE.Mul(B.Neg())).Mul(a) fmt.Printf("\nPassword= %s\n", pass) fmt.Printf("\n=== Bob generates ====") fmt.Printf("\nb (Bob)= %x\n", b.Bytes()) fmt.Printf("\nB (Bob)= %x\n", B.Bytes()) fmt.Printf("\n== Alice generates ===") fmt.Printf("\na (Alice)= %x\n", a.Bytes()) fmt.Printf("\nA (Alice)= %x\n", b.Bytes()) fmt.Printf("PE of password (SHA256):") fmt.Printf("\nH(password)= %x\n", msg1) fmt.Printf("\nPE(password)= %x\n", PE.ToAffineCompressed()) fmt.Printf("\n=== After key exchange ===") fmt.Printf("\nShared Secret (Bob)= %x\n", ss_a.ToAffineCompressed()) fmt.Printf("\nShared Secret (Alice)= %x\n", ss_b.ToAffineCompressed()) if ss_a.Equal(ss_b) { fmt.Printf("Bob and Alice have a shared secret") } else { fmt.Printf("Bob and Alice DO NOT have a shared secret") } }
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.