The real situation is even worse. The problem is not in the PKCS#1 1.5 padding. The problem is that the attack can be used on any message that has fixed header, 'magic cookie'. Think about HTML/XML header, etc.
Here I extended by code to handle a message with 8-bit header. It must be zero. Such messages are not uncommon.
...
m_lower_bound=gmpy2.mpz(0x0001000000000000)
m_upper_bound=gmpy2.mpz(0x00FFFFFFFFFFFFFF)
...
def oracle(c):
d=gmpy2.mpz(4911287298007382225)
assert isinstance(c, gmpy2.mpz)
plaintext=pow(c, d, n)
plaintext_b=int(plaintext).to_bytes(length=BITS//8, byteorder="big", signed=False)
return plaintext_b[0]==0 # first byte is zero
...
It will offer 3 possible plaintexts:
... Found! upper: 00000000: 00 90 CA D8 D8 DE DE DE ........ ... Found! upper: 00000000: 00 D9 30 45 45 4E 4E 4D ..0EENNM ... Found! upper: 00000000: 00 48 65 6C 6C 6F 6F 6F .Hellooo calls_to_oracle 1107
Only ~1k calls to oracle. The code.
Some people say this attack can be extended to just one bit in header. Not uncommon -- first character of Latin plaintext has highest zero bit.
What about mitigations? PKCS#1 1.5 must not be used at all. Think about RSA-OEAP at least. And of course, a remote server or a device must not leak information about such padding errors. About errors at all.
The 'textbook RSA' must not be used at all, only for learning.
More radical approach is to get rid of RSA completely and switch to ECC. Because RSA is so easy to misuse. However, some cryptographers say that ECC has its own problems.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.