Re: [Cfrg] Trusting government certifications of cryptography

["Lochter, Manfred" <[e-mail]>]

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 <[e-mail]>
Datum:	Dienstag, 7. Oktober 2014, 18:55:33
An:		Dirk Feldhusen <[e-mail]>
Kopie:	"[e-mail]" <[e-mail]>, "D. J. Bernstein" <[e-mail]>
Betr.:	Re: [Cfrg] Trusting government certifications of cryptography

> > On Oct 7, 2014, at 9:08 AM, Dirk Feldhusen <[e-mail]>
> > 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: [phone] 5643
Telefax: [phone] 5643
E-Mail: [e-mail]
Internet:
www.bsi.bund.de
www.bsi-fuer-buerger.de