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