1
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Feb 11 '16 at 17:41
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 11 '16 at 17:47
  • 3
    $\begingroup$ Which equals no padding at all... $\endgroup$
    – SEJPM
    Feb 11 '16 at 18:03
  • $\begingroup$ and this can be eliminated by redundancy; adding the last 64-bit of the message itself. ref: Menezes 8.14.i $\endgroup$
    – kelalaka
    Nov 10 '18 at 17:59
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I thought about it but I need a solution with probability 1. Can you explain the Jacobi symbol -1? $\endgroup$ Feb 11 '16 at 18:41
  • $\begingroup$ 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 $\endgroup$
    – poncho
    Feb 11 '16 at 18:48
  • $\begingroup$ And, by selecting a $y$ with Jacobi symbol -1, I really mean selecting one with $\Bigl(\frac{y}{n}\Bigr) = -1$ $\endgroup$
    – poncho
    Feb 11 '16 at 19:05
3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 14 '18 at 4:18

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.