Bleichenbacher’s e=3 forgery attack creates RSA signatures without the private key when verification combines public exponent 3 with incomplete PKCS#1 v1.5 padding validation. Because verification computes a cube, the attacker searches for a signature whose cube has the required encoded prefix and digest suffix, while invalid bytes remain hidden between them. section 9.6 section 9.6.3
The attack proceeds by exploiting the structure of the encoded message:
- Choose a target message whose digest satisfies the attack’s required suffix condition. section 9.3
- Construct a prefix cube root whose cube begins with the required PKCS#1 v1.5 header and message information. section 9.6.3
- Construct a suffix cube root whose cube ends with the required hash information, using bitwise adjustment. section 9.6.3
Prefix cube-root test
A Go test generates a random target, computes a prefix cube root, cubes it, and verifies that the leading bytes match. One run matches 0x6E46048A even though the remaining cubed bytes differ.
Suffix cube-root test
A second Go test adjusts bits of a candidate until its cube ends with a chosen random suffix. The displayed cube preserves the requested final bytes while allowing unrelated leading bytes.
