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, 8 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