New post on implementing groups in golang.

1 files changed, 454 insertions, 28 deletions

diff --git a/content/development/golang_spake2_groups.rst b/content/development/golang_spake2_groups.rst
index b1a496a..c1e3258 100644
--- a/content/development/golang_spake2_groups.rst
+++ b/content/development/golang_spake2_groups.rst
@@ -1,11 +1,10 @@
 SPAKE2 in Golang: Implementing Groups in Golang
 ###############################################
 
-:date: 2018-08-28 14:12 +0530
+:date: 2018-09-02 17:14 +0530
 :slug: golang_spake2_5
 :tags: go, golang, spake2, cryptography
 :author: copyninja
-:status: draft
 :summary: Fifth post in "SPAKE2 in Golang" series. This post is my
           implementation notes for groups in Golang
 
@@ -20,15 +19,15 @@ 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 I noticed some basic group operations common for all groups. Some of them
-are group operations listed below.
+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 I noticed some other functions which are needed, these are not
-exactly group related operations, but are needed in SPAKE2 calculation.
+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)
@@ -36,21 +35,23 @@ exactly group related operations, but are needed in SPAKE2 calculation.
 * 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. Brian has created a special mode called **Symmetric
-Mode**. This is a special mode created by Brian Warner with help from other
+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 above (A, B) and makes both side
-identical. This will reduce additional exchanges that had to be done to setup
-side/identities for both peers.
+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.
+groups I decided to make groups configurable in Golang as well with Ed25519 as
+default group.
 
-Defininig Group Interface
+Defining Group Interface
 =========================
 
 To make group as configurable in SPAKE2 package I had to define a generic type.
@@ -80,24 +81,26 @@ flexibility. As a first try I defined **Group** interface as follows
 
 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
-package outside SPAKE2. So I created SPAKE2 as
-`salsa.debian.org/vasudev/gospake2` and Ed25519 group operations under
-`salsa.debian.org/vasudev/ed25519group`.
+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 all above function but definitions
-were returning/accepting type `Ed25519` wherever `Group` was needed. My
-expectation was this should work because `Ed25519` confirms to `Group` interface
-but Go compiler thought otherwise!. Go compiler refused to agree `Ed25519` type
+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.
-It said for ConstM, **expected return value of Group but found Ed25519**. I did
-not get why this does not work but from my understanding of compilers, I think
-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 :).
+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 :).
 
-So once I hit the road block I modified definition to look like
+Without spending too much time to figure out why its not working, I changed the
+interface definition to look like below.
 
 .. code:: go
 
@@ -119,4 +122,427 @@ So once I hit the road block I modified definition to look like
           ElementSize() int
    }
 
-So now compiler is happy because `interface{}` means any type.
+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.
+
+.. code:: go
+
+   // 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.
+
+Annoyance with big.Int
+----------------------
+
+While using big.Int I was annoyed by the specific syntax which invovled invoking
+the operation using a big.Int variable which will set the result to same
+variable and additionally return same value also. This design felt redundant to
+me and also I had to create so many intermediate variables to get operations
+like Add or Double implemented. Are you thinking why?. Then look at below
+formula for Add to add 2 points `P1 = (X1,Y1,T1,Z1)` and `P2 = (X2, Y2, T2. Z2)`
+
+.. code:: python
+
+   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
+
+With big.Int I had to create every intermediate variable and then calculate
+their result, for eg. (Y1-X1) and (Y2 - X2) and then finally calculate A. At
+this point I started liking C++ more as it will allow me to override + operator
+;-). But at later point I noticed some Go code where people dealt with the
+big.Int in following format
+
+.. code:: go
+
+   Y1MX1 := new(big.Int).Sub(Y1, X1)
+   Y2MX2 := new(big.Int).Sub(Y2, X2)
+   A := new(big.Int).Mul(Y1MX1, Y2MX2)
+
+It reduced intermediate variables to some extent, additionally it avoids
+declaring required variables first and then use it. But still its bit of
+annoyance :).
+
+Confusions with Pointers
+------------------------
+
+When using local variables of type big.Int and returning a pointer to
+it, I started to have a doubt that if what I'm doing is correct. Being from C
+background where you are not supposed to be returning pointer to a stack
+variable, Go's ability to return address of local variable confused me. But it
+looks like `Go compiler is smarter in this aspect
+<https://stackoverflow.com/questions/38234487/go-returning-a-pointer-on-stack#38234526>`_.
+Basically Go compiler does escape analysis to figure out if variable leaves
+after function and if so it moves it to garbage collected heap. So basically as
+Go programmer I need not bother on where my variables are allocated. Thats a
+relief :).
+
+
+Type Aliasing in Go
+-------------------
+
+Type aliasing in languages like Rust or C++ is a handy way to create alternate
+name for previously created type. This just creates a new name for existing type
+and you can still use the original types methods or variables. But this is not
+the same case in Go. Go `language spec
+<https://golang.org/ref/spec#Type_declarations>`_. clearly says that new type
+does not derive anything from originl type. But compiler allows you to cast
+to-and-fro from original to new type and vice versa.
+
+I was bit by this as I did not knew about it. I created a alias for
+ExtendedPoint type as Ed25519 to implement Group interface. But when I tried to
+access original functions from ExtendedPoint I noticed this behavior. So I had
+to write private conversion function just to cast types around.
+
+Implementing Scalar Multiplication and stack exhaustion
+-------------------------------------------------------
+
+Implementing scalar multiplication was one of the last adventure I tackled in
+the ed25519 group implementation. Scalar multiplication is multiplying a given
+elliptic curve point with a large integer (otherwise called as scalar) limited
+by subgroup order. Warner's python implementation was as follows
+
+.. code:: python
+
+  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 _
+
+Though I don't exactly remember first version of my scalar multiplication
+function, it was mimicking the python code in Go with big.Int. The code worked
+well with small integers but when I gave big numbers generated using
+`RandomScalar` function of `Group` interface, code will panic as it will run out
+of stack.
+
+Above python code is slightly optimized version, so I looked at Haskell
+implementation of SPAKE2 which looked like below
+
+.. code:: haskell
+
+   -- | 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)
+
+So algorithm is like this
+
+1. If scalar is 1 return same point
+2. If scalar is 0 return identity element for group
+3. If scalar is even then recursively call scalarmult by reducing the scalar to
+   half and double the result.
+4. Otherwise recursively scalarmultiply the point with scalar reduced by 1 and
+   add the result to the point.
+
+It might look slightly confusing explanation so I will just show the code below.
+
+.. code:: go
+
+   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
+   }
+
+So instead of dividing by 2 I just right shift the scalar by 1 which is faster
+operation. (AddUnified  is one of the algorithm for point addition which is more
+safer but slower alternative, hence the name ScalarMultSlow.)
+
+So this implementation works with every input, except the negative one for which
+I modified ScalarMult definition in Group level to reduce input scalar to
+subgroup order L. Otherwise Group function just calls function from Element.
+Code below.
+
+.. code:: go
+
+   // 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
+   }
+
+Probably I shoud move reducing the scalar to subgroup order into scalarmult
+inside Element's implementation.
+
+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.
+
+How to Represent Group and Elements
+-----------------------------------
+
+Unlike Ed25519 where group elements are basically points on the curve, element
+in multiplicative integer groups are basically integers. So how do I represent
+various integer groups?. Various integer groups are differentiated by bit length
+of elements in it, group and subgroup order. Looking at python code I created a
+structure called `GroupParameters` which will contain necessary information for
+a given group.
+
+.. code:: go
+
+   type GroupParameters struct {
+          p, q, g *big.Int
+          elementSizeBytes, elementSizeBits, scalarSize int
+   }
+
+I did not want to export these fields as they are not useful outside the
+package. Python code implemented 3 integer group of 1024,2048 and 3072 bit
+integers. All values for above variables were taken from `NIST document
+<http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/DSA2_All.pdf>`_.
+
+In first iteration I only had a struct called `IntegerGroup` which had
+parameters as member and implemented `Group` interface from gospake2. But when I
+refactored Group interface to have Element interface refactoring the code for
+integergroup became bit challenging. I introduced `IntegerElement` struct to
+hold actual integer value, but since all operations needed access to order of
+group I had to modify it to also contain parameters defined above. So final
+definition of `IntegerGroup` and `IntegerElement` is as follows
+
+.. code:: go
+
+   type IntegerGroup struct {
+          params *GroupParameters
+   }
+
+   type IntegerElement {
+          params *GroupParameters
+          e *big.Int
+   }
+
+Operations in `IntegerGroup` were simply calling functions from
+`IntegerElement`. So its really redundant but to make sure I can distinguish
+between both group and its element I had to use it in this form.
+
+Scalar Multiplication and Addition Operations
+---------------------------------------------
+
+Since the integer groups are really multiplicative group, addition operation is
+really a multiplication modulo p. Scalar multiplication is just exponentiation
+modulo p. Since these operations are readily available in `math/big` I did not
+had to do anything much for integer group. These operations in `IntegerElement`
+are defined as follows.
+
+.. code:: go
+
+   // 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
+<https://salsa.debian.org/vasudev/gospake2>`_.