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

Jerry Zhu <jezhu@nvidia.com> Thu, 20 July 2017 06:28 UTC

Return-Path: <jezhu@nvidia.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6F88B129B34 for <cfrg@ietfa.amsl.com>; Wed, 19 Jul 2017 23:28:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id WeviSIB3we22 for <cfrg@ietfa.amsl.com>; Wed, 19 Jul 2017 23:28:20 -0700 (PDT)
Received: from nat-hk.nvidia.com (nat-hk.nvidia.com [203.18.50.4]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6E6891289B0 for <cfrg@irtf.org>; Wed, 19 Jul 2017 23:28:20 -0700 (PDT)
Received: from hkpgpgate102.nvidia.com (Not Verified[10.18.92.9]) by nat-hk.nvidia.com id <B59704d7f0000>; Thu, 20 Jul 2017 14:28:15 +0800
Received: from HKMAIL104.nvidia.com ([10.18.16.13]) by hkpgpgate102.nvidia.com (PGP Universal service); Wed, 19 Jul 2017 23:28:18 -0700
X-PGP-Universal: processed; by hkpgpgate102.nvidia.com on Wed, 19 Jul 2017 23:28:18 -0700
Received: from HKMAIL103.nvidia.com (10.18.16.12) by HKMAIL104.nvidia.com (10.18.16.13) with Microsoft SMTP Server (TLS) id 15.0.1263.5; Thu, 20 Jul 2017 06:28:16 +0000
Received: from HKMAIL103.nvidia.com ([fe80::f5ae:f43f:ff37:8c85]) by HKMAIL103.nvidia.com ([fe80::f5ae:f43f:ff37:8c85%19]) with mapi id 15.00.1263.000; Thu, 20 Jul 2017 06:28:16 +0000
From: Jerry Zhu <jezhu@nvidia.com>
To: "ilariliusvaara@welho.com" <ilariliusvaara@welho.com>
CC: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] RFC 8032: Question on Side-Channel Leaks
Thread-Index: AdMAahSpyutm7k8jSgmJRdRK3qusBgADApWAACrHtzA=
Date: Thu, 20 Jul 2017 06:28:16 +0000
Message-ID: <ef5c39e7ac904c0f806eb2a3be1f0384@HKMAIL103.nvidia.com>
References: <6fa65bd5e4ce454ba871ddec56a87d9c@HKMAIL103.nvidia.com> <20170719100225.wwaazm7f3mxz3aca@LK-Perkele-VII>
In-Reply-To: <20170719100225.wwaazm7f3mxz3aca@LK-Perkele-VII>
Accept-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.18.19.222]
MIME-Version: 1.0
Content-Language: en-US
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/gNmBtmV4blX1VbOlw6W-BSI6fmw>
Subject: Re: [Cfrg] RFC 8032: Question on Side-Channel Leaks
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 20 Jul 2017 06:28:24 -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: ilariliusvaara@welho.com [mailto:ilariliusvaara@welho.com] 
Sent: Wednesday, July 19, 2017 6:02 PM
To: Jerry Zhu <jezhu@nvidia.com>
Cc: cfrg@irtf.org
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.
-----------------------------------------------------------------------------------