Skip to content

Instantly share code, notes, and snippets.

@Scratch-net
Last active June 16, 2020 19:54
Show Gist options
  • Save Scratch-net/37ae11e589ea3d17fe104a2630306042 to your computer and use it in GitHub Desktop.
Save Scratch-net/37ae11e589ea3d17fe104a2630306042 to your computer and use it in GitHub Desktop.
sphinx implementation in 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
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment