Zero padded signatures in the Bleichenbacher attack

Question

I'm studying this attack and i have some doubts about it; let me explain with an example.

Here is my decoded signature:

00 01 FF .. FF .. 00 ASN1 HASH

I forge a decoded signature like this:

00 01 FF .. FF .. 00 AS1 HASH GARBAGE

and than I calculate the cube root in order to obtain the RSA encoded signature.

The cube root resulted from this attack has always a number of bytes lesser than the signature key (for example, RSA1024=128bytes) though. A signature properly padded has always 128bytes.

Why does RSA accept a 0x00 padded cube root as encoded signature? Couldn't a check like this (leftmost bytes != 0x00) be used to avoid this type of attack?

Answer 1

Why does RSA accept a 0x00 padded cube root as encoded signature?

It is not correct to assume that a valid RSA signature always starts with a byte containing a few bits set to one.

An RSA signature is calculated by padding the hash value. The padded hash value is then raised by the private exponent using modular exponentiation. The modular exponentiation of the value will return a value that is between zero and the modulus. Each of the signature values between these numbers is about equally likely.

That also means that a significant amount of signatures have fewer than $n - 8$ bits when encoded as unsigned big endian integer. It depends on the value of the modulus, but you would expect about 1 in 192 to be smaller than $n - 8$ bits overall. Here $n$ is the number of bits that the modulus occupies; for RSA this is also the key size - this answer assumed that $n$ is a multiple of 8, e.g. 1024 in the question.

The I2OSP function in RSA PKCS#1 will however make sure that all signature values are left-padded with zero-valued bytes until signatures have the same size as the modulus. So signatures that start with 00-valued bytes are valid by definition.

Couldn't a check like this (leftmost bytes != 0x00) be used to avoid this type of attack?

So, in conclusion, no, because your check would reject perfectly valid signatures.

The only check that can be meaningfully be performed before signature verification is to match the signature size (including zero bytes) to the key size.