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

Ilari Liusvaara <ilariliusvaara@welho.com> Wed, 19 July 2017 10:02 UTC

Return-Path: <ilariliusvaara@welho.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 4810C131C78 for <cfrg@ietfa.amsl.com>; Wed, 19 Jul 2017 03:02:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001, URIBL_BLOCKED=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 yxlaTUDKLbpJ for <cfrg@ietfa.amsl.com>; Wed, 19 Jul 2017 03:02:31 -0700 (PDT)
Received: from welho-filter3.welho.com (welho-filter3.welho.com [83.102.41.25]) by ietfa.amsl.com (Postfix) with ESMTP id C93A112F24E for <cfrg@irtf.org>; Wed, 19 Jul 2017 03:02:30 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by welho-filter3.welho.com (Postfix) with ESMTP id 79EEF223D1; Wed, 19 Jul 2017 13:02:28 +0300 (EEST)
X-Virus-Scanned: Debian amavisd-new at pp.htv.fi
Received: from welho-smtp1.welho.com ([IPv6:::ffff:83.102.41.84]) by localhost (welho-filter3.welho.com [::ffff:83.102.41.25]) (amavisd-new, port 10024) with ESMTP id dRm-me5nixsy; Wed, 19 Jul 2017 13:02:27 +0300 (EEST)
Received: from LK-Perkele-VII (87-92-19-27.bb.dnainternet.fi [87.92.19.27]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by welho-smtp1.welho.com (Postfix) with ESMTPSA id 8794A286; Wed, 19 Jul 2017 13:02:25 +0300 (EEST)
Date: Wed, 19 Jul 2017 13:02:25 +0300
From: Ilari Liusvaara <ilariliusvaara@welho.com>
To: Jerry Zhu <jezhu@nvidia.com>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Message-ID: <20170719100225.wwaazm7f3mxz3aca@LK-Perkele-VII>
References: <6fa65bd5e4ce454ba871ddec56a87d9c@HKMAIL103.nvidia.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <6fa65bd5e4ce454ba871ddec56a87d9c@HKMAIL103.nvidia.com>
User-Agent: NeoMutt/20170609 (1.8.3)
Sender: ilariliusvaara@welho.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/DuALG8BcFG7Lki7NHWkCgIJbs-0>
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: Wed, 19 Jul 2017 10:02:36 -0000

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