Re: [Cfrg] Trusting government certifications of cryptography

Mike Hamburg <mike@shiftleft.org> Wed, 08 October 2014 17:22 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 DDA161ACD1E for <cfrg@ietfa.amsl.com>; Wed, 8 Oct 2014 10:22:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 4.849
X-Spam-Level: ****
X-Spam-Status: No, score=4.849 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FB_WORD2_END_DOLLAR=3.294, 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 DoT9ixfZ14eM for <cfrg@ietfa.amsl.com>; Wed, 8 Oct 2014 10:22:40 -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 7839C1ACD1A for <cfrg@irtf.org>; Wed, 8 Oct 2014 10:22:40 -0700 (PDT)
Received: from [192.168.1.124] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 57E2F3AA49; Wed, 8 Oct 2014 10:21:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1412788874; bh=5FaxpV/ioI9Ei9gU/XxSsX9hF0EeIK8uzSjaIJ8v1i0=; h=Date:From:To:Subject:References:In-Reply-To:From; b=i0axF7ndbinWJOxZJCKF9JfyjmUpG0pM1v1F3eDsyY3lICAFNXXgAJJXhCRY3dA7V s/MPwBVENxWPX6yoqOTdPpkdUaOF3itshzEVB8CryFzI9/6PkAb11aN595i3zY/Hgh BoJcvBLFS0nou+oWq4v85sLEafo2lwBoddxPN9Jc=
Message-ID: <543572CE.5080409@shiftleft.org>
Date: Wed, 08 Oct 2014 10:22:22 -0700
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: "Lochter, Manfred" <manfred.lochter@bsi.bund.de>, cfrg@irtf.org
References: <20141003111024.20324.qmail@cr.yp.to> <54341010.8050207@src-gmbh.de> <CB8D38CD-55A1-4F04-9AA1-59A6556E30E4@shiftleft.org> <201410081357.03062.manfred.lochter@bsi.bund.de>
In-Reply-To: <201410081357.03062.manfred.lochter@bsi.bund.de>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/BQaX8pVkaGbOzQ-ss4U-rZzLh9o
Subject: Re: [Cfrg] Trusting government certifications of cryptography
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: Wed, 08 Oct 2014 17:22:42 -0000

OK, thanks Manfred.

On 10/8/2014 4:57 AM, Lochter, Manfred wrote:
> Mike,
>
> in a nutshell: Yes, they are harder to secure.
>
> Long version: There are theoretical arguments that show that blinding becomes
> harder for special primes:
>
> One of the proposed countermeasures against side-channel attacks on the point
> multiplication is Coron's first countermeasure \cite{Coron99}.
> Instead of computing $\lambda P$ one chooses a random number $r$ (usually $r$
> has 32 bits, \cite{Coron99} suggests using 20 bits)
> and computes $(\lambda +r q)P.$
>   It has been
> observed (\cite{Ciet}(The main ideas from \cite{Ciet} are also reproduced in
> \cite{Ebeid}, which is easily available} and later
> independently in
> \cite{RandReps})
> that the validity of this countermeasure relies on the structure of the binary
> representation of $p$. For cofactor one curves the upper half of
> the binary representation of $p$ coincides with the upper half of the
> representation of $q$ by the Hasse-Weil theorem.
> If this part of $p$ contains long runs of zeroes or
> ones
> (as e.g. for curves over fields with Pseudo-Mersenne characteristic, as the
> NIST curves, or over fields with special prime characteristic as
> $2^{255} -19$ over which curve25519 is defined)
> some bits of $r$ and $\lambda$ can directly be accessed through measurements.
Right.  I was trying to understand whether the problem can be solved by 
using a longer blinding factor -- even blinding to $r ~ \sqrt q$ would 
be faster on systems that accelerate special primes -- or whether it 
becomes truly infeasible or impractical.
> In \cite{SchiWi} it is even shown that for some curves even 64 bits blinding
> are not sufficient, depending on the
> error rate of the measurements. In addition an {\glqq alternate attack\grqq}\
> is introduced  \glqq that cannot be prevented by
> increasing the parameter $R$\grqq \ within
> a reasonable range\footnote{In the notation of \cite{SchiWi} $R$ is the
> bitlength of the random number $r$}.
This paper is paywalled, so I haven't read this paper beyond the first 
two pages, which describe the attack as working on RSA or ECC in general 
(with/without CRT).  But if they detail a way to attack realistic 
implementations of blinding on special primes and not general, even for 
long $r$, then I concede the point.

Thanks,
-- Mike
> @inproceedings{Coron99,
>      author = {Jean-Sebastien Coron},
>      booktitle = {Cryptographic Hardware and Embedded Systems},
>      title = {{Resistance against Differential Power Analysis for Elliptic
> Curve Cryptosystems}},
>      year = {1999}
> }
> @ARTICLE{Ebeid,
>      author = {Nevine Maurrice Ebeid},
>      title = {{Key Randomization Countermeasures to Power Analysis Attacks on
> Elliptic Curve Cryptosystems}},
>      journal = {Thesis},
>      year = {2007},
>      %volume = {12},
>      %pages = {1--28}
> }
>    @misc{Ciet,
>      author = {Mathieu Ciet},
>      title = {Aspects of fast and secure arithmetics for elliptic curve
> cryptography},
>      howpublished = {Thesis},
>      year = {2003},
>      }
> @article{RandReps,
>   title = "Randomised representations",
>   author = "Elisabeth Oswald and Daniel Page and Nigel Smart",
>   year = "2008",
>   volume = "2",
>   number = "2",
>   pages = "19--27",
>   journal = "IET Proceedings on Information Security",
>
>   }
> @ARTICLE{SchiWi,
>      author = {Werner Schindler and Andreas Wiemers},
>      title = {{Power Attacks in the Presence of Exponent Blinding} },
>      journal = {Journal of Cryptographic Engeneering},
>      year = {to appear},
>      %volume = {12},
>      %pages = {1--28}
> }
>
>
>
>
> __________ ursprüngliche Nachricht __________
>
> Von:		Michael Hamburg <mike@shiftleft.org>;
> Datum:	Dienstag, 7. Oktober 2014, 18:55:33
> An:		Dirk Feldhusen <dirk.feldhusen@src-gmbh.de>;
> Kopie:	"cfrg@irtf.org"; <cfrg@irtf.org>;, "D. J. Bernstein" <djb@cr.yp.to>;
> Betr.:	Re: [Cfrg] Trusting government certifications of cryptography
>
>>> On Oct 7, 2014, at 9:08 AM, Dirk Feldhusen <dirk.feldhusen@src-gmbh.de>;
>>> wrote:
>>>
>>> To exclude the possibilty of power or EM side channel you need the
>>> assumption that the attacker has no physical access to the device.
>>> As I understand Torsten the main problem here are special primes which
>>> are harder to secure against such side channel leakage.
>> Are they actually harder to secure (eg, requiring new countermeasures), or
>> just slower on hardware which doesn’t accelerate the special prime (eg, by
>> requiring longer blinding factors)?
>>
>> — Mike