# How to break RSA signature on XOR of hashed blocks

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

• Can I ask what is the aim? – kelalaka Dec 25 '18 at 15:54
• the general idea is to sign long messages with minimum signature length instead of signing every block – IGxCS Dec 25 '18 at 16:03
• Is this homework? It looks like it. Please let us know so that we can answer appropriately. – Yehuda Lindell Dec 25 '18 at 16:16
• 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? – IGxCS Dec 25 '18 at 16:23
• While possibly reducing the signature size, one has to process all to verify the sign for a single message. – 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.