Re: [Cfrg] Constant-time implementations

David Jacobson <dmjacobson@sbcglobal.net> Tue, 14 October 2014 13:14 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 9F1701A87EB for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 06:14:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001] 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 knEWCp66bGsu for <cfrg@ietfa.amsl.com>; Tue, 14 Oct 2014 06:14:10 -0700 (PDT)
Received: from nm15-vm2.access.bullet.mail.gq1.yahoo.com (nm15-vm2.access.bullet.mail.gq1.yahoo.com [216.39.63.43]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CFE671A8822 for <cfrg@irtf.org>; Tue, 14 Oct 2014 06:14:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1413292449; bh=1uwLOnIHtkfHaqCqqmvMqVAWJCWzvbsBShc8YlLYiDI=; h=Date:From:To:Subject:References:In-Reply-To:From:Subject; b=jGd/CFNsq10ilWG2XlCdP4b/uOGLyipBipMyFrwy6/OgSapCWaRfrs1JT9451Udq+hLdqInPUZHLSGShipWPf0EVgjz+vPcuU21MB5xs3D9Kjou/+tG7lHeQSNP7wWo1PKQtrOgAzq1/v3qJ77QTNwezE11jR/JRBQR1N1HOtGM=
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=sbcglobal.net; b=WudH8zW89hz9gNRtufi3tyes/dJgf1a+79UrXeHugQwuQrEgU3oYGw1XR4yMlX03OBmJ5icuH0/rCIVPKrgiFz/wJRla96p/pM74FXTdLPJ4mi/4VTVEiPcSVzTsx84RNHfIuSfPErc18H6Td0/ddMKyIFojICPS5da+c51+yLo=;
Received: from [216.39.60.171] by nm15.access.bullet.mail.gq1.yahoo.com with NNFMP; 14 Oct 2014 13:14:09 -0000
Received: from [67.195.23.147] by tm7.access.bullet.mail.gq1.yahoo.com with NNFMP; 14 Oct 2014 13:14:09 -0000
Received: from [127.0.0.1] by smtp119.sbc.mail.gq1.yahoo.com with NNFMP; 14 Oct 2014 13:14:09 -0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s1024; t=1413292449; bh=1uwLOnIHtkfHaqCqqmvMqVAWJCWzvbsBShc8YlLYiDI=; h=X-Yahoo-Newman-Id:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=cHgBIlb90HHOORr6Jv/qjlRzhU1UOFcSe9aEfiH9HSfRkfQyu6qF8NylSlE/nYW009MkKtmywYcrFK9JTGCQBioX+C/eocEGeUT3HoJqg6eB15loSPYFPpEucHdBKPXy+YAapZuHZ4ks0ZY+fMDZIc6vTydvnu4REsLEi4vKIj0=
X-Yahoo-Newman-Id: 690351.31478.bm@smtp119.sbc.mail.gq1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: 1epc_HcVM1nL3aNzH3uflRBWqXS3b9RcNJf3beodmI9LiKm KjVdqz3_LG0e3WtgMsHig_N0OxvC1MA1iQ6qwC1lhAy4c7ptVP3hQJ8ycDdp v0Jz0zeKFZ8EQVjDS_5BEUGl2aVwDeLXyaD4mSFBYnmQIBNZHjMw9T50Plax KdamETxz6K6K_d0ZmXL4EfcSmB3jUR4rsziGwDDCOA83.njQ09.Elkz3NCmq nJp3xklvbU4uHA4Y9UQ2w5QtAq2FGJRAE1x_KGg0vUUT38.qRnWppOId.TK5 OMzgtUZTGrWoqR0mgnElsZurVo4TnBo.e_yCzt2Wq2tUOsIxuMQTLfVbVNvF 9ajIFccPGl2esA8ESlgujE8qGJN_dbxNxVKjEp8lttj3yZIECQ5pbu6KfDtt 36G6XS07DnhQnGSqMHXp9Z44HFw0GBgeDqZ6cG6RQjT6q0bSoW0264OYLUL1 0z7aDZV5ZYZUEz0vZwF3ural.M1hCvOd64ZV1oao6yAN1ORT9dK6aSRv454t mWnrfQb.4gtMzKrEO7YFY4NNmK_EE_HK2BZSGVrZXII_0y.9UaA54KIz4uNG d5LT5nexEyJkOqYHSvYyd1b8gUixTDHHY51SFb53bRS_Sbdfv.yIEEwdLQQo 76PDVR_TtV_M1iuKHGjIu9a3RSazEzkOYSUT7RHbzCx2lHxAjgmhfrtAx8WS XMmAewXRg1QBgabm0G2ZRdFKID9V3E_Gu7dxvVciEr7kkIFg-
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
Message-ID: <543D21A0.3000109@sbcglobal.net>
Date: Tue, 14 Oct 2014 06:14:08 -0700
From: David Jacobson <dmjacobson@sbcglobal.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <20141014093640.24706.qmail@cr.yp.to>
In-Reply-To: <20141014093640.24706.qmail@cr.yp.to>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/GeWqEkeffZ6gcT9XS8W-PTHMvBA
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 13:14:13 -0000

On 10/14/14, 2:36 AM, D. J. Bernstein wrote:
> 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
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>
Sometimes data dependent branches cannot be avoided without a serious 
performance penalty.  I'm thinking of modular inversion using the binary 
method. But it that case it is easy to use blinding.

1/k = b * (1 / (b * k))

where b is a random blinding value.

In this case, I think it is still fair consider this leakage resistant, 
even though the inversion is actually full of data dependent branches.

Of course, the time to compute b has to be included in the benchmark.  
But do those blinding values  have to be generated with heavy-weight 
schemes such as the algorithms in NIST SP 800-90A, or is it, in 
practice, safe to use something fast like the keystream from RC4?

     --David Jacobson