Re: ECC in OpenPGP proposal

Hello Ian, thank you for your comments.

Ian G wrote:
> Hi all,
>
>
> Some comments.  Caveat:  I wouldn't know an EC if someone hit me over 
> the head with it...
> Big comment:  far too much variability, for little gain.
>
>
>
>
>
>
> Andrey Jivsov wrote:
> > Hello OpenPGP list,
> >
> > as Hal Finney had mentioned earlier, here is the draft:
> >    http://brainhub.googlepages.com/2008-draft-ietf-openpgp-ecc-pre-6.txt
> >
> > Unless you read this on a text terminal, here is the document in 
> > alternative formats that offer cross-references as navigation links:
> >    http://brainhub.googlepages.com/pgp
> > Why do we need ECC? The main reason is better alignment with the 
> > strength of symmetric key. Given that US government has chosen ECC in 
> > favor of modp for larger key sizes, this proposal is carefully 
> > written to comply with NSA Suite-B.
> I think it is sufficient to state that you want a Suite-B compatible 
> profile.
Suite-B offers fewer choices than this spec does. Some of restrictions 
imposed by Suite-B are debatable.
The purpose of this draft is to match the strength of AES-128, AES-192 
and AES-256. See section 12 for corresponding sizes for hashes and 
curves (which are "double width" of AES key sizes).
http://brainhub.googlepages.com/2008-draft-ietf-openpgp-ecc-pre-6.html#toc15 

Suite-B only lists AES-128 and AES-256, EC P256 and P384, SHA-256 and 
SHA-384. This creates a shift in relative strength. To illustrate this 
using the table in section 12, NSA dropped the row with AES-256 and 
replaced AES-192 with AES-256 in the second raw, resulting in weaker top 
public key algorithm.
Suite-B allows some patented techniques that were excluded.

This leaves us with two curves for Suite-B, but since we must have two, 
why not add next strongest one as SHOULD for better symmetry?  Without 
EC P521 addition applications will be left with 15K RSA/ElGamal key or 
weaker EC P384 to match AES-256.
>   ... "SHOULD support ECDH"
>
> what is the point of not supporting ECDH?  I recommend MUST.
I can support this.

However, please note that the signature has more weight by being a tool 
of certifications, i.e. self-signatures depends on it. Without support 
for ECDSA we cannot have functional EC keys, while we can have sign-only 
keys without ECDH. It is possible to have sign+encrypt keys with ECDSA 
top key and modp ElGamal DH.
Also note that ECDH brings with it the need to implement KDF and key 
wrapping methods, because there is no ElGamal alternative in ECC field. 
ECDSA should be easier to implement than ECDH.
> =====
>
> 6.  ... "the KDF hash function MAY be any hash function defined in 
> [FIPS 180-2] or its successor, except that SHA-1 MUST NOT be used."
> What is the point in permitting alternatives?  If there is a good 
> reason, I would prefer to see them enumerated for better understanding 
> and for certainty.
This is to continue good tradition of algorithm agility in OpenPGP. I am 
sure TLS designers would like to get rid of MD5, hardwired into their 
analog of KDF.
Implementors are advised to follow the recommendations set in the table 
of section 12, which will mean that there are 3 ways to set up KDFs, 
parameterized by different hash algorithms, for each of 3 sizes of 
symmetric keys. The hash algorithms have already been implemented in 
vast majority of OpenPGP applications. The code to use KDF should be 
written using generic hash API, so that there will be no difference 
which hash algorithm is passed to initialize this API. Overall, I think 
the benefits overweight the slightly more complex format.
> I especially don't like "or its successor."
I can drop this clause. I attempted to write a spec that doesn't need to 
be updated after NIST introduces new hashes. I wanted to make external 
the definition of what the right hashes for AES-128, AES-192, and 
AES-256 are.
> I ask ... without expecting to understanding the answer ... why it is 
> that it is useful or necessary to permit any variability in the KDF?
In summary, this follows from the need to support every AES key size. No 
other variability is allowed in section 6.
> =====
>
>
>
> 11.2  I don't think it makes sense for OpenPGP WG to suggest that it 
> knows what "Secret" and "Top Secret" means, nor that it can "achieve" 
> this.  The normative place for that is NSA.  If some guidance of 
> intentions is useful, it should be in the sense of a comment.  "This 
> profile is intended to be compatible with Suite B."  If the NSA can be 
> convinced to make a statement as to what works for them, include that too.
These Secret/Top Secret classifications are from Suite-B page. I can add 
your suggestion and the phrase "[SUITE-B] is the normative source of the 
definition" to section 11.2.  We need a way to say what an OpenPGP 
application shall do to comply with each level of Suite-B security.
http://www.nsa.gov/ia/industry/crypto_suite_b.cfm

> ====
>
> 11.2  I don't see any point in providing both Secret and Top Secret?  
> This seems like a way to create comaptibility problems for zero 
> payoff.  I suggest the full Top Secret as the only profile, and that's 
> it.
I think that the incremental cost to achieve Secret level of Suite-B is 
insignificant, given that an application has implemented Top Secret 
level. In addition, because I've dropped some of patented methods 
allowed by Suite-B, in my mind the scale is tipped to offer more 
choices. Also, Top Secret has less symmetry in the sense of relative 
security than Secret, as mentioned above.
> ====
>
> 11.  Indeed, what is the point in allowing people to fiddle around 
> with different curves, KDFs, and hashes?  Nobody has ever cracked any 
> of them, or nobody that we care about (which excludes the NSA, 
> perversely).  Set one and leave it as that.
> This "profile" proposes 2 different public key algorithms, 3 different 
> curves (plus future ones), 3 different hashes (plus future ones), 3 
> different AES strengths, MDC on or off, It/Salt as a SHOULD.
My goal was to limit as much as I can. Let me explain how I arrived at 
the present set. I will leave MDC and S2K out of this section.
Here is what have now:

 We want to support 3 sizes of AES algorithms.
 AES algorithms pair with 3 hashes and 3 curves in the sense of 
relative security.
 We need encryption and signing, and this is achieved with two new 
public key algorithms.
Let's put this into perspective and sketch what it could have been. In 
addition to above:
 Point compression format.
 Curves in binary field, using polynomial or normal basis representations
 Curves in prime field that allow the choice of the prime; there is no 
limit to customization, up to the random curves over random underlying 
fields
 ECDH with cofactor; ECMQV (both patented)
 Multiple KDF or key wrapping method in conjunction with ECDH

Another way to look at how flexible or constrained current proposal is 
is by comparing its flexibility with, for example, current modp ElGamal 
encryption in OpenPGP. An OpenPGP application today generates its own 
prime and is not constrained by the allowed size of such a prime 
(usually in a range of 1024-4096 bits). In this ECC proposal we 
essentially folding infinite number of primes into 3 predefined primes.
This proposal offers the least choice of ECC parameters of any IETF 
standard.
> I suggest you would half the entire workload by reducing all above 
> choices to 1 MUST, and reduce the compatibility problems to about a 
> tenth.
> It would then have a good chance of being a really useful profile.  To 
> business folks who don't care for the tea-room discussion about key 
> lengths and rights to be compatible but uncommunicative...
At present the only MUST for OpenPGP are curves ID 1 and 2. It also says 
that SHA-256 and SHA-384 are MUST. All this is in section 11.1. These 
are the curves/hashed approved by Suite-B. I can accepts that we reduce 
the OpenPGP profile to ID 1 and SHA-256. This will match Suite-B 
"Secret" level and drop "Top Secret".
The section 11.2 is for Suite-B compatibility. The MUSTs there are for 
applications implementing Suite-B profile. I should put a sentence into 
11.2 that makes this clear. I wasn't trying to tell an applications 
which Suite-B profile to use (for this there is section 12).
> =====
>
> 12.  "MDC SHOULD be used when symmetrical encryption key is protected 
> by ECDH."
> Is there any good reason to permit it to be dropped?  Remove a 
> compatibility complaint, make it a MUST?
Hal Finney had a reservation that MDC and S2K are orthogonal to ECC, so 
I changed the key word to SHOULD. The proponents of MUST would take an 
opportunity to tighten the security, because only recently updated 
applications can understand the ECC key. I will go with the consensus, 
and if there is none, I am happy to remove these references.
> Iterated and Salted S2K ... Ditto.

I looks forward to see other responses. I am flexible on many of these 
issues in the interest of the consensus.