[curves] A very simple PAKE

Mike Hamburg mike at shiftleft.org
Tue Nov 4 09:58:11 PST 2014

Hello Jonathan,

This is indeed a Simple PAKE.  It's a stripped-down variant of SPAKE1, 
which is described in Abdalla and Pointcheval's paper "Simple 
Password-Based Encrypted Key Exchange Protocols":


The main differences are that SPAKE uses different G2's for Alice and 
Bob, and that SPAKE1 computes the session key as 
Hash(Alice,Bob,P1,P2,abG).  There is also a SPAKE2 which throws the 
password into the hash function too, for reasons having to do with the 
security proof.

IIRC (and it's possible I don't), it's safe to use the same G2 on both 
sides, but it weakens the security proof slightly (from CDH to CDH 

Omitting the hash is a more dangerous proposition.  There are lots of 
attacks that the original paper doesn't have to worry about, just 
because it throws everything into that hash function.  In particular, 
not hashing in the identities means that you aren't sure who you're 
talking to, just that they have the same password.

-- Mike

On 11/04/2014 08:20 AM, Jonathan Cressman wrote:
> Hello,
> Sorry for potentially spamming your email reflector.  I’m an embedded 
> wireless programmer in need of a very simple Password Authenticated 
> Key Exchange(PAKE).  I believe I have created something similar to 
> SPEKE but that works considerable better over elliptic curves.  I 
> would like some help proving that it is secure.
> _Set up_
> The Protocol begins with an elliptic curve over F_2m with parameters T 
> = (m, f(x), a, b, G, n, h) and G_2 as second generator of that group 
> such that v, where vG = G_2 is unknown.  Also given P an arbitrary 
> element of the group generated by G and aP finding a is hard.  The 
> curves 163k1 and 283k1 are such curves with these properties.  T and 
> G_2 are fixed and known by all implementers of the algorithm.
> Convention:  Capitals will be points on the curve and lower case 
> letters will be integers.
> _Algorithm_
> 1.Let Alice and Bob have a shared password s, s is a “smallish” 
> non-negative integer.
> 2.Both Alice and Bob choose a number between 1 and n-2.  Let these 
> numbers be a and b.  Alice sends the point P_1 =aG + sG_2 to Bob and 
> Bob sends the point P_2 = bG+ sG_2 to Alice.
> 3a. Alice verifies P_2 is a generator of the group and then computes 
> a(P_2 - sG_2 ) = a(bG+ sG_2 - sG_2 ) = abG
> 3b. Bob verifies P_1 is a generator of the group and then computes 
> b(P_1 - sG_2 ) = b(aG+ sG_2 - sG_2 ) = abG
> 4.   Alice and Bob verify that they both know the new shared secret abG.
> If Alice and Bob fail to agree on the new shared secret, abG, they 
> know something has gone wrong.
> ..................
> Jonathan Cressman
> Firmware Developer
> cid:image001.gif at 01C91335.F4F940E0
> Energate Inc. 2379 Holly Lane, Suite 200, Ottawa, Ontario, Canada K1V 7P2
> T: 613-482-7928 x226  F: 613-288-0816 _http://www.energateinc.com 
> <http://www.energate.ca/>_
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141104/d423ba4b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/gif
Size: 1668 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141104/d423ba4b/attachment.gif>

More information about the Curves mailing list