**diff options**

author | Vasudev Kamath <vasudev@copyninja.info> | 2018-08-28 20:07:01 +0530 |
---|---|---|

committer | Vasudev Kamath <vasudev@copyninja.info> | 2018-08-28 20:07:41 +0530 |

commit | dc09f0daed11dd06902543163b155fff57be1880 (patch) | |

tree | 267ae8ea0afc650b736bac47fcd8372c9f4aed8a | |

parent | e8066b9913e1ead25d75458efd4ba09c857bbe54 (diff) |

New post on Twisted Edwards curve and SPAKE2

-rw-r--r-- | content/development/golang_spake2_edwards.rst | 236 |

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. |