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

From: Jerry Zhu <[email-masked]>
Date: Wed, 19 Jul 2017 08:34:46 +0000

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?

Thanks
-Jerry Zhu (Ext. 41218)

-----------------------------------------------------------------------------------
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.
-----------------------------------------------------------------------------------

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 19 Jul 2017 13:02:25 +0300

> 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

---

From: Jerry Zhu <[email-masked]>
Date: Thu, 20 Jul 2017 06:28:16 +0000

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: [email-masked] [mailto:[email-masked]] 
Sent: Wednesday, July 19, 2017 6:02 PM
To: Jerry Zhu <[email-masked]>
Cc: [email-masked]
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
> 

> 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.

Let L = 2^252 + k.

Let r1 = h1 * 2^252 + l1

Let r2 = h2 * 2^256 + l2

Let L = 2^446 - k.

Let r3 = h3 * 2^446 + l3

Let r4 = h4 * 2^448 + l4

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 20 Jul 2017 11:07:58 +0300

> Isn't there repudiation risk if k is leaked to adversary?

k is computable from context[1], message, signature and the public
key. And in fact, k is reconstructed in signature verification.

[1] Contexts turn out to be pretty much useless except for generating
time-wasting discussion...

-Ilari

---

From: Jerry Zhu <[email-masked]>
Date: Thu, 20 Jul 2017 08:34:11 +0000

Learned new knowledge. Thank you. 

Thanks
-Jerry Zhu (Ext. 41218)

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] 
Sent: Thursday, July 20, 2017 4:08 PM
To: Jerry Zhu <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cfrg] RFC 8032: Question on Side-Channel Leaks

> Isn't there repudiation risk if k is leaked to adversary?

k is computable from context[1], message, signature and the public key. And in fact, k is reconstructed in signature verification.

[1] Contexts turn out to be pretty much useless except for generating time-wasting discussion...

-Ilari