The Papers That Changed Cybersecurity, And Still Do

The Papers That Changed Cybersecurity, And Still Do

Okay, the RSA and Diffie-Hellman papers fundamentally changed the world of cybersecurity and brought us confidentially and assurance aspects. But cybersecurity should also be about the privacy of data and only giving away enough information that is necessary for a task to be performed. And, so, there is one research paper that stands head over heals above others in this respect, and it defined the Fiat-Shamir method:

And, also in Schnorr’s paper on signatures:

and the magical bit of the Schnorr paper is this:

And where we have “y:=r+se”. This little operation then allows us to create a proof of knowledge. These days, we do not use discrete logarithms for our implement, so let’s implement this with elliptic curve methods.

ZKPs

With Zero-Knowledge Proofs (ZKPs), I can prove I have knowledge of my data, without revealing it. This might relate to my password, my face biometrics, or even any digital data that I want to keep secret. So, let’s take an example of doing with the Schnorr methods and which implement a Fiat-Shamir approach. Our approach will be for Bob to register a secret (such as a password), and then create his own proof whenever required (such as logging into a system). Alice will then prove that he knows the secret, without Bob ever revealing it to her. As Bob generates his own proof, we define this as a Non-Interactive ZKP (NI-ZKP).

For the demo, I will use the Kryptology library for this and prove the knowledge of a text string. The demo is here:

https://asecuritysite.com/kryptology/ecc_zkp?b0=Testing%20123&a0=K256

Registering the secret

If we have a secret X, Bob first takes a hash of this:

X=Hash(x)

Bob then computes a statement (Y) of:

Y=X.G

and where G is the base point on the curve. This statement value can be registered with Alice, and Bob can now prove it with (C,S).

Creating the proof

To create a proof, Bob generates a random value (k) and generates a random point:

R=k.G

Next Bob generates a value of C by taking a hash of the following byte values:

C=H(X||G||Y||R)

S=k+x.G

Bob now passes the statement (Y), C and S to Alice as a proof of the knowledge of x.

Verifying

First Alice computes:

G_S=S.G

and next:

X_C=Y×(−C)

and then recovers R from:

R=G_S+X_C

Alice now can compute:

C′=H(X||G||Y||R)

and which check this against the C. If they are the same, the proof has been verified. This works because:

R=G_S+X_C=S.G+Y×(−C)=(k+x.C).G−k.G.C=k.G

Coding

The outline code is [here]:

package main

import (
 "crypto/rand"
 "fmt"
 "math"
 "os"

 "github.com/coinbase/kryptology/pkg/core/curves"
 "github.com/coinbase/kryptology/pkg/zkp/schnorr"
 "golang.org/x/crypto/sha3"
)

func powInt(x, y int) int {
 return int(math.Pow(float64(x), float64(y)))
}
func main() {

 curve := curves.K256()
 message := "Test"
 name := "K256"

 argCount := len(os.Args[1:])
 if argCount > 0 {
  name = os.Args[1]
 }
 if argCount > 1 {
  message = os.Args[2]
 }
 if name == "K256" {
  curve = curves.K256()
 } else if name == "P256" {
  curve = curves.P256()
 } 

 msgHash := sha3.New256().Sum([]byte(message))

 prover := schnorr.NewProver(curve, nil, msgHash)

 random_seed := curve.Scalar.Random(rand.Reader)

 proof, _ := prover.Prove(random_seed)

 fmt.Printf("Message to prove: %s\n", message)
 fmt.Printf("Curve: %s\n", curve.Name)
 fmt.Printf("\nProof Statement: %x\n", proof.Statement.ToAffineCompressed())
 fmt.Printf("Proof C: %x\n", proof.C.Bytes())
 fmt.Printf("Proof S: %x\n", proof.S.Bytes())

 err := schnorr.Verify(proof, curve, nil, msgHash)

 if err == nil {
  fmt.Printf("ZKP has been proven")
 } else {
  fmt.Printf("ZKP has NOT been proven")
 }

 fmt.Printf("\n\n== Now trying the wrong message ==")
 message = "Not correct!"
 msgHash = sha3.New256().Sum([]byte(message))
 proof, _ = prover.Prove(random_seed)

 err = schnorr.Verify(proof, curve, nil, msgHash)

 if err == nil {
  fmt.Printf("\nIncorrect hash is proven with incrrect message (bad) ")
 } else {
  fmt.Printf("\nZKP has NOT been proven with incorrect message (good)")
 }

}

For the P256 curve and a message of “Test 123” we get [here]:

Message to prove: Test 123
Curve: P-256Proof Statement: 038e1abb750975191287dcf7df8d9026cf78ea49763c50d395fe57bc168d973df9
Proof C: cecc95d5efaabeb9f10d924f14696551ba2d53b10c39764cc2bcdc777f903869
Proof S: 5bb571b6e55242b4a5110d164d8785c3677be6b48c2006c50c8317a367acbb8b
ZKP has been proven

Note that the Proof statement is an elliptic curve point in a compressed format. We with we compress the point, by only storing the x-axis value, and whether the y-axis point is odd or even. A compressed point that starts with a “03” is an odd value or “02” for an even value. For a compressed point, we do not need to store the y-axis point, as we can derive this from the x-axis point. A “04” identifies an uncompressed point for sepc256k1 and P256. The values of C and S are scalar values.

Conclusions

So, just to recap. Bob has a secret (x) and registers a statement (Y). Whenever required, Bob then creates his own proof for it and sends C and S to Alice. Alice uses Y, C and S, and proves that Bob still knows x. Magic!

If you want to see a magical transformation with this method, try here:

https://asecuritysite.com/bulletproof/aos

References

[1] Fiat, A., & Shamir, A. (1986, August). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (pp. 186–194). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Schnorr, C. P. (1991). Efficient signature generation by smart cards. Journal of cryptology, 4, 161–174.