[Cfrg] Constant-time implementations

"D. J. Bernstein" <djb@cr.yp.to> Tue, 14 October 2014 09:36 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 (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 431F61A7000 for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 02:36:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.7
X-Spam-Level:
X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=0.001] autolearn=ham
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 xRThhF_R6kv8 for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 02:36:49 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id C70AB1A6FFE for <cfrg@irtf.org>; Tue, 14 Oct 2014 02:36:48 -0700 (PDT)
Received: (qmail 29452 invoked by uid 1011); 14 Oct 2014 09:36:45 -0000
Received: from unknown (unknown) by unknown with QMTP; 14 Oct 2014 09:36:45 -0000
Received: (qmail 24708 invoked by uid 1001); 14 Oct 2014 09:36:40 -0000
Date: 14 Oct 2014 09:36:40 -0000
Message-ID: <20141014093640.24706.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: <2FBC676C3BBFBB4AA82945763B361DE608F1D021@MX17A.corp.emc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ksz0OgikTS3e0JVDEHa6xRKJZec
Subject: [Cfrg] Constant-time implementations
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Oct 2014 09:36:51 -0000

Parkinson, Sean writes:
> Also, I am concerned that, while some curves are being implemented to
> be constant time, not all curves are being implemented to be cache
> attack resistant.

When I say "constant time", I don't merely mean making the _total_ time
constant: I mean systematically avoiding all data flow from secrets to
the CPU's instruction timing, providing full immunity to cache-timing
attacks, branch-prediction attacks, etc.

On typical CPUs this means avoiding all data flow from secrets to branch
conditions, load addresses, and store addresses. On some CPUs there are
other timing leaks: for example, if there are early-abort multipliers,
then for me "constant time" says, for each multiplication instruction in
the code, that the abort condition is independent of secret data.

Unfortunately, I've often seen "constant time" used for code that
doesn't even try to meet the same requirements, or that tries and fails:

   * OpenSSL added "constant-time" code where there was no dependence on
     secret data in the choice of _cache lines_ being accessed. However,
     https://cryptojedi.org/peter/data/chesrump-20130822.pdf showed that
     this strategy actually produces variable timings and is thus
     inadequate to guarantee protection against cache-timing attacks.

   * Section 1.2 of http://cr.yp.to/hecdh/kummer-20140218.pdf gives two
     examples of DH implementations that were incorrectly claimed to
     take constant time.

I _think_ that all of the CFRG curve proposers are imposing the same
stringent requirements upon their speed reports that I impose upon mine.
For example, Microsoft says that one "should" avoid "leaking access
patterns" and should write "code which does not contain branches
depending on secret data". However, I haven't seen a clear statement of
exactly what protections _are_ actually provided by Microsoft's ECCLib.
Everything that ECCLib says---"regular, constant-time execution" and
"full protection against timing and cache attacks" and "no correlation
between timing and secret data"---is something that could just as easily
have been said about the broken OpenSSL code mentioned above. It would
be helpful for Microsoft to clarify the situation.

I don't mean to suggest that there's a huge performance difference
between constant-time ECC and non-constant-time ECC---usually the gap is
below 20%. I do mean to suggest that getting things right takes work.
What really bugs me about the NIST curves (and the Brainpool curves and
to a smaller extent Microsoft's curves) isn't their slowness but rather
their excessive complexity, leading to security problems:

   http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

We know how to eliminate many of these problems by choosing our
cryptographic systems more carefully.

---Dan