[curves] pure-python Ed25519 library for review

[Ron Garret]

Is there a reason you don’t just use DJB’s reference implementation?

http://ed25519.cr.yp.to/python/ed25519.py

On Apr 7, 2015, at 11:55 AM, Brian Warner <warner at lothar.com> wrote:

> Hi folks.. I could use some extra eyeballs on a pure-python library I
> put together to do Ed25519 operations:
> 
>  https://github.com/warner/python-pure25519
> 
> Of course it's very much not constant-time, and a lot slower than a C
> implementation. But a pure-python library is, in practice, much easier
> to depend upon than one that requires a C compiler.
> 
> And it's not unusably slow. If you run "python setup.py speed" in that
> tree, you'll get the speed-test results. On my machine (2.6GHz i7), I'm
> getting SUPERCOP-compatible Ed25519 sign/verify times of 2.8ms and
> 10.5ms .
> 
> I'm writing this to support a pure-python SPAKE2 library, for which I'm
> seeing each phase of the protocol take about 5-8ms.
> 
> I'm especially looking for feedback on the arbitrary_element() function,
> which provides SPAKE2 with the unknown-discrete-log group elements U and
> V (or M and N depending on which paper you read). That function is
> paraphrased here:
> 
> https://github.com/warner/python-pure25519/blob/master/pure25519/basic.py#L261
> 
> 
> def arbitrary_element(seed): # unknown DL
>     hseed = hashlib.sha512(seed).digest()
>     y = int(binascii.hexlify(hseed), 16) % Q
>     for plus in itertools.count(0):
>         y_plus = (y + plus) % Q
>         x = xrecover(y_plus)
>         Pa = [x,y_plus]
>         if not isoncurve(Pa):
>             continue
>         P = ElementOfUnknownGroup(xform_affine_to_extended(Pa))
>         P8 = P.scalarmult(8)
>         if is_extended_zero(P8.XYTZ):
>             continue
>         assert is_extended_zero(P8.scalarmult(L).XYTZ)
>         return Element(P8.XYTZ)
>     # never reached
> 
> ("Q" is 2**255-19, and xrecover() does what you'd expect)
> 
> What this code is doing and why:
> 
> * oversized hash (sha512) and reduction, to avoid any significant bias.
>  I'm pretty sure this doesn't matter for SPAKE2, but it seemed
>  appropriate. Should I remove this? Does Elligator avoid bias?
> * test isoncurve(P), increment-and-try-again if not. I find that about
>  50% of Y-coords result in not-on-curve points. I assume these points
>  are actually on the "twist", and that some protocols can run faster by
>  ignoring this fact, but I don't know enough to safely do the same.
> * multiply by 8 to force any points of order 2*L/4*L/8*L into the proper
>  order=L subgroup. It also forces points of order 1/2/4/8 into the
>  identity element (zero)
> * test against zero, which rejects points of order 1/2/4/8. I'm not sure
>  if I need to be worried about these: I suspect they're vanishingly
>  unlikely to happen. The full version has a large comment about my
>  probably-flawed beliefs of how common these points are, and I think
>  there are at most 8 of them.
> 
> The rest of that file defines addition and multiplication functions
> (using "extended" coordinates, XYTZ) and some object-oriented wrappers
> to make application code easier/safer. In the process of testing, I
> found a need for that ElementOfUnknownGroup, to exercise point math on
> things like the identity and the point of order 2. Most applications
> would stick to the correct-group-order Element class instead.
> 
> The repo includes a compatible implementation of Ed25519 signatures, a
> demo DH-key-agreement routine (functionally equivalent to Curve25519 but
> not interoperable with it), and a SPAKE2 implementation that I intend to
> use in another project I'll be asking y'all to review shortly.
> 
> The bytes_to_element() function does full is-this-in-the-right-group
> point validation, which slows things down by 2-4ms. It'd be nice to
> remove that for the protocols that were designed to not need it
> (Ed25519/Curve25519 clear the cofactor in other ways), but I don't
> understand the issues well enough to feel confident removing it. Plus, I
> don't want to leave a trap for later users of the library. Perhaps I'll
> add a function named bytes_to_8_times_element() that multiplies instead
> of validating.
> 
> An interesting side discussion would be how/where to speed up SPAKE2
> with these same tricks. Maybe instead of X=G*a+U*pw. Y=G*b+V*pw.
> Z1=(Y-V*pw)*a. Z2=(X-U*pw)*b, you'd do?:
> 
>  X=G*a+U*pw. Y=G*b+V*pw. Z1=(Y*8-V*pw*8)*a. Z2=(X*8-U*pw*8)*b
> 
> Anyways, any and all feedback is welcome. Let me know what you think!
> 
> cheers,
> -Brian
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves