[openpgp] EdDSA problem and possible change about ECC

[NIIBE Yutaka <[e-mail]>]

Hello,

I'm currently considering to add ECDH X448 to OpenPGP.

While I examined GnuPG and libgcrypt for that, I realized that there are
some discrepancy/inconsistency and possible interoperability issues
among OpenPGP implementations.

Thus, I share my observations and I'd like to propose changes of OpenPGP
specification.  I'd like to listen from different OpenPGP
implementations.

The issue is about EdDSA (and possibly for ECDH X448 in future).

Current implementation of GnuPG 2.2 has/does:

(1) discrepancy/inconsistency

  * In EdDSA key, it uses the prefix 0x40 for an EC point representation.
  * In EdDSA signature, for R, it uses no prefix for an EC point
    representation.

  Note that:
    GnuPG accepts EdDSA key with no prefix in an EC point.
    GnuPG does _not_ accept EdDSA signature which R has the prefix
    0x40.

(2) Removal of zeros in MPI handling in EdDSA

  While the native EdDSA octet string for secret is defined as
  fixed-size, it is defined as an MPI (big-endian) in OpenPGP.

  While the native EdDSA EC point representation is defined as
  fixed-size little-endian, it is defined as an MPI in OpenPGP.

  While the native EdDSA integer representation is defined as fixed-size
  little-endian, it is defined as an MPI (big-endian) in OpenPGP.

  Because of this,

  * In EdDSA secret key, the zeros (least significant bytes) in native
    representation of the secret are removed to compose an MPI.

  * In EdDSA signature, the zeros (least significant bytes) in native
    representation of an EC point R are removed to compose an MPI.

  * In EdDSA signature, the zeros (least significant bytes) in native
    representation of an integer S are removed to compose an MPI.

(3) Recovery of zeros in MPI handling in EdDSA

  To compensate the problem (2), it does special handling to recover
  zeros when it receives an EdDSA secret/signature in OpenPGP format.


While we should keep support of zero-removed EdDSA secret/signature, I
think that it's good to modify GnuPG so that it won't generate possibly
problematic EdDSA secret/signature any more.

And it's good to clarify the specification, so that EdDSA
secret/signature with no-zero removal (zeros as-is) can be valid.  I'm
afraid that no-zero removal EdDSA secret/signature is invalid by the
current draft of rfc4880bis, as ill-formed MPI.


So.... here is my suggestion to OpenPGP specification.

Since my language skill for specification is poor, I don't intend to fix
the text by my words, but I would like to point out the place where we
need to fix.

In the following patch, I introduced "SOS" for "simply, octet string".
I know it's not good term, it should be replaced by more relevant term
soon.  Please help for good term choice.

The reason for SOS is that I think that it is not good for curves which
have native format in fixed-size little-endian to use MPI to represent
its EC point and its integer.  The structure of SOS is exactly same
as MPI, so that existing implementation can avoid larger changes (no
change, hopefully).

When we will able to define an EC point representation as SOS, we won't
need to use the prefix 0x40, and we won't need to claim it as an
extension of the encoding given in SEC1.  While we need to support
existing Ed25519 keys with the prefix 0x40, in future, for Ed448 keys
and X448 keys (including ephemeral keys in ECDH), we can use no prefix
cleanly.


==========================
diff --git a/middle.mkd b/middle.mkd
index ca73704..3e3b548 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -211,6 +211,15 @@ Unused bits of an MPI MUST be zero.
 Also note that when an MPI is encrypted, the length refers to the
 plaintext MPI.  It may be ill-formed in its ciphertext.
 
+## Simply, Octet String
+
+Simply-Octet-String (also called SOSs) are opaque octet strings.
+
+A SOS consists of two pieces: a two-octet scalar that is the length of
+the SOS in bits followed by a string of octets.
+
+It should accepts SOS with unused bits in the first octet.
+
 ## Key IDs
 
 A Key ID is an eight-octet scalar that identifies a
@@ -636,7 +645,8 @@ The body of this packet consists of:
 
     Algorithm-Specific Fields for ECDH encryption:
 
-      - MPI of an EC point representing an ephemeral public key.
+      - SOS of an EC point representing an ephemeral public key.  It
+        may comes with the prefix octet of 0x40.
 
       - a one-octet size, followed by a symmetric key encoded using the
         method described in [](#ec-dh-algorithm-ecdh).
@@ -979,13 +989,13 @@ The body of a V4 or V5 Signature packet contains:
 
     Algorithm-Specific Fields for EdDSA signatures:
 
-      * MPI of EdDSA compressed value r.
+      * SOS of an EC point r.
 
-      * MPI of EdDSA compressed value s.
+      * SOS of an integer representing EdDSA value s.
 
-The compressed version of R and S for use with EdDSA is described in
-[](#RFC8032).  A version 3 signature MUST NOT be created
-and MUST NOT be used with EdDSA.
+The format of R and S for use with EdDSA is described in [](#RFC8032).
+A version 3 signature MUST NOT be created and MUST NOT be used with
+EdDSA.
 
 The concatenation of the data being signed and the signature data from
 the version number through the hashed subpacket data (inclusive) is
@@ -2301,7 +2311,7 @@ The public key is this series of values:
       - the octets representing a curve OID, defined in
         [](#ecc-curve-oid);
 
-  * a MPI of an EC point representing a public key.
+  * MPI of an EC point representing a public key.
 
 The secret key is this single multiprecision integer:
 
@@ -2322,13 +2332,12 @@ The public key is this series of values:
       - the octets representing a curve OID, defined in
         [](#ecc-curve-oid);
 
-  * a MPI of an EC point representing a public key Q as described
-    under EdDSA Point Format below.
+  * SOS of an EC point representing a public key Q.  It may comes with
+    the prefix octet of 0x40.
 
 The secret key is this single multiprecision integer:
 
-  * MPI of an integer representing the secret key, which is a
-    scalar of the public EC point.
+  * SOS representing the secret key.
 
 
 ### Algorithm-Specific Part for ECDH Keys
@@ -2344,7 +2353,8 @@ The public key is this series of values:
       - the octets representing a curve OID, defined in
         [](#ecc-curve-oid);
 
-  * a MPI of an EC point representing a public key;
+  * SOS of an EC point representing a public key.   It may comes with
+    the prefix 0x40.
 
   * a variable-length field containing KDF parameters,
     formatted as follows:
@@ -2365,8 +2375,8 @@ fields that define an ECDSA key, plus the KDF parameters field.
 
 The secret key is this single multiprecision integer:
 
-  * MPI of an integer representing the secret key, which is a
-    scalar of the public EC point.
+  * SOS representing the secret key, which is a scalar of the public
+    EC point.
 
 
 ## Compressed Data Packet (Tag 8)
@@ -4035,10 +4045,10 @@ in detail how this sequence of bytes is formed.
 ## ECDSA and ECDH Conversion Primitives
 
 This document defines the uncompressed point format for ECDSA and ECDH
-and a custom compression format for certain curves. The point is
-encoded in the Multiprecision Integer (MPI) format.
+and a custom compression formats for certain curves. The point is
+encoded in SOS format.
 
-For an uncompressed point the content of the MPI is:
+For an uncompressed point the content of the SOS is:
 
     B = 04 || x || y
 
@@ -4048,17 +4058,18 @@ size.  The adjusted underlying field size is the underlying field size
 that is rounded up to the nearest 8-bit boundary.  This encoding is
 compatible with the definition given in [](#SEC1).
 
-For a custom compressed point the content of the MPI is:
+For a custom compressed point the content of the SOS is:
 
     B = 40 || x
 
 where x is the x coordinate of the point P encoded to the rules
-defined for the specified curve.  This format is used for ECDH keys
-based on curves expressed in Montgomery form.
+defined for the specified curve.  The prefix octet 0x40 is optional.
+This format is used for ECDH keys based on curves expressed in
+Montgomery form.
 
-Therefore, the exact size of the MPI payload is 515 bits for "Curve
-P-256", 771 for "Curve P-384", 1059 for "Curve P-521", and 263 for
-Curve25519.
+Therefore, the exact bit size of the SOS payload is 515 bits for
+"Curve P-256", 771 for "Curve P-384", 1059 for "Curve P-521", and 263
+for "Curve25519".  For "X448", it's 448 bits with no prefix.
 
 Even though the zero point, also called the point at infinity, may
 occur as a result of arithmetic operations on points of an elliptic
@@ -4077,17 +4088,20 @@ given recipient of a given message.
 
 ## EdDSA Point Format
 
-The EdDSA algorithm defines a specific point compression format.  To
-indicate the use of this compression format and to make sure that the
-key can be represented in the Multiprecision Integer (MPI) format the
-octet string specifying the point is prefixed with the octet 0x40.
-This encoding is an extension of the encoding given in [](#SEC1) which
-uses 0x04 to indicate an uncompressed point.
+The EdDSA algorithm defines a specific point compression format.  In
+order to the key can be interpreted in the Multiprecision Integer
+(MPI) format, the octet string specifying the point may be prefixed
+with the optional octet 0x40.  This encoding is an extension of the
+encoding given in [](#SEC1) which uses 0x04 to indicate an
+uncompressed point.
 
 For example, the length of a public key for the curve Ed25519 is 263
 bit: 7 bit to represent the 0x40 prefix octet and 32 octets for the
 native value of the public key.
 
+The length of a public key for the curve Ed448 is 448 bit: no prefix
+octet and 56 octets for the native value of the public key.
+
 
 ## Key Derivation Function
 
@@ -4230,7 +4244,7 @@ normative sources of the definition.
     Compute Z = KDF( S, Z_len, Param );
     Compute C = AESKeyWrap( Z, m ) as per [RFC3394]
     VB = convert point V to the octet string
-    Output (MPI(VB) || len(C) || C).
+    Output (SOS(VB) || len(C) || C).
 
 The decryption is the inverse of the method given.  Note that the
 recipient obtains the shared secret by calculating
--