CVE-2014-1568, CVE-2006-4339
Daniel Bleichenbacher
The attacker wants to forge a cryptographic signature.
RSA is an algorithm invented in the 70's that makes it possible to do cryptographic encryption, and signing. To use this, someone publishes two values (e and N) and keeps another value (d) secret. To create a signature of a message, one calculates a cryptographic hash of a message which is then transformed to a standardized format (this is called padding) and then exponentiates it to the secret exponent (d). The verification operation becomes the exponentiation of the signature to the public exponent (e). Both of these operations are followed by dividing the result by N, ignoring the quotient, and outputting the remainder. This uses a property of modular exponentiation that allows someone to calculate d given e and the prime factors of N (the security of the system is based on the fact that calculating the prime factors of a large number is thought to be very difficult). Since e and N are public, signatures can be verified by anyone, and since d is secret, only whoever has it is able to create new signatures.
For performance reasons, it's very common to use 3 or other small primes as the value of the public exponent e. This, is not supposed to be a problem, but it makes it possible to calculate the exact cubic root of a message with enough control over it's value so that it's also a correctly formatted. This means that without having to calculate d, an attacker could calculate a number that looks like a signature of a message because the cube of that number would look like a correctly formatted hash. This abuses the fact that implementations of signature verification are often very lax and forgiving by accepting values that are incorrectly formatted.
Daniel Bleichenbacher
The attacker wants to forge a cryptographic signature.
RSA is an algorithm invented in the 70's that makes it possible to do cryptographic encryption, and signing. To use this, someone publishes two values (e and N) and keeps another value (d) secret. To create a signature of a message, one calculates a cryptographic hash of a message which is then transformed to a standardized format (this is called padding) and then exponentiates it to the secret exponent (d). The verification operation becomes the exponentiation of the signature to the public exponent (e). Both of these operations are followed by dividing the result by N, ignoring the quotient, and outputting the remainder. This uses a property of modular exponentiation that allows someone to calculate d given e and the prime factors of N (the security of the system is based on the fact that calculating the prime factors of a large number is thought to be very difficult). Since e and N are public, signatures can be verified by anyone, and since d is secret, only whoever has it is able to create new signatures.
For performance reasons, it's very common to use 3 or other small primes as the value of the public exponent e. This, is not supposed to be a problem, but it makes it possible to calculate the exact cubic root of a message with enough control over it's value so that it's also a correctly formatted. This means that without having to calculate d, an attacker could calculate a number that looks like a signature of a message because the cube of that number would look like a correctly formatted hash. This abuses the fact that implementations of signature verification are often very lax and forgiving by accepting values that are incorrectly formatted.
