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?

  • $\begingroup$ What the question calls "decrypted signature" is known as "encoded message" (or "message representative" before that's converted from number to bytestring), and obtained by "RSAVP1 verification primitive": no decryption in sight, which would require the private key. Independently: it is not entirely clear what the implementation considered checks, and where. Is the 00 01verified ? Is it verified that it is followed by some number of FF, then a 00? 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$ – fgrieu Feb 2 '17 at 14:14
  • $\begingroup$ @fgrieu Yes, it verifies that it's followed by some number of FF bytes then a 00. The hash is SHA-256, so 32 bytes. The hash identifier is 13 bytes, as usual. The broken implementation uses the position of the second 00 to know where to find the algorithm ID and hash. $\endgroup$ – Myria Feb 4 '17 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.