Re: [Cfrg] Hardware requirements for elliptic curves

[Torsten Schuetze <[e-mail]>]

On Sep 7, 2014, at 22:25:57 -0700 Paul Lambert <paul at marvell.com>
wrote:

> On 9/2/14, 9:31 AM, "Michael Hamburg" <mike at shiftleft.org> wrote:
>
>> I agree with Alyssa that hardware performance isn't our concern here.
>>
>> However, I'm curious about Joppe Bos' assertion that random primes are
>> just as fast and more secure in hardware.  What kind of hardware are you
>> thinking about?  Some kind of residue number system?  Or a bit-at-a-time
>> reduction system?
>
> I work at a chip company checking on design considerations:
> - random primes and special run at the same speed
> - flexibility and die size are more important than prime specific
> optimization
>
> Paul

I fully agree with Paul's statement on flexibility and random primes.
I work at Rohde & Schwarz SIT in the high-security/high-assurance
crypto business. We use ASICs, FPGAs and smart cards and even some
software crypto implementations in our products. Our requirements on
ECC are (in this order) 1. flexibility, 2. security, and, only then 3.
performance.

First, I would like to add, that in my opinion the discussion in this
thread should not be about software versus hardware rather than

       software in a secure environment, e.g., on a secured server,
       i.e., where only the global timing as side-channel is relevant

       versus

       software on constrained devices or hardware in a hostile
       environment, i.e., where the full set of local and global
       side-channels applies.

Most of the discussion until Joppe Bos' thread was on the first group
only. I represent the second group, for short, hardware.

Some proponents of highly optimized curves with special primes seem
only be focused on the software scenario with supposedly fast ability
for bug fixes (and short product cycles?). But TLS meanwhile is not
only used in the typical web server scenario. In Germany, it is
standardized for smart metering communication (with much longer
product cycles than typical Internet business and, later,
thousands/millions of devices rolled out in the field). ECC will be
used in Car2X and in digital tachographs (where even the legitimate
driver is a potential attacker).

Let's now come to the flexibility issue: In our company we must be
able to work with hitherto unknown domain parameters, i.e., arbitrary
random primes. The only thing we can assume is that the curves are
Brainpool like. Beyond that, the curves are part of the crypto setup.
This is a hard requirement of the government agency, Federal Office of
Information Security in our case, and is required by some (not all)
other nations as part of the crypto customization.

I suppose that crypto customization may sound strange to some people
on the list who think that we can live with one and only one curve.
But that's the reality in high-assurance crypto.

Besides that we have to use different curves (all in short Weierstrass
form, not different curve types as Montgomery etc.) for signature and
ECDH. Additional measures are taken, for example, for ECDH such that
an attacker cannot easily learn the domain parameters from the data on
the wire (point compression not for the sake of saving bandwidth,
additional symmetric schemes).

As a company representative I could relax and say that we are not
affected by standardization of Edwards-, Montgomery- or even Brainpool
curves as we have to use Brainpool-like curves. But my concerns go a
step further: I'm afraid that we as a crypto community are heading
for the wrong direction. We need flexibility, i.e., no curves with a
very special structure, especially no curves with a specific prime
structure as NIST-primes or other proposed primes.

The last statement was common consensus at the recent Brainpool
meeting. Other discussed features were not that unanimously. Most of
the participants could live with twist-secure curves, less favorable
would be the neglection of the property b non-square mod p (because of
distinguished point attacks), even less favorable the cofactor
question. But it seems to me that all these specific questions can be
solved, but the random primes issue is a remaining one. All three
participating hardware manufactures (two smart card manufacturers, NXP
and Infineon, and one HSM manufacturer) stated that they currently use
(and will use) random primes in their coprocessors.

Finally, let's come to the question of Mike Hamburg. I can only speak
about the Infineon coprocessor as I was involved in that. NXP and
other smart card manufacturers use completely different designs.

The current Infineon coprocessor is a unified coprocessor for GF(p)
and GF(2^n) based on a serial-parallel multiplier which can work with
up to 2303 bit (smaller bit length are possible and favorable for ECC).
Essentially all ECC (and RSA) operations boil down to a number of
modular multiplications Z=M*C mod N. This is the essential operation
of the coprocessor.

The algorithms of all other operations, e. g., operations in
GF(2)[x]/<N[x]> aka GF(2^n), can be derived from this basic algorithm.

The algorithm for modular multiplication basically consists of a
modified Booth algorithm with variable shift length for multiplication
coarsely interleaved with a modular reduction. For modular reduction,
the ZDN-principle developed by Sedlak is used. This reduction is based
on the repeated comparison of intermediate results Z with the value Zwei
Drittel N, i.e. 2/3*N. At the end of each step we have

2/3 N < |Z| <= 4/3 N

The multiplication part results in

Z=Z+a*2^{s_C}*C

with "sign" a = -1,0,+1 and shift 0<= s_c <= const_1.
The reduction part results in

Z=Z+b*2^{s_N}*N

with "sign" b=-1,0,+1 and shift -const_2 <= s_N <= const_2. These two
operational parts are combined into a Three Operand Addition

(#) Z=Z+a*2^{s_C}*C + b*2^{s_N}*N

The difficult algorithmic part is the data-dependent determination of
optimal "signs" a,b and shift values s_C, s_N. It should be noted that
the described scheme is that of the old ACE (i.e. before 2002), the
new Crypto@2304T uses further, rather technical refinements.

The 3-Operand-Addition is done by transformation into Carry-Save
Addition form -> (C,S) (fully parallelized) and further Carry Look
Ahead Adders.

The nice fact about this coprocessor is that in every step
approximately E(s_z,s_C) \approx 2.7 ... 2.8 bits of the multiplier
are processed and that Booth and ZDN are in a certain sense
optimal/dual.

One can easily see from (#) that a special structure of the modulus N
is of no use here. This can be verified by simulations and
measurements (take an arbitrary IFX smart card with public-key
coprocessor).

To sum up, especially for hardware vendors special primes are of no
use and can even be dangerous, see the separate mail by Wieland
Fischer on blinding issues.

Regards,

Torsten
-- 
ROHDE & SCHWARZ SIT GmbH
Hemminger Str. 41
D-70499 Stuttgart/Weilimdorf
Tel ++ 49 711 69945 183
Fax ++ 49 711 69945 170
http://www.sit.rohde-schwarz.com
mailto:[e-mail]