Curve 25519 is one of the most widely used ECC methods. It uses a curve of \(y^2 = x^3 + 486662 x^2 + x\), and which is a Montgomery curve. This page implements ECDH, and which is the method used in Tor to exchange the key.
ECDH with Curve 25519 using Go |
ECDH and Curve 25519
One of the uses of Curve 25519 is in Tor routing. The Web traces a wide range of information, including user details from cookies, IP addresses, and even user behaviour (with user fingerprints). This information be used to target marketing to users, and also is a rich seem of information for the detection and investigation of crime. The Tor network has long been a target of defence and law enforcement agencies, as it protects user identity and their source location, and is typically known as the dark web, as it is not accessible to key search engines such as Google. Obviously Tor could be used to bind to a server, so that the server will only talk to a client which has been routed through the Tor network, which would mean than search engines will not be able to find the content on them. This is the closed model in creating a Web which cannot be accessed by users on the Internet, and only by those using Tor. If then users trade within the dark web servers with Bitcoins, there will be little traces of their transactions.
With the Tor network, the routing is done using computers of volunteers around the world to route the traffic around the Internet, and with ever hop the chances to tracing the original source becomes reduces. In fact, it is rather like a pass-the-parcel game, where game players randomly pass to others, but where eventually the destination receiver will eventually receive the parcel. As no-one has marked the parcel on its route, it’s almost impossible to find out the route that the parcel took.
The trace of users access Web servers is thus confused with non-traceable accesses. This has caused a range of defence agencies, including the NCA, to invest in methods of compromising the infrastructure, especially to uncover the dark web. A strange feature in the history of Tor is that it was originally sponsored by the U.S. Naval Research Laboratory (which had been involved in onion routing), and its first version appeared in 2002, and was presented to the work by Roger Dingledine, Nick Mathewson, and Paul Syverson, who have since been named, in 2012, as one of Top 100 Global Thinkers. It since received funding from Electronic Frontier Foundation, and is now developed by The Tor Project, which is a non-profit making organisation.
The encryption involves each of the routing nodes having an encryption key, and the data is encrypted with each of the keys:
In this case the purple key is the encryption key of the first node, and is the last to be encrypted. As the data goes through the network, each node decrypts with their key. The last part of the communication, out of the gateway, will thus be non-encrypted, but a protocol such as HTTPS can be used to protect the last part of the communication.
Along the route, each Tor relay node takes the cell from its predecessor and decrypts with the negotiated symmetric key. It then passes the cell onto its successor. With Curve25519 we generate a 32-byte secret key (256 bits) and a 32-byte public key. A hash of the shared secret is then created as a 32-byte secret key (Curve25519(a,Curve25519(b,9)), as illustrated in the figure below. This is used for a 128-bit or 256-bit AES key.
Curve 25519 and ECDH
We must thus create a unique encryption key for each routing host. This is achieved by using Curve 25519, and uses ECDH (Elliptic Curve Diffie Hellman). With this we select a base x co-ordinate point of 9 (G), and then Bob and Alice generate random values, and determine their public keys. Alice generates a, and Bob generates b. Alice’s public key will be:
\(A=9 a \pmod p\)
and Bob’s public key becomes:
\(B=9 b \pmod p\)
The exchange their values, and Alice multiplies by the value received from Bob by \(a\), and Bob multiplies the value he receives from Alice by \(b\). They should then end up with the same value, and which should be:
\(K=9 a b \pmod p\)
So here is a basic Go program to implement:
package main import ( "golang.org/x/crypto/curve25519" "math/rand" "fmt" "time" ) func main() { rand.Seed(time.Now().UnixNano()) var privateKey [32]byte for i := range privateKey[:] { privateKey[i] = byte(rand.Intn(256)) } var publicKey [32]byte curve25519.ScalarBaseMult(&publicKey, &privateKey) fmt.Printf("\nAlice Private key (a):\t%x\n",privateKey) fmt.Printf("\nAlice Public key point (x co-ord):\t%x\n",publicKey) var privateKey2 [32]byte for i := range privateKey[:] { privateKey2[i] = byte(rand.Intn(256)) } var publicKey2 [32]byte curve25519.ScalarBaseMult(&publicKey2, &privateKey2) var out1, out2 [32]byte fmt.Printf("\nBob Private key (b):\t%x\n",privateKey2) fmt.Printf("\nBob Public key point (x co-ord):\t%x\n",publicKey2) curve25519.ScalarMult(&out1, &privateKey, &publicKey2) curve25519.ScalarMult(&out2, &privateKey2, &publicKey) fmt.Printf("\nShared key (Alice):\t%x\n",out1) fmt.Printf("\nShared key (Bob):\t%x\n",out2) }
A sample run is:
Alice Private key (a): fa10936fe8e7652a9504cf0970bf46dee8c94593ebd87f35a13dd4e1f4edd1ac Alice Public key point (x co-ord): 901737441b60c4226be178a93839a192441cb3d0bf1321f9c95dd0831cebe93e Bob Private key (b): 66f8df8f45f470c3a05826408de763f781c6aa5b61d0e5e040141acdd0e6e1e0 Bob Public key point (x co-ord): b05ea9404fea0c1c16640d96eec59c5412b8e07d4feac9d5a25dc458d0dae238 Shared key (Alice): 9a57c1bef48ae603466b34ba61c281ab93b0171e3e44a44e317427a46285ec71 Shared key (Bob): 9a57c1bef48ae603466b34ba61c281ab93b0171e3e44a44e317427a46285ec71