Skip to content

Lack of strong unforgeability↑

Higher-level cryptographic protocols, such as those used in secure communication or blockchain systems, rely on foundational building blocks like digital signature schemes. It’s crucial to assess whether these schemes meet the expected properties. For example, using a scheme that lacks the ‘strong unforgeability’ property can open the door to attacks, as demonstrated by some notable cases in cryptocurrency systems.

Context↑

The ability of an attacker to turn valid signatures into a new, still valid signature can compromise the security of a higher-level application or protocol. Whether this is the case depends on the specific security requirements of the higher-level system.

There are two formal definitions of “unforgeability” in the cryptographic literature:

  1. Existential Unforgeability under Chosen Message Attacks (EUF-CMA) says that it should be impossible for an adversary to produce a valid signature on a message that has not been previously signed by the legitimate signer, even if the adversary can obtain signatures for any messages they specify.
  2. Strong Unforgeability under Chosen Message Attacks” (SUF-CMA) states that an adversary cannot produce a new valid signature for a message, even if they already have access to valid signatures for that message. Like in EUF-CMA, the adversary can submit messages of its choice to a signing oracle and will receive valid signatures in return.

Many signature schemes, both theoretical and practical, target only EUF-CMA. For example, if a verification algorithm strips off trailing zeros of a signature, it would be trivial to violate SUF-CMA by adding zeros to create a “new” signature, even though breaking EUF-CMA might remain difficult.

Severity and recommendations↑

An example of a vulnerability exploiting the lack of SUF-CMA security is transaction malleability in Bitcoin.

Formal analysis, often called a “proof of security” in cryptographic literature, of the higher-level protocol establishes which properties are demanded of the underlying building block. In particular, this analysis establishes whether SUF-CMA is required for the protocol or whether EUF-CMA suffices. For example, a recent analysis relied on SUF-CMA to argue that the SSH protocol is secure.

Alternatively, instead of relying on a formal analysis to confirm that EUF-CMA is adequate, signature schemes can be upgraded to schemes that satisfy the stronger SUF-CMA security. For example, ECDSA is not SUF-CMA secure. In contrast, EdDSA, as specified in RFC 8032, achieves SUF-CMA security under established cryptographic assumptions.

However, it’s important to note that this guarantee only applies to EdDSA implementations that strictly follow RFC 8032. Furthermore, even when deploying an SUF-CMA secure signature scheme, it’s critical to enforce unique encoding of signatures. Without this, the SUF-CMA guarantees are compromised.

Resources↑

Refer to Matt Green’s blog post on EUF-CMA and SUF-CMA.