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

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.

> Regards,
> Pete Dettman

Thanks for the comments!

> 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
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>