Proof of Knowledge in Go (Logical)Within proof of knowledge, Peggy (the prover) must verify to Victor (the verifier) that she can solve a difficult problem. We must then have: An honest prover who can verify themselves to the verifier (completeness); A high probability that prover cannot cheat, and thus guess the solution (soundness); The prover cannot guess the secret from the proof (zero knowledge, witness hiding and minimum-disclosure). A standard proof in discrete logs, is to show that Peggy still knows the value of \(x\) given that the prover knows (\(X\)) and where \(q\) is a prime number: \(X= g^x \pmod q\). This page uses predicates of "X=x*B && Y=y*B" (which is true) and "X=x*B && Y=x*B" (which is false). |
Theory
Within proof of knowledge, Peggy (the prover) must verify to Victor (the verifier) that she can solve a difficult problem. we must then have- An honest prover who can verify themselves to the verifier (completeness).
- A high probability that prover cannot cheat, and thus guess the solution (soundness).
- The prover cannot guess the secret from the proof (zero knowledge, witness hiding and minimum-disclosure).
A standard proof in discrete logs, is to show that Peggy still knows the value of \(x\) given that the prover knows (\(X\)) and where \(q\) is a prime number:
\(X= g^x \pmod q\)
Coding
The following [taken from here]. In this case we will create:
\(X= xB\)
\(Y= yB\)
\(R= xB + yB\)
and where \(B\) is a base point on the elliptic curve, and \(x\) and \(y\) are secrets.
package main import ( "fmt" "go.dedis.ch/kyber" "go.dedis.ch/kyber/group/edwards25519" "go.dedis.ch/kyber/proof" "encoding/hex" ) func main() { suite := edwards25519.NewBlakeSHA256Ed25519() rand := suite.RandomStream() x := suite.Scalar().Pick(rand) y := suite.Scalar().Pick(rand) B := suite.Point().Base() X := suite.Point().Mul(x, nil) Y := suite.Point().Mul(y, nil) R := suite.Point().Add(X, Y) fmt.Printf("X=xB, Y=yB and R=xB+yB\n") fmt.Printf("B=%s, x=%s, X=%s, y=%s, Y=%s, R=%s\n\n",B,x,X,y,Y,R) sval := map[string]kyber.Scalar{"x": x,"y":y} pval := map[string]kyber.Point{"B": B, "X": X, "Y": Y} // X = xB pred1 := proof.Rep("X","x","B") pred2 := proof.Rep("Y", "y", "B") pred := proof.And(pred1, pred2) fmt.Println(pred.String()) prover := pred.Prover(suite, sval, pval, nil) proof_, _ := proof.HashProve(suite, "TEST", prover) fmt.Printf("We need to prove that we known the discrete log of X\n") fmt.Print("Proof:\n" + hex.Dump(proof_)) // Verify this knowledge proof. verifier := pred.Verifier(suite, pval) err := proof.HashVerify(suite, "TEST", verifier, proof_) if err != nil { fmt.Println("Proof failed to verify: ", err) return } fmt.Println("-- Proof verified.\n") // X = xB pred1 = proof.Rep("X","x","B") pred2 = proof.Rep("Y", "x", "B") pred = proof.And(pred1, pred2) fmt.Println(pred.String()) prover = pred.Prover(suite, sval, pval, nil) proof_, _= proof.HashProve(suite, "TEST", prover) fmt.Printf("We need to prove that we known the discrete log of X\n") fmt.Print("Proof:\n" + hex.Dump(proof_)) // Verify this knowledge proof. verifier = pred.Verifier(suite, pval) err = proof.HashVerify(suite, "TEST", verifier, proof_) if err != nil { fmt.Println("Proof failed to verify: ", err) return } fmt.Println("-- Proof verified.\n") }
The following is a sample run:
X=xB, Y=yB and R=xB+yB B=5866666666666666666666666666666666666666666666666666666666666666, x=2b2b55e63072a70de05e93a4bb7aa4157566e78fce642f89a5919a9f147e440e, X=681fd35655e161a0d2e8fe97d2dd14763d4f5a70ff32dfd37adfe38a010f9eae, y=f8424eaeffa9d7b6e009e01c7c0730ec0702cb25576b2f7e254f10d060175108, Y=8f92691995c27fc50f89bc7df5ea3c5807c871b502bafcddb71ba2761a7e7eba, R=e3298170d7178d953db51012200e77e4c3b572d9389f91c7aeb31e297dfc653e X=x*B && Y=y*B We need to prove that we known the discrete log of X Proof: 00000000 01 e7 d4 c9 1e 9b 53 22 e8 fb f0 75 bb f7 1c 07 |......S"...u....| 00000010 83 23 33 6e f2 5e 62 56 21 39 65 09 1a 2f 42 28 |.#3n.^bV!9e../B(| 00000020 01 9b 45 7f 52 9f 69 0c b3 b3 76 fb 6b 00 a3 15 |..E.R.i...v.k...| 00000030 20 5b 8a 88 da e2 a2 dd 3c f7 2f c8 7c ec 87 23 | [......../.|..#| 00000040 25 90 14 c9 59 1f 57 2b 7e d4 9c a4 cc ec 6d 2a |%...Y.W+~.....m*| 00000050 bd 29 b6 86 2a 5c b0 a6 da e0 50 dc b8 88 78 0e |.)..*\....P...x.| 00000060 f7 54 c0 37 0e fb 2f 67 5e ad ef b3 ea c2 56 f5 |.T.7../g^.....V.| 00000070 57 55 ca 49 38 f8 23 08 fc 28 2e b3 2c 30 a7 0a |WU.I8.#..(..,0..| -- Proof verified. X=x*B && Y=x*B We need to prove that we known the discrete log of X Proof: 00000000 c2 eb 00 82 0d 20 57 b7 a5 18 09 43 c8 36 98 05 |..... W....C.6..| 00000010 97 06 e5 81 50 42 cd c2 b7 d3 dc ba dd 9a 96 87 |....PB..........| 00000020 c2 eb 00 82 0d 20 57 b7 a5 18 09 43 c8 36 98 05 |..... W....C.6..| 00000030 97 06 e5 81 50 42 cd c2 b7 d3 dc ba dd 9a 96 87 |....PB..........| 00000040 04 9b d6 97 2e 81 64 b6 1f 3c e5 be 79 f1 a9 ea |......d.....y...| 00000050 77 64 10 96 f3 72 b5 22 2d 12 f5 92 61 96 27 0f |wd...r."-...a.'.| Proof failed to verify: invalid proof: commit mismatch
We see the value of "5866666666666666666666666666666666666666666666666666666666666666" for the base point. This is the base point for the Edwards Curve 25519 (\(−x^2 + y^2 = 1 − (121665/121666) \times x^2 \times y^2\)). The prime number used is \(q = 2^{255} - 19\) and which is "57896044618658097711785492504343953926634992332820282019728792003956564819949".
Outline
In the future, Cyber Security professionals will truly laugh when they look back at the things that we have done over the past 40 years. They will exist in a distributed world and one which will respect the rights of privacy and consent. The Wild West of Data, where anyone could do anything they wanted with personal data, will have gone, and the rights of privacy and consent will be fully respected.
Our blind over centralisation of our data infrastructures and resources will also be gone, and be replaced by a truly distributed infrastructure which respects the ownership and the access rights for every single data element.
For us, now, we continue to do things that are plainly wrong, just because it is the way that we have always done things since the start of the Internet. We are basically fixing the leaks in our dam as we go, and never really fixing it. And we educate in the same old way we have done for over 40 years, without caring that we need to build a better world. Our currently security problems are caused mainly because we have built an infrastructure which is severely flawed.
Why? Because we often don’t want to change something that is working. That has always been our attitude to networks and the Internet. If it’s working, just leave it, as we’ll break it! But it’s broken, and it needs fixed.
So why are we still hashing and salting passwords? What a crazy system for storing something so sensitive. With the Cloud and GPU crackers, the challenge is then just a matter to having enough computing resource to find the match. With crackers now working at rates of terahashes per second, and where even long-term encryption keys can be broken, we have a major problem that we are not solving.
The world is changing for the better, though. Blockchain methods allow for the rights of citizens to be respected through code, and not through a cumbersome legal system, which benefits those in power and who have wealth. Protocols that we have lived with for years, such as TLS 1.2 and WPA-2, are not being pushed into the 21st Century, and in the ageing-out of their flawed ways. TLS 1.3 and WPA-3 are just an acknowledgement that the world has moved on from the 1980s, and we need to improve, otherwise our existing Internet will unravel itself as it falls to match its expectations of building new worlds.
What’s the problem?
So let’s define the problem we want to solve. Basically, can I prove my password, that me and my Cloud service provider have agreed, but for me not to actually tell them what it is? Most of the time, though, I have to give my service provider my password, and then they hash it, and check against the hash that they have. We have thus become sheep, where we blindly fall down the same trap, again and again.
And so we have Peggy (the Prover) sending her password to Victor (the Verifier), and who will take the salt we have on the password, and then take Peggy’s password, and compute a hashed value for it. If the hashed value is the same as the hash stored on his system, then Victor has verified Peggy. How can something so simple lead to billions of passwords being released?
What a crazy system! Peggy is forced to give away her password every time, and Victor now has stored the salt with the hashed value, so that Eve can come along and try lots of possible passwords for Peggy, and then discover her password. Eve might then go and try other systems that Peggy uses, and crack them. Victor might not even know that Eve is doing this, as she can take all the hashed password off-line, and she can continually try possible passwords.
It is complete rubbish, and not fit for a world where Peggy is the true owner of her data and identity, and that Victor has no rights to know her sensitive information (like her password)! It is a system which worked in the 1980s, when we had computers that ran with clock speeds of 16MHz and which had 16MBs of memory, but doesn’t work in a modern era building with the computation power of The Cloud. The hard problem of cracking hashes in the 1980s, is certainly not so difficult in a era of almost endless computing power.
Enter Fiat-Shamir
What we need is a way that Peggy can generate her own password, and then register something with Victor so that he can generate a challenge to her to prove that she still knows it. This sounds, oh so simple, but we blindly still go down the same route of giving away our passwords for the systems that we build. For this we need Zero Knowledge Proofs (ZKPs), and we make sure that the registration process done in a way that has high levels of trust.
Now Peggy can generate an initial registration value, and which Victor can store. We will make sure that it is almost impossible to ever determine her original password from the registration value we use. Now, when Peggy wants to log in to Victor’s system, he sends her a random challenge, and she must produce the right answer to show that she still knows her password. If she return the right answer, Victor lets her log in. Every time Peggy wants to log in Victor sends her a different head
There are many ways to solve the problem, but one of the most widely used methods is the “non-interactive random oracle access” for zero-knowledge proofs. It is defined as the Fiat-Shamir heuristic [1]. It uses discrete logarithms to create a difficult puzzle for Eve, and an easy one for Peggy to prove, and for Victor to verify. Eve, with her array of GPU crackers, will have an extremely large electricity bill if we make the puzzle so difficult that she’ll be have to consume masses of computing power, just to solve one element of the puzzle.
Now let’s start. First Victor and Peggy agree on a generator value (g) and a prime number (p).
1. First Peggy decides on her password (pass), and generates a hash of it, and then converts this to an integer value (x).
x = Hash(pass)
\(y=g^x\)
and to make things more difficult and to allow us to create the puzzle we need to pick a prime number (p) and make the operation:
\(y=g^x \pmod p\)
Peggy sends Victor the value of y, and he stores it. In code this looks like:
x = int(hashlib.md5(pass).hexdigest()[:8], 16) % n y= g**x % n
2. Now Peggy wants to log on, so she send generates a new random number and sends Victor has value of t:
\(t=g^v\)
3. Victor thens sends her a challenge ( c ) and which is a random value that he has now used before.
4. Peggy generates another random value (v), and now takes the c value, and computes:
\(r=v−c \times t\)
She then sends Victor the value of r that she has computed.
5. He then computes:
\(val=g^c y^c\)
and checks if the result equals t equals val, and if they are the same, Peggy has proven her identity, and Eve is left scratching her head.
Note that the operations are conducted with (mod p) and it works because of the magic is logarithms:
\(g^r \times y^c = g^{v-cx} \times {g^x}^c = g^{v-cx+cx} = g^v\)
For a password reset, Peggy just contacts Victor and does some multi-factor authentication that she did when she registered her secret, and then registers a new secret.