Forging Rabin signature

Question

What is the chances to forge a signature for the system implementing Rabin signature with total message recovery, if attacker posses the public key and have some message pairs? The last byte of message to be signed is freely changeable. The attacker doesn't have access to signing oracle.

Answer 1

I'll assume a system as follows

• $N=p\,q$ is the public product of two large secret primes, chosen about uniformly randomly and independently, thus distinct (with overwhelming odds). Such $N$ is believed hard to factor.
• the signer chooses a meaningful message $m$ independently of $p$ and $q$, expressed as a non-negative integer verified to be less than $N/256$, and somewhat finds $k\in[0,255]$ and $c\in[0,N)$ so that $256m+k=c^2\bmod N$ (there are four such $c$ for $s\approx64$ values of $k$, and no $c$ for the others $k$, with high odds).
• the verifier receiving an alleged $c$ computes $m=\lfloor(c^2\bmod N)/256\rfloor$, and trusts that message if it makes sense.

The chances to forge a signature depends tremendously on what the verifier considers "makes sense". For example, the adversary could set $c=37152$, yielding $c^2=1380271104=\mathtt{52454400_h}$, $m$ is $\mathtt{524544_h}$, which in ASCII is RED. Similarly, $c=33360$ yields BUY. We can't pull that trick for many english words, but that counts as forgery unless we better define "makes sense". And for large $N$, if "makes sense" means that the low-order byte of $c^2\bmod N$ is set to zero to create a terminating character, and the whole thing passed as first argument to puts for display and must be something precisely specified, it is still trivial to forge anything desired up to about half the size of $N$. That can be next to any 127-byte string for 2048-bit $N$ (the lowest recommended minimum these days).

Update: We learn that "The meaningful bytes of $m$ (are) coupled together by (a) checksum" of unspecified size. Forgery can be attempted by trying various $c$ until finding one such that $c^2\bmod N$ pass the checksum check. Expected number of trials is $2^s$ (for optimal checksum), where $s$ is the number of bits in the checksum. For up to 32-bit checksum, we are talking at most seconds of computer time. There's nothing to force us to have $c>\sqrt N$, thus we can make the attack without using $N$ or example messages. Incremental $c$ will do, thus with mild optimization the cost is dominated by the computation of the checksum, at least if there is no other constraint on $m$ beyond the checksum. Even with such extra constraint, it still is possible to choose many bytes of the forged message without much increase in search cost. The high-order ones are particularly malleable: we choose $c$ such that the high bytes of its square are as desired, which merely requires computing a square root.