Re: [Cfrg] Hardware requirements for elliptic curves

[Andy Lutomirski <[e-mail]>]

On Thu, Sep 11, 2014 at 1:00 AM, Torsten Schuetze
<[e-mail]> wrote:
>
> 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.

What's the actual issue here?  Presumably this means that your device
will work just as well on e.g. GP(2^255-19) as on any other prime of
similar size.  It won't be faster the way that software implementation
can be faster, but that doesn't seem like it will cause a problem.

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

CFRG and/or IETF aren't about to give you flexibility no matter what
curves are chosen.  All signs point to choosing a very small number of
curves.

Why is this a problem?  If you need to support arbitrary curves,
you'll do this regardless.

If, on the other hand, you were implementing, e.g., a CFRG-recommended
Edwards-coordinate cryptosystem, could you convert to Weierstrass
coordinates and then use your hardware?  Obviously you can't
interoperate with someone expecting Edwards coordinates if you do
this, but if you need a specific wire format for some compliance
reason, then you can't interoperate with anyone who doesn't use that
wire format regardless.  Nonetheless, I think you could convert the
format and still have your hardware work fine.


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

Can anyone explain why "random" primes are better for blinding?  Keep
in mind that, from the point of view of an attacker, no common ECC
protocol uses a random prime; they just use primes without much
interesting structure.  The adversary knows the prime.

--Andy