Re: [Cfrg] Trusting government certifications of cryptography

[Mike Hamburg <[e-mail]>]

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 <[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