2
$\begingroup$

Searching about RSA signature forgery I came across this question. In the answer, it is stated that

for small to moderate $e$ (including $e=3$ and $e=2^{16}+1$, often used in practice), it would be possible to forge a large class of messages, including C strings showing as anything desired. For any $m_0$, it is easy to exhibit $m_1$ such that $m=m_0||m_1$ is the (non-modular) e-th power of a known integer $\sigma$ (compute $\sigma=⌈\sqrt[e]{m_0 2^{2e|N|}}⌉$ and $m_1 = \sigma^e − m_0 2^{2e|n|}$ of size $2e|N|$ bit); this $\sigma$ verifies as the signature for $m$; and $m$ prints the same as $m_0$ if $m_0$ is a zero-terminated C-string.

And actually I am having a hard time seeing how this can work with $e = 2^{16}+1$. I would say that $\sigma$ will most probably be greater than the modulus $N$ in this case and the reduction will make everything fall apart.

Should there be a condition on

$m_1 = \sigma^e − m_0 2^{2e|n|}$ of size $2e|N|$ bit

and thus the forgery shall work for $e = 2^{16}+1$ but only with a very large modulus and not standard 1024-/2048-/4096-bit ones?

Can anyone shed some light on this?

Many thanks

$\endgroup$
0
0
$\begingroup$

The quoted answer is about a question with

To verify, the receiver checks that $\sigma^e \equiv m \pmod N$. (…)
Given $m \pmod N$ but an unknown $m$ (…)

Thus in the context it does not necessarily hold $0\le m<N$ as in the textbook RSA signature scheme of the original article. Rather, the question considers an hypothetical signature system where $m$ can be larger than $N$, and the message is signed as an appendix $\sigma\gets m^d\bmod N$, sent independently of the message.

The line of attack in the old answer is ridiculously complex for this setup. Here is a simpler attack that works for any $e$, and if the receiver checks $0\le\sigma<N$ in addition to the question's $\sigma^e \equiv m \pmod N$.

The attacker

  • chooses $\sigma$ freely in $[0,N)$, including $0$, and $1$ and $N-1$ which would simplify computation.
  • decides $m_0$, e.g. ending with an 0x00 byte acting as a $C$ string terminator
  • if $N$ is $n$-bit, decides that $m_1$ [to me appended to $m_0$ forming $m=m_0\mathbin\|m_1$ ] will be a bitstring of $b=8\lceil n/8\rceil$ bit
  • computes $m\gets m_0\,2^b+((\sigma^e-m_0\,2^b)\bmod N)$.

I'll make an example with $N=$RSA-2048, $e=2^{16}+1$, $\sigma=3^{1291}$, message $m$ printing as the 15-byte A test message. in ASCII. Try it online!.


That said, the old answer was bogus, I fixed it; and the present question is right to state that with $0\le m<N$ (common in textbook RSA), an attack is possible for very small $e$ like $e=3$ but fails for $e=65537$ and usual size of $N$.

$\endgroup$
1
  • $\begingroup$ Ok, this is indeed really more simple and works perfectly! In the meantime, I had a look at Extending Bleichenbacher's Forgery Attack which, although it does not really talk about that, gives some more details about the relation between the size of $N$ and the use of $\sqrt[e]{}$ depending on $e$ Thanks for the answer! $\endgroup$
    – tilnn
    Jan 14 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.