I need a CRC mechanism to calculate the CRC of a number of strings, such that, given two strings, A and B, the sum crc(A) + crc(B) == crc(A+B).
P.S. XOR is too weak---the algorithm should be not trivial for reverse engineering.
+1
A:
I don't think any checksums would fill this condition.
Usually size(CRC(A)) == const (CRC codomain is a limited set, const == size(max_checksum) ).
So if you have message B for which CRC(B) == max_checksum, then for any other message size(CRC(B)) + size(CRC(C)) > const, (from CRC(B) + CRC(C) > max_checksum).
Or to put it differently there is no CRC function that satisfies the requirement.
EDIT:
However, if you meant the you want to be able to determine CRC of two messages together knowing CRC of both individual message, yes this is possible it is used for example by rsync and it is called rolling hash.
Unreason
2010-04-21 12:07:56
A simple XOR sum would.
Henk Holterman
2010-04-21 12:26:12
@Henk, yes but that's not +, that is XOR :) - requirement specified that it should be +
Unreason
2010-04-21 12:28:08
I think '+' means 'combine' here.
Henk Holterman
2010-04-21 14:28:09
@Henk, yes I agree; it probably means any function/operator (or informally combining). But I tried to make a point that question needs to be more clearly specified by formal proof that under current requirement there is no such function (trying to inspire OP to rethink the question); however I fumbled because I allowed myself to insist that at one point it is strictly numerical addition and on the other side I allowed it to mean CONCAT. so to redeem myself I posted the edit on rolling hashes, which I believe should be useful to the OP.
Unreason
2010-04-21 15:01:53
Yes, the irony of the first version was lost on me :-}
Henk Holterman
2010-04-21 16:31:37
+3
A:
Taking your required condition, with + meaning string concatenation on the RHS, and integer addition on the LHS, the checksum of any string would be the sum of the checksums of its individual characters. All such checksums are isomorphic[*], the only tunable parameters are what values you assign to each single char.
If XOR is too weak, then I doubt that any such linear checksum would be strong enough.
If + means anything else in your required condition, perhaps you could specify what...
[*] Well, something-morphic.
Steve Jessop
2010-04-21 12:47:30
+1
A:
Homomorphic hashing comes close to what you're asking for, but I'm not aware of one that works for string contactenation, as opposed to mathematical operations. All known homomorphic hash functions are absurdly slow, too.
I would speculate that it may not even be possible to create a secure hash function that has this property, though.
Nick Johnson
2010-04-22 10:52:07