An octet sequence as an MPI

[NIIBE Yutaka]

Hello,

Current libgcrypt + GnuPG implementation have an issue around handling
of an octet sequence as big-endian number in an MPI.

IIUC, this issue originates in RFC 6637, and we can find same problem in
the draft of rfc4880bis.  I will ask and discuss in OpenPGP WG, if
needed, but for now, I'd like to improve the implementation at first.

The issue can be found in the draft of rfc4880bis, quoting:

==========================
    5.6.5.  Algorithm-Specific Part for EdDSA Keys

       The public key is this series of values:

       o  a variable-length field containing a curve OID, formatted as
          follows:

          *  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 Section 9.2;

1?     o  a MPI of an EC point representing a public key Q as described
1?        under EdDSA Point Format below.

       The secret key is this single multiprecision integer:

2?     o  MPI of an integer representing the secret key, which is a scalar
2?        of the public EC point.

    5.6.6.  Algorithm-Specific Part for ECDH Keys

       The public key is this series of values:

       o  a variable-length field containing a curve OID, formatted as
          follows:

          *  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 Section 9.2;

3?     o  a MPI of an EC point representing a public key;

       o  a variable-length field containing KDF parameters, formatted as
          follows:

          *  a one-octet size of the following fields; values 0 and 0xff are
             reserved for future extensions;

          *  a one-octet value 1, reserved for future extensions;

          *  a one-octet hash function ID used with a KDF;

          *  a one-octet algorithm ID for the symmetric algorithm used to
             wrap the symmetric key used for the message encryption; see
             Section 13.5 for details.

       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:

4?     o  MPI of an integer representing the secret key, which is a scalar
4?        of the public EC point.
==========================

I put <NUMBER>? in the left column.  Here I enumerated four problems.
(Same for ECDSA, but this is omitted, right now, because my focus
is introducing new curves.)

It is described as "MPI", but I think that it is better to be described
as "size + octets".

MPI has semantics than mere octet string; It is (may be) interpreted as
a big-endian number, and its representation can be changed where minimum
size representation is assumed (removing zero octets at the beginning).

For #1 and #3, putting the point representation in an MPI is
questionable, as the point is not a big-endian number.  Because of its
prefix (the first octet, 0x04 or 0x40), it is safe against removing-zero
handling.  But, by defining as "size + octets", it allows any point
representation.

For #2, the description is not accuate for EdDSA, since it's not "a
scalar of the public EC point".  It is just a fixed-size octets.  When
it is handled as an MPI, it is unsafe against removing-zero handling.
So, our implementation of libgcrypt has special care for that, namely,
detecting removed zeros to recover them.  By defining as "size +
octets", it allows curve implementation to interpret octets.

For #4, current implementation assumes an MPI, but it is more natural
for other curves to define it as "size + octets".  For Curve25519, we do
use this field as an MPI (as a big-endian number), just like other NIST
curves.  For X448, it is more friendly to the X448 API to use this field
as a native fixed-size little endian octets.  By defining as "size +
octets", it allows curve implementation to interpret octets.
(We can define X25519, using X25519 native format.)
--