Re: [Cfrg] Trusting government certifications of cryptography
"Lochter, Manfred" <manfred.lochter@bsi.bund.de> Wed, 08 October 2014 11:57 UTC
Return-Path: <manfred.lochter@bsi.bund.de>
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 255E81A02F9 for <cfrg@ietfa.amsl.com>; Wed, 8 Oct 2014 04:57:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.341
X-Spam-Level:
X-Spam-Status: No, score=-1.341 tagged_above=-999 required=5 tests=[BAYES_50=0.8, FB_WORD2_END_DOLLAR=3.294, HELO_EQ_DE=0.35, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.786, 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 boFaGscX_dSM for <cfrg@ietfa.amsl.com>; Wed, 8 Oct 2014 04:57:32 -0700 (PDT)
Received: from m3-bn.bund.de (m3-bn.bund.de [77.87.228.75]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 948E11A02F8 for <cfrg@irtf.org>; Wed, 8 Oct 2014 04:57:32 -0700 (PDT)
Received: from m3.mfw.bn.ivbb.bund.de (localhost.mfw.bn.ivbb.bund.de [127.0.0.1]) by m3-bn.bund.de (8.14.3/8.14.3) with ESMTP id s98BvTbR020190 for <cfrg@irtf.org>; Wed, 8 Oct 2014 13:57:29 +0200 (CEST)
Received: (from localhost) by m3.mfw.bn.ivbb.bund.de (MSCAN) id 5/m3.mfw.bn.ivbb.bund.de/smtp-gw/mscan; Wed Oct 8 13:57:29 2014
X-P350-Id: 21a9350220643a1c
X-Virus-Scanned: by amavisd-new at bsi.bund.de
From: "Lochter, Manfred" <manfred.lochter@bsi.bund.de>
Organization: BSI Bonn
To: cfrg@irtf.org
Date: Wed, 08 Oct 2014 13:57:02 +0200
User-Agent: KMail/1.9.10 (enterprise35 20140205.23bb19c)
References: <20141003111024.20324.qmail@cr.yp.to> <54341010.8050207@src-gmbh.de> <CB8D38CD-55A1-4F04-9AA1-59A6556E30E4@shiftleft.org>
In-Reply-To: <CB8D38CD-55A1-4F04-9AA1-59A6556E30E4@shiftleft.org>
X-KMail-QuotePrefix: >
MIME-Version: 1.0
Content-Type: Text/Plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Message-ID: <201410081357.03062.manfred.lochter@bsi.bund.de>
X-AntiVirus: checked by Avira MailGate (version: 3.2.1.26; AVE: 8.3.24.34; VDF: 7.11.177.52; host: sgasmtp2.bsi.de); id=21034-JvOnzC
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/gun3jacFQtJ5ddwhqwhMyb0I65Q
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 11:57:35 -0000
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. 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$}. @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 -- Lochter, Manfred -------------------------------------------- Bundesamt für Sicherheit in der Informationstechnik (BSI) Referat K21 Godesberger Allee 185 -189 53175 Bonn Postfach 20 03 63 53133 Bonn Telefon: +49 (0)228 99 9582 5643 Telefax: +49 (0)228 99 10 9582 5643 E-Mail: manfred.lochter@bsi.bund.de Internet: www.bsi.bund.de www.bsi-fuer-buerger.de
- [Cfrg] Hardware requirements for elliptic curves Joppe Bos
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Michael Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Johannes Merkle
- Re: [Cfrg] Hardware requirements for elliptic cur… Michael Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Andy Lutomirski
- Re: [Cfrg] Hardware requirements for elliptic cur… Robert Ransom
- Re: [Cfrg] Hardware requirements for elliptic cur… Lochter, Manfred
- Re: [Cfrg] Hardware requirements for elliptic cur… Johannes Merkle
- Re: [Cfrg] Hardware requirements for elliptic cur… Wieland.Fischer
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Watson Ladd
- Re: [Cfrg] Hardware requirements for elliptic cur… Patrick Georgi
- Re: [Cfrg] Hardware requirements for elliptic cur… Paul Lambert
- Re: [Cfrg] Hardware requirements for elliptic cur… Torsten Schuetze
- Re: [Cfrg] Hardware requirements for elliptic cur… Torsten Schuetze
- Re: [Cfrg] Hardware requirements for elliptic cur… Andy Lutomirski
- Re: [Cfrg] Hardware requirements for elliptic cur… Mike Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Torsten Schuetze
- Re: [Cfrg] Hardware requirements for elliptic cur… Watson Ladd
- Re: [Cfrg] Hardware requirements for elliptic cur… Mike Hamburg
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Lochter, Manfred
- Re: [Cfrg] Hardware requirements for elliptic cur… Alyssa Rowan
- Re: [Cfrg] Hardware requirements for elliptic cur… Dirk Feldhusen
- Re: [Cfrg] Hardware requirements for elliptic cur… Lochter, Manfred
- Re: [Cfrg] Hardware requirements for elliptic cur… Ilari Liusvaara
- Re: [Cfrg] Hardware requirements for elliptic cur… Watson Ladd
- Re: [Cfrg] Hardware requirements for elliptic cur… Peter Gutmann
- [Cfrg] Trusting government certifications of cryp… D. J. Bernstein
- Re: [Cfrg] Trusting government certifications of … David Jacobson
- Re: [Cfrg] Trusting government certifications of … Torsten Schütze
- Re: [Cfrg] Trusting government certifications of … Watson Ladd
- Re: [Cfrg] Trusting government certifications of … Dirk Feldhusen
- Re: [Cfrg] Trusting government certifications of … Michael Hamburg
- Re: [Cfrg] Trusting government certifications of … Dirk Feldhusen
- Re: [Cfrg] Trusting government certifications of … Lochter, Manfred
- Re: [Cfrg] Trusting government certifications of … Mike Hamburg
- Re: [Cfrg] Primes vs. hardware side channels David Leon Gil
- [Cfrg] Primes vs. hardware side channels D. J. Bernstein
- Re: [Cfrg] Primes vs. hardware side channels Alyssa Rowan