[Cfrg] Side inputs to signature systems

["D. J. Bernstein" <[e-mail]>]

Simon Josefsson writes:
> Do you have a concrete example?  I would consider that a protocol flaw.

It's certainly a protocol flaw---but sometimes designers of multiple
protocols, or multiple protocol components, don't talk to each other:

   * Protocol A: There are two messages, "Put the troops through a
     surprise drill" and "Don't put the troops through a surprise
     drill". For efficiency these messages are compressed to "1" and
     "0" respectively. For security, make sure to check that the
     compressed message is signed with the General's PGP key.

   * Protocol B: There are two messages, "Launch the missiles" and
     "Don't launch the missiles". For efficiency these messages are
     compressed to "1" and "0". For security, make sure to check that
     the compressed message is signed with the General's PGP key.

Each protocol is safe by itself, but the two protocols together allow
forgeries. Here's a fairly recent example of this type of bug in TLS:

   https://www.cosic.esat.kuleuven.be/publications/article-2216.pdf

The standard fix for this type of problem is to encode more information
into the signed messages so that they can't be taken out of context. Of
course, to figure out how much information is enough, you have to work
at the protocol layer, understanding all the different contexts in all
of the high-level protocols that might sign messages under the same
key---and the protocol designers need to talk to each other! Any
encoding, no matter how verbose, can be ruined by another protocol
assigning new meanings to some of the encoded messages.

Ilari and Mike have both suggested a different approach, feeding extra
side inputs into signatures, where these inputs vary from one protocol
to another. I have the same questions about these side inputs that I had
about William's suggestion to include certificates:

   * Are cryptographic libraries supposed to change their signature APIs
     to allow an extra side input?

   * What exactly are the format and semantics of this input? For
     example, how exactly would this side input be used to stop the TLS
     bug mentioned above?

   * What happens when someone wants to use more of these inputs?

   * How should libraries handle all of the signature standards that
     don't support this input?

   * More to the point, how is this supposed to be better than having
     the application sign a more informative message, using the
     traditional concept of a signature system?

As I wrote before: The standard signature concept has been stable for
decades. It's shared by theoretical papers, signature specifications,
attack papers, and software. From this perspective, having a side input
to a signature algorithm per se---rather than having it be part of how
the higher-level application decides to use signatures---is a severe
layering violation. I've seen cases where there's real justification for
rethinking the layers in cryptography, but "this application always
needs to verify X,Y,Z so signature systems should have X,Y,Z as separate
inputs" is obviously a bad argument.

---Dan