sphinx implementation in go

sphinx.go

package main

import (
	"crypto/elliptic"
	"crypto/rand"
	"crypto/sha256"
	"fmt"
	"math/big"
)

var (
	c = elliptic.P256()

	// server's static secret value
	k = new(big.Int).SetBytes([]byte{164, 98, 192, 51, 205, 206, 226, 85, 22, 79, 248, 231, 248, 171, 160, 1, 248, 166, 173, 240, 47, 68, 92, 163, 33, 118, 150, 220, 69, 51, 98})
)

// sphinx implementation PoC
// http://webee.technion.ac.il/~hugo/sphinx.pdf

func main() {

	pwd := "p@ssw0rDD"       //master password
	domain := "example.com" //domain we want to log in to
	hash := sha256.Sum256([]byte(pwd + "|" + domain))

	pkx, pky := HashIntoCurvePoint(hash[:]) // turn password hash into elliptic curve point. c.ScalarBaseMult(hash[:]) can also be used as an alternative
	fmt.Println("original:           ", pkx, pky)

	r, _ := randScalar(c) // client's password mask value, random per every call

	x, y := c.ScalarMult(pkx, pky, r.Bytes()) //client masks his password hash with a random value
	fmt.Println("masked:             ", x, y)
	rInv := fermatInverse(r, c.Params().N) // rInv = r ^-1

	x1, y1 := c.ScalarMult(x, y, rInv.Bytes()) //unmask just to show it works properly

	fmt.Println("unmasked:           ", x1, y1)

	x, y = c.ScalarMult(x, y, k.Bytes()) // server multiplies client's masked value to its own secret value and returns to client
	fmt.Println("masked + server:    ", x, y)

	x, y = c.ScalarMult(x, y, rInv.Bytes())   // client un-masks returned value by multiplying it to r ^-1
	fmt.Println("unmask after server:", x, y) // a unique value that can be used as a password or key that only client knows

}

var one = new(big.Int).SetInt64(1)

// A invertible implements fast inverse mod Curve.Params().N
type invertible interface {
	// Inverse returns the inverse of k in GF(P)
	Inverse(k *big.Int) *big.Int
}

func randScalar(c elliptic.Curve) (k *big.Int, err error) {
	params := c.Params()
	k, err = rand.Int(rand.Reader, params.N)
	return
}

// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
// This has better constant-time properties than Euclid's method (implemented
// in math/big.Int.ModInverse) although math/big itself isn't strictly
// constant-time so it's not perfect.
func fermatInverse(k, N *big.Int) *big.Int {
	two := big.NewInt(2)
	nMinus2 := new(big.Int).Sub(N, two)
	return new(big.Int).Exp(k, nMinus2, N)
}

func HashIntoCurvePoint(r []byte) (x, y *big.Int) {
	t := make([]byte, 32)
	copy(t, r)

	x, y = tryPoint(t)
	for y == nil || !c.IsOnCurve(x, y) {
		increment(t)
		x, y = tryPoint(t)

	}
	return
}

func tryPoint(r []byte) (x, y *big.Int) {
	hash := sha256.Sum256(r)
	x = new(big.Int).SetBytes(hash[:])

	// y² = x³ - 3x + b
	x3 := new(big.Int).Mul(x, x)
	x3.Mul(x3, x)

	threeX := new(big.Int).Lsh(x, 1)
	threeX.Add(threeX, x)

	x3.Sub(x3, threeX)
	x3.Add(x3, c.Params().B)

	y = x3.ModSqrt(x3, c.Params().P)
	return
}

func increment(counter []byte) {
	for i := len(counter) - 1; i >= 0; i-- {
		counter[i]++
		if counter[i] != 0 {
			break
		}
	}
}