Query about hash function capability

Alexander Klimov alserkli at inbox.ru
Thu Aug 4 10:18:58 EDT 2005


On Thu, 4 Aug 2005, Arash Partow wrote:
> My question relates to hash functions in general and not specifically
> cryptographic hashes. I was wondering if there exists a group of hash
> function(s) that will return an identical result for sequentially
> similar yet rotate/shift wise dissimilar input:
>
> ie: input1 : abcdefg -> h(abcdefg) = 123
>      input2 : gabcdef -> h(gabcdef) = 123
>      input3 : fgabcde -> h(fgabcde) = 123
>
> Here a,b,c,d,e,f,g represent symbols (ie: groups of bits with equivalent
> group sizes etc...)
>
> I know that one simple hash method would be to add the symbols
> together, but the results would also be equivalent if say the symbols
> were in any order, also collisions would occur with other totally
> dissimilar sequences that happen to have the same sum as the sequence.
>
> Is there anything out there research/papers etc, or is this a meaningless
> avenue of enquiry?

Just sort all the rotations and use some known hash for the smallest.
For example, if you start with abcab you sort abcab, babca, ababc,
cabab, and bcaba, and calculate SHA1(ababc).

BTW: this rotate-and-sort technique is actually used for data
compression -- search for `Burrows-Wheeler Transform' if you are
interested.

-- 
Regards,
ASK

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list