Subject: [saag] Standardizing NSA Suite B public key algorithms (Elliptic curve NIST curves) with OpenPGP format

From: Andrey Jivsov <[email-masked]>
Date: Wed, 12 Oct 2011 19:40:38 -0700

Hello SAAG,

May I ask for an advice on what is the best way to advance a personal 
draft into an IETF standard?

Here is the latest version of the draft: 
http://www.ietf.org/id/draft-jivsov-openpgp-ecc-08.txt . Please refer to 
http://sites.google.com/site/brainhub/pgp for up-to-date details.

There are now two inter-operable implementation from different code base 
that implement this format, for example, GnuPG 2.1.0 beta.

The major design goal of the document was simplicity. ECDSA is 
straighforward and maps trivially to what was already defined for DSA 
over modp field. Encryption capability needed new format definitions to 
comply with NIST-blessed guidelines. As a result, the document uses ECDH 
per SP800-56A with AES WRAP. I believe that all described methods in the 
document are in public domain.

It would be great if an AD would help with sponsoring this document.

Any comment is appreciated. Thank you in advance.

---

From: Yoav Nir <[email-masked]>
Date: Fri, 14 Oct 2011 07:07:47 +0200

Hi Andrey.

The best way is to contact one of the security ADs (Sean Turner or Stephen
Farrell) and ask for this to more forward as an individual submission.

Hope this helps

Yoav

On 10/13/11 4:40 AM, "Andrey Jivsov" <[email-masked]> wrote:

>_______________________________________________
>saag mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/saag
>
>Scanned by Check Point Total Security Gateway.

---

From: Rene Struik <[email-masked]>
Date: Fri, 14 Oct 2011 16:55:02 -0400

Hi Andrey:

I had a quick look at your draft ; please see my preliminary notes
below. I hope this helps.

Best regards, Rene

==

Comments on draft-jivsov-openpgp-ecc-08:

Clause 6 (conversion routines):

(T-1) This clause suggests a fixed format for octet representation of
elliptic curve points (l. 8), thus hampering future extensibility
(suggested in the last para). Moreover, this seems to conflict the
format in SEC1 (since there if B0 = 0x00, then one has the point at
infinity). I would suggest specifying the format B0 || x || y only if
the leftmost octet B0 is the octet 0x04 (affine point representation)
and leaving other options for B0 (bar 0x00, 0x02, 0x03) for future
extensibility (the exception set corresponding to point at infinity
(0x00), resp. compressed points (0x02, 0x03), as defined in SEC1).

(T-2) The remark on extensibility (last para) seems to suggest forward
compatibility (which more or less kills extensibility prospects).
Wouldn't the proper approach be that one parses the string B0 || ....
and then simply rejects unrecognized B0 values. With the specification
here this would mean that one rejects the representation if the leftmost
octet is not equal to the string 0x04. This is a far less harsh
requirement on getting a foot in the door with potentially new
conversions, while not hampering proper operation at all.

(E-3) The encoding of elliptic curve points is an octet encoding, so the
output size would be in units of octets. Thus, B0 || x || y has octet
size 2*octet size of the underlying field + 1 (for B0=0x04). The text
suggests 2*curve size + 3 bits, which is not an integer number of
octets; moreover, the curve size (more accurately, the octet size of the
curve) is not necessarily the same as the octet size of the underlying
field. (With NIST prime curves P-256, P-384, P-521 it is, since #E(Fp) <
p and p is just smaller than a power of two, but generally this may not
be the case.)

Clause 7 (key derivation function):

(T-4) The suggested kdf format does not seem to entirely satisfy the
requirements stipulated with NIST SP 800-56a, Section 5.8.1: there, the
kdf has the format
kdf(Z, keydatalen, OtherInfo), where Z is the x-coordinate of the ECDH
key, keydatalen the size of the shared key, and the OtherInfo element
includes {Algorithm Id, PartyUInfo, PartyVInfo}, where PartyUInfo and
PartyVInfo explicitly includes the Ids of the correspondents engaged in
the key agreement scheme (see 800-56a, Section 5.8.1, (3.3) and (3.4)).

With the kdf in the draft, PartyUInfo seems to be independent of the
sender (since set to "anonymous"), whereas PartyVInfo is set to a key
"fingerprint" (as I distilled from Clause 8). Moreover, with the draft,
Z seems to be set to the (x,y) coordinates of the computed ECDH key,
although - admittedly, it may be the x-coordinate only {the pseudo-code
of Clause 7 refers to P for both the key P:=(x,y) and for "parameters",
which is ambiguous}.

Since the x-coordinate of the ECDH key K:= a(Qb) = b(Qa) does not
require the y-coordinate of inputs Qb or Qa, it would be a pity if one
would just need that as input to the kdf, without much benefit (after
all, the y-coordinate only adds 1 bit of entropy here). I presume this
confusion is just caused by ambiguity in the text and could easily be
taken away.

Clause 8 (ECDH):

(E-5) With the 2nd para, it is suggested that ECDH (or: C(1,1, ECC CDH))
in NIST SP 800-56a is modified, to always assume that the co-factor h of
the curve always assumes the value h=-1. This does not seem a
modification at all, since the only curves defined with this draft are
the NIST prime curves P-256, P-384, and P-521, which do have h=1. Thus,
any instantiation of the draft with the specified curves leaves the NIST
SP 800-56a as is.

(E-6) Third bullet, l. 2: replace "the corresponding filed" by "the
corresponding field".

(T-7) Third bullet, last sub-bullet: shouldn't the size of the
fingerprint be consistent with the cryptographic key strength? (e.g.,
for top secret info (Clause 12.2.2), one would have a 384-bit
fingerprint, rather than a 160-bit entry).

Clause 9 (Encoding of Public and Private Keys)

I presume the hash function Id and the algorithm Id are specified
elsewhere (could not immediately find those).

==

On 12/10/2011 10:40 PM, Andrey Jivsov wrote:
> http://www.ietf.org/id/draft-jivsov-openpgp-ecc-08.txt . Please refer
> to http://sites.google.com/site/brainhub/pgp for up-to-date details.
>
> There are now two inter-operable implementation from different code
> base that implement this format, for example, GnuPG 2.1.0 beta.
>
> over modp field. Encryption capability needed new format definitions
> to comply with NIST-blessed guidelines. As a result, the document uses
> ECDH per SP800-56A with AES WRAP. I believe that all described methods
> in the document are in public domain.
>

-- 
email: [email-masked]
Skype: rstruik
cell: +1 (647) 867-5658
USA Google voice: +1 (415) 690-7363

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 14 Oct 2011 04:16:02 -0700

Hello Rene. Thank you for your comments.

> (0x00), resp. compressed points (0x02, 0x03), as defined in SEC1).

I could not identify a conflict. The draft says to use uncompressed 
version with the tag value 0x04.

> conversions, while not hampering proper operation at all.

The draft doesn't prohibit other values. An application that implements 
the draft need only support the uncompressed point. This is the easiest 
route to establish inter-operability base. A future companion RFC can 
define other storage-efficient format.

What this future storage-efficient format will be is yet unclear. In the 
context of OpenPGP the storage efficiency is most beneficial with 
encrypted messages (which can have multiple recipients). It's more 
acceptable to have slightly larger public keys. ECDSA signatures don't 
contain points. This leaves us with ECDH as the most relevant target.

There is a method noted in 1985 by Miller for ECDH, documented in 
RFC6090, that doesn't require any compression. It simply irrecoverably 
drops the y coordinate. Given that OpenPGP ECC draft, per NIST 
guideline, uses only x coordinate to calculate the shared secret, this 
method offers another alternative you didn't mention for storage 
efficiency. In this case B0 is neither 0x2 nor 0x3, although it can be 
fixed at any some of these values for inter-operability. In any case, 
this is a subject for another document.

> field. (With NIST prime curves P-256, P-384, P-521 it is, since #E(Fp)<

OpenPGP MPI size encoding counts in bits, not bytes. Binary 
representation of 0x04 adds 3 bits. The following is a point representation:

    MPI_HEADER 4 x y

MPI_HEADER occupies 2 bytes and contains the size of the following large 
integer in bits, which highest octet is 04.

Thank you for pointing the concern for the underlying filed v.s. curve 
size. Since OpenPGP RFC 4880 is a storage format (as opposed to a 
policy), by curve size I meant the underlying field size, i.e. the size 
needed to store an x or an y. I will review the document for consistency 
in this respect.

So far the interest in OpenPGP community was for NIST Suite B curves and 
German Brainpool curves.  For there uses the terms are essentially synonyms.

> "fingerprint" (as I distilled from Clause 8).

The key's fingerprint is the identity in OpenPGP. This is what 
identifies a recipient. A fingerprint is what binds a signer to a signed 
message. An OpenPGP key typically contains multiple UserIDs (one per 
e-mail address), but they are not bound to a signed message. Same with 
public key certifications.

Anonymous encryption is a typical use of OpenPGP. Messages can be 
further signed, but the encryption is anonymous. In the context of a DH 
scheme with a static recipient key and an ephemeral sender's key, one 
can argue that the recipient is communicating with an Anonymous sender. 
There is no expectation of origin authentication with encrypted-only 
messages in OpenPGP.

As a practical matter, requiring sender binding in OpenPGP encryption 
will be difficult to achieve in practice. Users/automated agents may 
have multiple keys on their local keyrings and requiring them to select 
a key will not fit into variety of application use models. 
Users/automated agents, when acting as senders, may have no keys at all. 
In fact, the sender's identity as defined in SP 800-56a is not 
cryptographically proven, allowing no more security than simply putting 
"Anonymous" as a sender.

> Moreover, with the draft,

Only x contributes to the shared key.

Section 7 defines the KDF. It contains the text "extract the x portion 
from".

> any instantiation of the draft with the specified curves leaves the NIST

One of reasons for this is that by fixing the co-factors at 1 this 
document signals to the applications to not worry about cofactor-related 
attacks and the difference in on-the-wire format for cofactor != 1.

> (E-6) Third bullet, l. 2: replace "the corresponding filed" by "the

Thank you, noted.

> fingerprint, rather than a 160-bit entry).

Fingerprints are hardwired to be SHA-1 in OpenPGP. (SHA-1 is bellow the 
minimum requirement of the draft)

> elsewhere (could not immediately find those).

These IDs are from the main document, OpenPGP RFC4880.

This draft request ID 18 for ECDH. 19 was already reserved for ECDSA, 
and this draft uses the 19 with the ECDSA public key format. We are not 
aware of any deployed applications that were using ID 19 before.

Thank you.