# 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.

• Is the small RSA exponent the private exponent or the public exponent? If it is the latter, there is no attack (the SHA-1 hash is raised to the private exponent first). If it is the former there are worse attacks (since you can find it and just calculate the private key ops). – otus May 11 '16 at 10:16
• RSA exponent stated in the question is the public exponent. – desowin May 11 '16 at 10:18
• Funny enough this is probably more secure than simply verifying the signature based on the hash indicator within it. The hash should be a configuration parameter to the signature verification (otherwise you could simply request to verify a MD5 hash). Note that SHA-1 is close to be broken for collision attacks; if anything should worry you it's SHA-1, followed by the RSA key size. Both are still secure in short term, but they're certainly not recommended anymore – Maarten Bodewes May 11 '16 at 15:15
• Strongly related stackoverflow question. – fgrieu May 12 '16 at 16:25

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}<N<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<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<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<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<\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<\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<\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<\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}&\text{ if }r=0\\\left(\sqrt[e]{1+1/r}-1\right)\;\epsilon&\text{ if }r>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.

• Intel in BERserk Vulnerability uses $r=1$ for even values of $H(m)$ (they calculate $h′=H(m)+(N \pmod {2^{w}}))$) and then modify forged signature to force single modulo N reduction. Thay way after (single) reduction occurs there is correct data in the lest significant bytes. This works fine for e=3. In case of e=41, $r$ is already needed for many forged signatures (including odd ones) and is a big number. Also note, if $H(m)$ is even and can be achieved without modulo N reduction then method in accepted answer at Mathematics will find it. – desowin May 12 '16 at 13:07