Skip to content

Instantly share code, notes, and snippets.

@Zenithar

Zenithar/zkpauth.go

Last active September 16, 2023 17:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Zenithar/4d891a3bef9b0dc46358b55ea9e6bd3d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Zenithar/4d891a3bef9b0dc46358b55ea9e6bd3d to your computer and use it in GitHub Desktop.
Download ZIP
SMP / ZKP based secure comparison for authentication purpose.
Raw
output.txt
# Zero Knowledge based authentication
Based on
* https://www.cossacklabs.com/blog/introducing_secure_comparator/
* https://www.cossacklabs.com/files/secure-comparator-paper-rev12.pdf
```
{"time":"2023-09-16T19:23:25.663348882+02:00","level":"INFO","msg":"C -> S: Session boostrap"}
{"time":"2023-09-16T19:23:25.664432655+02:00","level":"INFO","msg":"S -> C: Session public keys"}
00000000 69 c4 9d 53 f7 ac e9 13 5a 7b 1f af a9 80 5c 2a |i..S....Z{....\*|
00000010 87 f4 94 e0 a3 5a 88 87 0a ac 86 d2 d5 ab de 48 |.....Z.........H|
00000020 60 a4 b4 bb 99 30 34 e3 04 d7 31 38 7a 1b 68 2e |`....04...18z.h.|
00000030 38 f6 c0 40 0e 6a 18 54 ad f7 41 83 27 d2 97 5e |[email protected].'..^|
00000040 fe 03 19 6b 16 02 e8 a1 4a 5a 35 f6 80 35 08 a1 |...k....JZ5..5..|
00000050 b3 4f fb 87 93 38 ac ca 15 a3 44 d3 7c 92 fc 09 |.O...8....D.|...|
00000060 b7 b8 18 0e 53 e5 1f 61 30 0c bf 82 fb 0d 5d 20 |....S..a0.....] |
00000070 b5 dd 8f 15 e4 fa 52 c1 15 b7 5c 62 39 6d 0a 8c |......R...\b9m..|
00000080 ed df e3 b9 55 d6 a1 56 e7 18 2e a1 6c a5 bd 1c |....U..V....l...|
00000090 cd cf ab 54 0b ce be 73 e5 eb 24 43 51 f8 66 d5 |...T...s..$CQ.f.|
000000a0 e6 70 09 ce f4 31 54 47 1a e9 c4 c8 5d b8 92 33 |.p...1TG....]..3|
000000b0 71 98 ad 3e 65 d6 26 da 6d f0 40 ed 0a 67 2a 09 |q..>e.&[email protected]*.|
{"time":"2023-09-16T19:23:25.665291918+02:00","level":"INFO","msg":"C -> S: Client proof"}
00000000 64 58 ad 62 91 af 5a 45 c4 db bb bb 7d 7a 7f e4 |dX.b..ZE....}z..|
00000010 c9 f7 a9 ab 4d c7 62 83 09 24 cd 23 0a 93 16 74 |....M.b..$.#...t|
00000020 38 98 ec 56 b9 fc 84 55 30 7f 25 de e6 d5 0d 1b |8..V...U0.%.....|
00000030 28 65 bf b5 5b 06 ec 3b 5c 33 11 d8 f1 0c 4f 81 |(e..[..;\3....O.|
00000040 ed 21 9f f2 76 37 ec 91 26 89 9b 67 d3 8a dc 7c |.!..v7..&..g...||
00000050 b1 9b 88 5c e5 98 6f 1b b4 c8 1d ce f8 2a 45 0c |...\..o......*E.|
00000060 e1 f1 56 2b 9a ea df 14 af a2 94 f0 5e 54 af 7a |..V+........^T.z|
00000070 c3 56 f5 57 9e 0a 91 ef 24 79 be 02 7d 03 ec 24 |.V.W....$y..}..$|
00000080 fd 25 95 c3 dc 75 7c 1f 66 02 a6 e1 20 6a 36 79 |.%...u|.f... j6y|
00000090 f5 24 57 8c ac 2c a2 04 7f e0 50 89 28 33 91 42 |.$W..,....P.(3.B|
000000a0 50 6e 4a 46 e5 06 d9 dd af 03 fc ea f8 8e 73 ec |PnJF..........s.|
000000b0 6a 80 84 e2 6b 23 2f e8 ca e6 3d db bc 2b fb 07 |j...k#/...=..+..|
000000c0 dd b4 6a 8a 50 79 c6 2b e1 dd 0c 9e d4 08 67 68 |..j.Py.+......gh|
000000d0 ed a8 e2 70 cf e8 4d 22 fa a1 88 13 42 7e 64 32 |...p..M"....B~d2|
000000e0 97 df 19 bf 15 ad a5 f3 de 05 14 93 7b 27 bd e7 |............{'..|
000000f0 10 53 ca cf 80 79 37 95 ff df 24 5c 23 e1 85 03 |.S...y7...$\#...|
{"time":"2023-09-16T19:23:25.665662329+02:00","level":"INFO","msg":"S -> C: Session proof"}
00000000 ae 6b 6d 7f 0c c3 8b 74 42 9b fe cc 07 fa 33 88 |.km....tB.....3.|
00000010 8b dc aa 66 90 1e 45 c7 f2 88 e0 c2 c8 bb a7 c7 |...f..E.........|
00000020 a6 2f e8 bd 2a 4d 76 25 26 dc a3 ad 3e 4f f4 ab |./..*Mv%&...>O..|
00000030 99 ff 0f 80 77 9d 3e bb 4d 03 79 73 d7 ed 66 57 |....w.>.M.ys..fW|
00000040 44 40 ec fc ba 11 08 cd b3 a0 c1 a3 ec f0 20 d4 |D@............ .|
00000050 1a 61 40 41 a7 b2 9e 88 38 6f e2 56 58 a9 2d 18 |[email protected].|
{"time":"2023-09-16T19:23:25.665825205+02:00","level":"INFO","msg":"C -> S : Session proof validation"}
00000000 e6 12 de a2 bd 1c bd 59 af bd c7 eb 80 27 b7 97 |.......Y.....'..|
00000010 f8 0d db 9f 86 36 30 40 59 ab c2 15 fb d6 02 08 |.....60@Y.......|
{"time":"2023-09-16T19:23:25.66588808+02:00","level":"INFO","msg":"S: Client Authenticated?"}
```
Raw
zkpauth.go
package main
import (
"crypto/ed25519"
"crypto/rand"
"crypto/sha512"
"encoding/hex"
"errors"
"fmt"
"io"
"os"
"log/slog"
"filippo.io/edwards25519"
)
// https://www.cossacklabs.com/blog/introducing_secure_comparator/
// https://www.cossacklabs.com/files/secure-comparator-paper-rev12.pdf
type Server struct {
a2, a3 ed25519.PrivateKey
g2a, g3a ed25519.PublicKey
pA, qA, pB, qB *edwards25519.Point
}
func (p *Server) Bootstrap() ([]byte, error) {
// Generate a2, a3
var err error
p.g2a, p.a2, err = ed25519.GenerateKey(rand.Reader)
if err != nil {
return nil, fmt.Errorf("unable to generate ephemeral key pair: %w", err)
}
p.g3a, p.a3, err = ed25519.GenerateKey(rand.Reader)
if err != nil {
return nil, fmt.Errorf("unable to generate ephemeral key pair: %w", err)
}
var out []byte
out = append(out, p.g2a...)
out = append(out, ed25519.Sign(p.a2, p.g2a)...)
out = append(out, p.g3a...)
out = append(out, ed25519.Sign(p.a3, p.g3a)...)
return out, nil
}
func (p *Server) Prove(proof, secret []byte) ([]byte, error) {
// Ensure expected length
// g2b || g2b signature || g3b || g3b signature || Pb || Qb
if len(proof) < 2*(ed25519.PublicKeySize+ed25519.SignatureSize)+2*ed25519.PublicKeySize {
return nil, errors.New("message too short")
}
// Ensure valid signatures
var (
g2b = proof[:ed25519.PublicKeySize]
g2bSig = proof[ed25519.PublicKeySize : ed25519.PublicKeySize+ed25519.SignatureSize]
g3b = proof[ed25519.PublicKeySize+ed25519.SignatureSize : ed25519.PublicKeySize+ed25519.SignatureSize+ed25519.PublicKeySize]
g3bSig = proof[ed25519.PublicKeySize+ed25519.SignatureSize+ed25519.PublicKeySize : ed25519.PublicKeySize+ed25519.SignatureSize+ed25519.PublicKeySize+ed25519.SignatureSize]
pb = proof[2*(ed25519.PublicKeySize+ed25519.SignatureSize) : 2*(ed25519.PublicKeySize+ed25519.SignatureSize)+ed25519.PublicKeySize]
qb = proof[2*(ed25519.PublicKeySize+ed25519.SignatureSize)+ed25519.PublicKeySize : 2*(ed25519.PublicKeySize+ed25519.SignatureSize)+2*ed25519.PublicKeySize]
)
if !ed25519.Verify(ed25519.PublicKey(g2b), g2b, g2bSig) {
return nil, errors.New("invalid proof of possession")
}
if !ed25519.Verify(ed25519.PublicKey(g3b), g3b, g3bSig) {
return nil, errors.New("invalid proof of possession")
}
// Compute generator groups
a2, err := privateToScalar(p.a2)
if err != nil {
return nil, fmt.Errorf("unable to initialize a scalar from ephemeral key: %w", err)
}
g2bp, err := (&edwards25519.Point{}).SetBytes(g2b)
if err != nil {
return nil, fmt.Errorf("unable to initialize a point from ephemeral public key: %w", err)
}
G2 := (&edwards25519.Point{}).ScalarMult(a2, g2bp)
a3, err := privateToScalar(p.a3)
if err != nil {
return nil, fmt.Errorf("unable to initialize a scalar from ephemeral key: %w", err)
}
g3bp, err := (&edwards25519.Point{}).SetBytes(g3b)
if err != nil {
return nil, fmt.Errorf("unable to initialize a point from ephemeral public key: %w", err)
}
G3 := (&edwards25519.Point{}).ScalarMult(a3, g3bp)
var challenge [32]byte
if _, err := io.ReadFull(rand.Reader, challenge[:]); err != nil {
return nil, fmt.Errorf("unable to generate random challenge: %w", err)
}
s, err := edwards25519.NewScalar().SetBytesWithClamping(challenge[:])
if err != nil {
return nil, fmt.Errorf("unable to create a scalar from random challenge: %w", err)
}
// Compute secret
h := sha512.Sum512_256(secret)
x, err := edwards25519.NewScalar().SetBytesWithClamping(h[:])
if err != nil {
return nil, fmt.Errorf("unable to prepare secret as scalar: %w", err)
}
//
p.qB, err = (&edwards25519.Point{}).SetBytes(qb)
if err != nil {
return nil, fmt.Errorf("unable to prepare secret public key as point: %w", err)
}
p.pB, err = (&edwards25519.Point{}).SetBytes(pb)
if err != nil {
return nil, fmt.Errorf("unable to prepare secret public key as point: %w", err)
}
p.pA = (&edwards25519.Point{}).ScalarMult(s, G3)
p.qA = (&edwards25519.Point{}).VarTimeDoubleScalarBaseMult(x, G2, s)
Ra := (&edwards25519.Point{}).ScalarMult(a3, (&edwards25519.Point{}).Subtract(p.qA, p.qB))
var out []byte
out = append(out, p.pA.Bytes()...)
out = append(out, p.qA.Bytes()...)
out = append(out, Ra.Bytes()...)
return out, nil
}
func (p *Server) Verify(proof []byte) (bool, error) {
// Ensure expected length
// Rb
if len(proof) < ed25519.PublicKeySize {
return false, errors.New("message too short")
}
a3, err := privateToScalar(p.a3)
if err != nil {
return false, fmt.Errorf("unable to initialize a scalar from ephemeral key: %w", err)
}
Rb, _ := (&edwards25519.Point{}).SetBytes(proof)
Rab := (&edwards25519.Point{}).ScalarMult(a3, Rb)
if (&edwards25519.Point{}).Subtract(p.pA, p.pB).Equal(Rab) != 1 {
return false, errors.New("invalid proof")
}
return true, nil
}
type Client struct {
b2, b3 ed25519.PrivateKey
g2b, g3b ed25519.PublicKey
p, q *edwards25519.Point
}
func (v *Client) Proof(in, secret []byte) ([]byte, error) {
// Ensure expected length
// g2a || g2a signature || g3a || g3a signature
if len(in) < 2*(ed25519.PublicKeySize+ed25519.SignatureSize) {
return nil, errors.New("message too short")
}
// Ensure valid signatures
var (
g2a = in[:ed25519.PublicKeySize]
g2aSig = in[ed25519.PublicKeySize : ed25519.PublicKeySize+ed25519.SignatureSize]
g3a = in[ed25519.PublicKeySize+ed25519.SignatureSize : ed25519.PublicKeySize+ed25519.SignatureSize+ed25519.PublicKeySize]
g3aSig = in[ed25519.PublicKeySize+ed25519.SignatureSize+ed25519.PublicKeySize : ed25519.PublicKeySize+ed25519.SignatureSize+ed25519.PublicKeySize+ed25519.SignatureSize]
)
if !ed25519.Verify(ed25519.PublicKey(g2a), g2a, g2aSig) {
return nil, errors.New("invalid proof of possession")
}
if !ed25519.Verify(ed25519.PublicKey(g3a), g3a, g3aSig) {
return nil, errors.New("invalid proof of possession")
}
// Generate b2, b3
var err error
v.g2b, v.b2, err = ed25519.GenerateKey(rand.Reader)
if err != nil {
return nil, fmt.Errorf("unable to generate ephemeral key pair: %w", err)
}
v.g3b, v.b3, err = ed25519.GenerateKey(rand.Reader)
if err != nil {
return nil, fmt.Errorf("unable to generate ephemeral key pair: %w", err)
}
b2, err := privateToScalar(v.b2)
if err != nil {
return nil, fmt.Errorf("unable to initialize a scalar from ephemeral key: %w", err)
}
g2ap, _ := (&edwards25519.Point{}).SetBytes(g2a)
G2 := (&edwards25519.Point{}).ScalarMult(b2, g2ap)
b3, err := privateToScalar(v.b3)
if err != nil {
return nil, fmt.Errorf("unable to initialize a scalar from ephemeral key: %w", err)
}
g3ap, _ := (&edwards25519.Point{}).SetBytes(g3a)
G3 := (&edwards25519.Point{}).ScalarMult(b3, g3ap)
var challenge [32]byte
if _, err := io.ReadFull(rand.Reader, challenge[:]); err != nil {
return nil, fmt.Errorf("unable to generate random challenge: %w", err)
}
r, _ := edwards25519.NewScalar().SetBytesWithClamping(challenge[:])
// Compute secret
h := sha512.Sum512_256(secret)
y, err := edwards25519.NewScalar().SetBytesWithClamping(h[:])
if err != nil {
return nil, fmt.Errorf("unable to prepare secret as scalar: %w", err)
}
v.p = (&edwards25519.Point{}).ScalarMult(r, G3)
v.q = (&edwards25519.Point{}).VarTimeDoubleScalarBaseMult(y, G2, r)
var out []byte
out = append(out, v.g2b...)
out = append(out, ed25519.Sign(v.b2, v.g2b)...)
out = append(out, v.g3b...)
out = append(out, ed25519.Sign(v.b3, v.g3b)...)
out = append(out, v.p.Bytes()...)
out = append(out, v.q.Bytes()...)
return out, nil
}
func (v *Client) Verify(proof []byte) ([]byte, error) {
// Ensure expected length
// Pa || Qa || Ra
if len(proof) < 3*(ed25519.PublicKeySize) {
return nil, errors.New("message too short")
}
// Ensure valid signatures
var (
pa = proof[:ed25519.PublicKeySize]
qa = proof[ed25519.PublicKeySize : 2*ed25519.PublicKeySize]
ra = proof[2*ed25519.PublicKeySize : 3*ed25519.PublicKeySize]
)
b3, err := privateToScalar(v.b3)
if err != nil {
return nil, fmt.Errorf("unable to initialize a scalar from ephemeral key: %w", err)
}
Pa, _ := (&edwards25519.Point{}).SetBytes(pa)
Qa, _ := (&edwards25519.Point{}).SetBytes(qa)
Ra, _ := (&edwards25519.Point{}).SetBytes(ra)
Rb := (&edwards25519.Point{}).ScalarMult(b3, (&edwards25519.Point{}).Subtract(Qa, v.q))
Rab := (&edwards25519.Point{}).ScalarMult(b3, Ra)
if (&edwards25519.Point{}).Subtract(Pa, v.p).Equal(Rab) != 1 {
return nil, errors.New("invalid proof")
}
return Rb.Bytes(), nil
}
func privateToScalar(pk ed25519.PrivateKey) (*edwards25519.Scalar, error) {
h := sha512.Sum512(pk.Seed())
s, err := edwards25519.NewScalar().SetBytesWithClamping(h[:32])
return s, err
}
func main() {
logger := slog.New(slog.NewJSONHandler(os.Stdout, &slog.HandlerOptions{}))
slog.SetDefault(logger)
c1 := &Client{}
logger.Info("C -> S: Session boostrap")
session := &Server{}
step1, err := session.Bootstrap()
if err != nil {
logger.Error("unable to initialize prover", "error", err)
return
}
logger.Info("S -> C: Session public keys")
fmt.Println(hex.Dump(step1))
step2, err := c1.Proof(step1, []byte("very-secret-password"))
if err != nil {
logger.Error("unable to initialize prover", "error", err)
return
}
logger.Info("C -> S: Client proof")
fmt.Println(hex.Dump(step2))
step3, err := session.Prove(step2, []byte("very-secret-password"))
if err != nil {
logger.Error("unable to compute proof", "error", err)
return
}
logger.Info("S -> C: Session proof")
fmt.Println(hex.Dump(step3))
step4, err := c1.Verify(step3)
if err != nil {
logger.Error("unable to validate proof", "error", err)
return
}
logger.Info("C -> S : Authenticate session proof")
fmt.Println(hex.Dump(step4))
valid, err := session.Verify(step4)
if err != nil {
logger.Error("unable to authenticate proof", "error", err)
return
}
logger.Info("S: Client Authenticated?")
fmt.Println(valid)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment