Subject: [COSE] Updated message recovery algorithm text

From: Jim Schaad <[email-masked]>
Date: Thu, 10 Sep 2020 20:09:54 -0700

Below is the text that I am proposing for COSE Struct.  The changes are all
in the last 5 paragraphs.

Jim

   The second scheme is signature with message recovery (an example of
   such an algorithm is [PVSig]).  In this scheme, the message content
   is processed, but part of it is included in the signature.  Moving
   bytes of the message content into the signature allows for smaller
   signatures; the signature size is still potentially large, but the
   message content has shrunk.  This has implications for systems
   implementing these algorithms and for applications that use them.
   The first is that the message content is not fully available until
   after a signature has been validated.  Until that point, the part of
   the message contained inside of the signature is unrecoverable.  The
   second is that the security analysis of the strength of the signature
   is very much based on the structure of the message content.  Messages
   that are highly predictable require additional randomness to be
   supplied as part of the signature process.  In the worst case, it
   becomes the same as doing a signature with appendix.  Finally, in the
   event that multiple signatures are applied to a message, all of the
   signature algorithms are going to be required to consume the same
   number of bytes of message content.  This means that the mixing of
   the different schemes in a single message is not supported, and if a
   recovery signature scheme is used, then the same amount of content
   needs to be consumed by all of the signatures.

   The signature functions for this scheme are:

   signature, message sent = Sign(message content, key)

   valid, message content = Verification(message sent, key, signature)

   Since there have not yet been any message recovery signature
   algorithms formally defined for COSE, it is very likely that there
   are going to be issues that arise that have not been anticipated yet.
   There are some issues that have been identified that the first such
   algorithm is going to need to make decisions about.  These issues
   include:

   *  The message content being signed is not the same as the message
      content that is transported.  This is because we build a larger
      message for the signature process.  The number of bytes contained
      in the message may exceed the number of bytes of payload, but not
      the number of bytes signed.  This may lead to privacy
      considerations if, for example, the application external data
      contains confidential information.

   *  There may be difficulties in determining where the recovered
      message matches up with the to be signed value because bytes other
      than the payload are included in the recovered message.  One
      possible option would be to create a padding scheme to prevent
      that.

   *  Not all of these signature algorithms take the recovered bytes
      from the end of the message.  If the recovered bytes are taken
      from the start of the message then, by default, none of the
      signature payload may be included in the message recovery data.
      One possible option to deal with this is to reverse the to-be-
      signed data in the event that bytes are taken from the start
      rather than end of the message.

   Signature algorithms are used with the COSE_Signature and COSE_Sign1
   structures.  At this time, only signatures with appendixes are
   defined for use with COSE; however, considerable interest has been
   expressed in using a signature with message recovery algorithm due to
   the effective size reduction that is possible.

---

From: Matthew Miller <[email-masked]>
Date: Mon, 14 Sep 2020 16:27:35 -0600

[ Speaking with no hats ]

I think this text is an improvement to what's there today.

- m&m
Matthew A. Miller

> On Sep 10, 2020, at 9:09 PM, Jim Schaad <[email-masked]> wrote:
> 
> _______________________________________________
> COSE mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cose

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 15 Sep 2020 10:55:17 -0700

Hi Jim,

Overall this seems a fine tack to take, but see comments inline.

>    The second scheme is signature with message recovery (an example of

I wonder if we could toss in a word or two about these being "general
classes of signature scheme" where we first bring it up (i.e., for
signature with appendix).

>    number of bytes of message content.  This means that the mixing of

Not just the same number; the same actual bytes, too. (Right?)

>    are going to be issues that arise that have not been anticipated yet.

I think this should get wordsmithed a bit.  The RFC Editor can probably
help, but here's my take:

% No message recovery signature algorithms have been formally defined for
% COSE yet, and given the new constraints that such schemes impose on
% usage, it is likely that there will be additional issues that arise when
% integrating message-recovery signature algorithms with COSE.

(And to be clear, this chunk is the main part that goes to resolving my
Discuss point.)

>    There are some issues that have been identified that the first such

(This could have a better transition from the rewritten previous paragraph,
maybe "Some such issues have already been identified, and the first such
[...]")

>       in the message may exceed the number of bytes of payload, but not

"contained in the message" means "recovered during signature validation",
right?

We may want to use a more precise term than "payload" since there are
several different variants floating around during this process.

>       contains confidential information.

(The "application external data" is the stuff that's covered under the
signature but not transmitted?)

>       from the end of the message.  If the recovered bytes are taken

I would suggest rephrasing to not privilege the end of the message (or,
alternatively, to be more explicit about that being the COSE expectation);
perhaps "take the recovered bytes from the same position of their input".

>       signature payload may be included in the message recovery data.

(which would, of course, entail some changes to this sentence as well...)

>    structures.  At this time, only signatures with appendixes are

("at the time of this writing" seems to be preferred in terms of aging
well.)

>    the effective size reduction that is possible.

Thanks,

Ben

---

From: Jim Schaad <[email-masked]>
Date: Mon, 21 Sep 2020 12:18:04 -0700

-----Original Message-----
From: Benjamin Kaduk <[email-masked]> 
Sent: Tuesday, September 15, 2020 10:55 AM
To: Jim Schaad <[email-masked]>
Cc: [email-masked]
Subject: Re: [COSE] Updated message recovery algorithm text

Hi Jim,

On Thu, Sep 10, 2020 at 08:09:54PM -0700, Jim Schaad wrote:
> Below is the text that I am proposing for COSE Struct.  The changes 
> are all in the last 5 paragraphs.
> 
> Jim
> 
> 
> 

I wonder if we could toss in a word or two about these being "general
classes of signature scheme" where we first bring it up (i.e., for signature
with appendix).

[JLS] The terms classes and scheme seem to be the same word to me.   Other
than that I have no problems with this.  Would this work?

There are two general signature algorithm schemes.  The first of these
general schemes is signature with appendix.

[JLS] Done.

% No message recovery signature algorithms have been formally defined for %
COSE yet, and given the new constraints that such schemes impose on % usage,
it is likely that there will be additional issues that arise when %
integrating message-recovery signature algorithms with COSE.

>    the effective size reduction that is possible.

[JLS] Rather than try to figure out how to break things out in the above set
of comments you just get the entire new section:

   Signature algorithms provide data origination and data integrity
   services.  Data origination provides the ability to infer who
   originated the data based on who signed the data.  Data integrity
   provides the ability to verify that the data has not been modified
   since it was signed.

   There are two signature algorithm schemes.  The first is signature
   with appendix.  In this scheme, the message content is processed and
   a signature is produced; the signature is called the appendix.  This
   is the scheme used by algorithms such as ECDSA and the RSA
   Probabilistic Signature Scheme (RSASSA-PSS).  (In fact, the SSA in
   RSASSA-PSS stands for Signature Scheme with Appendix.)

   signature = Sign(message content, key)

   valid = Verification(message content, key, signature)

   bytes of message content.  This means that the mixing of the
   different schemes in a single message is not supported, and if a

Schaad                    Expires 25 March 2021                [Page 38]

Internet-Draft               COSE Structure               September 2020

   No message recovery signature algorithms have been formally defined
   for COSE yet, and given the new constraints arising from this
   schemes, while some of these issues have already been identified
   there is a high probability that additional issues will arise when
   integrating message recovery signature algorithms.  The first
   algorithm defined is going to need to make decisions about these
   issues and those decisions re likely to be binding on any further
   algorithms defined.

   We use the following terms below:

   message content bytes:  The byte provided by the application to be
      signed.

   to-be-signed bytes:  The byte string passed into the signature
      algorithm.

   recovered bytes:  The bytes recovered during the signature
      verification process.

   Some of the issue2 that have already been identified are:

   *  The to-be-signed bytes are not the same as the message content
      bytes.  This is because we build a larger to-be-signed message
      during the signature processing.  The recovered bytes length may
      exceed the message content length, but not the length of the to-
      be-signed bytes.  This may lead to privacy considerations if, for
      example, the application external data contains confidential
      information.

   *  There may be difficulties in determining where the recovered bytes
      match up with the to-be-signed bytes, because the recovered bytes
      contains data not in the message content bytes.  One possible
      option would be to create a padding scheme to prevent that.

   *  Not all message recovery signature algorithms take the recovered
      bytes from the end of the to-be-signed bytes.  This is a problem
      because the message content bytes are at the end of the to-be-
      signed bytes.  If the bytes to be recovered are taken from the
      start of the to-be-signed bytes then, by default, none of the
      message content bytes may be included in the recovered bytes.  One
      possible option to deal with this is to reverse the to-be-signed
      data in the event that recovered bytes are taken from the start
      rather than end of the to-be-signed bytes.

   Signature algorithms are used with the COSE_Signature and COSE_Sign1
   structures.  At the time of this writing, only signatures with
   appendixes are defined for use with COSE; however, considerable
   interest has been expressed in using a signature with message
   recovery algorithm due to the effective size reduction that is
   possible.
[/JLS]

I think this has addressed all of your issues, but not necessarily in the
way you suggested.
Jim

Thanks,

Ben

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 23 Sep 2020 09:05:44 -0700

Hi Jim,

I didn't extract the text to do a side-by-side diff, but overall this looks
fine.  Your suggestion about "general schemes" is appreciated, so if that
could make it in that would be great.

I am still a bit unclear about the "application external data", though.

Thanks,

Ben

---

From: Rene Struik <[email-masked]>
Date: Wed, 23 Sep 2020 12:40:15 -0400

Hi Jim:

With PV signatures, the security depends on redundancy in the message, which is either already present or can be added (e.g., by always prepending an all-zero string). If the application always uses messages with built-in redundancy, this results in an effective signature size that is roughly the bit-size of the underlying curve; otherwise, 1 1/2 times the bit-size of the underlying curve. With P-256, this yields an increment of 256-bit or 384-bit, respectively (whereas ECDSA signatures would yield 512-bit).

In your text below, the wording "predictable" should therefore read "unpredictable", where the last sentence should be taken with a grain of salt (given the size of ECDSA signatures and PV increments indicated above).

The
   becomes the same as doing a signature with appendix. 

A potential disadvantage of PV signatures is that the signing process requires availability of the ephemeral signing key prior to encrypting the message, which depends on a scalar multiplication, where - if this is not available - this causes a wait cycle for processing the message. Schnorr signatures (including EdDSA) have the same disadvantage, though.

Having the message becoming available only at the end of PV signature verification may actually be an advantage, since it avoids implementers cutting corners (by simply processing data without knowing whether it is authentic first).

Best regards, Rene

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867