Re: Query about hash function capability
On Thu, 4 Aug 2005, Arash Partow wrote: ie: input1 : abcdefg - h(abcdefg) = 123 input2 : gabcdef - h(gabcdef) = 123 input3 : fgabcde - h(fgabcde) = 123 I don't have a formal reference for you, but this seems intuitively correct to me: put the strings in a canonical form so that all equivalent strings reduce to the same string, then hash conventionally. Eg., for rotation, the canonical form of a string is the rotation which gives the smallest value when the string is considered a binary number. In other words, alphabetize all the rotations and then take the first one. -J - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Query about hash function capability
| Hi all, | | 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? | | | any help would be very much appreciated. Rotate the input string until it has the smallest possible value among all possible rotations. Possible rotations are those that you want to consider equivalent under the hash - if you want just ab and ba as ASCII strings to be equivalent, then allow only rotations in units of bytes. If you also want 0xc2c4 - the result of rotating that pair of bytes left by one bit - to be equivalent, include bit rotations in the possible rotations. Finally, hash using any standard algorithm. (What this is doing is partitioning the set of inputs into equivalence classes - where two inputs are in the same equivalence class if they are intended to hash to the same value - and then replacing the input string by a unique representative of the equivalence class. You can define equivalence classes any way you like, as long as you can compute a unique representative. For example, a hash that ignores upper/lower case distinctions is trivially realized by replacing all letters in the input with their lower-case equivalents. That just chooses the all-lower-case version as the representative of the set of case-equivalent versions of the string. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Query about hash function capability
On Thu, Aug 04, 2005 at 12:55:51PM +1000, Arash Partow wrote: Hi all, 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 Sure, just pick the lexicographically first cycle and hash that. This is an invariant of all cyclic permutations of the string. epermut - h(epermut) ermutep - h(epermut) muteper - h(epermut) permute - h(epermut) rmutepe - h(epermut) tepermu - h(epermut) uteperm - h(epermut) More generally given any automorphism group on the input strings, hashing the lexicographically smallest member of the orbit of an input string under the group gives a hash that is invariant under the group operation. -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Query about hash function capability
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 [EMAIL PROTECTED]
Re: Query about hash function capability
On Aug 3, 2005, at 7:55 PM, 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...) Why not just include a canonicalization step at the beginning of the hash that is designed to ignore rotation? For example, if you can define an ordering on the set of possible inputs to the hash, then you can rotate any input to the point where it is the smallest (or largest) that it can be, and then hash *that* value. Ian Clelland [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
