Re: [Cfrg] Side Channel Attacks

"D. J. Bernstein" <djb@cr.yp.to> Thu, 28 September 2017 02:01 UTC

Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
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 43443135245 for <cfrg@ietfa.amsl.com>; Wed, 27 Sep 2017 19:01:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.598
X-Spam-Level:
X-Spam-Status: No, score=-2.598 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=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 KnaNS9CcnEwp for <cfrg@ietfa.amsl.com>; Wed, 27 Sep 2017 19:01:33 -0700 (PDT)
Received: from salsa.cs.uic.edu (salsa.cs.uic.edu [131.193.32.108]) by ietfa.amsl.com (Postfix) with SMTP id 3054313232C for <cfrg@irtf.org>; Wed, 27 Sep 2017 19:01:32 -0700 (PDT)
Received: (qmail 16404 invoked by uid 1010); 28 Sep 2017 02:01:31 -0000
Received: from unknown (unknown) by unknown with QMTP; 28 Sep 2017 02:01:31 -0000
Received: (qmail 7575 invoked by uid 1000); 28 Sep 2017 02:01:17 -0000
Date: Thu, 28 Sep 2017 02:01:17 -0000
Message-ID: <20170928020117.7574.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <CAFTSWvdq8p3i20veq=GgHi_rnOS6Wv4dK1xQpJHaPS4r5e5-SQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Ov8xePCsZ6ZEboqvH3dC0iRLkmI>
Subject: Re: [Cfrg] Side Channel Attacks
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, 28 Sep 2017 02:01:35 -0000

Thomas Garcia writes:
> According to [1], the libgcrypt implementation of curve25519 is based
> on bignum arithmetic which is not constant-time.

This isn't specific to Curve25519: libgcrypt has a huge amount of
non-constant-time code that needs to be fixed or replaced.

> Can something similar be done to encourage correct bignum arithmetic?
> Is it possible to choose the parameters, such as the prime, such that
> the simplest implementation will be less susceptible to side channel
> attacks?

Here's some discussion of prime choices from this perspective:

   https://cr.yp.to/talks.html#2015.06.11

Of course, bad choices at lower levels of the software stack can create
tensions between simplicity and security at higher levels. For example,
if your choice is between

   * simply calling a variable-time ECC library or
   * writing constant-time ECC software from scratch,

then the first option will be simpler for you, but will be insecure. As
a less extreme example, if your choice is between

   * simply calling a variable-time modular-arithmetic library or
   * writing constant-time modular-arithmetic software from scratch,

then the first option will again be simpler for you, but will be
insecure. The second option---done properly---produces a simpler,
smaller ECC software stack, but this is obscured by the existing
library for the first option.

---Dan