# Breaking hashless variant of the Rabin Signature system with chosen message attack

I heard that we can break the Rabin Signature system using chosen-message attack. For a message $M$ that is a quadratic residue modulo $N$, the signature is $x$ such that $x^2 \equiv M \pmod N$. I can't find a message to ask for its signature in order to spoof my message $M$.

Any suggestions?

• You can not break the Rabin Signature system (easier than factoring) when it uses a proper message padding, and the one proposed in the original article is fine. You can however break implementations with a bad message padding. Define exactly how the message to sign is transformed into a signature in your Rabin Signature system variant, and we'll be able to hint you. – fgrieu Feb 11 '16 at 17:41
• In my system, for a message A that is a quadratic residue modulo N, the signature is x such that x^2=a mod N. – user3415513 Feb 11 '16 at 17:47
• Which equals no padding at all... – SEJPM Feb 11 '16 at 18:03
• and this can be eliminated by redundancy; adding the last 64-bit of the message itself. ref: Menezes 8.14.i – kelalaka Nov 10 '18 at 17:59

Here's how the attack works:

• Select a random value $y$

• Compute $a = y^2 \bmod n$

• Ask for the signature of $a$, that is $x$ with $x^2 = a$

• If $x \ne y$ and $x + y \ne n$, then $\gcd(n, x+y)$ is a proper factor of $n$

The last step will succeed with probability $\approx 0.5$. You can make it probability 1 if you select a $y$ with Jacobi symbol -1.

• I thought about it but I need a solution with probability 1. Can you explain the Jacobi symbol -1? – user3415513 Feb 11 '16 at 18:41
• Actually, we would consider a cryptosystem broken if there is an attack which succeeds with probability $10^{-6}$. However, since you asked: en.wikipedia.org/wiki/Jacobi_symbol – poncho Feb 11 '16 at 18:48
• And, by selecting a $y$ with Jacobi symbol -1, I really mean selecting one with $\Bigl(\frac{y}{n}\Bigr) = -1$ – poncho Feb 11 '16 at 19:05

You heard incorrectly. Rabin signatures as proposed in his 1979 paper include (randomized) hashing of the message, which completely prevents the attack given reasonable choices of hash function.

The scheme without message hashing was never proposed, and should be called something like "oversimplified Rabin-like signatures" to avoid confusion. I recommend Bernstein's paper "RSA signatures and Rabin–Williams signatures: the state of the art" which sets the historical record straight. This is not a minor caveat: if we're going to ignore clearly stated conditions on the use of a scheme in the paper or standard that proposed it, then we might as well by the same argument say that RSA, ECDSA, EdDSA, and every other signature algorithm in common use are broken under chosen message attack (and also under weaker attack models in many cases).

• I'm glad I'm not the only one tilting at this windmill! The dangerously misleading trope of separating ‘signing’ from ‘hashing’ or, worse, ‘padding’, is painfully common. – Squeamish Ossifrage Mar 14 '18 at 4:18