Re: hash function Shahaha



Collision in the below hash function (and 256 bit tags; the tag size is
variable, and so I had to pick something):

Preimage1:
1d 87 30 02 9e 91 f9 51 c9 26 2a 5d e8 11 3f b0 19 f9 8a 86 91 30 70 fc 44
39 75 56 cf 1a 22 9e f5 4f 6c 8e 35 6d 22 69 a2 66 32 17 b0 4d eb 53

Preimage 2:
1d 87 30 02 9e 91 f9 51 c9 26 2a 5d e8 11 3f b0 19 f9 8a 86 91 30 70 fc 44
39 75 56 cf 1a 22 9e f5 4f 6c 8e 7a 26 9d 6e 41 11 4d ff b0 4d eb 53

Common Hash Value:
25 5d 77 b1 2a 47 38 21 e4 2a 97 9f 75 5a 34 97 b7 2d 1f a0 32 96 b5 80 8f
88 c7 72 5d f4 cd ee


I'd tell you how this collision works (and how I found it), but I suspect
it'd be more instructive for you to figure it out yourself.


"Rade" <rade.vuckovac@xxxxxxxxx> wrote in message
news:7da30d2d-0538-4cf9-a755-8bceb2817de8@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Shahaha is a hash function and ideas behind Shahaha are discussed
here
http://groups.google.com/group/sci.crypt/browse_thread/thread/118b5fdf66144d64

There is a few improvements over Wolfram's rule 30 hash design:
- a linear dependency cost on a message
- operating on a word level instead on a bit level

Shahaha is implemented as shahaha.h (see below). The genKat.c (google
NIST sha3 competition site) may be used to test / use shahaha function
(just include shahaha.h file). Shahaha conforms to the most of
requirements of NIST sha3 competition excluding the very long message
part of genKat.c. That part is not working because shahaha needs
complete message at once as an imput.

Regards Rade Vuckovac

//shahaha.h

#include <stdint.h>

typedef unsigned char BitSequence;
typedef unsigned long long DataLength; // a typical 64-bit value
typedef enum { SUCCESS = 0, FAIL = 1, BAD_HASHBITLEN = 2, NOMEM = 3 }
HashReturn;

typedef struct
{
int hashbitlen;
int rounds;
uint8_t mixer;
uint8_t carry;
uint64_t initial;
uint64_t asize;
uint8_t * ip;
}
hashState;

HashReturn Init(hashState *state, int hashbitlen)
{
state->hashbitlen = hashbitlen;
state->rounds = 3;
state->mixer = 85; //01010101
state->carry = 0;
state->initial = 256;
state->asize =0;
state->ip = (uint8_t *) calloc(state->initial, sizeof(uint8_t));
if(state->ip == NULL)
{
printf("Error allocating memory\n");
return NOMEM;
}

return SUCCESS;
}

HashReturn Update(hashState *state, const BitSequence *data,
DataLength databitlen)
{
uint64_t i, databytelen;

databytelen = databitlen / 8;
if(databitlen % 8 !=0)
{
databytelen++;
state->ip[0] ^= databitlen % 8;
}

state->asize = state->initial + databytelen;
state->ip = (uint8_t *) realloc(state->ip, (state->asize) *
sizeof(uint8_t));
if(state->ip == NULL)
{
printf("Error (re)allocating memory\n");
return NOMEM;
}

for(i = 0; i < databytelen; i++)
{
state->ip[state->initial + i] = data[i];
}

return SUCCESS;
}

HashReturn Final(hashState *state, BitSequence *hashval)
{
int i;
uint64_t j;

for(i = 0; i < state->rounds; i++)
{
for(j = 0; j < state->asize; j++)
{
uint8_t out = state->ip[j];
const uint8_t in = state->ip[(j + 1) % (state->asize)];
const uint8_t a = state->ip[(j + 2) % (state->asize)];
const uint8_t b = state->ip[(j + 3) % (state->asize)];

if (a > b)
state->carry ^= in;
else
state->carry ^= ~in;

state->ip[j] = (out ^= state->carry);
state->carry += state->mixer;
}
}

for(i = 0; i < (state->hashbitlen / 8); i++)
{
uint8_t out = state->ip[i];
const uint8_t in = state->ip[(i + 1) % (state->asize)];
const uint8_t a = state->ip[(i + 2) % (state->asize)];
const uint8_t b = state->ip[(i + 3) % (state->asize)];

if (a > b)
state->carry ^= in;
else
state->carry ^= ~in;

state->ip[i] = (out ^= state->carry);
state->carry += state->mixer;

hashval[i] = state->ip[i];
}

return SUCCESS;
}

HashReturn Hash(int hashbitlen, const BitSequence *data,
DataLength databitlen, BitSequence *hashval)
{
hashState state;

Init(&state, hashbitlen);

Update(&state, data, databitlen);

Final(&state, hashval);

return SUCCESS;
}


.