## Proof of Knowledge in Go[Back] 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 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" "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 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("X", "y", "B") fmt.Println(pred.String()) sval = map[string]kyber.Scalar{"y": y} pval = map[string]kyber.Point{"B": B, "X": X} 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=d91cf8c3dfc7c2b8f85220e88078617a680a9305bf1cd4479773423b6641ef04, B=5866666666666666666666666666666666666666666666666666666666666666, X=2b6691aafccb1957c4e0599a05345e33477a50f0e90e76907a3d260ed6fb5996, y=41806461e988fd866c24303a869b1c9c502be96aabd5846f99cc72ac6fdbf003, Y=ab4458a44bf14c02c1c8e54821874df9ff7c659484d4187d128b39a616c87eee, R=dfd96cdecc9fcd17f855b9ad8e8577893491eaed17a95c5894927e084d112a31 X=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" 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.