The NSA, NIST and Crypto in Court

The NSA, NIST and Crypto in Court

What will be greater in impact than Y2K? Ans: The replacement of our existing public key encryption methods with Post Quantum robust methods. And, so, NIST has been defining new standards for these. The initial winners were mainly lattice methods and were: Kyber (Key Exchange and Public Key encryption) and Dilithium, Falcon, and SPHINCS+ (digital signatures). SPHINCS+ is the only non-lattice method.

There were thoughts that NIST previously push a random key generator that had a backdoor. And, so, in March 2022, a FOIA (Freedom of Information Act Request) was submitted by the mighty Dan Bernstein [here]:

It quotes:

In fact, many of the records below were hidden from the public until this lawsuit forced their disclosure. Some of the records show critical decision steps, including outright errors that could have been corrected if they hadn’t been concealed. It’s clear that NIST’s non-transparency was intentional; some of the records are even marked “not for public distribution”.

The implication here is that some of the methods could have been updated with feedback on problems identified and that this was intentional. Dan (djb) then annexed the requests with his comments:

“I’ve incorporated the revisions and edits we discussed regarding the comments received from Donna and the NSA.” What was the NSA input?

Forwarded email from Moody says “By the way, our next meeting with the NSA PQC folks is Jan 26th.” This email approves disclosing NIST’s plans to NSA.

Then, in August 2022, Dan followed up with court action [here]:

The slowness of the response of NIST then led, in August 2022, to court action:

djb

Daniel J Bernstein (djb) was born in 1971. He is a USA/German citizen and a Personal Professor at Eindhoven University of Technology and a Research Professor at the University of Illinois at Chicago.

At the tender age of 24 — in 1995 — he, along with the Electronic Frontier Foundation — brought a case against the US Government related to the protection of free speech (Bernstein v. United States: here). It resulted in a ruling that software should be included in the First Amendment. A core contribution is that it has reduced government regulations around cryptography. It was a sign of the greatness that was to come from the amazing mind of Daniel. His viewpoint on reducing the strength of cryptography at the time defined:

“There are, fortunately, not many terrorists in the world. But there are many criminals exploiting Internet vulnerabilities for economic gain. They infiltrate computers and steal whatever secrets they can find, from individual credit-card numbers to corporate business plans. There are also quite a few vandals causing trouble just for fun.”

Since then few others have done so much for the cause of privacy, including creating the Sala20 [link] stream cipher in 2005, and then with ChaCha20 [link] and Poly1305 in 2008. Many connections in TLS now use ChaCha20, rather than AES, as it is faster — over three times after than AES — and has a lower computing requirement. His love of using dance names also comes to the fore with Rumba [here].

It is not just in symmetric key encryption that he has contributed to, he has made significant contributions to public key encryption. In 2005, he defined the Curve 25519 elliptic curve, and which is now a fairly standard way of defining elliptic curves. For signatures, he then defined Ed25519 and the resultant version of a new EdDSA signature (and which is now included in OpenSSH). The Tor protocol, for example, uses Curve 25519 for its key exchange for each of the nodes involved in a secure route.

In 2015, Daniel defined the methods that the NSA may have used to compromise the NIST-defined elliptic curves [paper]:

And 2005, it was Daniel again who introduced a new type of attack [here]:

And ChaCha20 continues on the course of its domination of TLS with XChaCha [here]:

One of the coolest things is that Daniel runs a domain name https://cr.yp.to/.

$ whois cr.yp.to
% IANA WHOIS server
% for more information on IANA, visit http://www.iana.org
% This query returned 1 objectrefer: whois.tonic.todomain: TOorganisation: Government of the Kingdom of Tonga
organisation: H.R.H. Crown Prince Tupouto’a
organisation: c/o Consulate of Tonga
address: 1350 Bayshore Hwy Suite 610
address: Burlingame CA 94010
address: United States

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 seam of information for the detection and investigation of crime. The Tor network has long been a target of defense 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 that search engines will not be able to find the content on them. This is the closed model in creating a Web that 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 every hop, the chances to tracing the original source becomes reduced. 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 accessing 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 has 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 its 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 coordinate 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 (mod p)

and Bob’s public key becomes:

B=9 b (mod p)

They exchange their values, and Alice multiplies 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=9ab (mod p)

So here is a basic Go program to implement:

package mainimport (
"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):  fa10936fe8e7652a9504cf0970bf46dee8c94593ebd87f35a13dd4e1f4edd1acAlice Public key point (x co-ord):  901737441b60c4226be178a93839a192441cb3d0bf1321f9c95dd0831cebe93eBob Private key (b):    66f8df8f45f470c3a05826408de763f781c6aa5b61d0e5e040141acdd0e6e1e0Bob Public key point (x co-ord):    b05ea9404fea0c1c16640d96eec59c5412b8e07d4feac9d5a25dc458d0dae238Shared key (Alice): 9a57c1bef48ae603466b34ba61c281ab93b0171e3e44a44e317427a46285ec71Shared key (Bob):   9a57c1bef48ae603466b34ba61c281ab93b0171e3e44a44e317427a46285ec71

Edwards 25519 elliptic curve

The Edwards 25519 elliptic curve is moving towards being the curve of choice in many applications for public key encryption and for key exchange. Its definition is:

−x^2 + y^2 = 1 − (121665/121666) * x^2 * y^2

When we use public key encryption, we create a secret key of x, and then take a base point on the curve (B). Our public key (B) then becomes:

X = xB

The value of x is a scalar, and B is an x point on the curve. Each of the calculations are done within a finite field, and defined by a prime number:

q = 2²⁵⁵-19

The following is a sample run of generating two secret values (x and y), and three public values (X, Y and R) [here]:

X=xB and Y=yB and R=xB+yB
x=d91cf8c3dfc7c2b8f85220e88078617a680a9305bf1cd4479773423b6641ef04, B=5866666666666666666666666666666666666666666666666666666666666666, X=2b6691aafccb1957c4e0599a05345e33477a50f0e90e76907a3d260ed6fb5996, y=41806461e988fd866c24303a869b1c9c502be96aabd5846f99cc72ac6fdbf003, Y=ab4458a44bf14c02c1c8e54821874df9ff7c659484d4187d128b39a616c87eee, R=dfd96cdecc9fcd17f855b9ad8e8577893491eaed17a95c5894927e084d112a31X=x*B
We need to prove that we known the discrete log of X
Proof:
00000000  ed 23 bc a3 a5 07 a7 79  7c bc ff 36 2f e4 72 66  |.#.....y|..6/.rf|
00000010  03 65 b8 ad 7b 56 61 55  38 57 83 75 0b 87 e1 4d  |.e..{VaU8W.u...M|
00000020  89 b9 09 19 f3 b9 a4 65  3c d9 e3 9f 84 b3 13 3b  |.......e.......;|
00000030  89 58 4f f9 df be 22 67  0a eb 7f 70 a8 7d f1 0a  |.XO..."g...p.}..|
-- Proof verified.R=x*B+y*B
Proof:
00000000  07 30 df 5d 3b 6a 24 41  81 44 81 65 54 ef b9 3c  |.0.];j$A.D.eT...|
00000010  88 d6 82 56 76 98 79 34  5e 54 34 a2 7b ae 43 d1  |...Vv.y4^T4.{.C.|
00000020  31 af 5f dc fe ec aa a2  4a 4d 96 09 88 81 be dc  |1._.....JM......|
00000030  92 ab d3 ff 5b ba 75 2e  6e a0 2d 3c 86 a1 86 09  |....[.u.n.-.....|
00000040  88 cf 11 bf 25 7f 95 b9  9b 99 fe 08 3f 46 01 12  |....%.......?F..|
00000050  af 09 6c d0 be ac f8 d9  29 08 ca 03 1d 99 6a 05  |..l.....).....j.|
-- Proof verified.X=y*B
Proof:
00000000  fb 1f 44 72 8a 95 68 37  89 58 54 4e 01 fb 9f 5c  |..Dr..h7.XTN...\|
00000010  68 61 e0 64 52 ec f1 ae  ae 4f 12 96 30 2d ea 9f  |ha.dR....O..0-..|
00000020  43 40 af fd 57 a3 2a b8  31 a5 d5 82 d9 10 79 7d  |C...W.*.1.....y}|
00000030  74 08 15 3a 7e 12 28 9f  e4 18 f1 c2 8f bc 4e 08  |t..:~.(.......N.|
Proof failed to verify:  invalid proof: commit mismatch

We see the value of “5866666666666666666666666666666666666666666666666666666666666666” in hex for the base point. The prime number used is q=2²⁵⁵−19 and which is a decimal value of “57896044618658097711785492504343953926634992332820282019728792003956564819949”.

In SSH, we can generate an Edwards 25519 curve with:

ssh-keygen -o -a 100 -t ed25519 -f ~/.ssh/id_ed25519 -C “fred@home.com”

Conclusions

The debate around backdoors in cryptography, and in the usage of end-to-end encryption. It is one of the greatest debates of the 21st Century. Daniel has been on the side of those looking to strengthen our security and reduce the opportunities for cybercriminals.