Review of draft-ecc-09

[Marko Kreen <[e-mail]>]

Hello,

I tried to implement ECC for pgcrypto, which is crypto module
for PostgreSQL database.  And I managed to get it to work,
mainly because of EC module in OpenSSL, which allowed me to be
ignorant of all low-level math details.

Also, I only implemented ECDH, pgcrypto does not do signing.
It uses PGP as a fancy encrypt/decrypt storage format only.

So this is a review of draft-08 by app developer who is ignorant
of EC math and has not read any detailed math/crypto papers...

[ I updated the review with diff from -09.  Thanks for taking
  my comments on the ref section into account. ]

> 5. Supported public key algorithms
> 
>    Supported public key algorithms are Elliptic Curve Digital
>    Signature Algorithm (ECDSA), defined in [FIPS 186-2], and Elliptic
>    Curve Diffie-Hellman (ECDH), defined in section 8.

Note for later: this basically states that section 8 plans to
fully describe ECDH used in OpenPGP.

> 6. Conversion primitives
> 
>    The method to convert an EC point to the octet string is defined in
>    [SEC1].  This specification only defines uncompressed point
>    format.  For convenience, the synopsis of the encoding method is
>    given below, however, the [SEC1] is the normative source of the
>    definition.
> 
>    The point is encoded in MPI format.  The content of the MPI is the
>    following:
> 
>         B = B0 || x || y
> 
>    where x and y are coordinates of the point P = (x, y), each encoded
>    in big endian format and zero-padded to the underlying field size.

*Then*, they are also padded to byte boundary.  As this is not mentioned
anywhere, it caused me some confusion, because I assumed they already
are on byte boundary, perhaps even power-of-two.

As it only matters to P-521 keys, the bad assumtions work fine on
P-256 and P-384 keys.  (Basically I assumed P-521 uses 512-bit values...)

>    B0 is a byte with following values:
> 
>     value description
> 
>       0   Point O.  In this case there is no x or y octets present.
> 
>       4   Uncompressed point.  x and y of EC point values follow.
> 
>    Note that point O shall not appear in a public or a private
>    key.  Therefore, the size of the MPI payload is always curve_size*2
>    + 3 bits.  For example, for "Curve P-256" the point is represented
>    as a bit string of length 515 bits.

Here it is clearly wrong - it is not (curve_size * 2 + 3), but
(curve_size_padded_to_8 * 2 + 3).

Missing detail: In addition to size check, what other validation must
be done when parsing a point?  This applies to when reading a public key,
but especially when reading incoming ECDH/ECDSA message.  I suggest
adding:  "You must check that the point is on curve." here.

> 8. EC DH Algorithm (ECDH)

>    The key wrapping method is based on [RFC3394].  KDF produces the
>    AES key that is used as KEK as specified in [RFC3394].  Refer to
>    section 13 for the details regarding the choice of the KEK
>    algorithm, which MUST be one of three AES algorithms.

This is only place which says that KEK *MUST* be AES-only.  (Ignoring 12.2)
This is in conflict with section 12.1 and 13, where non-AES is not
disallowed.  I'm not disagreeing with it, just I think it would be good
to clarify why.

It might be good idea to disallow cipher_ids < AES128, but why disallow
Camellia and Twofish?  I could imagine that because the algorithm
is not per-message but comes from key is the reason - you may not
know at key generation time all the people who want to send you messages
and what features their software has.  But I think it would be
good to put the reason in the doc.

In any case, 12.1 and 13 should be synced with the requirement.

>    For convenience, the synopsis of the encoding method is given
>    below, however, this section, [NIST SP800-56A], and [RFC3394] are
>    the normative sources of the definition.
> 
>        Obtain authenticated recipient public key R
>        Generate ephemeral key pair {v, V=vG}
>        Compute shared point S = vR;
>        m = symm_alg_ID || session key || checksum || pkcs5_padding;
>        curve_OID_len = (byte)len(curve_OID);
>        Param = curve_OID_len || curve_OID || public_key_alg_ID || 03 ||
>            01 || KDF_hash_ID || AES_alg_ID for AESKeyWrap ||
>           "Anonymous Sender    " || recipient_fingerprint;
>        Z_len = key size for AES_alg_ID to be used with AESKeyWrap
>        Compute Z = KDF( S, Z_len, Param );
>        Compute C = AESKeyWrap( Z, m ) as per [RFC3394]
>        VB = convert point V to octet string
>        Output (MPI(VB) || len(C) || C).
> 
>    The decryption is the inverse of the method given.  Note that the
>    recipient obtains the shared secret by calculating
> 
>        S = rV = rvG, where (r,R) is the recipient's key pair.
> 
>    Consistent with section 5.13 Sym. Encrypted Integrity Protected
>    Data Packet (Tag 18) of [RFC4880], the MDC SHOULD be used anytime
>    symmetric key is protected by ECDH.

Missing detail:  How to generate v?  What requirements it has?
I suggest expanding the second step with:

     Generate ephemeral key pair {v, V} where V=vG and v is random number
     in range 0 < v < n  (n - curve modulus)

As I noted earlier 8) claims to define ECDH as used in OpenPGP,
and it does - I managed to implement ECDH without digging in those
"real" specs.  That was the only point that I needed to look up.
I think is worth adding here, mostly because it simple.

> 9. Encoding of public and private keys

>    As an implementation note, observe that the ECDH public key fields
>    are the super-set of the ECDH key fields.

First one should be ECDSA.

> 13. Security Considerations

>    SHA-1 MUST NOT be used for ECDSA or with KDF in ECDH method.

But MD5 can?  How about RIPEMD160?  Why single out SHA1?


Final note: the section 8 was quite successful at describing ECDH,
how hard would it be to have same level of description of ECDSA here?
At least I would like to see packet format here, even if the 
algorithm is not described.


-- 
marko