<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Hi Jonathan,</div><div class=""><br class=""></div><div class="">It may still be worth hashing the P1 and P2 messages. I don’t know if there is actually an attack otherwise, but the proof strategy I’ve seen uses the hash function in an integral way (as a random oracle). It would be a major result if you could prove security of this system without hashing.</div><div class=""><br class=""></div><div class="">The reason SPAKE uses a separate G1 and G2 is that it’s not equivalent to the discrete log problem. Instead, it reduces from the CDH problem, which has two inputs G1,G2. Finding a P1 that allows Alice to guess two passwords at once ought to be equivalent to CDH(G1,G2). If both sides use the same G2, then you get CDH(G2,G2) in the same place, which is a “squaring” problem, which is less general but probably not weaker in practice. I *think* that’s the only downside.</div><div class=""><br class=""></div><div class="">If one side is initiator, they can use G1, and the responder can use G2. If simultaneous init is allowed, and the two parties don’t know each others’ identities, then you’re probably stuck with just a single G2. On the other hand, if one side is initiator and the other is responder, then I *think* the responder doesn’t need to blind at all, and it’s still CDH-equivalent so long as they confirm knowledge of the key first (in the same message flow, before the initiator uses the key).</div><div class=""><br class=""></div><div class="">All of this assumes that you are hashing at least P1, P2, and possibly also (for proof reasons) the password.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class="">— Mike</div><br class=""><div><blockquote type="cite" class=""><div class="">On Nov 4, 2014, at 11:15 AM, Jonathan Cressman <<a href="mailto:JCressman@energateinc.com" class="">JCressman@energateinc.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="WordSection1" style="page: WordSection1; font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255);"><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class="">Hello Mike.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class=""> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class="">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.)<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class=""> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class="">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.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class=""> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class="">I will read the link you sent me.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class=""> </span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class="">Thanks,<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class="">Jonathan<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="color: rgb(31, 73, 125);" class=""> </span></div><div class=""><div style="border-style: solid none none; border-top-color: rgb(181, 196, 223); border-top-width: 1pt; padding: 3pt 0cm 0cm;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><b class=""><span lang="EN-US" style="font-size: 10pt; font-family: Tahoma, sans-serif; color: windowtext;" class="">From:</span></b><span lang="EN-US" style="font-size: 10pt; font-family: Tahoma, sans-serif; color: windowtext;" class=""><span class="Apple-converted-space"> </span>Mike Hamburg [<a href="mailto:mike@shiftleft.org" style="color: purple; text-decoration: underline;" class="">mailto:mike@shiftleft.org</a>]<span class="Apple-converted-space"> </span><br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>November-04-14 12:58 PM<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Jonathan Cressman; '<a href="mailto:curves@moderncrypto.org" style="color: purple; text-decoration: underline;" class="">curves@moderncrypto.org</a>'<br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>Re: [curves] A very simple PAKE<o:p class=""></o:p></span></div></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hello Jonathan,<br class=""><br class="">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":<br class=""><br class=""><a href="http://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf" style="color: purple; text-decoration: underline;" class="">http://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf</a><o:p class=""></o:p></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><br class="">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.<br class=""><br class="">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).<br class=""><br class="">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.<br class=""><br class="">-- Mike<br class=""><br class="">On 11/04/2014 08:20 AM, Jonathan Cressman wrote:<o:p class=""></o:p></div></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Hello,<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">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.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><u class="">Set up</u><o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">The Protocol begins with an elliptic curve over F<sub class="">2m</sub><span class="Apple-converted-space"> </span>with parameters T = (m, f(x), a, b, G, n, h) and G<sub class="">2</sub><span class="Apple-converted-space"> </span>as second generator of that group such that v, where vG = G<sub class="">2</sub><span class="Apple-converted-space"> </span>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<sub class="">2</sub><span class="Apple-converted-space"> </span>are fixed and known by all implementers of the algorithm.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">Convention: Capitals will be points on the curve and lower case letters will be integers.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><u class="">Algorithm</u><o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 11pt; font-family: Calibri, sans-serif; text-indent: -18pt;" class=""><span class="">1.<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';" class=""> <span class="Apple-converted-space"> </span></span></span><span lang="EN-AU" class="">Let Alice and Bob have a shared password s, s is a “smallish” non-negative integer. </span><o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt 36pt; font-size: 11pt; font-family: Calibri, sans-serif; text-indent: -18pt;" class=""><span class="">2.<span style="font-style: normal; font-variant: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';" class=""> <span class="Apple-converted-space"> </span></span></span><span lang="EN-AU" class="">Both Alice and Bob choose a number between 1 and n-2. Let these numbers be a and b. Alice sends the point P<sub class="">1</sub>=aG + sG<sub class="">2</sub><span class="Apple-converted-space"> </span>to Bob and Bob sends the point P<sub class="">2</sub>= bG+ sG<sub class="">2</sub><span class="Apple-converted-space"> </span>to Alice.</span><o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt 18pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">3a. Alice verifies P<sub class="">2</sub><span class="Apple-converted-space"> </span>is a generator of the group and then computes a(P<sub class="">2</sub><span class="Apple-converted-space"> </span>- sG<sub class="">2</sub>) = a(bG+ sG<sub class="">2</sub><span class="Apple-converted-space"> </span>- sG<sub class="">2</sub>) = abG<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt 18pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">3b. Bob verifies P<sub class="">1</sub><span class="Apple-converted-space"> </span>is a generator of the group and then computes b(P<sub class="">1</sub><span class="Apple-converted-space"> </span>- sG<sub class="">2</sub>) = b(aG+ sG<sub class="">2</sub><span class="Apple-converted-space"> </span>- sG<sub class="">2</sub>) = abG<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt 18pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">4. Alice and Bob verify that they both know the new shared secret abG.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-size: 12pt; font-family: 'Times New Roman , serif', serif;" class=""> </span><o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">If Alice and Bob fail to agree on the new shared secret, abG, they know something has gone wrong.<o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 10.5pt; font-family: Arial, sans-serif; color: gray;" class="">..................</span><o:p class=""></o:p></div><p class="MsoNormal" style="margin: 6pt 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><span lang="EN-US" style="font-size: 10.5pt; font-family: Arial, sans-serif; color: gray;" class="">Jonathan Cressman</span><o:p class=""></o:p></p><p class="MsoNormal" style="margin: 6pt 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;"><span lang="EN-US" style="font-size: 8.5pt; font-family: Arial, sans-serif; color: gray;" class="">Firmware Developer</span><o:p class=""></o:p></p><p class="MsoNormal" style="margin: 0cm 0cm 12pt; font-size: 11pt; font-family: Calibri, sans-serif;"><span style="font-size: 8.5pt; font-family: Arial, sans-serif; color: gray;" class=""><image001.gif></span><span lang="EN-US" style="font-size: 8.5pt; font-family: Arial, sans-serif; color: gray;" class=""><br class=""></span><span lang="EN-US" style="font-size: 9pt; font-family: Arial, sans-serif; color: gray;" class="">Energate Inc. 2379 Holly Lane, Suite 200, Ottawa, Ontario, Canada K1V 7P2<br class="">T: 613-482-7928 x226 F: 613-288-0816 <u class=""><a href="http://www.energate.ca/" style="color: purple; text-decoration: underline;" class="">http://www.energateinc.com</a></u></span><o:p class=""></o:p></p><div style="margin: 0cm 0cm 0.0001pt; font-size: 10.5pt; font-family: Consolas;" class=""> <o:p class=""></o:p></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><br class=""><br class=""><br class=""><o:p class=""></o:p></span></div><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">_______________________________________________<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">Curves mailing list<o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class=""><a href="mailto:Curves@moderncrypto.org" style="color: purple; text-decoration: underline;" class="">Curves@moderncrypto.org</a><o:p class=""></o:p></pre><pre style="margin: 0cm 0cm 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class=""><a href="https://moderncrypto.org/mailman/listinfo/curves" style="color: purple; text-decoration: underline;" class="">https://moderncrypto.org/mailman/listinfo/curves</a><o:p class=""></o:p></pre></blockquote><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span style="font-size: 12pt; font-family: 'Times New Roman', serif;" class=""> </span></div></div></div></blockquote></div><br class=""></body></html>