During past days the errors of bash interpreter called Shellshock shaded other messages including errrors in NSS influencing the verification of certificates in Firefox and Chrome. The matter concerned is another instance of not quite common vulnerability which, however, occurs repeatedly: Bleichenbacher´s attack on RSA with little public exponent, typically 3.
The use of the public exponent 3 at RSA is still quite popular because the encoding and verification of signature is quick with this exponent. The exponent 3 itself is not dangerous, but just because of the susceptibility of implementations to Bleichenbacher´s error it is no more recommended.
For repetition we will describe how RSA signature is verified. We have a public key which is composed of module N and public exponent e=3. We have a message M in which the S signature is generated. For the attestation of signature we will calculate:
c = S3 mod N
The resulting number c should be consistent with M. In practice the message M must have a specific form so as “textbook“ attacks could not be applied. PKCS#1 in 1.5 padding is used which looks in the following way:
00 01 FF FF ... FF FF 00 ASN.1_blob hash
There are so many FF bytes so as to “level“ hash on the right in such a way that all the block has the size of a module (e.g. 256 bytes for 2048-bit modulus). ASN.1_blob is a structure which specifies the type of hash and the last item is the very hash of the original message to which the signature belongs.
Bleichenbacher´s error occurs if we allow some trash to be after hash which the false ASN.1 parser unignores (the number of filling FF FF bytes is decreased and hash turns to the left).
Trash on the right enables us to calculate the common third root rounded down so that the signature does not “spin“ through modulus N during raising to a higher power – the signature will not depend at all on the module of the key. We will create the false signarure S2 in the following way (M2 as well as S2 are in big-endian notation):
M2 = 00 01 FF FF FF FF FF FF FF FF 00 ASN.1_blob hash FF ... FF S2 = floor(cube_root(M2))
Eight FF bytes to the left from ASN.1 blob are selected because they are the minimal number of filling bytes required from most of implementations. If S2 is checked as signature, it will be cubed and we will have:
c = S2^3 = 00 01 FF FF FF FF FF FF FF FF 00 ASN.1_blob hash smetí
Considering, however, that the false parser ignores trash after hash, it will shell only hash, compare it with hash from the message and declare that it fits. This “trash“ instead of the original FF bytes at the end emerged in such a way that we after extracting the root rounded the result in the false signarure.
The error in NSS is a variant of this attack. In case of NSS, bytes were not filled in to the right from hash but inside the ASN.1 blob because of integral overflow in formatting of ASN.1 structures. A detailed and completely technical analysis of error in the interpretation of ASN.1 blob is described in the little record by Adam Langley.