Split, sign, and combine [closed]

Question

I have a device that signs (symmetrically) very short messages, and I would like to sign a long one.

I split it into several short messages, signed each one separately, and now combine all the signatures. Of course, the trivial way is to concatenate them, but is there a way to have the combined signature of the same length as the individual ones?

It doesn't seem easy to protect from rearranging the pieces in a different order (hashing the whole sequence of sequences is not considered easy in my case).

However, the device covers by the signature not only the message but also the running index of the messages it signs. Now, it is evident that the straightforward xor of the piecewise signatures is a perfect signature of the whole message.

Has anybody encountered anything like this in theory or practice?

Answer 1

It doesn't seem easy to protect from rearranging the pieces in a different order.

That depends; you haven't specified the operation to combine the hashes at this point.

Certainly any cryptographic hash function has a different value if it performs $H(x|y)$ instead of $H(y|x)$ where $x \neq y$ and the size of $x$ and $y$ are identical. If not, the collision resistance goals of the hash aren't met.

It doesn't seem easy to protect from rearranging the pieces in a different order.

Sure there is, just use HMAC, which is based on a cryptographic hash with SHA-256 or SHA-512.

Now, it is evident that the straightforward xor of the piecewise signatures is a perfect signature of the whole message.

Really? If you say it is evident then you need to provide the evidence.

Say that you have the signature of three messages consisting of sub messages $A$ and $B$: $M_1=(A,B)$, $M_2=(A,B')$ and $M_3=(A',B)$. Now if you XOR the signatures together you get the same value as for $M_4=(A', B')$:

$$S_1 = Sign(1, A) \oplus Sign(2, B)$$ $$S_2 = Sign(1, A) \oplus Sign(2, B')$$ $$S_3 = Sign(1, A') \oplus Sign(2, B)$$ $$S_4 = Sign(1, A') \oplus Sign(2, B') = S_1 \oplus S_2 \oplus S_3$$

XOR is a dangerous operation. What you are generally after is a Merkle tree using cryptographic hashes.

Note that you could first perform a cryptographic hash over the messages and perform a HMAC over the concatenated hashes. That might be more secure than performing a signature over the various parts, especially if the output of the signature function is small.