SMP / ZKP based secure comparison for authentication purpose.

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)
	}

	// G2a || SIGN(a2, G2a) || G3a || SIGN(a3, G3a)
	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)
	}

	// Convert to point for arithmetic
	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)
	}

	// Pa = s * G3
	p.pA = (&edwards25519.Point{}).ScalarMult(s, G3)
	// Qa = x * G2 + s * G
	p.qA = (&edwards25519.Point{}).VarTimeDoubleScalarBaseMult(x, G2, s)
	// Ra = a3 * (Qa - Qb)
	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 = a3 * Rb
	Rab := (&edwards25519.Point{}).ScalarMult(a3, Rb)

	// CHECK( Rb == (Pa - Pb) )
	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)
	}

	// Convert to scalars for arithmetric
	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 (use SH512/256)
	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)
	}

	// Pb = r * G3
	v.p = (&edwards25519.Point{}).ScalarMult(r, G3)
	// Qb = y * G2 + r * G
	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 = b3 * (Qa - Qb)
	Rb := (&edwards25519.Point{}).ScalarMult(b3, (&edwards25519.Point{}).Subtract(Qa, v.q))
	// Rab = b3 * Ra
	Rab := (&edwards25519.Point{}).ScalarMult(b3, Ra)

	// CHECK( Rab == (Pa - Pb) )
	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)
}

~readme.md

Zero Knowledge based authentication

Based on

• https://www.cossacklabs.com/blog/introducing_secure_comparator/
• https://www.cossacklabs.com/files/secure-comparator-paper-rev12.pdf

Interactive protocol to authenticate a secret knowledge without sharing it on the wire.

{"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  |8..@.j.T..A.'..^|
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.&.m.@..g*.|

{"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  |.a@A....8o.VX.-.|

{"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?"}
true