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