New post on Twisted Edwards curve and SPAKE2

1 files changed, 236 insertions, 0 deletions

diff --git a/content/development/golang_spake2_edwards.rst b/content/development/golang_spake2_edwards.rst
new file mode 100644
index 0000000..4e95f51
--- /dev/null
+++ b/content/development/golang_spake2_edwards.rst
@@ -0,0 +1,236 @@
+SPAKE2 in Golang: ECDH, SPAKE2 and Curve Ed25519
+################################################
+
+:date: 2018-08-28 11:38 +0530
+:slug: golang_spake2_4
+:tags: go, golang, spake2, cryptography, ecc
+:author: copyninja
+:summary: Fourth post in SPAKE2 in Golang series. This post is my notes on
+          ECDH, SPAKE2 and curve Edwards25519 group
+
+In my `previous post <https://copyninja.info/blog/golang_spake2_3.html>`_  I
+talked about finite field and how it helps in *Elliptic Curve Cryptography*. In
+this post we will see briefly how Diffie-Hellmann key exchange varies with use
+of *Elliptic curve* groups, then we will see SPAKE2 original variant followed by
+Elliptic curve version and finally we will have a look at curve Ed25519 which is
+used as default group in *python-spake2* module.
+
+Elliptic Curve Diffie-Hellman (ECDH)
+====================================
+
+In the previous post we defined the domain parameter of elliptic curve
+cryptography as :math:`(p, a, b, G, n, h)`. Now we will see how we use this in
+Diffie-Hellman Key exchange.
+
+Diffie-Hellman key exchange is a way to securely exchange cryptographic key over
+public channel. Original Diffie-Hellman protocol used **multiplicative group of
+integers modulo p** where `p` is the a large prime and `g` a generator for
+subgroup (as we saw in earlier post). The protocol can be explained as follows
+
+1. Alice and Bob agrees on `p` and `g` belonging to group `G`
+2. Alice selects `a` belonging to `G` and calculates :math:`A = g^a \bmod{p}`
+3. Bob selects `b` belonging to `G` and calculates :math:`B = g^b \bmod{p}`
+4. Alice sends Bob `A`
+5. Bob sends Alice `B`
+6. Now Alice calculates :math:`s = B^a \bmod{p}`
+7. Now Bob calculates :math:`s = A^b \bmod{p}`
+
+Mathematically `s` computed by both Alice and  Bob are same and hence both
+share a shared secret now.
+
+.. math::
+
+   s = B^a \bmod{p} = g^{ba} \bmod{p} = A^b \bmod{p} = g^{ab} \bmod{p}
+
+
+Now in ECC,
+
+1. private key :math:`d` is a random integer choosen from :math:`\{1, \dots, n -
+   1\}` where `n` is the order of subgroup
+2. public key is the point :math:`H = dG` where `G` is the base point of
+   subgroup.
+
+With above now we can write Diffie-Hellman key exchange as
+
+1. Alice selects private key :math:`d_A` and public key :math:`H_A = d_AG` and
+   sends it to Bob
+2. Bob selects private key :math:`d_B` and public key :math:`H_B = d_BG` and
+   sends it to Alice
+3. Alice calculates :math:`S = d_AH_B` and Bob calculates :math:`S = d_BH_A`
+   which if you see carefully is one and same and Alice and Bob now share a
+   secret key!.
+
+.. math::
+
+   S = d_A H_B = d_A (d_B G) = d_B (d_A G) = d_B H_A
+
+
+In both cases observer only sees the public key and will not be able to find
+discrete logarithm (hard problem), given the numbers are large prime.
+
+Advantage of ECDH is its faster as its replacing the costly exponentiation
+operation with *scalar multiplication* without reducing hardness of the problem.
+
+SPAKE2 Protocol
+===============
+
+Now that we understood Diffie-Hellman exchange and saw how to apply Elliptic
+curve in Diffie-Hellman exchange, lets see what is SPAKE2 protocol. This paper
+by `Abdalla and Pointcheval
+<https://www.di.ens.fr/~pointche/Documents/Papers/2005_rsa.pdf>`_ gives full
+explanation of SPAKE2 and proof of its security. I highly recommend reading the
+paper as I can only summarize my understadning here.
+
+SPAKE2 is a variation of Diffie-Hellman problem we described above. Domain
+parameters for SPAKE2 are :math:`(G, g, p, M, N, H)`
+
+* `G` is the group
+* `g` is the generator for group
+* `p` is the big prime which is order of group
+* :math:`M, N \in G` and are selected by Alice and Bob respectively
+* `H` is the hash function used to derive final shared key.
+
+Along with this SPAKE2 both side will have common password :math:`pw \in Z_p`.
+Protocol is defined as follows
+
+1. Alice selects a random scalar :math:`x \xleftarrow{R} Z_p` and
+   calculates :math:`X \leftarrow g^x`.
+2. Alice then computes :math:`X^* \leftarrow X \cdot M^{pw}`
+3. Bob selects a random scalar :math:`y \xleftarrow{R} Z_p` and calculates
+   :math:`Y \leftarrow g^y`.
+4. Bob then computes :math:`Y^* \leftarrow Y \cdot N^{pw}`.
+5. :math:`X^*, Y^*` are called pake messages and are sent to other side. i.e.
+   Alice sends :math:`X^*` to Bob and Bob sends :math:`Y^*` to Alice.
+6. Alice computes :math:`K_A \leftarrow (Y*/N^{pw})^x` and Bob computes :math:`K_B
+   \leftarrow (X^*/M^{pw})^y`
+7. Shared Key is calculated by Alice as :math:`SK_A \leftarrow
+   H(A,B,X^*,Y^*,pw,K_A)` and Bob computes :math:`SK_B \leftarrow H(A,B,X^*,Y^*,
+   pw, K_B)`
+
+:math:`SK_A = SK_B` because mathematically value :math:`K_A = K_B` (you can
+expand :math:`X^*` and :math:`Y^*` in step `6` aboveand see that they are really
+same).
+
+In step `7` we calculate Hash of transcript, where `A` and `B` are identities of
+Alice and Bob. and rest is calculated during protocol execution.
+
+One thing to note here is paper does not define what are identities or which
+hash function is used. This allows some creativity from implementer side to
+choose things. For *python-spake2* interoperability *Brian* has written a
+`detailed blog post <http://www.lothar.com/blog/57-SPAKE2-Interoperability/>`_
+describing decision he has taken for all these points which are not defined in
+original paper.
+
+
+Curve Ed25519 Group
+===================
+
+Now that we have seen the SPAKE2 protocol, we will next see the use of Elliptic
+Curve groups in it and see how it varies.
+
+SPAKE2 uses *Abelian Group* with large number of "elements". `Brian Warner
+<http://lothar.com/blog/>`_ has choosen elliptic curve group *Ed25519* (some
+times also referred as X25519) as default group in *python-spake2*
+implementation. This is the same group which is used in *Ed25519 signature
+scheme*. The difference between multiplicative integer group modulo p and
+elliptic curve group is that, element in integer group is just a number but in
+elliptic curve group its a point. (represented by 2 co-ordinates).
+
+Curve Ed25519 is a *twisted Edwards curve*, defined in affine form as
+:math:`ax^2 + y^2 = 1 + dx^2y^2` where :math:`d \in k\{0,1\}`.
+
+* :math:`q = 2^{255} - 19` is the order of curve group
+* :math:`l = 2^{252} + 27742317777372353535851937790883648493` is the order of
+  curve subgroup.
+* :math:`a = -1`
+* :math:`d = \frac{-121665}{121666}`
+* Base point :math:`B` is unique and has y-co-ordinate `:math:4/5` and x
+  co-ordinate is positive.
+
+Curve itself is given as :math:`E/\mathbb F_q`
+
+.. math::
+
+   -x^2 + y^2 = 1 - \frac{121665}{121666} x^2y^2
+
+This curve is birationally equivalaent to the Montgomery curve known as
+*Curve25519*. If you are wondering what *25519* is?, well its in the order of
+group i.e. :math:`2^{255} - 19`.
+
+Till now we were working with elliptic curves with affine co-ordinates, i.e.
+each point is represented as :math:`(x,y)`. But for fast operation twisted
+edwards curve introduces new type of co-ordinates called *Extended Co-ordinates*
+where *x, y* is represented as *X,Y,T and Z*, and affine co-ordinates are
+represented using the extended co-ordinates as follows
+
+.. math::
+
+   x = X/Z \\
+   y = Y/Z \\
+   x*y = T/Z \\
+
+Initial base point is converted to extended co-ordinate using `Z` as 1. In all
+above case the operations are :math:`mod q`. Additionally all division
+operations are actually multiplication with inverse of element.
+
+We also noted above, Base point represented using only y co-ordinate. This is
+because x co-ordinate can be recovered from y, using twisted edwards curve
+equation we defined above. In most of libraries you will see that this
+compressed notation of representing a point as just `y` co-ordinate is used.
+(Its called *CompressedEdwardsY* in Rust's *curve25519-dalek* crate.)
+
+In all above case the operations are :math:`mod q`. Additionally all division
+operations are actually multiplication with inverse of element.Inverse of a
+element is calculated as point raised to power `q-2` modulo `q`. I could not
+find the technical/mathematical reason behind this. If some one knows please let
+me know. So the inverse operation can be mathematically defined as follows.
+
+.. math::
+
+   x^{-1} = x^{q - 2} \bmod{q}
+
+The addition and doubling operations are as per algorithms defined in
+`hyperelliptic.org post
+<http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html>`_. We have
+seen scalar multiplication in `second post of this series
+<https://copyninja.info/blog/golang_spake2_2.html>`_, which depends on addition
+and doubling operation.
+
+
+SPAKE2 using Ed25519 group
+--------------------------
+
+Unlike normal elliptic curve here the domain parameters are slightly different.
+Ed25519 domain parameters are defined as :math:`(q, d, B, l)` where `q` gives
+the order of elliptic curve group and `l` is the order of subgroup. `B` is the
+base point of the group.
+
+Now lets rewrite original SPAKE2 protocol using elliptic curve groups
+
+1. Alice selects a random scalar :math:`x \xleftarrow{R} E/\mathbb F_q` and calculates
+   :math:`X \leftarrow B \cdot x` and computes :math:`X^* \leftarrow X + M \cdot
+   pw`. Alice sends :math:`X^*` to Bob.
+2. Bob selects random scalar :math:`y \xleftarrow{R} E/\mathbb F_q` and
+   calculates :math:`Y \leftarrow B \cdot y` and computes :math:`Y^* \leftarrow
+   Y + N \cdot pw`. Bob sends :math:`Y^*` to Alice.
+3. Alice now calculates :math:`K_A \leftarrow (Y^* - N \cdot pw) \cdot x`
+4. Bob now calculates :math:`K_B \leftarrow (X^* - M \cdot pw) \cdot y`
+5. Shared key is calculated by Alice :math:`SK_A \leftarrow H(A, B, X^*, Y^*,
+   pw, K_A)` and by Bob :math:`SK_B \leftarrow H(A,B, X^*, Y^*, pw, K_B)`
+
+In 3 and 4 if you expand :math:`X^*` and :math:`Y^*` you will see that
+:math:`K_A = K_B`. And given password used by both sides are same we will arrive
+at same shared key.
+
+As you see above protocol for SPAKE2 remains same only things what changed from
+earlier is operations, exponentiation is changed to multiplication and division
+to substraction. Since we do not explicitly define substraction what we do is
+negate the password and do addition instead.
+
+Conclusion
+==========
+
+So we now have seen all the basics needed to start writing the actual Go code to
+implement SPAKE2 library. It was bit long I know but if you know the basics
+writing code is a cake walk!. (quoting from Ramakrishnan). So in the next post I
+will start writing implementation notes.