[curves] A very simple PAKE

[Jonathan Cressman]

Hello Mike.

Hashing everything -  I'm not assuming anything about the identities of Alice and Bob and the only messages before calculating abG are the P1 and P2 messages.  All Alice and Bob know is they are supposed to talk to the other person who knows the same password as them.  Once Alice and Bob have a larger secret they can then reveal their identities to each other.  I have already created a protocol to use the new shared secret as a session key but I've left that part out since by keeping things so simple I should just be able to take the lower 128 bits of the bit representation of the point abG as a session key (I do intend to do a hash but I don't think it is necessary and I don't think it should be necessary to prove the algorithm is secure.)

I could use some help understanding how using the same G2 on both sides weakens the security proof.  It would not be practical to use different "G2" depending on who the partner device is since I don't want to have either side reveal anything about itself before exchanging P1 and P2.

I will read the link you sent me.

Thanks,
Jonathan

From: Mike Hamburg [mailto:mike at shiftleft.org]
Sent: November-04-14 12:58 PM
To: Jonathan Cressman; 'curves at moderncrypto.org'
Subject: Re: [curves] A very simple PAKE

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":

http://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf

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

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 F2m with parameters T = (m, f(x), a, b, G, n, h) and G2 as second generator of that group such that v, where vG = G2 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 G2 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 P1=aG + sG2 to Bob and Bob sends the point P2 = bG+ sG2 to Alice.
3a. Alice verifies P2 is a generator of the group and then computes a(P2 - sG2) = a(bG+ sG2 - sG2) = abG
3b. Bob verifies P1 is a generator of the group and then computes b(P1 - sG2) = b(aG+ sG2 - sG2) = 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<mailto: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/ed50b187/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 1668 bytes
Desc: image001.gif
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20141104/ed50b187/attachment.gif>