### 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,

-
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]

```