I'm looking at a broken RSA signature padding implementation in a real device. It's a very-badly implemented version of PKCS #1-like encoding, but before PKCS added the DER-encoded hash identifier.

The signature format is intended to be:

00 01 FF FF FF FF FF ... FF FF 00 <SHA-1 hash>

However, for some reason, the programmers saw how the second byte can also be 02 in PKCS and in that case any nonzero padding could replace the FF bytes. This is misinterpreting PKCS, because that's for encryption padding, not the signature padding. Allowing encryption-mode PKCS padding is a major mistake.

A second mistake is that the implementation does not require the SHA-1 hash to be flushed right. (In 01 mode, it does require that there be at least 8 FF bytes, making attacks on 01 impractical.) Thus, the actual padding format, if abused to be 02 format, is this:

00 02 <nonzero garbage> 00 <SHA-1 hash> <garbage>

If the public exponent were $3$, both the 01 and 02 forms would be trivially broken by taking the floor of the cube root (Bleichenbacher). Alas, the public exponent is $65537$.

Without an oracle, is there an attack against this?

Note that if there were an algorithm that could generate numbers whose 65537th power contained the desired SHA-1 hash anywhere within the message, leaving the rest of the number corrupted randomly, such an algorithm would succeed in $2^{26}$ or so outputs.


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.