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

[Ilari Liusvaara <[e-mail]>]

On Mon, Mar 25, 2024 at 09:27:11AM -0000, D. J. Bernstein wrote:
> Simon Josefsson writes:
> > Can we give some examples of bad hybrid signature schemes, to better
> > understand the failure modes of signature combiners?
> 
> There have been some papers (e.g., https://eprint.iacr.org/2020/1525)
> pointing out attacks against protocols for which it's reasonable to
> think that extra hashing in signature schemes would stop the attacks.

I think it is completely unreasonable for protocol to expect extra
hashing without explicitly requiring it.

 
> The extra hashing can also be carried out by protocols, so signature
> schemes can blame protocols for not being based purely on standard
> properties such as EUF-CMA, while protocols can blame signature schemes
> for not doing some cheap hashing to provide additional properties. The
> finger-pointing lets both sides avoid taking any action. It's rare for
> there to be any engineering analysis of how the ecosystem as a whole
> should avoid the attacks.

I blame the protocols.

Protocols need to identify requirements for underlying primitives and
then only use primitives that meet (or are at least thought to meet)
those requirements.

Ed25519 is a lot nicer behaved than most signatures, yet I have seen it
fail due to protocol assuming properties it does not have.

And I have seen nasty issues from protocol not explicitly stating a
security requirement it has, and then somebody adding security-breaking
algorithm.


> I think that combiners are a good place to put the hashing. We want
> combiners anyway to be sure that adding post-quantum systems isn't
> losing security. The basic reasons for having multiple signature systems
> and multiple protocols don't apply to combiners, so we should expect
> fewer combiners than signature systems and protocols, meaning less
> review work for the hashing.

How does the combiner guard against downgrade? There is no generic
method of doing so, and the effects are protocol-dependent, meaning
protocol-dependent analysis (which one would rather avoid).


> > What properties should a good generic hybrid signature combiner have?
> > Can we describe one example?
> 
> Here are some design goals and a specific combiner proposal.
> 
> As a starting point, to make it less likely for people to skip signature
> verification, it's good to have APIs producing signed messages rather
> than signatures. A hybrid of two signature systems then internally has
> 
>    (1) message -> first signature system -> signed message,
>    (2) signed message -> second signature system -> double-signed message.
> 
> This also forces the attacker to break the second signature system
> before being able to feed forgeries to the first signature system.

Most protocols (even more true if weighted by usage) are fundamentally
designed for appendix signatures, so signed messages are useless for
those protocols.

The end result of only having message signatures would be hybrid
signatures not getting deployed at all, or protocol designers coming
up with their own ways, completely incompatible and with all sorts of
exciting problems. Which would overload crypto library maintainers,
which is Extremely Bad.

ML-DSA might be "too damn big", but at least there is no BS.


>    * Most proposals for extra hashing in combiners are clearly
>      affordable because the CPU time for hashing is roughly 1% of the
>      cost of communicating the data being hashed. This proposal is
>      different, since it's incurring extra network traffic.

Not true with hot transreceiver.


>    * On the other hand, none of the claims that I've seen of
>      unaffordability of post-quantum signatures are based on such small
>      size differences. If there are real examples of 32 extra bytes
>      being unaffordable on top of post-quantum signatures, then why are
>      anti-hybrid arguments resorting to unquantified "less efficient"
>      statements? (See https://blog.cr.yp.to/20240102-hybrid.html.)

While it is less bad with signatures, with encryption, using hybrids
with hot transreceiver is >150% overhead.

The main arguments seem to be complexity and interoperability. Yes,
it is also less efficient, the question is how much and is it worth
the performance impact.

Hybrid signatures are much more complex than hybrid key exchange/
encryption. And with much less benefit.


>    * In the context of web pages (normally >2MB spread across <=10
>      connections, with maybe 6 signatures per connection), code signing,
>      etc., it's not plausible that an extra 32 bytes per signature is an
>      issue.

There are size cutoffs, and crossing those is absolutely a major
problem. However, the PQ signatures alone are likely to bust those
limits (the "too damn big" above).

E.g., QUIC handshake server reply exceeding ~7,000 bytes causes
performance to tank. And about 1/6th of that is already used up by
PQC key exchange. TLS has similar limit (I think it is somewhere in
14,000 byte ballpark).


>    * The rationale for the recommendation is a specific protocol that's
>      broken if an attacker, without seeing m, can convert a signature on
>      m into a signature on m under another public key. Saying that a
>      signature system should provide "non-resignability" is inherently
>      incompatible with a traditional signed-message ("message recovery")
>      API, which, as noted above, is less error-prone than a
>      detached-signature API.

And as noted above, signed-message API is mostly useless.


> One more recommendation is to include the signature-system name and
> application name as extra hash inputs (along with any context specified
> by the application), in a way that can be uniquely parsed across
> applications, so that signatures can't be moved across protocols.

That has been tried. Turned out to be a major mistake.




-Ilari