Review of draft-ecc-09

Marko Kreen <markokr@gmail.com> Sat, 18 February 2012 21:51 UTC

Received: from hoffman.proper.com (localhost [127.0.0.1]) by hoffman.proper.com (8.14.5/8.14.3) with ESMTP id q1ILpM5f098086 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sat, 18 Feb 2012 14:51:22 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
Received: (from majordom@localhost) by hoffman.proper.com (8.14.5/8.13.5/Submit) id q1ILpM4w098085; Sat, 18 Feb 2012 14:51:22 -0700 (MST) (envelope-from owner-ietf-openpgp@mail.imc.org)
X-Authentication-Warning: hoffman.proper.com: majordom set sender to owner-ietf-openpgp@mail.imc.org using -f
Received: from mail-ey0-f171.google.com (mail-ey0-f171.google.com [209.85.215.171]) by hoffman.proper.com (8.14.5/8.14.3) with ESMTP id q1ILpKnH098078 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=FAIL) for <ietf-openpgp@imc.org>; Sat, 18 Feb 2012 14:51:21 -0700 (MST) (envelope-from markokr@gmail.com)
Received: by eaan12 with SMTP id n12so2061563eaa.16 for <ietf-openpgp@imc.org>; Sat, 18 Feb 2012 13:51:19 -0800 (PST)
Received-SPF: pass (google.com: domain of markokr@gmail.com designates 10.14.50.193 as permitted sender) client-ip=10.14.50.193;
Authentication-Results: mr.google.com; spf=pass (google.com: domain of markokr@gmail.com designates 10.14.50.193 as permitted sender) smtp.mail=markokr@gmail.com; dkim=pass header.i=markokr@gmail.com
Received: from mr.google.com ([10.14.50.193]) by 10.14.50.193 with SMTP id z41mr7346124eeb.19.1329601879926 (num_hops = 1); Sat, 18 Feb 2012 13:51:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=date:from:to:cc:subject:message-id:mime-version:content-type :content-disposition; bh=g9+WfYBQ/fuwK8J/QKswYXARQf7rJsPYpToiv7b38FI=; b=czvASDf636Ir8tVZTH1+dGfoHG+A6BFfwHRsgcKEYRaffeS+X63K87GSoxnOA8VG35 nK1T/qV1UbH9EmQ7oSMvkfJnP7sFVAHIlvWKjt26ueYQIRw15AbKfSU4MoXvzg2M7eWf KIUxOmzce8EWseq19/Zx/ns0G+mR9HRel+P7c=
Received: by 10.14.50.193 with SMTP id z41mr5903530eeb.19.1329601879834; Sat, 18 Feb 2012 13:51:19 -0800 (PST)
Received: from gmail.com (turu7.ee. [217.159.207.194]) by mx.google.com with ESMTPS id a58sm56436923eeb.8.2012.02.18.13.51.17 (version=SSLv3 cipher=OTHER); Sat, 18 Feb 2012 13:51:18 -0800 (PST)
Date: Sat, 18 Feb 2012 23:51:15 +0200
From: Marko Kreen <markokr@gmail.com>
To: ietf-openpgp@imc.org
Cc: Andrey_Jivsov@symantec.com
Subject: Review of draft-ecc-09
Message-ID: <20120218215115.GA18978@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Sender: owner-ietf-openpgp@mail.imc.org
Precedence: bulk
List-Archive: <http://www.imc.org/ietf-openpgp/mail-archive/>
List-Unsubscribe: <mailto:ietf-openpgp-request@imc.org?body=unsubscribe>
List-ID: <ietf-openpgp.imc.org>

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