SOS in OpenPGP

I was not able to describe SOS itself accurately in ECC in OpenPGP by SOS.

So, this article is to augument the explanation.

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.