Score:1

Split, sign, and combine

cn flag

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?

Maarten Bodewes avatar
in flag
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.
Score:1
in flag

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.

uk-ny avatar
cn flag
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.
Maarten Bodewes avatar
in flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.