Subject: New contribution specifying ECC domain parameters

From: Johannes Merkle <[email-masked]>
Date: Tue, 15 Aug 2006 11:00:15 +0200

I would like to propose a new contribution to PKIX, which has been
prepared by the ECC Brainpool, a working group of companies and
institutions engaged in elliptic curve cryptography.

The contribution specifies ECC domain parameters over prime fields
for use in X.509 conforming PKIs. It can be downloaded here
http://www.ecc-brainpool.org/download/draft_pkix_additional_ecc_dp.txt

We are aware that the domain parameters recommended by ANSI X9.62
are already widely employed. The specification of additional
parameters is motivated by the following facts:

1. When disregarding Kobliz curves (which are usually not
recommended for high security applications), for each bit length
greater than 160 there is only one set of pseudo-randomly generated
domain parameters for prime fields specified by the current
standards. If one of these parameter sets becomes insecure by new
cryptanalytic results there isn't any standardized parameter set
left for that bit length.

2. Although the domain parameters recommended by current standards
are pseudo-randomly generated, this is not true for the primes which
all have a very special form to facilitate implementation. Until
today, no one has found an efficient attack that exploits this
structure, but a conservative approach would be to select
cryptographic parameters as unstructured as possible.

3. Current standards do not motivate the selection of the seeds.
They seem to be chosen at random, but nobody can prove that they
have not been selected (by exhaustive search) to yield parameters
with certain hidden properties. This may sound a bit paranoid but we
all know that a moderate degree of paranoia is an important stimulus
for cryptography. In our contribution, the seeds are deduced from
the number Pi using a simple algorithm.

4. Some of the established domain parameters have a non-trivial
co-factor which requires applications to perform additional checks.

Further differences to the domain parameter specifications of X9.62 are:

5. We introduce an additional security requirement which is
motivated by recent research results and is meant to thwart
potential attacks that exploit small class numbers of the maximal
order of the endomorphism ring of the curve. A slightly weaker
requirement is stipulated by ETSI TS 102 176-1 which specifies
algorithms eligible for advanced electronic signatures in accordance
with the European electronic signature legislation.

6. X9.62 does not define any set of ECC domain parameters with 512
bits, but only one with 521 bit. Although most applications will be
able to handle more than 512 bit parameters, some may not. We
propose a parameter set with "natural" length of 512 bit.

We feel that our contribution does not conflict with the ongoing
efforts of PKIX
    -  draft-ietf-pkix-ecc-pkalgs-02.txt
    -  draft-ietf-pkix-sha2-dsa-ecdsa-00.txt
but rather complements them. It does not define any new ASN.1 syntax
but recommends complying with draft-ietf-pkix-ecc-pkalgs-02.txt.
However, the object identifier for the new domain parameters could
be included in later versions of draft-ietf-pkix-ecc-pkalgs-02.txt.

Kind regards,
Johannes Merkle