Re: [Cfrg] Constant-time implementations

Mike Hamburg <mike@shiftleft.org> Tue, 14 October 2014 17:43 UTC

Return-Path: <mike@shiftleft.org>
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 D02B51A90EE for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 10:43:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=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 mJYOEkYZgIlh for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 10:43:00 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 801971A90E9 for <cfrg@irtf.org>; Tue, 14 Oct 2014 10:43:00 -0700 (PDT)
Received: from [192.168.1.124] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 27A113AA13; Tue, 14 Oct 2014 10:41:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1413308470; bh=rynId8qas6cJjIT6o3XBG2f6kwqG9NwhpvlB+2MhUFQ=; h=Date:From:To:CC:Subject:References:In-Reply-To:From; b=ACOVI4UeTRJy+x14b52boD9NXtZEnjkDTpELsBD8Ze8Gp8ioiV60AzbbzMYGX1T8T KaElaS8ztBf545l0DVADMdrnwBDwCjU4OQvBFfk8EG067IYIql025ELDV63y9wRhJl /dWxitlg1Dj7t+XenN0ct9Y5HM3aCu6Ihp2WbYcA=
Message-ID: <543D60A0.8070205@shiftleft.org>
Date: Tue, 14 Oct 2014 10:42:56 -0700
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.1.2
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>, Yoav Nir <ynir.ietf@gmail.com>
References: <20141014093640.24706.qmail@cr.yp.to> <543D21A0.3000109@sbcglobal.net> <CAMfhd9Wude6j+PAG3pyeEukEBy4U7Tv1nsUVbtLcpALYvL2jpA@mail.gmail.com> <7421C78D-A667-419B-8576-DA837AF20188@gmail.com> <CACsn0ckHg7J4juStobVHB=Em2MOXvXJTUCW3z=gGstmspY-c=A@mail.gmail.com>
In-Reply-To: <CACsn0ckHg7J4juStobVHB=Em2MOXvXJTUCW3z=gGstmspY-c=A@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/gij-JUrA-NC7J3aNVN7jH1QjQu4
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [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 17:43:02 -0000


On 10/14/2014 08:05 AM, Watson Ladd wrote:
> On Tue, Oct 14, 2014 at 6:49 AM, Yoav Nir <ynir.ietf@gmail.com> wrote:
>> Doesn’t it become better (or at least safer) at some point to set a timer before beginning the operation and then not use the results until the timer expires?
>>
>> Sure this has a cost in memory, but any fool can write an implementation with an upper bound on processing time, whereas true constant time is both hard and has a 20% overhead (according to DJB’s message upthread).
>
This ends up working very poorly for many reasons, beyond (as Watson 
said) not solving your problem.  Estimating maximum time is difficult, 
especially across different platforms, and especially on a loaded system 
where you might miss cache or be descheduled.  It will probably be more 
than 20% overhead, whereas DJB's dataflow-constant-time definition 
usually has *less than* 20% overhead (from my numbers, ~6% for 
Goldilocks on Haswell).  Worse, you will need to figure out how to 
measure time, and how to sleep. That means threading libraries or 
busy-waiting, neither of which is appealing.

It is also important to recognize that timing isn't the only side 
channel.  In particular, constant-time array indexing (with logic 
operations) will be much leakier than direct lookups for a power-channel 
adversary.  So for software which runs on a PC or server, then timing- 
(, cache-, branch-) invariance is the important thing, but on an 
embedded device, power, EM and possibly fault resistance are more 
important.  This will necessitate blinding instead of constant-time 
array indexing, and usually has a much higher overhead.  As Torsten 
said, smart cards don't even use constant-time multiply.

I skimmed the ECClib code.  They seem to take efforts to avoid leaking 
data to addresses, with a masking approach to constant-time lookups.  
They use cmovc; is that constant-time?  IIRC it is at least on recent 
Intel chips.  Anyway, I think the authors clearly intended to avoid 
dataflow to addresses or branches, though a confirmation would be nice.

I agree that they should have used untwisted Edwards instead of twisted 
Edwards, but that's easy enough to fix: CFRG can just adopt the 
isogenous untwisted curves instead.  Is this what you mean by "excessive 
complexity"?  Is there another problem with those curves, that other 
curves with the same field size would not have?

For the record, since DJB seems to be calling people out on precision: 
my Ed448-Goldilocks software is designed not to let secret data flow to 
addresses, branch conditions or operations which are variable-time on 
most CPUs.  If it does, that's a bug.  However, secret data can flow to 
multiply and multiply-accumulate instructions, which are variable-time 
on some embedded CPUs. Furthermore, my code is mostly in C and so is at 
the mercy of the compiler and optimizer.  Finally, while I'm not using 
any blinded variable-time algorithms today (such as blinded EGCD), I 
consider them to be a safe and reasonable thing to do in the right 
circumstances.

Cheers,
-- Mike