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.
leftmost bytes != 0x00
) a number of correct signatures will be rejected by this check. $\endgroup$ – CaptainRR Jan 20 '17 at 7:17