Re: [Cfrg] Hardware requirements for elliptic curves

[Torsten Schuetze <[e-mail]>]

On Sep 11, 2014 09:22:53 -0700 Mike Hamburg <mike at shiftleft.org>
wrote:

>> On Sep 11, 2014, at 7:58, Andy Lutomirski <luto at amacapital.net> wrote:
>>
>>
>> Can anyone explain why "random" primes are better for blinding?
>>
>> --Andy
>
> With an unstructured prime, adding a small random multiple of p or
> the group order q will change every bit of the addend.  With a
> sparse prime, it will not.  This makes blinding a less effective
> countermeasure when p is sparse.

Mike, thanks for explaining.

> Torsten, thanks for the description of smart card hardware and
> concerns. It was very educational. I expected something looking
> more like a specialized CPU, where a sparse prime reduction unit
> could be bolted on easily.

The only thing I know in this direction are FPGA proposals like
Güneysu:Paar:2008 CHES 2008 'Ultra High Performance ECC over NIST
Primes on Commercial FPGAs' and even Sasdrich:Güneysu:2014 ARC 2014
'Efficient ECC using Curve25519' which both use the specific DSPs on
the FPGAs.

These are both great papers with very good performance results. But
they show what I mean with flexibility: it is not easily possible to
use 'random' or unstructured primes or even use the original primes
with enough blinding (because the blinding disturbs the structure).

Some years ago, I was looking for a general GF(p) crypto coprocessor
on a FPGA (Car2X standardization, like IEEE 1609.2, but without NIST
primes). The only thing I came up with was Nele Mentens Phd, 2007
(Montgomery multiplication, coarsely integrated operand scanning) and
the CHES 2010 paper by N. Guillermin (RNS). Unfortunately, I could not
find direct comparisons of, say, Brainpool and NIST curves on these
architectures.

> You should keep in mind, though, that the curves being proposed are
> designed for security against local side channels as well as global
> ones. The submitted implementations are designed not to leak against
> an adversary who can see all memory addresses accessed and
> instructions executed, even without blinding.

It all depends on the adversarial model.

> That's a lot easier than power and fault defense, but we're not
> slacking on the software side either.

But you surely know from your company background Cryptography
Research that electromagnetic attacks in a template like fashion are
currently the most advanced attacks. And I don't see that one can
solve this issue without heavy blinding.

Torsten