Re: [Cfrg] RFC 8032: Question on Side-Channel Leaks

[Jerry Zhu <[e-mail]>]

Hi Ilari,

Appreciate your response and sample implementation. 
Isn't there repudiation risk if k is leaked to adversary?

Thanks
-Jerry Zhu (Ext. 41218)

-----Original Message-----
From: [e-mail] [mailto:[e-mail]] 
Sent: Wednesday, July 19, 2017 6:02 PM
To: Jerry Zhu <[e-mail]>
Cc: [e-mail]
Subject: Re: [Cfrg] RFC 8032: Question on Side-Channel Leaks

On Wed, Jul 19, 2017 at 08:34:46AM +0000, Jerry Zhu wrote:
> Dear RFC experts,
> 
> I am an engineer in Nvidia. When reading below statement in 
> https://tools.ietf.org/html/rfc8032#section-8.1
> 
> "To make an implementation side-channel silent in this way, the modulo p arithmetic must not use any data-dependent branches, e.g., related to carry propagation."
> 
> Does the 'modulo p' refer to a generic prime number, or the prime number defining GF(p) e.g. 2^255-19 for Ed25519?
> I am asking this because some modulo arithmetic in  Ed25519 Sign is against  L, not p.

> 
> "5.  Compute S = (r + k * s) mod L.  For efficiency, again reduce k modulo L first."
> I think this computation shall also be side channel silent to keep confidentiality of k.
> 
> Could you please clarify?
> 

Looks like the section concentrates on elliptic curves and forgets the scalar (mod L) computations.

However, there are much less computations modulo L than mod p. So even relatively dumb implemenantion does not affect speed very much.

k is AFAIK not secret.



The way I coded the mod L calculations was:

- The multiplication and addition are ordinary integer operations, done
  on constant number of words for being constant-time.
- There are specialized routines for partially reducing from "double
  width" (e.g., 512 bits for 25519) to "single width" (e.g., 255 bits).
- Then there is specialized full reduction routine (e.g., from 256 bits
  to ~252 bits).

The ladder the code uses to reduce numbers uses the following:

Let L = 2^252 + k.

Let r1 = h1 * 2^252 + l1

Then r1 = l1 - k * h1 = x1*L + l1 - k * h1 (mod L).

Choose x1 to be big enough so that the expression is always positive.

Let r2 = h2 * 2^256 + l2

Then r2 = l2 - 16k * h2 = x2*L + l2 - 16k * h2 (mod L).

Choose x2 to be big enough so that the expression is always positive.



Let L = 2^446 - k.

Let r3 = h3 * 2^446 + l3

Then r3 = l3 + k * h3 (mod L).

Let r4 = h4 * 2^448 + l4

Then r4 = l4 + 4k * h4 (mod L).


These formulas rather rapidly can reduce the numbers, eliminating half of the bits in about three rounds, with the last round having single-word multiplication.

For full reductions, one needs one round followed by conditional substraction (which takes some care to do in constant time).



-Ilari

-----------------------------------------------------------------------------------
This email message is for the sole use of the intended recipient(s) and may contain
confidential information.  Any unauthorized review, use, disclosure or distribution
is prohibited.  If you are not the intended recipient, please contact the sender by
reply email and destroy all copies of the original message.
-----------------------------------------------------------------------------------