1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ So in the comment below my question you say that the signatures of the large messages are prefixed with a counter. However, you say that you XOR the signatures over the smaller messages to derive at that signature, so for me that doesn't make sense. Please include a formal description of your scheme. $\endgroup$
    – Maarten Bodewes
    Jan 14 at 14:56

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ No, if $S_1 = Sig(A,B)$, $S_2 = Sig(A,B')$ and $S_3 = Sig(A',B)$, then $S_1 \oplus S_2 \oplus S_3$ is by no means the signature of $(A', B')$. In fact, in my situation, $S_1 = Sig(1,A,B)$, $S_2 = Sig(2,A,B')$ and $S_3 = Sig(3,A',B)$, but it is irrelevant to your comment. $\endgroup$
    – uk-ny
    Jan 14 at 13:32
  • $\begingroup$ Please write down your scheme formally, then we can actually create on topic answers. As it is currently described, I don't see why my answer doesn't work. Just saying it aint so is no argument. $\endgroup$
    – Maarten Bodewes
    Jan 14 at 13:58

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