Subject: Re: [Cfrg] How to (pre-)compute a ladder [full C implementation]

From: Francisco Rodriguez- Henriquez <[email-masked]>
Date: Fri, 14 Jul 2017 14:28:56 -0500 (CDT)

Dear CFRG community,

We would like to share with you a full C implementation of the 
ladder procedure described in the IACR pre-print 2017/264:

        "How to (pre-)compute a ladder"

The C code can be downloaded from,
https://github.com/armfazh/rfc7748_precomputed

We are reporting the following benchmarked timings for 64-bit Intel 
architectures (table entries are given in clock cycles),

X25519 				Haswell 	Skylake
proposed Keygen rtl ladder	 90,895 	 72,571
Shared secret 	 		138,962 	107,942
S.Secret/Keygen speedup		  1.529	          1.487
overall D-H speedup               1.209           1.196

X448				Haswell 	Skylake
Proposed Keygen rtl Ladder	401,902 	322,040
Shared Secret 			670,747 	528,470
S.Secret/Keygen speedup           1.668           1.641
overall D-H speedup               1.251           1.243

Notes:

+ The Key generation reported above was computed using the proposed
   right-to-left ladder
+ The Shared secret was computed using the procedure described in the RFC
   7748 memo
+ The D-H speedup is obtained as the ratio,
 		2*shared secret / (shared secret + key generation);
+ In the sense explained in our pre-print, our procedure fully complies
   with the RFC 7748 memo.

With best regards,
Thomaz Oliveira, Julio López, Hüseyin Hisil, Armando Faz-Hernández and 
Francisco Rodríguez-Henríquez

On Thu, 11 May 2017, Francisco Rodriguez- Henriquez wrote:

> Dear CFRG community,
>
> We would like to draw your attention to an improved version of our IACR 
> pre-print 2017/264 now entitled:
>
> 	"How to (pre-)compute a ladder"
>
> In this revised version, we present an improved differential addition formula 
> that uses pre-computation to match the computational cost of the classical 
> Montgomery differential addition.
>
> Accordingly, our estimates suggest that a full implementation of our 
> pre-computable ladder proposal should outperform state-of-the-art software 
> implementations of the X25519 and X448 functions by a 40% speedup when 
> working in the fixed-point scenario.
>
> We would be delighted to receive feedback (including sightings of typos) from 
> the CFRG community.
>
> With best regards,
>
> Thomaz Oliveira, Julio López, Hüseyin Hisil and Francisco Rodríguez-Henríquez

---

From: Francisco Rodriguez- Henriquez <[email-masked]>
Date: Fri, 14 Jul 2017 14:33:48 -0500 (CDT)

Hi Peter,

Please see my reply below.

Cheers,
Francisco
[on behalf of the authors]

On Fri, 16 Jun 2017, Peter Dettman wrote:

> Hi Francisco,
>
> I've updated my (java) implementations of X25519 and X448 in line with
> your revised paper. My rough benchmark results for a complete ECDH are
> -17.7% and -19.5% time required for X25519 and X448 respectively.

Great!
This is roughly in the same ballpark of what we are getting in our C 
implementation, which is available at,

[please check my previous email to this list]

> These are perhaps slightly more modest than the paper's estimates. Your
> paper already anticipates that (uncounted) field add/sub are significant
> in practice.

Right!

This effect appears to be more significant in the case of X25519 than in 
the case of X448.

> Part of the difference however is that my implementation of Algorithm 3
> handles the final 'q' bits using simple doublings, and removes redundant
> cswaps - just as Algorithm 5 does. Of course Alg. 3 is just as presented
> in RFC 7748, but it might be a fairer comparison to first apply to Alg.
> 3 those of your optimizations that are applicable.
>
> Also, my (32-bit) X448 implementation (Alg. 5) required a carry
> propagation for 'A' (line 10), due to tight bounds on limbs when
> squaring D, E. I did the same for (32-bit) X25519 although I haven't yet
> proved it necessary.

OK!
If you have time please compare against the C implementation mentioned 
above.

> An idea: for fixed-base X25519, why not precompute one doubling? i.e.
> just calculate (k/2) * 2P, needing only 2 final doublings (you even
> already have S of order 4). I am not sure whether this extends to
> precomputing (q-1) doublings.
>
> Another thought that occurred to me is that someone might get the idea
> to use your fixed-base ladder with some other point. Couldn't this go
> awry if that point were already "P + S" or similar? If so, a caution
> somewhere in the paper on preconditions for the fixed point might be
> advised.
>
> Regards,
> Pete Dettman

Thanks for both suggestions. We will carefully analyze both of them.

Cheers,
Francisco

---

From: Francisco Rodriguez- Henriquez <[email-masked]>
Date: Fri, 14 Jul 2017 14:54:26 -0500 (CDT)

On May 12, 2017, at 2:15 PM, Mike Hamburg <[email-masked]> wrote:

> Hello Francisco et al,

> This is a clever and useful piece of work.  It's a good intermediate 
> between just using the standard Montgomery ladder for everything, and 
> going to a full Edwards implementation with combs or something.  It 
> especially seems useful where power analysis resistance is required, 
> because other precomputation methods usually aren't suitable.  The RTL 
> Montgomery ladder (or Joye double-add ladder) is already known to be 
> useful in this situation, at least with some modification to prevent 
> coordinates from staying the same between iterations.  Since you're 
> speeding up the RTL Montgomery ladder, your optimization can slot right 
> in to some implementations.

Hi Mike,

Thanks for your comments and sorry for this really slow reply :)

I agree with you about the fact that the RTL Montgomery ladder by Joye was 
already known for performing this feature.

> You should probably compare to existing Edwards precomputation methods 
> in your paper, since they are the likely alternative to your technique. 
> In particular, I noticed that you compared against the EBACS version of 
> Ed448-Goldilocks.  With a fixed base point, your method uses 41% less 
> time for the Montgomery ladder with a 25kiB table.  However, the EBACS 
> version of Ed448-Goldilocks doesn't use the Montgomery ladder for 
> fixed-base scalarmul.  Instead it uses a combs algorithm, which uses a 
> 15kiB table and takes about 70% less time than the Montgomery ladder; 
> see https://bench.cr.yp.to/results-dh.html.  Libdecaf likewise uses 
> precomputed combs for fixed-base scalarmul.  But your new technique is 
> certainly simpler.

I agree with you, there are faster methods to perform pre-computation, 
which offer [some] protection against side-channel attacks.

In our work, we were specifically targeting the RFC 7748 Memo, and hence 
we only meant to compare against ladder procedures for computing the 
scalar multiplication.

I believe that the tradeoffs between the simplicity/elegance/beauty of 
the ladders Vs. the efficiency of regular recoding + other methods of 
pre-computation, was already debated in this list :)

Cheers,
Francisco

> -- Mike