Proof of Knowledge in GoWithin 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 does two valid proofs and one invalid one. |
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/v3" "go.dedis.ch/kyber/v3/group/edwards25519" "go.dedis.ch/kyber/v3/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 and Y=yB and R=xB+yB\n") fmt.Printf("x=%s, B=%s, X=%s, y=%s, Y=%s, R=%s\n\n",x,B,X,y,Y,R) // X = xB pred := proof.Rep("X", "x", "B") fmt.Println(pred.String()) sval := map[string]kyber.Scalar{"x": x} pval := map[string]kyber.Point{"B": B, "X": X} 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") pred = proof.Rep("R", "x", "B","y", "B") fmt.Println(pred.String()) sval = map[string]kyber.Scalar{"x": x,"y": y} pval = map[string]kyber.Point{"B": B, "R": R} prover = pred.Prover(suite, sval, pval, nil) proof_, _ = proof.HashProve(suite, "TEST", prover) fmt.Print("Proof:\n" + hex.Dump(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") // pred = proof.Rep("Y", "y", "B") - Correct // This test will fail as we try to prove X=yB pred = proof.Rep("X", "y", "B") - Incorrect fmt.Println(pred.String()) sval = map[string]kyber.Scalar{"y": y} pval = map[string]kyber.Point{"B": B, "Y": Y} prover = pred.Prover(suite, sval, pval, nil) proof_, _ = proof.HashProve(suite, "TEST", prover) fmt.Print("Proof:\n" + hex.Dump(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.") }
The following is a sample run:
X=xB and Y=yB and R=xB+yB x=6f3632050865e77afdb974d58b357bce3feb94a0056380687c3c32b070c03f05, B=5866666666666666666666666666666666666666666666666666666666666666, X=f51db694db6a19ffe9970251f8f909fe571b4be79cf84421ee388812922f0540, y=b5b295dcc4c49ee7798ab2513ae3b01711a3d875cccd694f3ca593db0731d606, Y=a97c6ec8de585b34ce837f009ce5e999225accd50b8a95cb9d01c8a287a3de8b, R=4acfc0b4a6afc7698b3ccd74a358cc25d051e903fbe60e64ab8fa5ec97d99383 X=x*B We need to prove that we known the discrete log of X Proof: 00000000 10 50 30 e2 ff d1 eb e9 c3 a8 55 1d 97 c0 1f 65 |.P0.......U....e| 00000010 a0 07 bc 13 84 55 b6 2a 0e 56 bc f5 04 be 10 3d |.....U.*.V.....=| 00000020 68 bc 1a 15 b3 0b 94 e0 2e eb 5b 09 b4 05 86 c4 |h.........[.....| 00000030 aa 64 3c f4 b6 5a 09 e3 72 fd 41 83 34 5d db 03 |.d<..Z..r.A.4]..| -- Proof verified. R=x*B+y*B Proof: 00000000 33 bb b9 a4 96 ea 46 15 b6 8c c5 7d 4a 76 fd 9c |3.....F....}Jv..| 00000010 1b fd 13 2d a5 0e b8 05 f5 ad c1 be c0 5a ce 64 |...-.........Z.d| 00000020 7d bc de 3a eb d7 47 7b 2e e2 5c c9 cb a2 0a fa |}..:..G{..\.....| 00000030 40 8b 8f e2 82 ea 7a d6 81 bb 87 5c b4 bf 68 00 |@.....z....\..h.| 00000040 a0 f5 e1 0e 63 ae bf ec ce b0 87 26 9a c6 59 29 |....c......&..Y)| 00000050 10 f6 6f 46 7b 2e 6a da 3f 9e be c3 70 ec 01 00 |..oF{.j.?...p...| -- Proof verified. Y=y*B Proof: 00000000 27 b9 0c d3 59 95 19 00 62 cc e4 0e 34 c0 49 f6 |'...Y...b...4.I.| 00000010 14 5e bb 57 09 58 d7 bf f8 0a e7 7d 40 d9 1c ac |.^.W.X.....}@...| 00000020 ba 83 2e c6 d8 e2 8a cf 06 0a de 91 52 10 1a df |............R...| 00000030 14 58 cb 0f e6 ca 9f bd b7 26 60 c3 ae 50 e7 00 |.X.......&`..P..| -- Proof verified.
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.