3
$\begingroup$

I know that because of the multplicative property of RSA

$s =(s_1s_2) \bmod n = (m_1m_2)^d \bmod n$

If Oscar wants to sign now an own message $m$ he chooses another message $m_1$ with $\gcd(m_1,n)=1$ and he calculates $m_2 = m\cdot m_1^{-1} \bmod n$

After this part I don't understand the attack...

How is he able to sign now his own message $m$ ?

$\endgroup$
2
$\begingroup$

The Procedure

Step 1: Factor the original signature $s$ into $s=\prod_{i=1}^n s_i$ and then exponentiate each signature with $e$ as in: $m=\prod_{i=1}^n s_i^e=\prod_{i=1}^n m_i$. Different methods to obtain multiple $s_i,m_i$ pairs work just as well, such as asking the signing oracle.

Step 2: Build a new message with a valid signature as the product of any subset of the $m_i$, e.g. $m'=\prod_{k\in M'\subseteq \{m_1,...,m_n\}}m_k$ now build the same product for the signatures and you've successfully forged your message: $s'=\prod_{k\in S'\subseteq \{s_1,...,s_n\}}s_k$ where $S'$ is the corresponding set of signatures to $M'$.


The Theory

The theory behind step 2 is exactly as you'd have imagined, e.g. you have some $(m_i,s_i=m_i^d \bmod n)$ pairs and multiply them the signatures to get the new signature $s'=s_1\cdot s_2 \cdot ... \cdot s_n=m_1^d\cdot m_2^d \cdot ... \cdot m_n^d=(m_1\cdot m_2 \cdot ... \cdot m_n)^d=(m')^d$ which by definition of the RSA signature scheme is a valid signature for $m'$.


The (simple) Example

Let's take the example from the comments: $p=3,q=11,n=33,\varphi(n)=20,e=3,d=7$ and we are provided with two message / signature pairs: $(m_1,s_1)=(4,16),(m_2,s_2)=(6,30)$.

Now let's skip step 1 for now and directly proceed with step 2 (as we already have more than one message-signature-pair). Step 2 says: "select any message-signature-pairs and multiply them together". So we have $m'=m_1\cdot m_2\bmod n=(4\cdot 6) \bmod 33 = 24$ and we have $s'=s_1\cdot s_2 \bmod n=16\cdot 30 \bmod 33=18$. Thus we have constructed the message-signature-pair $(24,18)$.

Let's also quickly apply the theory part here: $m^d\bmod n$ is a valid signature for any message $m$. $s'=16\cdot 30 \bmod 33=(4^7\bmod 33)\cdot (6^7 \bmod 33) =(4\cdot 6 )^7 \bmod 33=(24)^7\bmod 33 = 18$

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have for example n =33, phi(n)=20, e =3 Alice did send Bob two messages --> (m,s) = (4,16) and (6,30) Then we calculated m' = (4*6 mod 33 = 24) and s'=(16*30 mod 33 = 18) $\endgroup$ – userkir May 28 '16 at 15:08
  • $\begingroup$ Yet, I still do not get the second part, where we have to build our own new message $\endgroup$ – userkir May 28 '16 at 15:14
  • $\begingroup$ @userkir I have tried to clarify my answer, tell me if there's still something unclear. $\endgroup$ – SEJPM May 28 '16 at 17:30
  • $\begingroup$ I'm really thankful for the answers. Nearly everthing is clear except for m' . So in this case Oscar can't choose the message m' freely , can he ? $\endgroup$ – userkir May 28 '16 at 18:25
  • $\begingroup$ @userkir, no he can't. $m'$ must be constructed from what you can extract from the given set of signatures / messages. $\endgroup$ – SEJPM May 28 '16 at 18:27
6
$\begingroup$

Suppose you want to obtain the signature $s = m^d \bmod n$ on a chosen message $m$. Here is that attack.

  1. You ask the signer to sign a random message $m_1$ and obtain the corresponding signature $s_1 = m_1^d \bmod n$;
  2. You compute message $m_2 := m\cdot m_1^{-1} \bmod n$ and ask the signer to sign message $m_2$; you obtain the signature $s_2 = m_2^d \bmod n$.

From the pairs $(m_1,s_1)$ and $(m_2,s_2)$, the signature $s$ on chosen message $m$ can be recovered as $s = s_1 \cdot s_2 \bmod n$.

To see it, observe that $s \equiv s_1 \cdot s_2 \equiv m_1^d \cdot m_2^d \equiv m_1^d \cdot (m\cdot m_1^{-1})^d \equiv m_1^d \cdot m^d \cdot m_1^{-d} \equiv m^d \pmod n$.


Note that you could obtain the signature on message $m$ by only asking one signature to the signer. Indeed, you can construct the pair $(m_1,s_1)$ in Step 1 above by yourself as follows: choose a random $s_1$ modulo $n$ and define $m_1 = s_1^e \bmod n$ (where $e$ is the public verification exponent). We then have $m_1^d \equiv s_1 \pmod n$ as required.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But why should Alice sign a single message for me ? $\endgroup$ – userkir May 29 '16 at 8:44
  • $\begingroup$ The messages Alice is asked to sign are "random looking"---and so appear as innocent messages. Bob (the attacker) can for example tells Alice that the message represents a key and asks Alice to sign it to authenticate the key. From the received signature, Bob can then obtain the signature on chosen message $m$ (for example, $m= $"Alice owes Bob $1,000,000"). $\endgroup$ – user94293 May 29 '16 at 13:50
  • $\begingroup$ Okay, cool thats interesting. But this wouldn´t work if Alice and her Partner would use a Hash function, right ? $\endgroup$ – userkir May 29 '16 at 14:08
  • $\begingroup$ Correct in general (this depends on the hash function) ---see Desmedt and Odlyzko (Crypto'85) though. But for example, if the hash function is a full-domain hash function (i.e., whose output range is $\{0, \dots, n-1\}$), the resulting signatures are secure. This is the well-known RSA-FDH signature scheme. $\endgroup$ – user94293 May 29 '16 at 14:36

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.