<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi Arasch,<div class=""><br class=""></div><div class="">If the password is salted, then the issue is probably exploitable.  This is because you will give away one bit of the password per salt.  Whether the exploit is against the user or the device depend on protocol flow and on who choses the salt.</div><div class=""><br class=""></div><div class="">If the password is not salted, then you give away one bit of the password total.  This might not be exploitable, but it’s definitely not ideal.  Also, lack of salt isn’t ideal either.</div><div class=""><br class=""></div><div class="">If properly implemented (i.e. using one inverse square root), Elligator 2 adds about 10% to the curve25519 operation, which is to say 5% to each party’s runtime (since they do 2 curve25519 operations).  It probably adds a few hundred bytes to the code size as well.  It can reuse all the existing field operations, except that you need to extend your inverse operation to inverse square root.</div><div class=""><br class=""></div><div class="">On a related note, if you haven an M4 and are truly strapped for code size, you might want to consider STROBE.  It supports Curve25519 key exchange, signing and verification, as well as (totally non-standard) hashing, AEAD encryption, pseudorandom generation, PBKDF2-quality password strengthening, and a lightweight protocol framework in as little as 3kB of code (probably more like 4k since you’d have to talk with Rambus to get the M4 asm version).  So implementing SPEKE would just require the addition of Elligator.  It’s probably not as fast as Wouter’s Curve25519 implementation though.</div><div class=""><br class=""></div><div class="">— Mike</div><div class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Oct 24, 2017, at 1:14 PM, Arasch Honarbacht <<a href="mailto:honarbacht@ubisys.de" class="">honarbacht@ubisys.de</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-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">Hi Björn,<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">Thank you for your prompt reply. Actually your paper is one of the sources I’ve been reading the past days. We’ll certainly consider the suggestions you have made. In fact, the hash could incorporate a random session ID (as I understood there is an attack against SPEKE where you create multiple concurrent sessions), but those are separate concerns – and therefore I was referring to a random base point.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">Your note about an ephemeral generator is apparently also orthogonal, right?<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">So to better understand your point, if for example the hash of the password has n bits of effective security, say 128, then we would leak one bit of the hash (not the password itself), correct? Put differently, how could this information practically be exploited? Is it a realistic attack today or e.g. a potential weakness that could be attacked using a quantum computer and a nuclear power plant in e.g. 20 years from now?<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">The question is, whether or not added code space, execution time and battery drain for eliigator2 are worth it, for our particular use case. Or would you consider the additional complexity negligible compared to X25519. For example on a Cortex-M4 (ATSAM4S8B) the scalar product requires 4kB flash and roughly 1.8M cycles using Wouter de Groot’s implementation. What would elligator2 add to this, assuming an implementation of similar quality – or even reusing the field primitives already present (as far as possible)?<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">Thanks again<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class="">Arasch<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div class=""><div style="border-style: solid none none; border-top-width: 1pt; border-top-color: rgb(225, 225, 225); 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" class="">Von:</span></b><span lang="EN-US" class=""><span class="Apple-converted-space"> </span>Curves [<a href="mailto:curves-bounces@moderncrypto.org" class="">mailto:curves-bounces@moderncrypto.org</a>]<span class="Apple-converted-space"> </span><b class="">Im Auftrag von<span class="Apple-converted-space"> </span></b>"Björn Haase"<br class=""><b class="">Gesendet:</b><span class="Apple-converted-space"> </span>Dienstag, 24. Oktober 2017 17:17<br class=""><b class="">An:</b><span class="Apple-converted-space"> </span><a href="mailto:curves@moderncrypto.org" class="">curves@moderncrypto.org</a><br class=""><b class="">Betreff:</b><span class="Apple-converted-space"> </span>[curves] Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?<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=""><span lang="EN-US" class=""><o:p class=""> </o:p></span></div><div class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Hi,<o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div></div><div name="quoted-content" class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">first of all, I agree that using a PAKE scheme for password-based authentication on zigbee networks is a good idea. Also, SPEKE-based protocols are IMHO the fastest choice available. Since SPEKE patents have expired, there is no need to avoid that the password itself enters the calculation of the generator, which was (IIUC) the main reason for the patent circumvention approach for that PACE has been developped.<o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Regarding the base point selection, I'd strongly recommend to use Elligator2 and not just the hash of the password. The reason is, that depending on your construction, you will at least leak one bit of the password. If you just use the hash, you will either be having a point on the curve or on it's twist and this information could be exploited.<br class=""><br class="">IMO there are a couple of things to consider when suggesting standardization: I'd recommend to combine the construction with use of a sound password hash, such as scrypt or argon2, mainly because it's likely that you will never enter the password on the small node. At least one should use PBKDF2 with a strong parameter set.<br class=""><br class="">The second thing is consideration of side-channel stuff. I'd advocate on using an ephemeral generator. This costs essentially one additional communication round, but this might be worth the effort, since you anyway might be having a communication telegram exchange before the actual PAKE scheme.<br class=""><br class="">When combining some ephemeral (and publicly known) random with the password hash for generating an ephemeral generator with Elligator2, you will be ending up with something very similar to our PACE paper at chess (</span><a href="https://eprint.iacr.org/2017/562.pdf" target="_blank" style="color: purple; text-decoration: underline;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">https://eprint.iacr.org/2017/562.pdf</span></a><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">).<br class=""><br class="">Note that the fact that you are using an ephemeral generator comes virtually at no added cost. I'd suggest to use a permutation or a hash for combining random values from both sides, and the password hash and feed the result into elligator2 to get an ephemeral generator. The patent circumvention step in our PACE paper (that forced us to use a symmetric cipher, in our case Salsa20, on top) is now no longer necessary.<br class=""><br class=""></span><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Yours,<br class=""><br class="">Björn<o:p class=""></o:p></span></div></div><div style="border-style: none none none solid; border-left-width: 1.5pt; border-left-color: rgb(195, 217, 229); padding: 0cm 0cm 0cm 8pt; margin: 7.5pt 3.75pt 3.75pt 7.5pt;" class=""><div style="margin-bottom: 7.5pt;" class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><b class=""><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Gesendet:</span></b><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> Dienstag, 24. Oktober 2017 um 14:03 Uhr<br class=""><b class="">Von:</b> "Arasch Honarbacht" <</span><a href="mailto:honarbacht@ubisys.de" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">honarbacht@ubisys.de</span></a><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">><br class=""><b class="">An:</b> </span><a href="mailto:curves@moderncrypto.org" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">curves@moderncrypto.org</span></a><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""><br class=""><b class="">Betreff:</b> [curves] SPEKE using Curve25519 - elligator2 required or recommended?<o:p class=""></o:p></span></div></div><div class=""><div class=""><div class=""><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Hi all,<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">I’m working on a proposal for key agreement in zigbee networks. The idea is to use SPEKE and Curve25519. My understanding is that Curve25519 accepts all 32-byte strings as valid public keys. Now, instead of the default base point 9, the base point is generated using a hash of the password. For argument’s sake, assume the base point would be a random number. I’ve implemented a test bench and tested this approach and it works well (for the small set of experiments I made, i.e. a couple of thousand executions).<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">The approach as it stands:<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Alice generates a secret a, Bob generates a secret b.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Alice computes P = aG and sends it to Bob. Bob computes Q = bG and sends it to Alice.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Alice computes k = aQ = abG. Bob computes k = bP = baG.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">When the base point G is chosen as one of the 12 points listed under the “contributory” behavior on Bernstein’s site (</span><a href="https://cr.yp.to/ecdh.html" target="_blank" style="color: purple; text-decoration: underline;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">https://cr.yp.to/ecdh.html</span></a><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">) the scalar products P and Q and the shared secret become zero – so these points need to be avoided.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Now, I saw in literature that reverse elligator2 mapping is used to map a random string to a Montgomery x coordinate u, e.g. instead of G simply being the hash, G = elligator2(hash), c.f. Figure 1 in this paper:<span class="Apple-converted-space"> </span></span><a href="https://eprint.iacr.org/2017/562.pdf" target="_blank" style="color: purple; text-decoration: underline;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">https://eprint.iacr.org/2017/562.pdf</span></a><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">, or section 2.6 here:<span class="Apple-converted-space"> </span></span><a href="https://signal.org/docs/specifications/xeddsa/" target="_blank" style="color: purple; text-decoration: underline;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">https://signal.org/docs/specifications/xeddsa/</span></a><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">.<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">My question is: Would a elligator2 mapping be required for the SPEKE use case outlined above, or is any point, except for the 12 points mentioned above suitable as a generator?<o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""> <o:p class=""></o:p></span></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Thanks, Arasch<o:p class=""></o:p></span></div></div><div style="margin: 0cm 0cm 0.0001pt; font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">_______________________________________________ Curves mailing list<span class="Apple-converted-space"> </span></span><a href="mailto:Curves@moderncrypto.org" style="color: purple; text-decoration: underline;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">Curves@moderncrypto.org</span></a><span style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""></span><a href="https://moderncrypto.org/mailman/listinfo/curves" target="_blank" style="color: purple; text-decoration: underline;" class=""><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class="">https://moderncrypto.org/mailman/listinfo/curves</span></a><span lang="EN-US" style="font-size: 9pt; font-family: Verdana, sans-serif;" class=""><o:p class=""></o:p></span></div></div></div></div></div></div></div></div><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">Curves mailing list</span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="mailto:Curves@moderncrypto.org" class="">Curves@moderncrypto.org</a></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="https://moderncrypto.org/mailman/listinfo/curves" class="">https://moderncrypto.org/mailman/listinfo/curves</a></span></div></blockquote></div><br class=""></div></body></html>