Threshold ECDSA Modes of Operation: Pre-signing and More
Multiparty Computation (MPC) protocols to distribute signing authority for ECDSA are now a standard best practice for managing signing keys. Much like other MPC protocols, many threshold ECDSA protocols support different modes of operation, like the offline-online paradigm. In this mildly technical blog post, we will review the security of such modes of operation, largely agnostic to any specific threshold ECDSA protocol. In particular, we will focus on “pre-signatures”, and also touch upon pipelining, additive key derivation, and raw signing. This post mostly highlights and contextualizes the recent results of Groth and Shoup from Eurocrypt ‘22.
The TLDR of their results for readers only concerned with whether standard pre-signing with threshold ECDSA is safe, is “yes, for all known attack strategies”. Read on to get a more nuanced view of the picture.
What Are Pre-signatures?
The offline-online model for MPC is a popular design paradigm, initiated by Beaver and adopted by several more recent practical MPC protocols like SPDZ and MASCOT. It assumes that MPC nodes have a period of inactivity prior to their inputs being defined, which can be leveraged to save time later on once the input is known. The idea is to delegate as much heavy cryptography as possible to an “offline” phase, so that the “online” phase can be simple and efficient. In the context of threshold signing, this means that the signing nodes create a “pre-signature” before the message to be signed is known, and then consume this pre-signature to complete signing the message once available. Let’s start building intuition for what this could mean by taking a look at the usual single-party signing. We denote by 𝔾 the elliptic curve of prime order q generated by G, and recall that a signature is of the format (rₓ,s) where rₓ is the x-coordinate of the uniformly random signing nonce R = k·G ∈𝔾, and
Observe that rₓ is entirely independent of the signature, moreover generating this value is commonly the heaviest component of signing as it involves an exponentiation. In order to minimize the online latency of signing, one could pre-compute rₓ and assemble s once m is known.
This principle is much more pronounced in the threshold signing setting: several threshold ECDSA protocols allow for the heavy interactive “pre-signature” component to be performed before m is known, so that online signing is orders of magnitude more efficient. In fact the online signing procedure is typically a single (non-interactive) round, in which each party sends a few tens of bytes, which can be assembled into a full signature in a fraction of a millisecond.
Caution: it is imperative that each pre-signature is used exactly once. Repeating rₓ for two messages in the single party case leads to catastrophic failure by nonce reuse, and the same logic applies in the threshold setting. This is often easier said than done—especially in the context of cloud deployments, protecting against state reuse can be quite tricky. Employing the offline-online paradigm therefore necessitates good engineering and system administration practices to ensure that pre-signature reuse does not happen.
However, unlike the single party case, in the threshold setting pre-signatures—at least those that enable non-interactive online signing—come with an additional caveat: rₓ is revealed to the signing nodes before m is fixed, meaning that if one of them is compromised, an attacker could choose m as a function of rₓ. It is not immediate how this might admit an attack, but it demands a new security assumption on ECDSA for continued safe operation.
Here’s a toy example to demonstrate the point: let’s say we construct a modified version of ECDSA called ECDSA*, in which the signing algorithm has a silly backdoor. ECDSA* produces signatures (rₓ,s) where rₓ is still the x-coordinate of the uniformly random signing nonce R = k·G ∈𝔾, but:
In particular, s is the same as in ECDSA, but in the event that the message m being signed matches the sampled rₓ exactly, it leaks the signing key. Observe that ECDSA* still satisfies standard unforgeability where an attacker can only obtain (rₓ,s) in “one shot” upon providing m; this is because once the attacker fixes any m on which it requests a signature, it is statistically unlikely that the signer will sample an rₓ that matches it. However, ECDSA* is completely insecure when pre-signing: an attacker who sees rₓ before it is bound to a message can simply request a signature on m = rₓ and obtain the full signing key in response. Of course ECDSA itself does not have such a backdoor, and is considerably more complex to analyze.
It’s worth noting at this point that the equivalent security assumption for Schnorr/EdDSA is decidedly false. Briefly put, a subtle concurrency attack arises, wherein an attacker who has simultaneous access to multiple pre-signing instances can carefully assign messages for each one, so that the induced full signatures can be combined into a forged Schnorr signature on a chosen message. The insecurity of pre-signing with Schnorr makes it all the more crucial to examine the security of pre-signing with the closely related ECDSA.
Security Implications of Pre-signing in Threshold ECDSA
In their recent paper, Groth and Shoup consider precisely the issue discussed above: is the security assumption on ECDSA with pre-signing safe?
The short answer is that they prove that it is indeed safe, in the Generic Group Model. In order to interpret this result, it is helpful to recall what guarantees such proofs, and cryptographic security proofs provide in general.
Provable Security typically involves showing that if an attacker were to compromise some well-defined notion of security (such as unforgeability of a signature), then we can use such an attacker as a black box to solve some hard mathematical problem. This mapping is accomplished by an algorithm called a reduction. The best case outcome here is showing that breaking ECDSA with the ability to choose m as a function of rₓ yields a reduction to forging ECDSA signatures even without this ability. However, as appears to be common with provable security for signatures as deployed in the wild, constructing such a reduction runs into some technical difficulties. One way to get around these difficulties—as Groth and Shoup do—is to give a proof with idealized cryptographic tools.
Security Proofs in Idealized Models reason about a restricted class of attackers. For instance, proofs in the Random Oracle Model only guarantee security against attackers that treat hash functions as black boxes that don’t interact with any other component of the system. Proofs in the Generic Group Model (GGM)—usually considered to be a stronger idealization than Random Oracle—only guarantee security against attackers that use the Elliptic Curve as a black box. There are different methods of modeling this intuition of “black box usage”, but the specific formalization does not matter for the purpose of this article. While there are ways to abuse the model by deliberately designing insecure constructions that admit proofs in the GGM, we have yet to find a “natural” candidate that is secure in the GGM but broken in reality. This is because as of writing, all known attack strategies on real constructions respect the constraints of the model—they do not (for instance) exploit any special properties of common signing curves, nor are such curves known to interact in strange ways with standard cryptographic primitives like hash functions. Even the previously mentioned attack on Schnorr pre-signing conforms to the GGM constraints. One class of curves that does allow for operations beyond just generic point addition is those that support pairings, however such curves are not typically used for ECDSA and therefore not within the scope of this discussion.
ECDSA itself was for a while only known to admit a security proof in the GGM. More recently it was proven secure under another idealized assumption, and there is evidence that some form of strong idealization is inherent to any security proof for ECDSA. How then, do we interpret the security of ECDSA itself? A conservative approach would be to say that the idealized proofs simply make explicit the limitations of current attack techniques. A more optimistic take would be that the community’s continued use of ECDSA indicates confidence that generic attacks are essentially the best possible for this class of cryptography.
Do we then consider ECDSA with pre-signing to be as secure as ECDSA itself? One must entertain the possibility that a “non-generic” cryptanalytic technique might be found, one that violates the GGM in a way that breaks pre-signing, but leaves ECDSA itself unharmed. However, given the state of the art, it would be a major breakthrough if a practical non-generic attack strategy was to be discovered on any commonly used signing curve. Therefore, a cautiously optimistic approach would be to consider Groth and Shoup’s GGM proof (Theorem 3 in the paper) to serve as evidence that pre-signing is safe as a mode of operation—at least in isolation, i.e. not composed with other modes of operation. However, the previously mentioned caveats—vulnerability to state reuse, and limited security guarantees—might warrant the conservative system designer to relegate the pre-signature mode of operation to circumstances where default regular signing is simply much too expensive.
Other Optimized Modes of Operation
Besides pre-signing, there are other modes of operation that optimize some metric or the other, whose security is worth revisiting in the threshold signing case.
Raw Signing is a straightforward example. In this mode of operation, rather than sending m to the signer(s), H(m) is sent directly to be plugged into the signing equation. While this may save substantially on bandwidth—especially when there are several signing nodes—it removes the ability for signers to verify that the requester actually knows m, i.e. a valid pre-image of H(m). Groth and Shoup show that when composed with pre-signatures, raw signing leads to a complete break of the system.
Additive Key Derivation (such as BIP32) is a commonly used method to derive several sub keys from a master key. As derivation involves simple additive tweaks, it is easy to incorporate into a threshold signing system. Groth and Shoup prove that while additive key derivation is safe in the threshold signing setting in isolation, it does not compose securely with pre-signing. In particular, they show an attack that severely degrades the security level of the system that combines both—not to the point of a complete break, but enough to cause concern.
Re-randomization is a technique that Groth and Shoup show has the power to mitigate the above issues. Simply put, this involves incorporating a public additive offset (to the signing nonce) that is freshly sampled once the message is defined. They show that the original security levels of ECDSA can be recovered for Raw Signing and Additive Key Derivation, even in composition with pre-signing. They suggest that the random tweak can be obtained by leveraging access to a random beacon, or by hashing all public parameters of the system (i.e. the public key, R, and m) in a Fiat-Shamir like fashion—although they do not formally analyze this proposal.
Pipelining is the practice of doing some useful work in advance for the (i+1)ᵗʰ signing instance, in parallel with the iᵗʰ instance. For instance in the 3-round DKLs23 protocol, in parallel with the current signing instance, signing nodes can pre-compute the first round of the next instance at no impact on security (modulo the risk of state reuse). This has the advantage of bringing the average round count to 2 when pipelining is possible.
In Conclusion
Care must be taken when applying optimizations like pre-signing in the threshold case, as security of the resulting system can be quite non-trivial to analyze. Groth and Shoup present such an analysis for pre-signing, and show that it is at least safe from all known attack strategies via a GGM proof. While this serves as evidence that pre-signing is likely safe to use in practice, one has to accept the risks of accidental state reuse, and of non-generic attacks being discovered in the future. Of course mathematical proofs are only one component of the full picture, and the best advertisement of security for a scheme is surviving years of deployment and analysis—ECDSA itself has thus far been vulnerable to no more than generic attacks (randomness failures, side channels, and fault attacks notwithstanding). Regardless, the conservative system designer might wish to employ regular one-shot signing by default, and pre-sign only when regular signing can not possibly meet efficiency constraints. Composition of pre-signing with other modes of operation can be tricky as well, and Groth and Shoup give proofs and attacks for some common optimizations.
As usual, the best source of information on this topic is the paper itself, while readers interested in learning more about the GGM and what security it offers may take a look at the note by Koblitz and Menezes, as well as recent work by Zhandry (and references therein).
Acknowledgments
I would like to thank Diego Aranha, Daniel Escudero, and Luisa Siniscalchi for their review of, and comments on this post.
We welcome you to join in the discussion, collaborate, and build together. Please write to us by email or by booking a slot to discuss things, through our Calendly here.
ABOUT US: Silence Laboratories
Silence Laboratories is a deep-tech, decentralized, compute and authentication-infrastructure (MPC-focused) provider that offers developer-focused SDKs and libraries, for protocols, wallets, and projects that can be used to embed/build distributed, zero-trust authentication and authorization products, alike. We aim to be a defacto MPC and Proofing product suite for other builders to build on top of. For ease of integration, we are application, protocol, custodian, and stack agnostic, collaboration-friendly, and future-forward.
Learn more about their work: https://silencelaboratories.com
