Subject: Re: ECC in OpenPGP proposal: how to use ECDH

From: Andrey Jivsov <[email-masked]>
Date: Thu, 06 Mar 2008 00:33:17 -0800

Erratum 1:  nist_aes_wrap is shown in
http://brainhub.googlepages.com/aeswrap-RFC3394.c.html, while the 
algorithm is defined in RFC 3394.

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 06 Mar 2008 00:29:04 -0800

Responding to request by David, I will describe in more details what is 
happening during ECDH encryption, the only encryption scheme allowed in 
the spec.

( Please check for errata before implementing anything from this. )

High-level overview of the steps:

    1) Generate shared EC point
    2) Generate KEK from it
    3) use KEK with RFC3394 to encrypt symmetric key.

Step 1. ECDH public key contains s*G, which is a curve point (think of 
it as g^s in modp notation).

Step 2. Sender generates its secret v and calculates v*G. Then the point 
S =v*s*G is the initial shared secret.

Step 3. Sender arrives at common symmetric message encryption key 
algorithm for the recipients. The algorithm is encoded with a byte from 
RFC4880, for example, for AES -128 use 7. Sender generates random string 
of appropriate length for the key and appends it to the algorithm ID, 
for example:

    07   R1 R2 R3 R4 R5 R6 R7 R8 R9 Ra Rb Rc Rd Re Rf R10

where R* is a random byte.

Step 4. Sender appends 16 byte checksum to this string:

    07   R1 R2 R3 R4 R5 R6 R7 R8 R9 Ra Rb Rc Rd Re Rf R10  C0 C1

(This is what passed in RFC4880 to PKCS#1 padding.)

Step 5. Set KDF parameter like this:

    Param = 01 16 01 0a 09 "AnonymousSender" F0 F1 F2 ... F14

This setting assumes recipient curve ID 1, IANA assignment of value 
22=0x16 for ECDH, SHA512 for KDF (ID 10=0xa), AES-256 for AESWrap. F* is 
the 20 byte fingerprint of the recipient. There are always 40 bytes here.

Step 6. Pass 40 byte KDF parameter from step 5 and point S from step 2 
to KDF in section 6 
http://brainhub.googlepages.com/2008-draft-ietf-openpgp-ecc-pre-6.html#toc5 
. KDF works in counter-mode-style and outputs KEK. Stop when sufficient 
number of bits for selected AESWrap algorithm is generated (AES-256 in 
our example, so we need 32 bytes).

* Using KEK from step 6 and string in step 4, call nist_aes_wrap, 
defined in 
http://brainhub.googlepages.com/2008-draft-ietf-openpgp-ecc-pre-6.html.

  nist_aes_wrap( c, kPGPCipherAlgorithm_AES256,
    KEK, 32,
    {07 R1 R2 R3 R4 R5 R6 R7 R8 R9 Ra Rb Rc Rd Re Rf R10 C0 C1}, 19,
    out, 32, &actual_size );

AES-128, AES-256, AES-256, SHA2-256, SHA2-384, and SHA2-512 are the only 
algorithms allowed with AESWrap and KDF. This restriction has no 
relation to message encryption symmetric key or hash used for message 
signing.

The following is not mentioned in the spec, but I think the sender 
should start from the AES-256 and SHA-512 and move down to choose weaker 
algorithms if recipient has excluded these algorithms from its key 
preferences for encryption or hash list.