RSA signature verification code had been written (in many places, most notably in Mozilla's NSS library) to "parse" the RSA signature message block that resulted from the public key verification operation. RSA signature verification is a little like RSA encryption "inverted", and the element being encrypted is a hash of the content being signed. What vulnerable implementations would do was, they'd perform the public key transform and the extract the hash, then just check the hash against the content.
The problem is that a SHA2 hash of a message is much smaller than an RSA message block. The remainder of the content of the block is supposed to be "padding". "RSA padding" is one of the worst names in cryptography, because it isn't so much "padding" as it is "armor". If you don't pad in a very particular way, and check the padding scrupulously, you end up with multiple different vulnerabilities.
In this case, the vulnerability was that libraries like NSS weren't checking the padding at all (they naively assumed that if an RSA public key operation produced a SHA2 hash of a complicated message, whoever generated the signature must have the private key). The Bleichenbacher attack was that for E=3 RSA, the unchecked padding created a huge amount of "head room" in which garbage data would be ignored. Because of the low exponent, the modular multiplications performed by the signing (private) operation might never wrap the modulus; in other words, the modulus was irrelevant, because the math worked out to a simple cubing/cube root without ever hitting it. The bits produced by this "key oblivious" E=3 signing operation were gibberish, of course... but the RSA implementations weren't checking them, because they were "just padding". As long as the message bits included a hash in a predictable place, they looked valid.
The correct way to perform this operation was not to extract anything from the RSA message block produced by verification. Instead, the verifier should have simply created their own properly-padded message block from the original content and verified the whole block byte-for-byte. So the bug was, basically, trying to parse RSA signature blocks at all.
The end result was, because RSA verifiers were effectively ignoring most of the signature bits in the message, attackers could use trivial (as in, type- it- into- a- python- repl) math to generate valid-looking signatures for any SHA2 hash.
This bug was in RSA code for years and years and years.
There was a nice 5-part series you and I wrote on this topic back in 2006. However, parts of it are no longer available. Could you rescue it from your archives, with diagrams? Thanks.
The problem is that a SHA2 hash of a message is much smaller than an RSA message block. The remainder of the content of the block is supposed to be "padding". "RSA padding" is one of the worst names in cryptography, because it isn't so much "padding" as it is "armor". If you don't pad in a very particular way, and check the padding scrupulously, you end up with multiple different vulnerabilities.
In this case, the vulnerability was that libraries like NSS weren't checking the padding at all (they naively assumed that if an RSA public key operation produced a SHA2 hash of a complicated message, whoever generated the signature must have the private key). The Bleichenbacher attack was that for E=3 RSA, the unchecked padding created a huge amount of "head room" in which garbage data would be ignored. Because of the low exponent, the modular multiplications performed by the signing (private) operation might never wrap the modulus; in other words, the modulus was irrelevant, because the math worked out to a simple cubing/cube root without ever hitting it. The bits produced by this "key oblivious" E=3 signing operation were gibberish, of course... but the RSA implementations weren't checking them, because they were "just padding". As long as the message bits included a hash in a predictable place, they looked valid.
The correct way to perform this operation was not to extract anything from the RSA message block produced by verification. Instead, the verifier should have simply created their own properly-padded message block from the original content and verified the whole block byte-for-byte. So the bug was, basically, trying to parse RSA signature blocks at all.
The end result was, because RSA verifiers were effectively ignoring most of the signature bits in the message, attackers could use trivial (as in, type- it- into- a- python- repl) math to generate valid-looking signatures for any SHA2 hash.
This bug was in RSA code for years and years and years.
Don't build crypto.