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?