Re: [Cfrg] Constant-time implementations

David Jacobson <> Tue, 14 October 2014 13:14 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 9F1701A87EB for <>; Tue, 14 Oct 2014 06:14:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id knEWCp66bGsu for <>; Tue, 14 Oct 2014 06:14:10 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CFE671A8822 for <>; Tue, 14 Oct 2014 06:14:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; b=WudH8zW89hz9gNRtufi3tyes/dJgf1a+79UrXeHugQwuQrEgU3oYGw1XR4yMlX03OBmJ5icuH0/rCIVPKrgiFz/wJRla96p/pM74FXTdLPJ4mi/4VTVEiPcSVzTsx84RNHfIuSfPErc18H6Td0/ddMKyIFojICPS5da+c51+yLo=;
Received: from [] by with NNFMP; 14 Oct 2014 13:14:09 -0000
Received: from [] by with NNFMP; 14 Oct 2014 13:14:09 -0000
Received: from [] by with NNFMP; 14 Oct 2014 13:14:09 -0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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-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: <>
Date: Tue, 14 Oct 2014 06:14:08 -0700
From: David Jacobson <>
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
References: <>
In-Reply-To: <>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [Cfrg] Constant-time implementations
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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,
> showed that
>       this strategy actually produces variable timings and is thus
>       inadequate to guarantee protection against cache-timing attacks.
>     * Section 1.2 of 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:
> We know how to eliminate many of these problems by choosing our
> cryptographic systems more carefully.
> ---Dan
> _______________________________________________
> Cfrg mailing list
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