Full Report
ECDSA has many unexpected properties that can cause security issues if people are not completely sure on how it works. I can imagine that many of these issues being found in blockchain-land, since the public nature of all data gives everyone more access to data than anticipated. The first, and most well-known issue, is signature malleability. All EC curves are y2=x3 + Ax + B. Because of the y2, the entire curve is reflected over the x axis perfectly. As a result, there are always two valid points or two valid signatures. The math to generate the other point is trivial to do. In blockchain, the usage of signatures is common. To prevent replay and double spend attacks, the verification of the orientation of the signature is crucial. Otherwise, using the signature as a key can create a duplicate signature to bypass the scheme. Given a signature, it's trivial to generate a keypair that has the same signature for a chosen message. In our replay attack example, this doesn't do us any good. However, if there is a scheme that assumes signatures are unique and anybody can call it, then this can be a problem. Now, we have the ability to create arbitrary messages with the same signature. Super weird issue but interesting in practice. The next one is not as common but pops up from time to time. It's super important to hash the data that is provided in and NOT trust an incoming hash. If a hash is supposed to be trusted then an attacker can generate signatures for arbitrary private keys. One of the examples is an app that tries to prove that they created Bitcoin to spoof the Satoshi address. The final two have to do with knowledge of the random k value. Any knowledge of the random can makes it trivial to find the private key. Additionally, if two signatures have the same k from a user then it's also trivial to recover the private key using similar techniques. All of the issues above have a POC in the code, which is super nice as well. Cryptography is absolute black magic and we all need to be careful when using it. The author also linked this as inspiration, which has lots more content about cryptography issues.
Analysis Summary
# Vulnerability: Critical Cryptographic Weaknesses in ECDSA Implementations
## CVE Details
- **CVE ID**: N/A (General Algorithmic Flaws/Implementation Risks)
- **CVSS Score**: 7.5 - 9.8 (High to Critical, depending on application context)
- **CWE**:
- CWE-347: Improper Verification of Cryptographic Signature
- CWE-327: Use of a Broken or Risky Cryptographic Algorithm
- CWE-330: Use of Insufficiently Random Values
## Affected Systems
- **Products**: Blockchain protocols, digital wallets, and authentication systems utilizing ECDSA (Elliptic Curve Digital Signature Algorithm).
- **Versions**: Implementations following standard ECDSA (e.g., NIST P-256, secp256k1) without specific hardening.
- **Configurations**:
- Systems that use signatures as unique identifiers (Transaction IDs).
- Implementations that accept untrusted/externally provided message hashes.
- Systems using weak or non-deterministic Random Number Generators (RNG) for the nonce ($k$).
## Vulnerability Description
The research highlights four fundamental cryptographic "quirks" in ECDSA that lead to severe security failures:
1. **Signature Malleability**: For any valid signature $(r, s)$, the pair $(r, -s \pmod{n})$ is also a valid signature for the same message. This occurs because elliptic curves are symmetric over the x-axis.
2. **Duplicate Signatures**: An attacker can generate a specific keypair that produces a valid signature for a chosen message that matches a signature from a different message/keypair.
3. **Untrusted Hash Input**: If a verification function accepts a pre-computed hash rather than the raw message, an attacker can craft a "message hash" that validates against an arbitrary public key (e.g., spoofing a Satoshi Nakamoto address).
4. **$K$-Value Fragility (Nonce Reuse/Exposure)**:
- If the random nonce $k$ is known, the private key can be recovered via simple algebra.
- If the same $k$ is used to sign two different messages, the private key is instantly leaked.
## Exploitation
- **Status**: PoC available (demonstrated in Sage/Python). These techniques are widely documented in historical exploits (e.g., Sony PS3 hack, Android Bitcoin wallet thefts).
- **Complexity**: Low to Medium (requires basic algebraic knowledge of Elliptic Curves).
- **Attack Vector**: Network (for protocol-level exploits) or Local (for side-channel $k$ recovery).
## Impact
- **Confidentiality**: **Critical**. Total compromise of the private key if $k$ is reused or leaked.
- **Integrity**: **High**. Malleability allows for transaction replay or double-spending in poorly designed blockchains. Duplicate signatures allow for identity spoofing.
- **Availability**: **Medium**. Potential for account lockout or transaction flooding.
## Remediation
### Patches
- **Deterministic ECDSA (RFC 6979)**: Replace random $k$ generation with a deterministic process derived from the private key and the message hash.
- **Library Updates**: Use vetted libraries like `libsecp256k1` which include built-in protection against malleability.
### Workarounds
- **Signature Normalization**: Enforce a "Low-$S$" rule (forcing the $s$ value to be in the lower half of the group order) to eliminate malleability.
- **Strict Hashing**: Never allow users to provide a hash; the application must always perform the hashing internally.
## Detection
- **Indicators of Compromise**:
- Multiple transactions with different signatures but identical $r$ values (indicates $k$ reuse).
- Successive transactions with identical payloads but slightly different signature encodings.
- **Detection Methods**: Use static analysis tools to ensure `RFC 6979` is implemented for signing operations.
## References
- hXXps://kel[.]bz/
- hXXps://github[.]com/SalusaSecondus/CryptoGotchas
- hXXps://github[.]com/google/wycheproof
- hXXps://cryptopals[.]com/sets/8