Subject: Re: [Cfrg] A note on how to (pre-)compute a ladder

From: Peter Dettman <[email-masked]>
Date: Sat, 1 Apr 2017 21:34:42 +0700

Hi Francisco,
Some more feedback:

- Typo: Alg. 5 line 12 has an X_R1 that should be U_R1.

- Typo: the Magma code (Appendix B) refers to "Sec. 6.2 of RFC7748", but
the Curve25519 test vectors are from 6.1.

- I've now implemented Alg. 5 in my RFC 7748 code (Java). I measure a
16% speedup for Curve25519 ECDH (i.e. 1 fixed + 1 variable) and 19% for
Curve448. Only about 100 lines of extra code per curve.

- My Curve448 implementation uses unsigned digits; subtraction is slower
than addition. The 2 subtractions involving A, B at lines 11-12 of Alg.
5 can be replaced by additions if the u_Pi coordinates are
(pre-)negated. Or instead of negating u_Pi, init Z_R1 and Z_R2 to -1,
then negate Z_R1 prior to the final doublings (line 16). It gives a
little over 1% further speedup here.

Regards,
Pete Dettman

On 30/03/2017 8:00 AM, Francisco Rodriguez- Henriquez wrote:
> Dear CFRG community,
> 
> We would like to draw your attention to our IACR pre-print entitled,
> 
> "A note on how to (pre-)compute a ladder
> Improving the performance of X25519 and X448"
> 
> https://eprint.iacr.org/2017/264.pdf.
> 
> For the point multiplication computation Q = kP, this note describes a
> right-to-left version of the Montgomery ladder, which is amenable for
> pre-computing multiples of the base point P. By requiring very modest
> memory resources and a small implementation effort, it obtains noticeable
> performance improvements with respect to the RFC 7748 classical ladder
> procedure.
> 
> We stress that our proposal fully complies with the RFC 7748
> specification, in the sense that given any arbitrary secret keys of
> Alice and Bob, our ladder generates exactly the same public keys that an
> implementation of the RFC 7748 would output.
> 
> As a way of illustration, in Appendix B of our note, we include a magma
> script, which given Alice and Bob private keys of RFC7748 Sec. 6.2, it
> computes the same public keys as specified in that document.
> 
> We would be delighted to receive feedback (including sightings of typos)
> from the CFRG community.
> 
> With best regards,
> 
> Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Francisco Rodriguez- Henriquez <[email-masked]>
Date: Mon, 3 Apr 2017 20:11:22 -0500 (CDT)

Hi Peter,

Thank you very much for your feedback!

Please see below for our interlined comments.

Cheers,
The authors

On Fri, 31 Mar 2017, Peter Dettman wrote:

> Hi Francisco,
>
> Seems like a nice performance win for key generation with very little
> extra effort over the variable-point ladder in RFC 7748.

Thanks!

> Would it be worth briefly addressing safe-error attacks?

Yes, indeed. A preliminary analysis could go along the following lines.

C safe-error attacks: The addition in [Alg. 4, Stp. 8] is not a dummy 
operation, but it is required for performing further R1 = R0 + R1
additions. Moreover, given that in the X25519 and X448 functions the most 
significant bit of the scalar k is always set k_(n-1) = 1, the last
iteration of [Alg. 4] performs the addition R1 = R0 + R1 (with R2 = R0 - 
R1). As a result, a computational fault induced at any iteration
in [Stp. 8] would produce an incorrect point Q.

M safe-error attacks: let M0 and M1 be memory addresses. The "cswap" 
function guarantees that every iteration of [Alg. 4] performs the
operation M0 <- R0 + M0 (with M1 = R0 - M0), where (M0, M1) contains (R1, 
R2) if k = 1 and (R2, R1) otherwise. Then, the attacker is only
able to modify the blocks of M0, which is not sufficient to deduce the 
bits of the scalar k. Most probably, for hardware implementations other
countermeasures should be taken, but they are similar to the ones applied 
on the classical Montgomery ladder.

On the other hand, as pointed out in previous messages in this forum, the 
"cswap" function does not protect against every side-channel threat.
Furthermore, as far as we know, the practical implications of safe-error 
attacks over the "cswap" function have not been studied yet.

> At first glance Algorithm 4 appears to not involve R2 in the final
> result, although it's made clear later in Algorithm 5 that both R1 and
> R2 are used in every addition due to the choice of addition formula.

You are right, the R2 is the difference R0 - R1.

> Remark 2 at the end of 5.1 presents this as a minor performance
> optimization, but fails to point out that it is needed to protect
> against safe-error attacks.

Using the improvements suggested by Peter Montgomery in his '87 paper, we 
have the following formulas:

U3 <- Z2*((U1+Z1) + A*(U1-Z1))^2
U3 <- U2*((U1+Z1) - A*(U1-Z1))^2
with A = (U0+Z0) and Z0 = 1/(u-1), U0 = x*Z0. /* all operations 
pre-computed */

Here, the coordinates of R2 are used too. Consequently, the advantage of 
the formulas listed in Remark 2 is actually the savings of two
field additions.

> Pete Dettman

Thanks for the comments!

---

From: Francisco Rodriguez- Henriquez <[email-masked]>
Date: Mon, 3 Apr 2017 20:14:21 -0500 (CDT)

> the Curve25519 test vectors are from 6.1.

Thanks, corrections done!

> Curve448. Only about 100 lines of extra code per curve.

That is great news!, the improvements are within the range of our 
estimations :)

> little over 1% further speedup here.

We've checked your suggestion, and indeed your trick looks quite 
interesting. We think that the best option would be to pre-compute the u 
coordinates as -uPi, because this would involve no extra programming 
effort.

Thanks again for your feedback.

Cheers!
The authors