[curves] New curve25519/ed25519 library

[Michael Hamburg]

I should add to this that I haven’t actually seen a complete comb implementation for Curve25519 before, though there might be one somewhere.  I think Donna (including Floodyberry’s Donna fork) uses the older windowed technique.  So if you make a nicely tuned implementation, you will be the first.  I’m working on one as well, but it uses Decaf so it won’t be directly compatible with curve25519.

To tune your comb implementation, here are a few ideas:

1) As Peter said, you should probably use constant-time lookups for signing, though it isn’t necessary for verification.  This will limit you to a smaller table.

2) Signed binary uses half the table space vs unsigned binary, and also is half as expensive if you’re using constant-time lookups.  You can convert a scalar to signed binary by adding a certain constant (2^width-1 IIRC) and halving mod the curve order.

3) Using multiple tables (so the inner loop is double; add; add; add) lets you reduce the number of doubles without making the tables too wide.

4) For any given size, there's a tradeoff between more tables and bigger tables.  You can optimize that tradeoff with a simple script or spreadsheet.

Cheers,
— Mike

> On Jun 30, 2015, at 10:56 AM, Mike Hamburg <mike at shiftleft.org> wrote:
> 
> Hi Mehdi,
> 
> I think your "folding" trick has been invented and re-invented many times.  I came up with it in 2012, and thought it should be called "combs".  I Googled the term, and found that Pippenger invented it in 1979. Lim and Lee reinvented it in 1994. Hankerson-Menezes-Vanstone improved it in 2004 (by using multiple tables), as did Hedabou (by using signed all-bits-set binary); Feng et al published a different version in 2006 (signed-MSB-set).  The first Ed25519 implementation used a less efficient, non-combed variant of the same technique.
> 
> Some of the variants are patented, too, but I think your variant is similar to Lim-Lee and so should probably be out of patent by now.
> 
> I think the best variant these days is to combine the 2004 techniques: multiple combs, signed-all-bits-set.  It's simpler than signed-MSB-set, and I think it's the fastest once you have the table.  The table is slightly slower to compute than signed-MSB-set, which makes that algorithm better in a few limited circumstances, but SMSBS is also patented (by Microsoft) and SABS is unpatented to the best of my knowledge.
> 
> You're right that fixed-point techniques can be useful for verification and not just signing.  For example, in a vehicle-to-vehicle setting, you will see many signed messages from each car going the same direction as you.  Verification latency is important, so precomputing a small table on another core may be worthwhile if memory permits.  A small table can be worthwhile even for only 2 signatures, and a larger one for 3.
> 
> -- Mike
> 
> On 06/30/2015 10:26 AM, Peter Schwabe wrote:
>> Mehdi Sotoodeh <mehdisotoodeh at gmail.com> <mailto:mehdisotoodeh at gmail.com> wrote:
>> 
>> Dear Mehdi,
>> 
>>> I would like to introduce a remarkable implementation of x25519 and ed25519
>>> library. The sources are hosted at: https://github.com/msotoodeh/curve25519 <https://github.com/msotoodeh/curve25519>
>>> 
>>> The code is experimental but rather stable. It is compact, portable
>>> and uses simple design logic.  On the security front, it employs
>>> several measures for side-channel security.
>> I only took a quick look at the software, but two things immediately
>> caught my eye. 
>> 
>> The first aspect is that the Curve25519 implementation uses secretly
>> indexed memory access which is a possible source for timing attacks.
>> State-of-the-art Curve25519 implementations avoid this by using
>> constant-time conditional swaps.
>> Similar statements apply to the table lookup in the fixed-basepoint
>> scalar multiplication, but those would be much more expensive to
>> protect.
>> 
>>> But the most remarkable feature is speed. This library sets new speed
>>> records. It uses a new technique I call it FOLDING for achieving this goal.
>>> FOLDING chops the scalar multiplier into n pieces (or folds) and operates
>>> on the folds simultaneously reducing number of point operations by a factor
>>> of 4 or 8. For example, ed25519 signature takes 31 point doubling and 31
>>> point additions.
>> The second thing is: It's great to hear about new speed records!
>> Are you planning to support the SUPERCOP API and submit to eBATS so that
>> the software can be publicly benchmarked on a large bunch of computers?
>> My understanding is that the technique that you call folding is only
>> efficient for signing; the verification part needs a precomputation
>> which is just way too expensive: it needs 384 point doublings! You will
>> probably answer that the ed25519_Verify_Init needs to be done just once
>> for many verifications, but then a huge expanded public key is sitting
>> around in memory and if I'm not totally mistaken, a sliding-window
>> method would still be faster. 
>> 
>> Best regards,
>> 
>> Peter
>> 
>> 
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org <mailto:Curves at moderncrypto.org>
>> https://moderncrypto.org/mailman/listinfo/curves <https://moderncrypto.org/mailman/listinfo/curves>
> 
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150630/48e4dbf6/attachment.html>