Attacking RSA signature verification that ignores padding I am looking at a RSA signature verification that is quite obviously flawed and am wondering if there's a way to exploit that flaw in practice.

Signature is generated using RSA with PKCS 1.5 padding, i.e. $S = M^d \mod N$, where $M$ is a padded message: $M = 00 \| 01 \| FFF ... F\|00\|m$ and $m$ is the raw message being signed, which is always a 64-char pseudo-random ASCII hex string (it's a hash value).

When verifying signature, however, there is no check for padding. Verification is done by computing $M = S^e \mod N$, converting M to a byte array and then simply looking for a substring $m$ in $M$.

Modulus $N$ is 2048 bits and public exponent $e = 65537$.

Attacker can obtain a limited number of valid signatures (of a padded message) but there's no direct control over what $m$ will get signed (it's a time-base hash value).

Do you see any way to forge signature of attacker-chosen $m$ so that it'd be accepted by this flawed verification procedure?

Thanks!
If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android).

In any case, the attack does not work for $e=65536$. However, if your question is whether or not it's OK to use this, then it certainly is not. The existence of the $e=3$ attack should be enough to convince you of that. On the other hand, if your question is constructive to find an attack, then I don't know - but it's a great research question.