Tor key creation - Curve25519
[Back] The Tor routing network uses relay node to secure traffic. Each node has their own encryption key and is negotiated with Curve25519 (Elliptic Curve Diffie Hellman). The following generate a shared key using Curve25519 [X448]:
As we move into an Information Age, there is a continual battle on the Internet between those who would like to track user activities, and those who believe in anonymity. The recent right to be forgotten debate has shown that very little can be hidden on the Internet, and deleting traces can often be difficult. The Internet, too, is be a place where crime can thrive through anonymity, so there is a continual tension between the two sides of the argument.
To law enforcement agencies the access to Internet-based information can provide a rich source of data for the detection and investigation of crime, but they have struggled to find evidence with the Tor (The Onion Routing) network. Its usage has been highlighted over the years, including in June 2013 when Edward Snowden, used it to send information on PRISM to the Washington Post and The Guardian. The trace of a user’s access to Web servers is thus confused with non-traceable accesses. This has caused a range of defence agencies to invest methods of compromising the infrastructure, especially to uncover the dark web. Its development received funding from Electronic Frontier Foundation, and further developed by The Tor Project - a non-profit making organisation. Many government agencies around the World now target its cracking, such as with the Russian government offering a bounty of $111,000. 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), with its first version appeared in 2002. The original demonstrator was created by Roger Dingledine, Nick Mathewson, and Paul Syverson, and who have since been named, in 2012, as one of Top 100 Global Thinkers.
Web traces contain a wide range of information, including user details from cookies, IP addresses, and even user behaviour (with the usage of user behaviour fingerprints). This information can then be used to target marketing to users, and also is a rich seam of information for the detection and investigating crime. The Tor network has long been a target of defence and law enforcement agencies, as it protects user identity, the contents of the accesses, and the source and destination locations. Connections within the Tor network can either just use it to route over public network networks (in a similar way to tunnelled VPN connection which are tunnelled through a gateway) and connect using HTTP or HTTPS (and where an exit gateway will define the host which is making the accesses), or can route directly from the browser to the service (these connect to .onion sites).
Web sites which exist in the Tor network and which have a binding from the Tor browser to the end service are often known as residing in the dark web, and are not accessible to most search engines such as Google. Tor can thus 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. This is the closed model of creating a Web infrastructure and which cannot be accessed by users on the Internet using non-Tor enabled browser.
With the Tor network, the routing is done using computers of volunteers around the world to route the traffic around the Internet, and within each hop the chances to trace the original source significantly 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 encryption involves each of the routing nodes (the relay nodes) having a symmetric encryption key, and the data is encrypted with each of the keys (Figure 1). 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.
Figure 1: Onion routing
At the core of Tor is Onion Routing, which uses subscriber computers to route data packets – known as cells - over the Internet, rather than using publically available routers. One thing that must be said is that Tor aims to tunnel data through public networks, and keep the transmission of the data packets safe, which is a similar method that Google uses when you search for information (as it uses the HTTPS protocol for the search). So for a Tor network, let’s ask a few questions:
Tor traffic uses fix length cells which flow across the network, and create a circuit, and where each relay node only knows its predecessor and its successor. Each relay node then stores its own symmetric key for the connection and uses this to decrypt cells that are routed through it. For a connection between a client and a server we thus have:
The client or server will initially send a cell and which is encrypted with each of the symmetric keys used in the Tor relay nodes, and encrypted in the sequence where the first relay node has the last encryption key applied (the outer layer of the onion), and the first one used has the key of the last relay node (the inner most layer of the onion). The negotiation of the key that each relay node uses is done on the creation of the circuit with the ntor handshake. This uses the Curve25519 method  and where the network shares the G and N value.
Along the route, each Tor relay node takes the cell from its predecessor and unencrypts 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 Figure 7.22. This is used for a 128-bit or 256-bit AES key.
Figure 2: Curve25519 method 
Some sample code is:
import os import binascii # Based on code from https://github.com/nnathan/eccsnacks/blob/master/eccsnacks/curve25519.py P = 2 ** 255 - 19 A24 = 121665 def cswap(swap, x_2, x_3): dummy = swap * ((x_2 - x_3) % P) x_2 = x_2 - dummy x_2 %= P x_3 = x_3 + dummy x_3 %= P return (x_2, x_3) def X25519(k, u): x_1 = u x_2 = 1 z_2 = 0 x_3 = u z_3 = 1 swap = 0 for t in reversed(range(255)): k_t = (k >> t) & 1 swap ^= k_t x_2, x_3 = cswap(swap, x_2, x_3) z_2, z_3 = cswap(swap, z_2, z_3) swap = k_t A = x_2 + z_2 A %= P AA = A * A AA %= P B = x_2 - z_2 B %= P BB = B * B BB %= P E = AA - BB E %= P C = x_3 + z_3 C %= P D = x_3 - z_3 D %= P DA = D * A DA %= P CB = C * B CB %= P x_3 = ((DA + CB) % P)**2 x_3 %= P z_3 = x_1 * (((DA - CB) % P)**2) % P z_3 %= P x_2 = AA * BB x_2 %= P z_2 = E * ((AA + (A24 * E) % P) % P) z_2 %= P x_2, x_3 = cswap(swap, x_2, x_3) z_2, z_3 = cswap(swap, z_2, z_3) return (x_2 * pow(z_2, P - 2, P)) % P # When passed as a byte array def unpack(s): if len(s) != 32: raise ValueError('Invalid Curve25519 scalar (len=%d)' % len(s)) t = sum((s[i]) << (8 * i) for i in range(31)) t += (((s) & 0x7f) << 248) return t # When passed as a string def unpack2(s): if len(s) != 32: raise ValueError('Invalid Curve25519 scalar (len=%d)' % len(s)) t = sum((ord(s[i]) ) << (8 * i) for i in range(31)) t += (((ord(s) ) & 0x7f) << 248) return t def pack(n): return ''.join([chr((n >> (8 * i)) & 255) for i in range(32)]) def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n def scalarmult(n, p): n = clamp(unpack(n)) p = unpack2(p) return pack(X25519(n, p)) def scalarmult_base(n): n = clamp(unpack(n)) return pack(X25519(n, 9)) a = os.urandom(32) b = os.urandom(32) a_pub = scalarmult_base(a) b_pub = scalarmult_base(b) k_ab = scalarmult(a, b_pub) k_ba = scalarmult(b, a_pub) print ("Bob private:\t",binascii.hexlify(a)) print ("Alice private:\t",binascii.hexlify(b)) print ("\n\nBob public:\t",binascii.hexlify(b_pub.encode())) print ("Alice public:\t",binascii.hexlify(a_pub.encode())) print ("\n\nBob shared:\t",binascii.hexlify(k_ba.encode())) print ("Alice shared:\t",binascii.hexlify(k_ab.encode()))
and a sample run is:
Bob public: 2f2a9b6b82a1a696a4622923f1fe2ec7689383183ae32d1c011b9fce02b2225d Alice public: a44ae94deccf2313a4cffda0b93c1031b49902e7a34e86e73d30c40eeac49f14 Bob shared: 4cce4255bc41ff7c2b4a2d153c499dbaaf665d26426bf3f10f156c0849c19c49 Alice shared: 4cce4255bc41ff7c2b4a2d153c499dbaaf665d26426bf3f10f156c0849c19c49