SPAKE2 in Golang: Implementing Groups

In the Beginning ...

Like always I had too many question on how to do? what to do? etc. etc. Well there is no definitive answer, you have to experiment to get the answer. So as a first step I had to decide what I need. Looking at Python implementation of SPAKE2 some basic group operations needed are as follows.

• Element Addition for the group
• Scalar Multiplication for the group
• Scalar Multiplication with Base point/Generator of group

Along with this some other functions are needed, these are not exactly group related operations, but are needed in SPAKE2 calculation. We can call them helper operations and they are listed as follows.

• Convert password into Scalar of the group (Scalar is nothing but big integer in the group)
• Generate a Random scalar for the group.
• Constants M, N and S.
• Converting group element to bytes and creating element from bytes.
• Element Size for the group.
• Order of the subgroup

Now you might be wondering what S might be, as I only talked about M and N while explaining SPAKE2. This is for a special mode called Symmetric Mode. This special mode created by Brian Warner with help from other cryptographic folks for magic-wormhole use case. This mode removes the side/identity from the SPAKE2 protocol as we saw in previous post (A, B) and makes both side identical. This will reduce additional exchanges that had to be done to setup side/identities for both peers.

Next question was whether SPAKE2 implementation is going to be Ed25519 group specific or whether I plan to introduce other groups as well?. This was important decision I had to make, since Python version also has some integer groups I decided to make groups configurable in Golang as well with Ed25519 as default group.

Defining Group Interface

To make group as configurable in SPAKE2 package I had to define a generic type. Though Golang does not have generics, we can define interface type to get some flexibility. As a first try I defined Group interface as follows

type Group interface {
       ConstM() Group
       ConstN() Group
       ConstS() Group

       RandomScalar() (*big.Int, error)
       PasswordToScalar(pw []byte) *big.Int

       ElementToBytes(ele Group) []byte
       ElementFromBytes(b []byte) Group

       BasePointMult(s *big.Int) Group
       Add(other Group) Group
       ScalarMult(s *big.Int) Group

       ElementSize() int
}

Remember this was not final version which I reached but initial version. I kept this under group.go file. I also thought it would be better to keep group implementations outside SPAKE2. So I created SPAKE2 as salsa.debian.org/vasudev/gospake2 Ed25519 group operations under salsa.debian.org/vasudev/ed25519group and integergroup operations under salsa.debian.org/vasudev/integergroup.

I hit my first road block with this representation. I created a type Ed25519 in ed25519group package and implemented the Group interface above but instead of function accepting/returning Group I used Ed25519. This felt natural to me as Ed25519 was confimring to Group interface but that Go compiler thought otherwise. Go compiler refused to agree Ed25519 type implemented Group interface and told the defintion of functions do not match. For eg. it said for ConstM, expected return value of Group but found Ed25519. I did not yet figure out why this does not work, but as far as I can understand this happens because when Go compiler scans ConstM line it still does not know that type Ed25519 implements Group interface. I could have asked in forums but frankly I did not know how to phrase this question :). If you are a gopher and know the answer please do let me know :).

Without spending too much time to figure out why its not working, I changed the interface definition to look like below.

type Group interface {
       ConstM() interface{}
       ConstN() interface{}
       ConstS() interface{}

       RandomScalar() (*big.Int, error)
       PasswordToScalar(pw []byte) *big.Int

       ElementToBytes(ele interface{}) []byte
       ElementFromBytes(b []byte) interface{}

       BasePointMult(s *big.Int) interface{}
       Add(other interface{}) interface{}
       ScalarMult(s *big.Int) interface{}

       ElementSize() int
}

So now compiler is happy because interface{} means any type. Though I was not happy because I had to do lot of type assertions in the actual implementation of group.

After I did first version of ed25519group and successfuly used it in gospake2 0.1.0, I was feeling something was not correct and things needs to be improved. Then when I started to implement integergroup package things started becoming more clear to me. I finished writing integergroup with same interface definition as above.

After both groups are implemented and integrated into gospake2, I started to look at python code moe carefully. A pattern started emerging in my mind. Python code was structured to differentiate Group and its elements, and this seemed natural separation. Once you separat Elements your interface definition will become more simpler.

So after struggling a bit I wrote a new interface, now differentiating Elements and Group itself. The final code as of writing this post is below.

// Element represents the operation that needs to be satisfied by Group element.
type Element interface {
     Add(other Element) Element
     ScalarMult(s *big.Int) Element
     Negate() Element
}

// Group defines methods that needs to be implemented by the number / elliptic
// curve group which is used to implement SPAKE2 algorithm
type Group interface {
     // These functions are not really group operations but they are needed
     // to get the required group Element's needed for calculation of SPAKE2
     ConstM() Element
     ConstN() Element
     ConstS() Element

     // This operation is needed to get a random integer in the group
     RandomScalar() (*big.Int, error)

     // This operation is for converting user password to a group element
     PasswordToScalar(pw []byte) *big.Int

     // These operations are group operations
     BasePointMult(s *big.Int) Element
     Add(a, b Element) Element
     ScalarMult(a Element, s *big.Int) Element

     ElementToBytes(e Element) []byte
     ElementFromBytes([]byte) (Element, error)

     // This operation should return size of the group
     ElementSize() int

     // This operation returns order of subgroup
     Order() *big.Int
}

Element interface requires implementer to implement Add, ScalarMult and Negate function. Group interface also has Add and ScalarMult operation but Group functions require you to pass Element as input and returns Element as output. Though it may be redundant it gives a natural organization to code.

With new interface new group implementations don't have to do too much type assertions but there will still be some which can't be avoided (eg. Element to actual type).

Packages, Subpackages and....

Well there is no such thing called subpackage in Go, this is one of the learning I had while writing gospake2 and related group implementation. I first created the Group interface in file called group.go which was under salsa.debian.org/vasudev/gospake2 package. So to refer Group interface I just need to import gospake2 and refer it as gospake2.Group. In the beginning this seemed correct approach as I did not directly refer the Group interface in the first versions of ed25519group and integergroup. (The version where I used interface{} extensively). But when I refactored to have 2 interfaces above I got cyclic dependency error. ed25519group and integergroup both referred gospake2.Group and gospake2 referred these groups.

So to fix the error I moved the interface declaration from group.go to groups folder under gospake2 package, and made it package groups. Few points I learned while doing this is

• Even if the package is inside your package you can't directly use it. i.e. there is no such thing as subpackage. gospake2 had to refer groups with its full namespace i.e. salsa.debian.org/vasudev/gospake2/groups
• Folder structure inside package does not directly relate to each other, its just placing them in meaningful path like crypto/sha256 and crypto/sha512 they do not mean they are related its just that they fall under cryptography.
• Standard library can refer to interface in parent package, for example crypto/ecdsa can refer to crypto.SignerOpts interface which is defined in crypto package just by importing "crypto" inside ecdsa package. This works because crypto is package name in GOPATH, but there is nothing special here. For us to refer something in so called parent package we need to use fullpath for example salsa.debian.org/vasudev/gospake2/groups because that is how user packages are namespaced under GOPATH.

So finally I got a proper layout for Group and Element interfaces, its now available under salsa.debian.org/vasudev/gospake2/groups package. If you intend to provide a new group implementation for gospake2 you need to implement these interfaces in your package.

Implementing Ed25519 Group

Implementing Ed25519 group was a bit of adventurous journey. First I searched for ready made implementation if any. Only thing I found was golang.org/x/crypto/ed25519/internal/edwards25519 which is port of DJB's original C code to Go by Adam Langley. Problem was this package was internal to ed25519 package and Go compiler would refuse to allow you import it outside the ed25519 package. So I decided to embed edwards25519 as a internal package with in gospake2. This was prior to second version of Group interface design.

Even with embedding I could not really use it properly. I could get the BasePointMult operation working but nothing else worked and naively I tried to use ScMulAdd for Scalar multiplication which was really a wrong thing to do. Later I understood that the module was specifically written for Ed25519 signature scheme. Though it might still be possible to use it now that I've understood the basics of curve, I will definitely give it a second try at later point in time.

After the failed attempt with edwards25519 Ramakrishnan suggested me to use big integer and implement those methods myself and finally that is what I did. I used math/big package to implement the operations required myself. So the experience of writing this module taught me a lot. Below are few of my learnings.

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*k*T2
D = Z1*2*Z2
E = B-A
F = D-C
G = D+C
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

Y1MX1 := new(big.Int).Sub(Y1, X1)
Y2MX2 := new(big.Int).Sub(Y2, X2)
A := new(big.Int).Mul(Y1MX1, Y2MX2)

def scalarmult_element(pt, n): # extended->extended
  # This form only works properly when given points that are a member of
  # the main 1*L subgroup. It will give incorrect answers when called with
  # the points of order 1/2/4/8, including point Zero. (it will also work
  # properly when given points of order 2*L/4*L/8*L)
  assert n >= 0
  if n==0:
      return xform_affine_to_extended((0,1))
  _ = double_element(scalarmult_element(pt, n>>1))
  return _add_elements_nonunfied(_, pt) if n&1 else _

-- | Scalar multiplication parametrised by addition.
scalarMultiplyExtendedPoint :: (ExtendedPoint a -> ExtendedPoint a -> ExtendedPoint a) -> Integer -> ExtendedPoint a -> ExtendedPoint a
scalarMultiplyExtendedPoint _ 0 _    = extendedZero
scalarMultiplyExtendedPoint add n x
       | even n    = doubleExtendedPoint (scalarMultiplyExtendedPoint add (n `div` 2) x)
       | n == 1    = x
       | n <= 0    = panic $ "Unexpected negative multiplier: " <> show n
       | otherwise = add x (scalarMultiplyExtendedPoint add (n - 1) x)

func (e *ExtendedPoint) ScalarMultSlow(s *big.Int) ExtendedPoint {
     if s.Cmp(big.NewInt(0)) == 0 {
             return Zero
     }

     if s.Cmp(big.NewInt(1)) == 0 {
             return *e
     }

     var result ExtendedPoint
     if IsEven(s) {
             // If scalar is even we recursively call scalarmult with n/2 and
             // then double the result.
             result = e.ScalarMultSlow(new(big.Int).Rsh(s, 1))
             result = result.Double()
     } else {
             // We decrement the scalar and recursively call scalarmult with
             // it then we add the result with point
             result = e.ScalarMultSlow(new(big.Int).Sub(s, big.NewInt(1)))
             result = AddUnified(&result, e)
     }

     return result
}

// ScalarMult multiples given point with scalar and returns the result
func (e Ed25519) ScalarMult(a group.Element, s *big.Int) group.Element {
     // First let's reduce s to curve order, this is important in case if we
     // pass negated value
     s.Mod(s, L)
     if s.Cmp(big.NewInt(0)) == 0 {
             return Zero
     }

     extendedPoint := a.(ExtendedPoint)
     result := extendedPoint.ScalarMult(s)
     return result
}

Implementing Integer Group

Given the problems I faced and things I learnt, implementing Ed25519 group, implementing integer group was much straight forward. Only some design decisions had to be made.

type GroupParameters struct {
       p, q, g *big.Int
       elementSizeBytes, elementSizeBits, scalarSize int
}

type IntegerGroup struct {
       params *GroupParameters
}

type IntegerElement {
       params *GroupParameters
       e *big.Int
}

// Add is actually multiplication mod `p` where `p` is order of the
// multiplicative group
func (i IntegerElement) Add(other group.Element) group.Element {
     a := i.e
     b := other.(IntegerElement).e

     if !i.params.equal(other.(IntegerElement).params) {
             panic("You can't add elements of 2 different groups")
     }

     result := new(big.Int).Mul(a, b)

     return group.Element(IntegerElement{params: i.params, e: result.Mod(result, i.params.p)})
}

// ScalarMult for multiplicative group is g^s mod p where `g` is group generator
// and p is order of the group
func (i IntegerElement) ScalarMult(s *big.Int) group.Element {
     reducedS := new(big.Int).Mod(s, i.params.q)
     return group.Element(IntegerElement{params: i.params, e: new(big.Int).Exp(i.e, reducedS, i.params.p)})
}

Conclussion

Well its been already a pretty long post, so without extending it more I would like to say that I had lot of learning experience in writing the Go code to implement these integer and ed25519 group. Main learnings were

1. There is no definite answer for any questions, may it be how to write a library or if I structured my library correctly. Of course there will be some best practice available but you have to start at some point and then improve it in iteration.
2. Go provides great tooling especially linters and formatters which makes you write a clean code. And also document all your exported functions as you write (else you will keep seeing warnings in your editor which is annoying).
3. Use your library yourself and you will see how you can improve it. If you are feeling uncomfortable with your own written API then that means others will too :).
4. Every language is designed for a specific purpose, if I'm feeling discomfort using some features of the language (I had problems with verbose error handling) then probably I'm less experienced with language and should see how others handle such things. There are many good projects which you can refer to and lern from.

In the next post which should be last in series I will write about design decisions I made writing gospake2 package. Code for both ed25519 and integer groups are now merged into gospake2 as that is the right place for them. You can find the code for them in my gospake2 repo.