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?

Improve this question
$\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 ♦
    Commented Feb 11, 2016 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$
    – user3415513
    Commented Feb 11, 2016 at 17:47
  • 3
    $\begingroup$ Which equals no padding at all... $\endgroup$
    – SEJPM
    Commented Feb 11, 2016 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
    Commented Nov 10, 2018 at 17:59

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I thought about it but I need a solution with probability 1. Can you explain the Jacobi symbol -1? $\endgroup$
    – user3415513
    Commented Feb 11, 2016 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
    Commented Feb 11, 2016 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
    Commented Feb 11, 2016 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).

Improve this answer
$\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$
    – Squeamish Ossifrage
    Commented Mar 14, 2018 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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