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 ( "crypto/rand" "fmt" "io" "github.com/cloudflare/circl/dh/x25519" ) func main() { var AliceSecret, BobSecret, AlicePublic, BobPublic, AliceShared, BobShared x25519.Key _, _ = io.ReadFull(rand.Reader, AliceSecret[:]) x25519.KeyGen(&AlicePublic, &AliceSecret) _, _ = io.ReadFull(rand.Reader, BobSecret[:]) x25519.KeyGen(&BobPublic, &BobSecret) _ = x25519.Shared(&AliceShared, &AliceSecret, &BobPublic) _ = x25519.Shared(&BobShared, &BobSecret, &AlicePublic) fmt.Printf("Alice Secret %x\nAlice Public %x\n\n",AliceSecret,AlicePublic) fmt.Printf("Bob Secret %x\nBob Public %x\n\n",BobSecret,BobPublic) fmt.Printf("\nBob Shared %x\n\nAlice Shared %x",AliceShared,BobShared) }
A sample run is:
Alice Secret 11b6f455b293eb5222bcfdaf07d44e26a8d6de80e4e033326f9552d6c5baa6c4 Alice Public 78ffff4ff6da58c4561d42a007e4bab5cdf62766db71f4b66615e2097dadff7c Bob Secret 8bf225bdf7ec8a91b3370aef174a0439439f32aa28b3eef4d5eb4a905d544e57 Bob Public f9d20110d8e9bbe17d349cf7f7cb5442646934a14bb9d405fd1c73bfe1e7235d Bob Shared e0c3716490b83eeaece00b6624c7018440f53590d6fe75b00e68c05452e81e41 Alice Shared e0c3716490b83eeaece00b6624c7018440f53590d6fe75b00e68c05452e81e41