Let's say that an RSA implementation of PKCS #1 signatures fails to validate that the 00 01 FF FF FF ... FF 00
portion of the decrypted signature is exactly as long as needed to fill up the signature block entirely when appended with the hash identifier and hash. This means that the padding could be shortened to some minimum length. The latter part of the block may then vary arbitrarily and the broken validator would accept it.
For the case of $e = 3$, the Bleichenbacher attack would work: you could calculate $\left\lceil{\sqrt[3]m}\right\rceil$ of a signature block $m$ with the padding and hash in the upper part and zeros below. Since greater than $\frac23$ of the decrypted block is unchecked, the random data in the low part from using an inexact cube root doesn't break the signature as far as the broken validator is concerned.
Does such an attack exist for $e > \log_2n$, such as the common $e = 65537$?
I believe that an attack exists in this scenario if you have access to a signer for other signatures, but what about the case when you don't?
00 01
verified ? Is it verified that it is followed by some number ofFF
, then a00
? What's the size of the hash and of the hash identifier? Are these two expected at fixed or data dependent offsets? Is anything else checked? $\endgroup$FF
bytes then a00
. The hash is SHA-256, so 32 bytes. The hash identifier is 13 bytes, as usual. The broken implementation uses the position of the second00
to know where to find the algorithm ID and hash. $\endgroup$