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

"D. J. Bernstein" <> Sat, 20 August 2022 18:29 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id CB664C152701 for <>; Sat, 20 Aug 2022 11:29:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -6.905
X-Spam-Status: No, score=-6.905 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_HI=-5, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id X-QiOGQR7Av2 for <>; Sat, 20 Aug 2022 11:29:34 -0700 (PDT)
Received: from ( []) by (Postfix) with SMTP id 64E3CC1522D6 for <>; Sat, 20 Aug 2022 11:29:34 -0700 (PDT)
Received: (qmail 31215 invoked by uid 1010); 20 Aug 2022 18:29:32 -0000
Received: from unknown (unknown) by unknown with QMTP; 20 Aug 2022 18:29:32 -0000
Received: (qmail 232810 invoked by uid 1000); 20 Aug 2022 18:29:08 -0000
Date: Sat, 20 Aug 2022 18:29:08 -0000
Message-ID: <>
From: "D. J. Bernstein" <>
In-Reply-To: <>
Archived-At: <>
Subject: Re: [lamps] Whether to hash-then-sign with Dilithium and Falcon?
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: "This is a venue for discussion of doing Some Pkix And SMime \(spasm\) work." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sat, 20 Aug 2022 18:29:38 -0000

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

> 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., ("A decade
unscathed") to For many more examples

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