3 ms·

Does anyone know what the "Bleichenbacher bug" was that scared people away from using 3 for the exponent?

dfranke 15y ago
http://archiv.infsec.ethz.ch/education/fs08/secsem/Bleichenbacher98.pdf http://archiv.infsec.ethz.ch/education/fs08/secsem/Bleichenb...
- agl 15y ago
  This was actually a different attack on RSA by the same person! tptacek described the padding attack well in a sibling comment.
- NateLawson 15y ago
  Bleichenbacher often comes out of hiding and posts some terrible crypto bug, usually based on a slight implementation deviation from best practices. The above bug is in RSA encryption, not signing, and is much more interesting technically than the e=3 padding verification bug. Just by revealing a different error message, attackers can use your server as a decryption oracle. It's different than the POET/BEAST attacks though, which are on block cipher modes. I tried to write a clear review of the paper here: http://rdist.root.org/2008/01/07/ssl-pkcs-padding-attack/ http://rdist.root.org/2008/01/07/ssl-pkcs-padding-attack/ The amusing thing is that he usually picks a random toolkit you've never heard of to attack, and then someone else (Hal Finney in the case of the e=3 padding bug) realizes it's a widespread issue in much more important systems.
tptacek 15y ago
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. Don't build crypto.
- NateLawson 15y ago
  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. http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-forgery-explained-with-nate-lawson-part-iv.html http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-...
  - tptacek 15y ago
    Nate thinks that by asking me publicly, I'm more likely to get this done than the last 10 times he's asked me privately. :)

http://archiv.infsec.ethz.ch/education/fs08/secsem/Bleichenbacher98.pdf http://archiv.infsec.ethz.ch/education/fs08/secsem/Bleichenb...

agl 15y ago
This was actually a different attack on RSA by the same person! tptacek described the padding attack well in a sibling comment.
NateLawson 15y ago
Bleichenbacher often comes out of hiding and posts some terrible crypto bug, usually based on a slight implementation deviation from best practices. The above bug is in RSA encryption, not signing, and is much more interesting technically than the e=3 padding verification bug. Just by revealing a different error message, attackers can use your server as a decryption oracle. It's different than the POET/BEAST attacks though, which are on block cipher modes. I tried to write a clear review of the paper here: http://rdist.root.org/2008/01/07/ssl-pkcs-padding-attack/ http://rdist.root.org/2008/01/07/ssl-pkcs-padding-attack/ The amusing thing is that he usually picks a random toolkit you've never heard of to attack, and then someone else (Hal Finney in the case of the e=3 padding bug) realizes it's a widespread issue in much more important systems.

tptacek 15y ago

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. Don't build crypto.

NateLawson 15y ago
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. http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-forgery-explained-with-nate-lawson-part-iv.html http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-...
- tptacek 15y ago
  Nate thinks that by asking me publicly, I'm more likely to get this done than the last 10 times he's asked me privately. :)