[messaging] sign(y) for Elligator2_p2r from X25519 u-points

[Van Gegel]

Sorry, Trevor Perrin!
I was not registered in the curves maillist. I just registered and now will be ask related questions in curves.

Thank you, Mike Hamburg!  Your advise was very useful for me.
Now I try to add a complete elligator2 (both r2p and p2r functional)  to the standard X25519 M0 and M4 library for future use (for example, uncensorable IKE).
But there is a problem. The main advantage of X25519 is a very simple and reliable interface for the user preventing implementation errors. The lower three bits of the scalar are zeroed internally implicitly for the user. But this seems does not work to get a random value: the points are in subgroup. The same problem was with the implementation of a two-point EC-EKE: seems impossible to do this using only the standard X25519 library functions. Of course, multiplying by 8 can be skipped easy, but this requires editing the library code to get a special mul_base function for this case, and also can require verification of the receiving points (or multiplication results). This is not a problem in general but can be not so clear for users. 

For my current project for small-resource Cortex M0, I use SPEKE and implement a compact Hash2Point  based on your isr() and uNaCl X25519 asm library:
I computes a point candidate x=-A/(2r^2+1), then compute curve equation y^2 = x^3 + Ax^2 + x and then use 02^254-10 part of your code to selects x or -A-x depends y is a root.
It require 6 field values in stack and produce about 400 bytes of code. I was check constant time on M0 using system ticks and compare some vectors with twitamber library https://github.com/bernedogit/amber run on PC, all are OK.
This seems to be the simplest solution to password authentication.

Van Gegel

--- Original message ---
From: "Mike Hamburg" <mike at shiftleft.org>
Date: 14 March 2018, 18:59:36


Hello Van Gegel,

You must select sign(v), the sign of the square root, and bit 255 all at random, and the point can’t be confined to a subgroup of curve25519.

But also, this is for a PAKE right?  I thought you were implementing a two-point EKE to avoid Elligator.  If you’re implementing Elligator, why not use SPEKE, where you would only need the forward direction?

— Mike

Sent from my phone.  Please excuse brevity and typos.

> On Mar 14, 2018, at 05:46, Van Gegel <torfone at ukr.net> wrote:
> 
> Hello, Messaging!
> 
> I'm trying to adapt Elligator2 p2r()  to the uNaCl X25519 library for embedded systems. 
> The original p2r() uses the sign(v)  to select between sqrt(-u/(2(u+A))) and sqrt(-(u+A)/(2u))) . 
> But X25519 point has no v  ( sign(v) is always assumed to be 0 ). 
> Can I use sign(v)=0 or must select the sign(v) randomly to get a completely random representation string of X25519 u-point with p2r()?
> 
> Thanks, 
> Van Gegel.
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging

_______________________________________________
Messaging mailing list
Messaging at moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180315/8b4f82c5/attachment.html>