Re: [openpgp] ECC point encoding and "flag byte"

NIIBE Yutaka <gniibe@fsij.org> Wed, 03 March 2021 03:27 UTC

Return-Path: <gniibe@fsij.org>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 09A633A1820 for <openpgp@ietfa.amsl.com>; Tue, 2 Mar 2021 19:27:05 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Level:
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=fsij.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id XGnQ_n_ZU_ug for <openpgp@ietfa.amsl.com>; Tue, 2 Mar 2021 19:27:02 -0800 (PST)
Received: from akagi.fsij.org (akagi.fsij.org [217.70.189.144]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6144C3A180A for <openpgp@ietf.org>; Tue, 2 Mar 2021 19:27:02 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=fsij.org; s=main; h=Content-Type:MIME-Version:Message-ID:Date:References:In-Reply-To: Subject:Cc:To:From:Sender:Reply-To:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=MybijfpMJQGjUkPWjiGicDVTskw9U0kWfNVNdDBkhh0=; b=t9/q7GcjflhpsZr2qbw2g2sWxX vlQE5kfL1UU8rJhZfkI4Wf50l/mZ8McqedtxkNzkQrd/e5aZ6UeJWsVO5zI8a3qoT+AMAVZr6/8bg 88qJrJTwvKnm2/FjlSV7EXAxWH0tpnqMgDk3HwF+pz2ldsddprBVjz/9Soukn2Bak+QOV+isGGau+ 63BJowftsFEiWhoXXvelK9dmy0t/BDoKqD55CVhrSphuoFvCYT5UQUqmOh365pg09FBPVIVuMBVq1 EXSZq/9s0ekF7pKWa+7GInWsgLeUOZDb0hamGny/hQPGhqVNq2KdsR8PKsO9xnNMlcjAIKmfn1S2t m0QXCJzA==;
Received: from m014008080161.v4.enabler.ne.jp ([14.8.80.161] helo=iwagami.gniibe.org) by akagi.fsij.org with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from <gniibe@fsij.org>) id 1lHIA5-0002oD-8O; Wed, 03 Mar 2021 04:26:58 +0100
Received: by iwagami.gniibe.org (sSMTP sendmail emulation); Wed, 03 Mar 2021 12:26:52 +0900
From: NIIBE Yutaka <gniibe@fsij.org>
To: Werner Koch <wk@gnupg.org>, Daniel Kahn Gillmor <dkg@fifthhorseman.net>
Cc: openpgp@ietf.org
In-Reply-To: <87czwj8d3b.fsf@wheatstone.g10code.de>
References: <87h7lyccns.fsf@fifthhorseman.net> <87czwj8d3b.fsf@wheatstone.g10code.de>
Date: Wed, 03 Mar 2021 12:26:52 +0900
Message-ID: <87v9a829z7.fsf@iwagami.gniibe.org>
MIME-Version: 1.0
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/FJkI6YgWMpAOiVJCqLbz7MD9NVw>
Subject: Re: [openpgp] ECC point encoding and "flag byte"
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 03 Mar 2021 03:27:06 -0000

Hello,

I tried to modify/fix the specification, but I realized that I don't
have enough skills writing (a part of) specification.

So, instead of the modifying the specification, I wrote a bug report.

Here it is (in ReST format, an initial version).

It is also available at:
https://www.gniibe.org/log/bugreport/openpgp/ecc-in-openpgp.html
(possibly, more update in future)

Your comments will be appreciated. 

--------------------------
=================================
ECC in OpenPGP (as of March 2021)
=================================

In this bug report, I describe how we can improve OpenPGP specification
for ECC, so that different implementations can inter-operate well, and
an implementation can avoid a bug.

Firstly, I point out the single issue: **Opaque Data Element should be
available in OpenPGP**.  I name it **Strange Octet String (SOS)**.

Secondly, I explain about where we should use SOS to represent ECC
things in OpenPGP.

Thirdly, I describe how ECC things were defined in OpenPGP.  And I
explain how these were implemented in GnuPG for classic ECC, then
modern ECC (Ed25519 and Curve25519).

Fourthly, I describe my bug in GnuPG 2.3-beta regarding Ed25519 key
and signature, which I'm fixing now.

Fifthly, I explain about the implementation of handling Ed448
signature and X448 encryption in GnuPG 2.3-beta, with SOS.

Lastly, I conclude that SOS may be the best apporach for OpenPGP.


1: Opaque Data Element should be available in OpenPGP
=====================================================

RFC 4880 and RFC 6637 were good, when it was common to represent data
in big-endian format.

These days, in modern ECC, things are defined in little-endian format.

In this situation, it's good to have a data element which can
represent **something in native format** (or anything, hopefully).


Don't repeat, just refer
------------------------

It's good for a specification to be able to simply **refer** another
specification when it uses technology of latter.

When we repeat some definitions in a specification from another
specification, something wrong may happen.  It's good when we can
avoid this.


Strange Octet String (SOS)
--------------------------

Here, I propose an opaque data element in OpenPGP, named Strange Octet
String (SOS).

I had tried introducing straight-forward Octet String to OpenPGP
(length in octets plus an opaque string), but for backward
compatibility, I concluded that "strange" one is better, instead.

It is defined as:

    An SOS consists of two pieces: a two-octet scalar that is the length
    of the SOS in bits followed by an opaque string of octets.

Most important point is that no semantics is given for the data
element, but it is up to underlying crypto algorithm.  (-: down to?)

Another point is that it has exactly the same structure of MPI, thus,
every MPI can be handled as an SOS.

When an SOS data object is handled as an MPI, it would look "strange"
as it may include preceding zeros, which is not allowed in well-formed
MPI.


2: Let us use SOS for ECC things
================================

I'd like to propose using SOS for ECC things.  We can use SOS for
following data.

* EdDSA Signature

  - R: to represent an EC point, use SOS
  - S: to represent integer, use SOS

* EdDSA Public Key

  - For an EC point, use SOS

* ECDH Public Key with modern Curves

  - For an an EC point, use SOS

* EdDSA Secret Key

  - Just use SOS

* ECDH Secret Key with modern Curves

  - Just use SOS

* ECDH Ephemeral Public Key with modern Curves

  - For an an EC point, use SOS

(If needed,) existing definitions for ECC can replace MPI to SOS.


3: ECC in RFC 6637, Ed25519 and Curve25519 in OpenPGP
=====================================================

You'd say, it's a mess.  But that's how it's evolved.


Classic ECC with MPI
--------------------

In RFC 6637, it is defined using MPI as:

::

   9. Encoding of Public and Private Keys
   [...]
      Algorithm-Specific Fields for ECDSA keys:
   [...]
         o  MPI of an EC point representing a public key
   [...]
        Algorithm-Specific Fields for ECDH keys:
   [...]
            -  MPI of an EC point representing a public key
   [...]
        Algorithm-Specific Fields for ECDH or ECDSA secret keys:
   [...]
         o  an MPI of an integer representing the secret key, which is a
            scalar of the public EC point
   [...]
   10.  Message Encoding with Public Keys
   [...]
      Algorithm-Specific Fields for ECDH:
   [...]
         o an MPI of an EC point representing an ephemeral public key

And ECDSA signature is effectively defined using MPI as:

::

      Algorithm-Specific Fields for ECDSA signatures:

        - MPI of ECDSA value r.

        - MPI of ECDSA value s.



Ed25519 data format
-------------------

If I described current format for Ed25519...

Keys are something like this:

::

   9. Encoding of Public and Private Keys
   [...]
      Algorithm-Specific Fields for EdDSA keys:
   [...]
         o  MPI of an EC point representing a public key with prefix 0x40
            so that we can avoid removing preceding zeros.
   [...]
        Algorithm-Specific Fields for EdDSA secret keys:
   [...]
         o  an MPI of an integer representing the secret key,
            in little-endian format, removing preceding zeros to be
            well-formed MPI.

Signature are something like this:

::

      Algorithm-Specific Fields for ECDSA signatures:

        - MPI of R of EdDSA, whcih represents an EC point without
          prefix 0x40, removing preceding zeros to make it well-formed
          MPI.

        - MPI of EdDSA value s, an integer in little endian format,
          removing preceding zeros to be well-formed MPI.

Please note that we don't put 0x40 to represent an EC point in R part
of signature.  Please also note that we have to remove preceding zeros
to form well-formed MPI for secret keys (non-encrypted), R and S part
of signature.


Curve25519 data format
----------------------

If I described current format for Curve25519, it's something like this:

::

   9. Encoding of Public and Private Keys
   [...]
        Algorithm-Specific Fields for ECDH keys:
   [...]
            -  MPI of an EC point representing a public key with prefix 0x40
               so that we can avoid removing preceding zeros.
   [...]
        Algorithm-Specific Fields for ECDH secret keys:
   [...]
         o  an MPI of an integer representing the secret key, which is a
            scalar of the public EC point (!!big-endian integer!!)
   [...]
   10.  Message Encoding with Public Keys
   [...]
      Algorithm-Specific Fields for ECDH:
   [...]
         o an MPI of an EC point representing an ephemeral public key
           with prefix 0x40 so that we can avoid removing preceding zeros.

It's a mixture of little-endian and big-endian, unfortunately.


4: Ed25519 interoperability issue in GnuPG 2.3-beta (currently being fixed)
===========================================================================

In GnuPG 2.3-beta, it is handled as SOS, so, we have an issue for Ed25519.

See:

- Key: https://dev.gnupg.org/T5120

- Signature: https://dev.gnupg.org/T5331


5: Ed448 and X448 in GnuPG 2.3-beta, using SOS
==============================================

Keys and signatures are simply defined using SOS, there are no prefix,
no removal or recovery of zeros.

As described above, it would look a bit strange as an OpenPGP data, if
you interpret it as an MPI (it may include preceding zeros), but it's
a way simple.


Conclusion
==========

For new things, like Ed448 and X448, it's better to use SOS.

Lastly, let me make an excuse.  Curve25519 in GnuPG was implemented in
that way, the intention at that time was to align to RFC 6637 and
existing implementation (X25519 specification was not yet available).
--