Re: [openpgp] Algorithm-specific data: problems with Simple Octet Strings, and possible alternatives

[Niibe Yutaka <[e-mail]>]

NIIBE Yutaka wrote:
> Sorry, I was not able to describe SOS accurately, in detail.

So, I write this.  It is also available at:
https://www.gniibe.org/memo/standard/openpgp/sos-in-openpgp.html

==========================

SOS is a suggestion to OpenPGP implementations to address the zero
removal/recovery problem.  I know that implementations already handle
it by adding zero recovary for Ed25519.  For new curves, it's good if
we won't need to support zero recovary again.


SOS in practice
===============

Referring the definition of SOS (in the previous article), 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.

The important point here is: There are multiple interpretations of
"the length of the SOS in bits".

This means that canonicalizing SOS representation is not defined by
the SOS handling itself.


Reading SOS representation
--------------------------

When parsing octet sequence in SOS representation, an implementation
expects a two-octet scaler and then an opaque string of octets with
the following length in octets:

    ("the length of the SOS in bits" + 7) / 8

Then, it does **not** check representation in bits.

Thus, when reading, the SOS [00 02 01] is considered formed correctly.
So are [00 08 01], and [00 08 00].


Writing SOS representation
--------------------------

When writing an octet string into SOS representation, an
implementation does following steps:

* 1: Examine the first octet in the octet string.

* 2: NBITS = 8 * length_of_string_in_octets

  * 2-1: If the first octet is zero, then no change of NBITS.

  * 2-2: If it's not zero, examine the bit-representation of it, to
         tweak NBITS = NBITS - number_of_leading_0_bits.

* 3: Output the scalar to represent NBITS, then the octet string.

Note that it does **never** remove anything from an octet string.


Impact to OpenPGP implementations
=================================

If it will be agreed, implementations will have to support non-zero
removal representations in Ed25519 signature and secret.


My conclusion (Manga practice requires conclusion, but I don't insist)
=======================================================================

SOS asks a clarification of Ed25519 signature and secret, and adding
support of non-zero removal to implementations.

In return, it will be easier to add support of new curves in a cleaner
way, with no need to support zero-recovery.

Note that it's not best for new curves, when assigning algo number to
specification is possible.  Use of SOS means that adding a two-octet
scalar to represent an octet string (in each use), which might not be
needed if the length information is determined by the context easily.



Post Script
===========

I don't like zero-removal or any removal by some internal processing.

I remember that for the song `S.O.S`_ (around 1977 in Japan), the intro
of the track was removed during its broadcast.

.. _S.O.S: https://en.wikipedia.org/wiki/S.O.S._(Pink_Lady_song)
--