The OpenPGP standard is in a bit of a mess when it comes to wire
formats for public key algorithms.
There are not infrequent reports of interoperability problems (most
recently https://dev.gnupg.org/T5464), and difficulties for
implementers in understanding what is expected.
I believe everything I've included in this changeset is in line with
existing wire format practice. I am not trying to make substantive
changes in wire format here, just to more accurately describe what
existing implementations do.
This changeset tries to clarify the situation by explicitly spelling
out (and summarizing!) the wire formats for each public key algorithm,
using the IANA registries for organized, tabular clarity. In
particular, we are interested in wire formats for public keys, secret
keys, signatures, and encryption frames.
This proposed change uses the term "SBS" ("stripped bit string") to
describe the weird form used by existing OpenPGP implementations for
Ed25519 and Curve25519, where leading zeros are stripped but the
"native" format is still used. This is an homage to gniibe's "SOS"
proposal, while acknowledging that what Ed25519 and Curve25519 are
doing isn't quite SOS.
More significantly, the proposal explicitly binds specific elliptic
curves to specific wire formats. So, if you're using NIST P-256, the
wire format will always be the same going forward. If you're using
EdDSA with Ed25519, it will also always use the same form. Most
importantly, this clears the way for us to introduce simpler wire
formats for new algorithms in the future (like "native 56-octet
string" for Ed448).
I believe this tight coupling is acceptable because anywhere these
asymmetric elements (pubkey, seckey, signature, encryption) show up
there is nothing of significance *after* them in any OpenPGP packet.
So either you know the key and curve you're using (in which case you
know how to parse the field) or you don't (in which case an ignorant
parser can simply skip to the end of the packet directly, with no harm
because it couldn't have dealt with the data anyway).
I also believe this is acceptable because i don't know of anyone has
actually tried to use alternate formats -- for EC points, scalars, etc
-- with any curves other than the 25519 work. If that's wrong, I hope
folks will speak up and show evidence.
I am *not* confident in either my descriptions of the structures, or
in how I've mapped them to different curves. I hope the WG will
review the proposed changes, and help to resolve any lack of clarity
or misrepresentations.
---
crypto-refresh.md | 174 +++++++++++++++++++++++++++++-----------------
1 file changed, 112 insertions(+), 62 deletions(-)
diff --git a/crypto-refresh.md b/crypto-refresh.md
index 4b2d001..a47b5b8 100644
--- a/crypto-refresh.md
+++ b/crypto-refresh.md
@@ -411,6 +411,24 @@ 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.
+## Stripped Bit Strings
+
+A Stripped Bit String (SBS) is formed in the same way as a MPI, but it encodes
a "native" bit string, not a big-endian integer, while stripping leading zero
bits.
+
+The "length" of a bit string for this structure is calculated as the number of
bits starting from the first 1 bit through the end of the string.
+
+On the wire, an SBS starts with a two-octet scalar that is the length,
followed by a whole number of octets representing the bit string starting with
the first non-zero octet.
+
+Like an MPI, the size on the wire of an SBS is ((SBS.length + 7) / 8) + 2
octets.
+
+Note that due to stripping of leading zeros, it is not possible with an SBS to
encode a distinct string that has any leading zero bits.
+That is, the raw 12-bit string `0b000000001111` would be encoded as an SBS in
exactly the same way as the 6-bit string `0b001111` --- both would be `[00 04
0f]` on the wire.
+
+An implementation that encounters an SBS encoding in a context that demands an
octet string with exactly N bits (e.g. for a native format that wants a
fixed-length string) may find an SBS with fewer than N bits.
+In this case, the implementation MUST create its internal representation of
the value by prefixing zero bits to the wire representation, to bring the
string to the expected size.
+
+This format is NOT RECOMMENDED for use when specifying future algorithms with
OpenPGP, but it is necessary for handling pre-existing data.
+
## Key IDs
A Key ID is an eight-octet scalar that identifies a key.
@@ -752,7 +770,7 @@ The body of this packet consists of:
Algorithm-Specific Fields for ECDH encryption:
- - MPI of an EC point representing an ephemeral public key.
+ - An EC point representing an ephemeral public key, encoded according to the
curve in use.
- a one-octet size, followed by a symmetric key encoded using the method
described in {{ec-dh-algorithm-ecdh}}.
@@ -1843,13 +1861,11 @@ The public key is this series of values:
- a one-octet size of the following field; values 0 and 0xFF are reserved
for future extensions,
- - the octets representing a curve OID, defined in {{ecc-curve-oid}};
+ - the octets representing a curve OID, defined in {{ecc-curves}};
-- a MPI of an EC point representing a public key.
+- an EC point representing a public key, encoded according to the curve used.
-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.
+The secret key is encoded according to the curve used, see {{ecc-curves}}.
### Algorithm-Specific Part for EdDSA Keys
@@ -1859,13 +1875,11 @@ The public key is this series of values:
- a one-octet size of the following field; values 0 and 0xFF are reserved
for future extensions,
- - the octets representing a curve OID, defined in {{ecc-curve-oid}};
+ - the octets representing a curve OID, defined in {{ecc-curves}};
-- a MPI of an EC point representing a public key Q as described under EdDSA
Point Format below.
+- an EC point representing a public key Q, encoded according to the curve used.
-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.
+The secret key is encoded according to the curve used, see {{ecc-curves}}.
### Algorithm-Specific Part for ECDH Keys
@@ -1875,9 +1889,9 @@ The public key is this series of values:
- a one-octet size of the following field; values 0 and 0xFF are reserved
for future extensions,
- - the octets representing a curve OID, defined in {{ecc-curve-oid}};
+ - the octets representing a curve OID, defined in {{ecc-curves}};
-- a MPI of an EC point representing a public key;
+- an EC point representing a public key, encoded according to the curve used;
- a variable-length field containing KDF parameters, formatted as follows:
@@ -1891,9 +1905,7 @@ The public key is this series of values:
Observe that an ECDH public key is composed of the same sequence of 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.
+The secret key is encoded according to the curve used, see {{ecc-curves}}.
## Compressed Data Packet (Tag 8)
@@ -2509,18 +2521,18 @@ See {{notes-on-algorithms}} for more discussion of the
algorithms.
## Public-Key Algorithms {#pubkey-algos}
{: title="Public-key algorithm registry"}
-ID | Algorithm
----:|--------------------------
- 1 | RSA (Encrypt or Sign) {{HAC}}
- 2 | RSA Encrypt-Only {{HAC}}
- 3 | RSA Sign-Only {{HAC}}
- 16 | Elgamal (Encrypt-Only) {{ELGAMAL}} {{HAC}}
- 17 | DSA (Digital Signature Algorithm) {{FIPS186}} {{HAC}}
- 18 | ECDH public key algorithm
- 19 | ECDSA public key algorithm {{FIPS186}}
+ID | Algorithm | Public Key Format | Secret Key Format | Signature Format |
Encryption Format
+---:|--------------------------|---|---|---|---
+ 1 | RSA (Encrypt or Sign) {{HAC}} | MPI(n), MPI(e) | MPI(d), MPI(p), MPI(q),
MPI(u) | MPI(m\**d mod n) | MPI(m\**e mod n)
+ 2 | RSA Encrypt-Only {{HAC}} | MPI(n), MPI(e) | MPI(d), MPI(p), MPI(q),
MPI(u) | N/A | MPI(m\**e mod n)
+ 3 | RSA Sign-Only {{HAC}} | MPI(n), MPI(e) | MPI(d), MPI(p), MPI(q), MPI(u) |
MPI(m\**d mod n) | N/A
+ 16 | Elgamal (Encrypt-Only) {{ELGAMAL}} {{HAC}} | MPI(p), MPI(g), MPI(y) |
MPI(x) | N/A | MPI(g\*\*k mod p), MPI (m * y\*\*k mod p)
+ 17 | DSA (Digital Signature Algorithm) {{FIPS186}} {{HAC}} | MPI(p), MPI(q),
MPI(g), MPI(y) | MPI(x) | MPI(r), MPI(s) | N/A
+ 18 | ECDH public key algorithm | OID, Point (see {{ecc-curves}}) | see
{{ecc-curves}} | N/A | Point (see {{ecc-curves}})
+ 19 | ECDSA public key algorithm {{FIPS186}} | OID, Point (see {{ecc-curves}})
| see {{ecc-curves}} | see {{ecc-curves}} | N/A
20 | Reserved (formerly Elgamal Encrypt or Sign)
21 | Reserved for Diffie-Hellman (X9.42, as defined for IETF-S/MIME)
- 22 | EdDSA {{RFC8032}}
+ 22 | EdDSA {{RFC8032}} | OID, Point(see {{ecc-curves}}) | see {{ecc-curves}}
| see {{ecc-curves}} | N/A
23 | Reserved (AEDH)
24 | Reserved (AEDSA)
100 to 110 | Private/Experimental algorithm
@@ -2532,10 +2544,9 @@ See {{rsa-notes}}.
See {{reserved-notes}} for notes on Elgamal Encrypt or Sign (20), and X9.42
(21).
Implementations MAY implement any other algorithm.
-
A compatible specification of ECDSA is given in {{RFC6090}} as "KT-I
Signatures" and in {{SEC1}}; ECDH is defined in {{ec-dh-algorithm-ecdh}} this
document.
-## ECC Curve OID
+## ECC Curve OID {#ecc-curves}
The parameter curve OID is an array of octets that define a named curve.
The table below specifies the exact sequence of bytes for each named curve
referenced in this document:
@@ -2549,6 +2560,15 @@ ASN.1 Object Identifier | OID len | Curve OID bytes in
hexadecimal representatio
1.3.6.1.4.1.11591.15.1 | 9 | 2B 06 01 04 01 DA 47 0F 01 | Ed25519
1.3.6.1.4.1.3029.1.5.1 | 10 | 2B 06 01 04 01 97 55 01 05 01 | Curve25519
+{: title="ECC Curve wire formats"}
+Curve name | ECDSA? | EdDSA? | ECDH? | EC Point Format | Secret Key Format |
Signature Format
+-----------|---|---|---|--------------|-------------|---
+NIST P-256 | Y | N | Y | Uncompressed | MPI(scalar) | MPI(r), MPI(s)
+NIST P-384 | Y | N | Y | Uncompressed | MPI(scalar) | MPI(r), MPI(s)
+NIST P-521 | Y | N | Y | Uncompressed | MPI(scalar) | MPI(r), MPI(s)
+Ed25519 | N | Y | N | MPI-wrapped Native | SBS(native scalar) | SBS(r), SBS(s)
+Curve25519 | N | N | Y | MPI-wrapped Native | SBS(native scalar) | N/A
+
The sequence of octets in the third column is the result of applying the
Distinguished Encoding Rules (DER) to the ASN.1 Object Identifier with
subsequent truncation.
The truncation removes the two fields of encoded Object Identifier.
The first omitted field is one octet representing the Object Identifier tag,
and the second omitted field is the length of the Object Identifier body.
@@ -2752,6 +2772,36 @@ ID | Algorithm | Reference
\[ Note to RFC-Editor: Please remove the table above on publication. \]
+This document requests IANA add the following wire format columns to the
OpenPGP public-key algorithm registry:
+
+- Public Key Format
+- Secret Key Format
+- Signature Format
+- Encryption Format
+
+And populate them with the values found in {{pubkey-algos}}.
+
+It also requests IANA to instantiate a new OpenPGP registry of Elliptic Curve
Point Formats, with the columns:
+
+- Name
+- Description
+- Reference
+
+and populate these fields with the values found in
{{ecc-point-representations}}.
+
+It also requests IANA to instantiate a new OpenPGP registry of Elliptic
Curves, with the following columns:
+
+- Curve name
+- OID
+- ECDSA?
+- EdDSA?
+- ECDH?
+- EC Point Format
+- Secret Key Format
+- Signature Format
+
+And populate these fields with the values found in {{ecc-curves}}.
+
### Symmetric-Key Algorithms
OpenPGP specifies a number of symmetric-key algorithms.
@@ -3010,42 +3060,55 @@ This document references three named prime field
curves, defined in {{FIPS186}}
Further curve "Curve25519", defined in {{RFC7748}} is referenced for use with
Ed25519 (EdDSA signing) and X25519 (encryption).
The named curves are referenced as a sequence of bytes in this document,
called throughout, curve OID.
-{{ecc-curve-oid}} describes in detail how this sequence of bytes is formed.
+{{ecc-curves}} describes in detail how this sequence of bytes is formed.
+
+## ECC Point Representations {#ecc-point-representations}
+
+This document defines wire formats for points on Elliptic Curves for use with
ECDSA, ECDH, and EdDSA.
+
+Compression formats are associated with particular elliptic curves.
+When a particular curve is in use, the point MUST be represented with the
associated wire format.
+A compliant application MUST NOT use an EC point format that is not associated
with the curve used.
+
+The table below summarizes the registered forms.
+Associations between the registered forms and specific curves are listed in
{{ecc-curves}}.
+
+Even though the zero point, also called the point at infinity, may occur as a
result of arithmetic operations on points of an elliptic curve, it SHALL NOT
appear in data structures defined in this document.
-## ECDSA and ECDH Conversion Primitives
+{: title="ECC Point representations"}
+Name | Description | Reference
+---|--------------|-------------
+Uncompressed | MPI(04 \|\| x \|\| y) | {{ecc-point-uncompressed}}
+MPI-wrapped Native | MPI(40 \|\| LE(x)) | {{ecc-mpi-wrapped-native}}
-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.
+### Uncompressed ECC Points {#ecc-point-uncompressed}
+
+An uncompressed point on an elliptic curve is encoded in the Multiprecision
Integer (MPI) format.
+
+This format is used by NIST curves P-256, P-384, and P-521.
For an uncompressed point the content of the MPI is:
B = 04 || x || y
-where x and y are coordinates of the point P = (x, y), each encoded in the
big-endian format and zero-padded to the adjusted underlying field size.
+where `x` and `y` are coordinates of the point `P = (x, y)`, each encoded in
the big-endian format and zero-padded to the adjusted underlying field 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:
-
- 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.
+Since the coordinates are zero-padded to the adjusted underlying field size,
the exact size of the MPI payload is 515 bits for "Curve P-256", 771 for "Curve
P-384", and 1059 for "Curve P-521".
-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.
+### MPI-wrapped Native ECC Points {#ecc-mpi-wrapped-native}
-Even though the zero point, also called the point at infinity, may occur as a
result of arithmetic operations on points of an elliptic curve, it SHALL NOT
appear in data structures defined in this document.
+Points on the elliptic curve 25519 are also represented in a Multiprecision
Integer (MPI) format, but use a different prefix octet of 0x40, and use that
curve's native little-endian format.
-If other conversion methods are defined in the future, a compliant application
MUST NOT use a new format when in doubt that any recipient can support it.
-Consider, for example, that while both the public key and the per-recipient
ECDH data structure, respectively defined in
{{algorithm-specific-part-for-ecdh-keys}} and
{{public-key-encrypted-session-key-packets-tag-1}}, contain an encoded point
field, the format changes to the field in
{{public-key-encrypted-session-key-packets-tag-1}} only affect a given
recipient of a given message.
+This format is:
-## EdDSA Point Format
+ B = 40 || x
-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.
+where `x` is the x coordinate of the point `P`, zero-padded to the the field
size in full octets, and encoded in little-endian form.
+This encoding of `x` is compatible with the definition in section 2 of
{{RFC8032}}.
-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 exact size of the MPI payload is 263 for Curve25519 (ECDH) or Ed25519
(EdDSA): 7 bits to represent the 0x40 prefix octet and 32 octets for the native
value of the public key.
## Key Derivation Function
@@ -3082,7 +3145,7 @@ The KDF parameters are encoded as a concatenation of the
following 5 variable-le
- a one-octet size of the following field
- - the octets representing a curve OID, defined in {{ecc-curve-oid}}
+ - the octets representing a curve OID, defined in {{ecc-curves}}
- a one-octet public key algorithm ID defined in {{pubkey-algos}}
@@ -3733,19 +3796,6 @@ An open problem can be recorded and tracked as [an
issue](https://gitlab.com/ope
\[Note to RFC-Editor: Please remove this section on publication.\]
-# ECC Point compression flag bytes
-
-This specification introduces the new flag byte 0x40 to indicate the point
compression format.
-The value has been chosen so that the high bit is not cleared and thus to
avoid accidental sign extension.
-Two other values might also be interesting for other ECC specifications:
-
- Flag Description
- ---- -----------
- 0x04 Standard flag for uncompressed format
- 0x40 Native point format of the curve follows
- 0x41 Only X coordinate follows.
- 0x42 Only Y coordinate follows.
-
# Acknowledgements
This memo also draws on much previous work from a number of other authors,
including: Derek Atkins, Charles Breed, Dave Del Torto, Marc Dyksterhouse, Gail
Haspert, Gene Hoffman, Paul Hoffman, Ben Laurie, Raph Levien, Colin Plumb, Will
Price, David Shaw, William Stallings, Mark Weaver, and Philip R.
--
2.30.2
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp