[Cfrg] Conditional requirements in ANSI X9.62-2005 [was 25519 naming]

[Dan Brown <[e-mail]>]

Continuing this discussion for two reasons:
- various IETF docs indirectly refer to ANSI X9.62, for key generation, key
validation, and for ECDSA signing and verifying, so correct interpretation
is warranted
- a clarity issue that Dan Bernstein raised about ANSI X9.62 may be more
generally relevant to other standards documents.

> -----Original Message-----
> From: D. J. Bernstein
> Sent: Thursday, August 28, 2014 2:54 AM
> 
> The ANSI ECDSA standard specifies elliptic curves mod p to have short
> Weierstrass form y^2 = x^3+ax+b (see the "elliptic curves and points"
> section), 

That quote's from Annex A.3.1.1.   

All elliptic curves defined over Fp can be converted to short Weierstrass
form.

ANSI X9.62-2005 opts to describe Fp curves (and points) using this form.

Note that this is an abstraction, not an encoding.  Encodings and conversion
are covered elsewhere in the ANSI X9.62-2005, e.g. A.5 and E.

In particular, in the abstract, this section supports the curve used in
Curve25519, though not the exact form thereof.

> specifies ECDSA public keys as points on such curves ("key pair
> generation"),

Again, an abstraction.

This level of abstraction allows implementations to use their own internal
point and integer representation, e.g. little-endian or big-endian, and
still claim conformance to the algorithms.

Clearly, any protocol, e.g. RFC 4492, using these algorithms must go further
and specify encodings on the wire.

> specifies required encodings ("conversions between data types
> that SHALL BE USED in the algorithms specified in this
Standard"---emphasis
> added), and in particular specifies the string encodings of curve points
(x,y)
> ("point-to-octet-string conversion").

Both of these quotes are from Annex A.5, which is referred to in:

Section 7.3 (signature generation), for converting a point and a hash to
integers, 
Section 7.4 (signature verification), for converting a point and a hash to
integers, 
Annex A.3.3 and A.3.4 ("random" curve and base point selection) for
converting a hash to an integer, for converting an integer to a field
element.
Annex E for representing keys and signatures as ASN.1 values (which can then
be encoded using DER, PER, XER, etc.)

Annex E.1 says "it is not required that elliptic curve domain parameters,
key, and signatures, be represented with ASN.1 syntax". 

So, to represent keys and signatures without ASN.1, ANSI X9.62-2005 does not
bind the implementer to using A.5 for such representation.  

> 
> The NIST ECDSA standard simply copies the ANSI formats (e.g., requiring
> signatures to be "verified as specified in ANS X9.62"). As for Internet
wire
> formats, RFC 4492 states that its point formats "are specified in [7]";
[7] is a
> normative reference, the ANSI ECDSA standard. RFC 4492 requires exactly
these
> formats to be used on the wire in TLS. An implementation using a different
> format wouldn't interoperate with standard TLS ECDSA. Similar comments
apply
> outside the TLS context.
> 
> I'm not saying that these are good standards. I'm also not saying that it
would
> be difficult for IETF to deviate from the previous standards and specify a
better
> wire format (as I recommend). I'm simply saying that various claims here
> regarding ECDSA compliance are incorrect.

I'm not quite sure if you're saying my claims from yesterday are incorrect,
but I hope I have helped clarify.  I don't see what I wrote yesterday on the
previous thread to be inconsistent with the cross-reference tracking above.

That all said, I agree that ANSI X9.62-2005 could have been made clearer.  

The clarity issues seem to have two aspects: the first is that a thorough
implementer might scan the document for "shall",  and mistakenly fail to
realize some "shall" is only a conditional requirement, and not required in
all possible contexts.

For another example, Annex A.3.5.3 says "Elliptic curve domain parameters
shall be generated as follows".  If a text-scanning implementer failed to
notice Section 2 of ANSI X9.62, which advises that the conformance to the
standard only requires one of the six techniques, s/he might mistakenly
believe s/he must implement curve generation even if all s/he wants to do is
verify a signature or generate a key pair.

In general, what is a good wording to avoid this potential confusion from
such confusion?

Here are some awkward re-wordings of the examples above:

A.3.5.3: "If elliptic curve domain parameters are generated, then they shall
be generated as follows:"
A.5 "conversions between data types that are specified in the algorithms in
this Standard shall be as follows"

Actually, the full sentence from A.5 is:

"Figure A.1 provides a cross-reference for the annexes defining conversions
between data types that shall be used in the algorithms specified in this
Standard."

In hindsight, it was a mistake to place a "shall" in a sentence that merely
explains a figure.  So, I'd think that changing "shall be" to "are" would be
appropriate.

The correct way to for the requirement is along a path such as: Section 2 ->
Section 7.3 -> Section A.5.6

The second aspect of the clarity issue is that an implementer needs some
kind of internal representation and would look in A.5 for such a
representation.  At that point, the implementer might think "shall" language
to be binding upon external representations too.  I think an explanatory
note might resolve this problem.  Or, perhaps removing the term "shall" from
A.5 would work too, with the term "shall" being used in the section
referring to A.5.

Best regards,

Dan