[curves] curve25519-donna stack usage

[Mike Hamburg]

> On Dec 9, 2016, at 11:03 AM, Thomas DuBuisson <thomas.dubuisson at gmail.com> wrote:
> 
> On Fri, Dec 9, 2016 at 10:52 AM, Mike Hamburg <mike at shiftleft.org> wrote:
>> OK, I’ve released my tiny x25519 code as open source.
> 
> Do you think it would be worth proving equivalence of your code with
> another implementation, such as -donna?  If so, how similar are the
> structures and fundamental operations?
> 
> -Thomas

Lots of things are worth proving if you’re not the one doing it :-)

Seriously though.  Donna uses unsaturated arithmetic, but my code uses saturated arithmetic to save memory, and because on some platforms like ARM that’s more efficient anyway.  So I’d have to check mainly against carry-handling bugs.

My code uses a very similar formula for the ladder step to Donna.  However, it uses the modified condswap schedule from RFC 7748 (a trivial change), and it recomputes BB = AA-E to save memory.

My code uses a different power chain than Donna for the inversion.  With X25519_USE_POWER_CHAIN set, it uses a power chain that’s 2M longer but uses one fewer temporary, again to save memory.  Without that flag, it uses a slower algorithm (square and usually multiply) that saves code size.

In sum, it should be possible to verify it using gfverif, but it might be easier to just show equivalence to some master Python or SAGE implementation instead of donna.

— Mike

>> This is the
>> platform-agnostic version.  The ARM asm version isn’t there, it’s staying
>> proprietary for now :-/.  But you can get most of the effect by
>> intrinsic’ing umaal and friends.
>> 
>> https://sourceforge.net/p/strobe/code/ci/master/tree/x25519.c
>> https://sourceforge.net/p/strobe/code/ci/master/tree/x25519.h
>> 
>> Presumably this code could be accelerated somewhat by using a dedicated
>> sqr() routine, or by unrolling loops and inlining code.  Maybe I’ll get
>> around to that at some point, but there’s a bunch more to be done with that
>> repository to make it useful.
>> 
>> These files also have a totally nonstandard signature implementation, the
>> only real advantage of which is that it adds very little code.
>> 
>> Let me know what you think, or if you find any bugs or missing features.
>> 
>> Cheers,
>> — Mike
>> 
>> On Nov 9, 2016, at 4:13 PM, Jason A. Donenfeld <Jason at zx2c4.com> wrote:
>> 
>> I just tried out the so called "tweet nacl implementation", because it
>> has very tiny stack requirements. It was 26 times slower than donna.
>> Wow!
>> 
>> 
>> 
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves
>> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3693 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161209/4c598c25/attachment.bin>