Why Do We Still Give Away Our Secrets?

Why Do We Still Give Away Our Secrets?

Building a Zero-Knowledge Proof World With Elliptic Curves and Golang

The demo of the code is defined [here].

We will in a world where we continually give away our secret. We blinding send our passwords to systems, and which then create a hash of them. Unfortunately, these days, it is not too difficult to determine the password which caused the hash. The days of rainbow tables are gone too, as most passwords are salted for their hash. But the power of Hashcat and GPUs, makes brute force the natural choice in cracking passwords.

So there must be a better way!

And the better way is not to give away your sensitive information. Why not register a version of your secret, and then just prove that you still know it. For this, we turn to Fiat-Shamir method. One way of implementing it is in discrete logarithms [here], but we can use something even more powerful … elliptic curve cryptography. First Bob and Alice agree on two points on their selected elliptic curve (G and H). Next Bob, takes his secret and hashes it to produce a secret value (x). He then computes xG and xH (which is the points G and H added x times), and sends these to Alice. Alice then registers them:

Next Alice sends a random challenge value ( c ) and sends this to Bob. Bob then generates his own random value (v), and computes r:

r = v — cx

This is done as an elliptic curve multiply (cx) and subtract (v-cx). He also computes vG and vH, and sends r, vG, and vH back to Alice. Alice then checks that:

vG is equal to rG + c(xG)

and

vH is equal to rH + c(xH)

If they are the same, Bob has proven his password!

In Go we can convert our password (m) into a value by taking a hash of it (SHA-256):

message := []byte(m)
    scal := sha256.Sum256(message[:])

x := suite.Scalar().SetBytes(scal[:32])

Next we can generate our elliptic curve points (G and H):

G := suite.Point().Pick(rng)
H := suite.Point().Pick(rng)

The values passed to Alice can be generated with:

xG := suite.Point().Mul(x, G)
xH := suite.Point().Mul(x, H)

Alice can then generate a challenge (c ) with:

c := suite.Scalar().Pick(rng)

Bob can then compute r, rG, and rH with:

r := suite.Scalar()
r.Mul(x, c).Sub(v, r)

rG := suite.Point().Mul(r, G)
rH := suite.Point().Mul(r, H)

Alice then checks:

cxG := suite.Point().Mul(c, xG)
    cxH := suite.Point().Mul(c, xH)
    a := suite.Point().Add(rG, cxG)
    b := suite.Point().Add(rH, cxH)

fmt.Printf("Alice sends challenge:\n c: %s\n\n",c)
    fmt.Printf("Bob computes:\n v:\t%s\n r:\t%s\n\n",v,r)

if !(vG.Equal(a) && vH.Equal(b)) {
        fmt.Printf("Incorrect proof!")
    } else {
        fmt.Printf("Proof correct")
    }

Here is the Go code to implement this [demo]:

package main

import (

    "fmt"
    "go.dedis.ch/kyber/group/edwards25519"
    "go.dedis.ch/kyber/util/random"
    "os"
    "crypto/sha256"

)
var rng = random.New()

func main() {
    suite := edwards25519.NewBlakeSHA256Ed25519()

    m:="Hello"

    argCount := len(os.Args[1:])

        if (argCount>0) {m= string(os.Args[1])}

    message := []byte(m)
    scal := sha256.Sum256(message[:])

    x := suite.Scalar().SetBytes(scal[:32])

    G := suite.Point().Pick(rng)
    H := suite.Point().Pick(rng)

    fmt.Printf("Bob and Alice agree:\n G:\t%s\n H:\t%s\n\n",G,H)

    fmt.Printf("Bob's Password:\t%s\n",m)
    fmt.Printf("Bob's Secret (x):\t%s\n\n",x)

    xG := suite.Point().Mul(x, G)
    xH := suite.Point().Mul(x, H)

    fmt.Printf("Bob sends these values:\n xG:\t%s\n xH\t%s\n\n",xG,xH)

    v := suite.Scalar().Pick(suite.RandomStream())
    vG := suite.Point().Mul(v, G)
    vH := suite.Point().Mul(v, H)

    h := suite.Hash()
    cb := h.Sum(nil)

    c := suite.Scalar().Pick(suite.XOF(cb))

    // Response 
    r := suite.Scalar()
    r.Mul(x, c).Sub(v, r)

    rG := suite.Point().Mul(r, G)
    rH := suite.Point().Mul(r, H)
    cxG := suite.Point().Mul(c, xG)
    cxH := suite.Point().Mul(c, xH)
    a := suite.Point().Add(rG, cxG)
    b := suite.Point().Add(rH, cxH)

    fmt.Printf("Alice sends challenge:\n c: %s\n\n",c)
    fmt.Printf("Bob computes:\n v:\t%s\n r:\t%s\n\n",v,r)

    if !(vG.Equal(a) && vH.Equal(b)) {
        fmt.Printf("Incorrect proof!")
    } else {
        fmt.Printf("Proof correct")
    }

}

A sample run is [demo]:

Bob and Alice agree:
 G: 3fd96d7b139e8805e3d94f1e04cd637aae7b9c2565a708464b62449cbbfb07fa
 H: f7bf1938a30b2a84e745cbe96b25854be4a62ea69b936b8071bad412c89118f5

Bob's Password: qwerty
Bob's Secret (x):   49f9c587f98c1e5840ee76f205437cf9a582b27168c0ea744b2cf58ee0233705

Bob sends these values:
 xG:    b21b0fe0af6c874300fd3dcd95b6c7a2d98ef9014632661a9f86e16e134cbc0d
 xH 6d009dacea721114976c5da13fbe88afeaac8ff204dfdf73b6a5c4f9b1bb651e

Alice sends challenge:
 c: 7592f5abb87a6797e6f63eb0a571a51a0197a258d25002079acd82e5dc9c990e

Bob computes:
 v: 18025bbd0c975f8762a263603ab1c1887884e10a748a65b2f2a428a90994220f
 r: af90b47cf39b03966bd5003de377147c0103e4d22b424740a23dcd046057300e

Proof correct

In a following article, I will make this non-interactive, and where Bob does not have to send Alice a challenge.