# Forging Rabin signature

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.

• The name of the system is Rabin signature with total message recovery, but that name (not so well-known BTW) is not enough to describe the system. It leaves unspecified: A) The padding. Apparently, there's none. B) When a signature $c$ is accepted. That is: after recovered message is computed as $m=c^2\bmod N$, how $m$ is determined to be valid or worth forging. C) How $c$ was produced. There are 4 different $c$ leading to the same $m$, not all $m$ are possible thus $m$ needs adjustment to allow the production of $c$, and methods for that vary. – fgrieu Dec 20 '19 at 8:18

## 1 Answer

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.

• The verifier strictly checks 127 bytes of message except the last one, the 128th. – Georg D Dec 20 '19 at 9:44
• @Georg D: define "strict check". Is that equality (in which case we can only sign a single message), and if so how is the other argument of the comparison determined? Is it specified that $N$ is 1024-bit? Sorry but in crypto, such "details" are of paramount importance, for they make or break security. ISO 9796(-1) specified Rabin signature with total massage recovery in exquisite details, yet was broken (factorization of $N$ thus total break from 2 or 4 queries to a signing oracle). But this won't occur here for there is no signing oracle. – fgrieu Dec 20 '19 at 10:07
• At first I greatly appreciated your effort to answer my questions. The meaningful bytes of $\ m$ is coupled together by checksum and I have a freedom to change only the last one freely. – Georg D Dec 20 '19 at 10:10
• @Georg D: I'm not pulling your leg when stating that details make or break security in crypto, and that in Rabin signature with total message recovery and without padding (your scheme) the absolutely critical thing is what the verifier considers "makes sense". Here that is (still very insufficiently) stated in in your "coupled together by checksum", which you have withheld from us for over three days. – fgrieu Dec 20 '19 at 10:43