As Bleichenbacher states, a wrong implementation of the parsing function of the padding could lead to a signature forgery attack when using a low exponent.
In the provided example he assumes the attacker has the freedom to put chosen bytes in the "garbage" section at the end of the message, in order to create a perfect cube root.
00 01 FF FF ... FF 00 ASN.1 HASH GARBAGE
I wonder if this attack, or any variants, could be generalized to the case where the GARBAGE (eg. the chosen bytes) is not at the end of the message. In general, let say we only have a few "free" bytes we can play with, in the middle of the message:
00 01 FF FF ... FF 00 ASN.1 HASH FREE_1 00 00 ... 00 FREE_2 ... 00 ... FREE_N
Is it possible to efficiently (not by bruteforce) choose them in order to produce a fake signature? If yes, how many free bytes are needed to make it working and feasable?
[EDIT]
Example:
Let say we have exactly 5 free bytes available, marked as XX
. HH
is a byte of some hash. All the others are fixed values (hex) we cannot change. Of course we can play a bit with the hash itself.
00 01 FF FF FF FF FF FF FF FF 00
HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH HH
XX XX
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
XX XX
00 00
AA BB CC DD
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
XX
[00 [01 [FF…]]] GARBAGE [[00] ASN.1] HASH
and then about $4/7$ (for $e=3$) of hashes enable an attack, for large enough public modulus. $\endgroup$FREE_J
, size ofASN.1
andHASH
, minimum size of[FF FF … FF]
, size of the public modulus. Do you have a typical setup ? $\endgroup$