Query about hash function capability

Jerrold Leichter jerrold.leichter at smarts.com
Thu Aug 4 17:07:45 EDT 2005


| 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 majordomo at metzdowd.com



More information about the cryptography mailing list