Re: [lamps] Whether to hash-then-sign with Dilithium and Falcon?

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

Phillip Hallam-Baker writes:
> If this is a useful approach, then move it out of the signature
> primitive and push it into the envelope format.

Sure, people converting a signature system m |-> Sign(m) into a one-pass
signature system m |-> Sign(H(m)) can maybe be convinced to instead
convert it into a safer one-pass signature system m |-> r,Sign(H(r,m))
where r is chosen randomly at signing time. Both conversions are
generic, and the performance differences are minor.

But moving this _out_ of the underlying signature system is dangerous.
Applications will often expose the underlying signature system directly
to attackers. For example, an RSA HSM that returns h^d given h, trusting
the environment to choose h as a hash, is breakable by essentially the
attack of https://link.springer.com/article/10.1007/s00145-015-9205-5.

> If SHAKE is broken, then we are going to have so many problems that the
> security of the signature algorithm is irrelevant.

Certainly we'd like to end up in a world where everyone is using a hash
function that we can confidently assume is collision-resistant. However,
avoiding this assumption turns out to simplify security review:

   * Avoiding collision resistance means that cryptanalysts can avoid
     worrying about some important, hard-to-analyze attack avenues
     (e.g., what Wang dubbed "message modification").

   * Some components of security analyses can be computer-verified
     today, but (because of well-known formalization difficulties)
     assuming collision resistance creates problems for this.

   * In the opposite direction, the random r above creates its own
     complications in security review, but looking at the details shows
     that these complications are _relatively_ easy to analyze.

Simplifying security review is important because the overall situation
in post-quantum cryptography is that security reviewers are terribly
overloaded. Compare, e.g., https://eprint.iacr.org/2021/543 ("A decade
unscathed") to https://eprint.iacr.org/2022/975. For many more examples
see https://ntruprime.cr.yp.to/latticerisks-20211031.pdf.

If a cryptosystem takes 10 unnecessary risks, each independently
incurring a 10% chance of disaster, then the cryptosystem has, overall,
a 65% chance (1-0.9^10) of disaster from these risks. Systematically
avoiding risks is much safer.

---D. J. Bernstein