RSA-OAEP's proof and the caveats
OAEP (Bellare-Rogaway, 1994; security proof corrected by Shoup, 2001; tighter proof by Fujisaki-Okamoto-Pointcheval-Stern, 2001) is IND-CCA2 secure assuming RSA is one-way and the underlying hash and mask generation function behave as random oracles.
Caveats:
- Random oracle assumption: provably impossible to instantiate in the standard model; works in practice but is technically a heuristic.
- Implementation timing: Manger's 2001 attack on a naive OAEP implementation recovers the plaintext with O(log n) queries via timing leaks. The fix is constant-time decoding.
- Key reuse across protocols: using the same RSA key for OAEP encryption and PKCS#1 v1.5 signing was exploitable (DROWN).
ECDSA biased nonces: a true catastrophe
ECDSA's signing equation: s = k^-1 (z + r*d) mod n, where k is a per-signature random nonce, z is the message hash, r derives from k*G, and d is the private key.
If k repeats across two messages, the attacker recovers d with linear algebra: subtract two signing equations, solve for d. Sony PlayStation 3 (2010): every signature used the literal value 4. Fail0verflow extracted the master key in days.
If k is merely biased (a few bits predictable), the Hidden Number Problem applies. Lattice-based attacks (Bleichenbacher 2000, Howgrave-Graham-Smart 2001, recent improvements by Mulder et al, Tibouchi-Albrecht) can recover the key from a few hundred signatures if only 3-4 bits of each nonce are biased. Real Bitcoin wallet thefts have used this against weak RNGs.
Defense: deterministic nonces per RFC 6979, k = HMAC-SHA256(d, z). Mathematically equal to ECDSA but no entropy dependence. EdDSA uses this construction natively.
Schnorr and BIP340
Schnorr signatures (1989; patent expired 2008) are simpler and have a tighter security proof than ECDSA. Signing equation: s = k + e*d where e = H(R || P || m). Verification: s*G == R + e*P.
Bitcoin's BIP340 (2020 standard, Taproot) adopted Schnorr because:
- Linearity: signatures aggregate. n participants in a MuSig protocol produce one combined signature indistinguishable from a single-key Schnorr signature.
- Provable security in the random oracle model with a tight reduction (no biased-nonce footgun if you follow RFC-style deterministic
k). - Smaller verification: cheaper batch verification of many signatures.
Pairings and BLS signatures
A bilinear pairing is a map e: G1 x G2 -> GT with e(aP, bQ) = e(P, Q)^(ab). Built on specific elliptic curves (BN254, BLS12-381).
BLS signatures (Boneh-Lynn-Shacham, 2001): the signature is a single curve point, s = d * H(m) for hash-to-curve H. Verification: e(G, s) == e(P, H(m)). Properties:
- Aggregation: n signatures from n keys on the same message aggregate to one signature. Useful for blockchain consensus (Ethereum 2.0 attestations).
- Threshold: t-of-n signing schemes via Shamir secret sharing of the private key.
- Identity-based encryption: a public string (an email address) becomes the public key; a trusted key generator issues the matching private key. Useful where deploying full PKI is infeasible.
Post-quantum: what changes mathematically
ML-KEM (formerly Kyber) and ML-DSA (Dilithium) are lattice-based. Their security reductions go through the Module Learning With Errors (MLWE) and Module Short Integer Solution (MSIS) problems. These are believed quantum-hard with currently-known algorithms but lack the decades of cryptanalysis that RSA and ECC have.
Pragmatic posture: use hybrid modes (classical X25519 + ML-KEM together) for the next decade or so. Either is independently secure against today's adversary; if a flaw appears in one, the other holds.