<html><body><span class="xfm_40183439">Thanks all!<br/><br/>Katriel Cohn-Gordon, I'm sorry, I assumed checking A'!=B! but not include this in trascription.<br/>Of cource, UKS protecting also can be achived including IDs into hashing.<br/><br/><br/>Mike Hamburg, ops, it is a real dictionary attack! <br/>Now I see SPEKE paper:<br/>https://eprint.iacr.org/2014/585.pdf<br/>The difference only in key deriving function: f(s) = (H(s))^ 2 mod p;<br/>Can I applied this to curve?<br/><br/>And now I find this thread:<br/>https://moderncrypto.org/mail-archive/curves/2017/000940.html<br/>My problem is closely same: I use Cortex M0 with limited program code memory so small for Edvards Ed25519.<br/>I havn't elligator's C code for Montgomery 25519: I have only EC25519 refference DJB's code with only mul() and mul_base() in my system.<br/>And also have Keccak Sponge as near "ideal" hash, mac and crypt (like Shake-128).<br/> <br/>Is it possible to design any safe PKE in this environment? Maybe even with extra passes and decreasing computation efficiency but without any additional math.<br/><br/><div style="font-size:0.9em;font-style:italic;"> --- Original message ---<br/> From: "Ben Harris" <mail@bharr.is><br/> Date: 25 January 2018, 10:46:03<br/></div> <br/><blockquote class="xfmc1" style="border-left:1px solid rgb(204, 204, 204);margin:0px 0px 0px 0.8ex;padding-left:1ex;"><span><span><div dir="ltr">If I have this right (??), the attack is:<div><br/></div><div>Alice sends A which is equivalent to a*c*G.</div><div>Mallory takes A and multiplies by random b and sends back B as b*G.</div><div>Alice computes S as a*B = a*b*G and sends MA as H(A | B | S).</div><div><br/></div><div>Mallory now guesses a password to compute c'. She then computes a guess S' as (1/c')*b*A = (1/c')*b*a*c*G. If c' == c then this is a*b*G and S' == S.</div><div>Mallory checks S' by computing H(A | B | S') and comparing to MA.</div></div><div class="xfmc2"><br/><div class="xfmc3">On 25 January 2018 at 07:56, Mike Hamburg <span dir="ltr"><<a href="mailto:mike@shiftleft.org" target="_blank" rel="noreferrer noopener">mike@shiftleft.org</a>></span> wrote:<br/><blockquote class="xfmc3" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div>Er, you would compute A’ = mul(8*a, elligator(c)). That is, you don’t also have to multiply by c.<div><br/></div><div>Whoops,</div><div>— Mike<div><div class="xfmc4"><br/><div><br/><blockquote type="cite"><div>On Jan 24, 2018, at 12:56 PM, Mike Hamburg <<a href="mailto:mike@shiftleft.org" target="_blank" rel="noreferrer noopener">mike@shiftleft.org</a>> wrote:</div><br class="xfmc5"/><div><div>It’s not safe against dictionary attacks by Alice or Bob. For that, you want SPEKE, SPAKE2, PAK, …<div><br/></div><div>This is a variant of SPEKE. To make it secure you would compute A = mul(8*a, elligator(c)) and B = mul(8*b, elligator(c)) instead of what you have here, and also hash elligator(c) in the final MA/MB computation, in addition to adding identities or something to address Katriel’s concern.</div><div><br/></div><div>— Mike</div><div><div><br/><blockquote type="cite"><div>On Jan 24, 2018, at 3:37 AM, Katriel Cohn-Gordon <<a href="mailto:me@katriel.co.uk" target="_blank" rel="noreferrer noopener">me@katriel.co.uk</a>> wrote:</div><br class="xfmc5"/><div><div style="font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:georgia,serif;">What does "safe" mean in this context?<br/></div><div style="font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:georgia,serif;"><br/></div><div style="font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:georgia,serif;">For example, an adversary could reflect Alice's initial message back to Alice, and then reflect the hash back as well. The result is that Alice will complete a protocol execution without Bob even existing. Is that bad?<br/></div><div style="font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:georgia,serif;"><br/></div><div style="font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:georgia,serif;">Katriel</div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;"><br/></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;"><br/></div><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;">On Wed, 24 Jan 2018, at 10:45 AM, Van Gegel wrote:<br/></div><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;"><div style="font-family:georgia,serif;"><span>Hi all!<br/>Please advise on this protocol:<br/><br/>Two parties comparing 2 bytes short common secret using EC25519 (only mul and mul_base procedures) and SHA3 hash.<br/>Any side can be active adversary trying obtain secret.<br/><br/>c = H(secret)<br/><br/>Side A:<br/>- picks a at random<br/>- computes A = mul_base(a)<br/>- computes A' = mul(c, A)<br/>- sends A' to side B<br/><br/>Side B:<br/>- picks b at random<br/>- computes B = mul_base(b)<br/>- computes B' = mul(c, B)<br/>- sends B' to side A<br/><br/>Side A:<br/>- computes S = mul(a, B')<br/>- sends MB=H(A' | B' | S) to side A<br/><br/>Side B:<br/>- computes S= mul(b, A')<br/>- sends MA=H(B' | A' | S) to side B<br/><br/>Both A and B checks MA and MB.<br/><br/>Is this protocol safe?<br/></span></div><div><u>______________________________<span>_________________</span></u><br/></div><div>Messaging mailing list<br/></div><div><a href="mailto:Messaging@moderncrypto.org" target="_blank" rel="noreferrer noopener">Messaging@moderncrypto.org</a><br/></div><div><a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank" rel="noreferrer noopener">https://moderncrypto.org/<span>mailman/listinfo/messaging</span></a><br/></div></blockquote><div style="font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-family:georgia,serif;"><br/></div><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important;">______________________________<span>_________________</span></span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;"/><span style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;float:none;display:inline!important;">Messaging mailing list</span><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;"/><a href="mailto:Messaging@moderncrypto.org" style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;" target="_blank" rel="noreferrer noopener">Messaging@moderncrypto.org</a><br style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;"/><a href="https://moderncrypto.org/mailman/listinfo/messaging" style="font-family:Helvetica;font-size:12px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;" target="_blank" rel="noreferrer noopener">https://moderncrypto.org/<span>mailman/listinfo/messaging</span></a></div></blockquote></div><br/></div></div></div></blockquote></div><br/></div></div></div></div><br/>______________________________<span>_________________<br/> Messaging mailing list<br/><a href="mailto:Messaging@moderncrypto.org" target="_blank" rel="noreferrer noopener">Messaging@moderncrypto.org</a><br/><a href="https://moderncrypto.org/mailman/listinfo/messaging" rel="noreferrer noopener" target="_blank">https://moderncrypto.org/<span>mailman/listinfo/messaging</span></a><br/><br/></span></blockquote></div><br/></div></span><span><pre>_______________________________________________ Messaging mailing list <a href="mailto:Messaging@moderncrypto.org" target="_blank" rel="noreferrer noopener">Messaging@moderncrypto.org</a> <a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank" rel="noreferrer noopener">https://moderncrypto.org/mailman/listinfo/messaging</a> </pre></span></span></blockquote> </span></body></html>