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

[Ilari Liusvaara <[e-mail]>]

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