I'm trying to figure out if there's a way of breaking or weakening the following method of signing long messages

Given $M=m_{1}m_{2}...m_{n},\,\,|m_i|=64b, \,\,h=h(m_{1})\oplus h(m_{2})\oplus\cdots\oplus h(m_{n})$

sign $h$ using the RSA method.

also, is it weaker than the original way (of signing every message separately)?

  • $\begingroup$ Can I ask what is the aim? $\endgroup$ – kelalaka Dec 25 '18 at 15:54
  • $\begingroup$ the general idea is to sign long messages with minimum signature length instead of signing every block $\endgroup$ – IGxCS Dec 25 '18 at 16:03
  • 1
    $\begingroup$ Is this homework? It looks like it. Please let us know so that we can answer appropriately. $\endgroup$ – Yehuda Lindell Dec 25 '18 at 16:16
  • $\begingroup$ It's not homework, it's a question from past exam, this is my first question here and I was wondering if I need to mention it, why is it important? $\endgroup$ – IGxCS Dec 25 '18 at 16:23
  • $\begingroup$ While possibly reducing the signature size, one has to process all to verify the sign for a single message. $\endgroup$ – kelalaka Dec 25 '18 at 16:32

To sign a message $M = m_1 \ldots m_n$, you calculate $h(M) = h(m_1) \oplus \ldots \oplus h(m_n)$ then $S(M) = \textsf{RSASSA}(h(M))$ where $\textsf{RSASSA}$ is some RSA-based signature mechanism. $h$ is presumably a cryptographic hash function. You're looking for a weakness of this signing method.

Start small. Given $M = m_1 m_2$, can you think of another message $M'$ such that $S(M) = S(M')$? (Note that a weakness could be more complicated than this. For example, it could be impossible to find two messages with the same signature, but possible to derive the signature of $M'$ from the signature of $M$. However, in this case, it is possible to forge another message with the same signature.)

$S(m_1 m_2) = \textsf{RSASSA}(h(m_1) \oplus h(m_2)) = \textsf{RSASSA}(h(m_2) \oplus h(m_1)) = S(m_2 m_1)$

Follow-up exercise (easy): given an arbitrary message $M = m_1 \ldots m_n$, find a longer message with the same signature. Hint:

Above I used the fact that $\oplus$ is commutative. What other algebraic properties does $\oplus$ have?

The normal way to sign a message $m_1 \ldots m_n$ is of course $\textsf{RSASSA}(h(m_1 \ldots m_n))$. If you also want to be able to verify the signature of one part independently, one solution is to build a hash tree and sign the root hash. A two-level hash tree would be $h(h(m_1) \ldots h(m_n))$. If you transmit the signature $\textsf{RSASSA}(h(h(m_1) \ldots h(m_n)))$ as well as the list of individual hashes $(h(m_1), \ldots, h(m_n))$ then it's possible to verify the signature of any of the individual $m_i$. Signatures are larger than hashes and more expensive to compute, so this can save resources compared so signing each $m_i$ independently.

| improve this answer | |

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.