Re: [CFRG] How to construct a hybrid signature combiner?

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

Ilari Liusvaara writes:
> "only having message signatures" means not having the raw message (m)
> in the tuple.

Thanks for the clarification. All of the hybrid-signature proposals that
I've seen have m in the tuple when the input signature systems do, and
I'm happy skipping things like RSA-with-message-recovery as an option.

But let me emphasize that the API considerations still put a constraint
on how the combiner works. Here are two simple examples (no extra
hashing) to illustrate this.

Example 1: Suppose we apply the SUPERCOP-et-al. crypto_sign() interface
first for Ed25519 and then for whichever post-quantum system:

   * Ed25519 signs the original message m, producing a signed message.

   * The post-quantum system signs the result, producing a double-signed
     message.

Verification works the same way in reverse, applying crypto_sign_open()
first for the post-quantum system and then for Ed25519.

What happens if people want to use the same double-signature system but
with detached-signature interfaces?

   * Ed25519 is compatible with that: a signed message looks like
     (s1,m), and a detached-signature interface returns s1 separately.

   * Let's assume the post-quantum system has the same form: starting
     from the input (s1,m), it produces a signed message (s2,s1,m); a
     detached-signature interface returns s2 separately.

The combiner then looks like this: first obtain a detached signature s1
of m, and then obtain a detached signature s2 of (s1,m), and then return
(s2,s1).

In short, Example 1 is compatible with both types of interfaces.

Example 2: Suppose you instead ask for detached signatures s1 and s2 of
m under Ed25519 and the post-quantum system respectively, and return
(s2,s1) as a signature.

There's one critical difference from Example 1: in Example 2, s2 is a
signature on m rather than on (s1,m).

Now what happens if people want to use safer signed-message interfaces?
Well, let's see:

   * Calling an Ed25519 signed-message interface produces a signed
     version of m. Easy.

   * Calling a signed-message interface for the post-quantum system
     produces a signed version of m. Also easy.

   * But, hmmm, how does the combiner put the two signed messages
     together? It has to break the signed-message encapsulation,
     extracting s2 from the second signed message (s2,m), so that it
     can return (s2,s1,m).

The difficulty here is directly connected to the reason that signed
messages are a safer interface than detached signatures. Sure, having a
signature as a separate object next to an unchanged message makes
Example 2 work straightforwardly, but that's also exactly what makes it
trivial for people to forget to verify the signature.

In short, Example 2 is compatible with a detached-signature interface
but not compatible with a safer signed-message interface.

A separate advantage of Example 1, as I mentioned before, is that the
attacker has to break the outer signature system before being able to
feed forgeries to the inner signature system. I think we're on the verge
of having everyone suddenly using formally verified Ed25519 software,
but that's not the current situation; why give the attacker extra
flexibility?

> Another API consideration: That (s2,s1,r,h) needs to be packed as a
> byte string.

Definitely. We managed to get all the post-quantum signature systems
providing a wire-format interface already. A few systems have
variable-length signatures, but I think that it's just fine for a
combiner to insist on fixed-length signatures.

---D. J. Bernstein