Is this Bleichenbacher '06 style signature forgery possible? (Or more like, why isn't it?) I assume that most of you know this, but just for the sake of context; Bleichenbacher's signature forgery (https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html) basically abuses implementations that do not check that the PKCS#1 1.5 padding of a decrypted signature is correctly layed out. Most vulnerable implementations accept cases where the embedded hash is not right-justified. With a reduced padding, the hash can be moved forward (more to the left) then the remaining bytes can be treated as "garbage", which in turn make enough room for organizing so that this number is a perfect cube. In case of public exponent 3, it means that the cuberoot of the latter number is a valid signature as seen by the wrong implementation. Actually what happens is that you're basically good with the rounded cube root of a number of your choice of the form (line29, https://github.com/akalin/cryptopals-python3/blob/master/challenge42.py), and cubing it only messes up the garbage digits/places anyway.

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all. Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code. On the other hand, the ending digits are already restricted just by the value being a cube number.
Let hashlen be the length of the hash in bits, and rsalen the much bigger length of the signature. Giving up on forging a signature for a particular hash, my intuition would tell me that if you take the last hashlen bits of the possible cube numbers for the signature (for which there are possibilities on the order of 2^1/3*rsalen*) then this set would have a non-negligible intersection/overlap with the possible hash values of size hashlen. Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs?
Conversely, is there a quick and profound argument that shows that the outlined "signature checking" (looking at only the hash at the end) does not weaken the implementation?
Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all.


That case is completely broken for $e=3$


  Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code. 


That actually pretty easy, with the assumption that the lsbit of the hash is a 1 (or more generally, that the number of 0's at the end of the hash is a multiple of 3); this assumption is necessary, because if it is not true, no perfect cube will exist.  It turns out if this assumption is true, then a cube will always exist.

The most straight-forward approach to find it is to do it iteratively; if we have a value $x^3 = h \pmod{2^n}$, then we can easily find a value $y^3 = h \pmod {2^{n+1}}$, as either $y = x$ or $y = x + 2^n$, and it's easy to check which one it is.  So, we just start with a small $n$, and just repeatedly add bits to $x$ until, when cubed, it generates the entire hash in its $n$ least significant bits.


  Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs?


The above procedure works for more than half of all possible messages (assuming the hash function acts as random), hence the attacker can easily pick a message that he likes.