What is the probability of attacking SHA1 used in RSA signature with small exponent? There is RSA signature check which has following properties:


RSA modulus N which is 2048-bit
RSA public exponent equal 41 (0x29)
Genuine Signature uses EMSA-PKCS1-v1_5 padding of SHA1 hash, however the verifier only compares 20 least significant bytes which are the SHA1 hash. In order to trick verifier, forged signature needs to contain SHA1 of message on the 20 least significant bytes. All other bytes are ignored.


Due to broken check, there exists around $2^{48}$ (because $(2^{48})^{41}$ is smaller than modulus) SHA1 signatures that can have signature forged using algorithm described in Mathematics.

If I try $2^{32}$ different hashes (by trying all numbers in the last 4 bytes of the hashed message), what is the probability that I will encounter one of these $2^{48}$ easy-to-forge hashes?

Is there any other attack type that might be used for such broken signature check?

Adversary has 6 genuine signed messages (message and signature; message not chosen by attacker) and is not able to obtain more.
This is not an answer; rather, I attempt to improve the method outlined in the question.

Problem statement (slightly simplified): it is given an RSA public key $(N,e)$ with $2^{n-1}&lt;N&lt;2^n$, $n=2048$, $e=41$, a hash function $H=\operatorname{SHA-1}$ with output of $w=160$ bits. It is asked an $(m,s)$ with $0\le s&lt;N$ and $H(m)=(s^e\bmod N)\bmod2^w$.

Note: for simplicity, I ignore the six given (message, signature) pairs and that the $(m,s)$ to exhibit must not be among them. These $(m_i,s_i)$ are such that $0\le s_i&lt;N$ and $(s_i^e\bmod N)=H(m_i)+c$ with known $c=2^{n-15}-2^{8+v+w}+2^w b$, $v=120$, $2^{v-8}\le b&lt;2^v$, $b=\mathtt{0x3021300906052b0e03021a05000414}$ (that's by definition of EMSA-PKCS1-v1_5).



As noted in the question, for any given $m$ with $H(m)$ odd, if there exists an odd $s$ such that $(m,s)$ is a solution to our problem and $0\le s&lt;\Big\lceil\sqrt[e]N\Big\rceil$, then we can efficiently find that $s$ by computing $h=H(m)$ and solving for $w$-bit $s$ the equation $s^e\equiv h\bmod 2^w$; we keep $s$ as solution if $s&lt;\Big\lceil\sqrt[e]N\Big\rceil$.

If we try this for a random $m$, each attempt costs an average of two hashes to find $H(m)$ odd, finding one solution to the equation $s^e\equiv h\bmod 2^w$, and succeeds with probability about $\epsilon=\sqrt[e]N/2^{w+1}\approx2^{(n-1/2)/e-1-w}$; that's slightly under $2^{-111}$ and as is, this strategy is doomed.



Notice that for any given $m$, if there exists $r\ge0$ with $r+H(m)$ odd and odd $s$ such that $(m,s)$ is a solution to our problem and $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s&lt;\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$, then we can find that $s$ by computing $h=H(m)$, and solving for $r$ of appropriate parity and $w$-bit $s$ the equation $s^e\equiv(h+r N)\bmod 2^w$; we keep $s$ as solution if $\Big\lceil\sqrt[e]{r N}\Big\rceil\le s&lt;\Big\lceil\sqrt[e]{(r+1)N}\Big\rceil$.

If we just enumerate small incremental $r$ of the appropriate parity, compute $h'=h+r N\bmod 2^w$, and solve for $w$-bit $s$ the equation $s^e\equiv h'\bmod 2^w$, then for each $r$ we have probability about $\epsilon_r=\left(\sqrt[e]{(r+1)N}-\sqrt[e]{r N}\right)/2^{w+1}$ that $s$  turns out to be in the correct range; that is, $\epsilon_r=\begin{cases}
\epsilon=\sqrt[e]N/2^{w+1}&amp;\text{ if }r=0\\\left(\sqrt[e]{1+1/r}-1\right)\;\epsilon&amp;\text{ if }r&gt;0\end{cases}$
This is an improvement if the cost of solving $s^e\equiv h'\bmod 2^w$ is much lower that the cost of a hash (or if our messages $m$ are heavily constrained). In particular, if $h=H(m)$ turns out to be even, we formerly abandoned that $m$, and now have probability about $\epsilon_1\approx\epsilon/59$ that the solution $s$ to $s^e\equiv(h+N)\bmod 2^w$ is acceptable.

Also, when solving $s^e\equiv(h+r N)\bmod 2^w$, if we compute $s$ bit by bit starting from the low-order bits, we can abandon as soon as we have enough bits that it is certain that $s$ is not in the appropriate range.

Perhaps a simultaneous search of $(r,s)$ is feasible; I'll be thinking about it. As the saying (attributed to the NSA) goes: attacks only get better; they never get worse.