yet another hash algorithm

[Rade]

Hi all

There is a new attempt for hash algorithm . Initial idea is discussed
here
http://groups.google.com/group/sci.crypt/browse_thread/thread/118b5fdf66144d64/6bf70c66565222a7?hl=en&lnk=gst&q=rule+30+hash#6bf70c66565222a7
First unsuccessful try is here
http://groups.google.com/group/sci.crypt/browse_thread/thread/508a58bb1559a9cb/ad661fd1d51d53ac?hl=en&lnk=gst&q=rule+30+hash#ad661fd1d51d53ac
Interface is the same as for SHA 3 competition. The algorithm may not
be more secure than first attempt, but it has some interesting
features.

//vez.h

#include <stdint.h>
#include <string.h>
#include <stdlib.h>

typedef enum { SUCCESS = 0, FAIL = 1, BAD_HASHBITLEN = 2 }
HashReturn;

typedef unsigned char BitSequence;

typedef unsigned long long DataLength; // a typical 64-bit value

typedef struct
{

uint8_t rounds_no;
uint16_t hashbytelen;
uint64_t pos;
uint16_t size;
uint64_t mixer;
uint64_t carry;
uint64_t state[512];
uint64_t current[512];

} hashState;

HashReturn Init (hashState *state, int hashbitlen);

HashReturn Update (hashState *state, const BitSequence *data,
DataLength databitlen);

HashReturn Final (hashState *state, BitSequence *hashval);

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

int evolve(hashState *state);

HashReturn Init(hashState *state, int hashbitlen)
{
int i;

state->hashbytelen = hashbitlen / 8;
if((hashbitlen % 8) != 0)
state->hashbytelen++;
state->rounds_no = 3;
state->mixer = 6148914691236517205;
state->carry = 1234567890123456789;
state->pos = 0;
state->size = 512;

for(i = 0; i < state->size; i++)
{
state->state[i] = 0;
state->current[i] =0;
}



return SUCCESS;
}

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

state->carry += databitlen;

databytelen = databitlen / 8;
if((databitlen % 8) > 0 || databitlen == 0)
databytelen++;

datablock = databitlen / 64;
if((databitlen % 64) > 0 || databitlen == 0)
datablock++;

uint64_t padded[datablock];

for(i = 0; i < datablock; i++)
padded[i] = 0;

memcpy(padded, data, databytelen);

start = state->pos;

for(i = 0; i < datablock; i++)
{
state->current[(start+i) % state->size] = padded[i];
state->pos++;
if(state->pos == state->size)
evolve(state);
}

return SUCCESS;
}

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

if(state->pos > 0)
evolve(state);

for(i = 0; i < (2 * state->size); i++)
{
if(state->state[(i + 1) % state->size] > state->state[(i + 3) %
state->size])
state->state[i % state->size] ^= state->state[(i + 1) % state-
>size];
else
state->state[i % state->size] ^= ~state->state[(i + 1) % state-
>size];

if(state->state[(i + 2) % state->size] > state->state[(i + 3) %
state->size])
state->state[i % state->size] ^= state->state[(i + 2) % state-
>size];
else
state->state[i % state->size] ^= ~state->state[(i + 2) % state-
>size];

if(state->state[(i + 3) % state->size] % 2 == 1)
state->state[i % state->size] ^= state->state[(i + 3) % state-
>size];
else
state->state[i % state->size] ^= ~state->state[(i + 3) % state-
>size];
}

memcpy(hashval, state->state, state->hashbytelen);

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;
}

int evolve(hashState *state)
{

int j, k;

//operation key
for(j = 0; j < state->size; j++)
state->state[j] ^= state->current[j];

for(j = 0; j < state->rounds_no; j++)
{
for(k = 0; k < state->size; k++)
{
if(state->state[(k+2)%state->size]>state->state[(k+3)%state->size])
state->carry ^= state->state[(k+1)%state->size];
else
state->carry ^= ~state->state[(k+1)%state->size];

state->state[k] ^= state->carry;
state->carry += state->mixer;
}
}
//operation evolve
for(j = 0; j < state->size; j++)
state->state[j] ^= state->current[j];

for(j = 0; j < state->rounds_no; j++)
{
for(k = 0; k < state->size; k++)
{
if(state->state[(k+2)%state->size]>state->state[(k+3)%state->size])
state->carry ^= state->state[(k+1)%state->size];
else
state->carry ^= ~state->state[(k+1)%state->size];

state->state[k] ^= state->carry;
}
}

state->pos = 0;

for(j =0; j < state->size; j++)
state->current[j] = 0;

return 0;
}

[orz]

Meh.

Leftward information flow occurs only in the addition of state-
>mixer. Which is very slow.
Rightward information flow occurs only from the highest few bits.

Given those two details, I doubt it's possible to get a cryptographic
quality hash in much less than 64 rounds, as an attacker could attack
the lowest bit in isolation from the upper bits.

[Rade]

The purpose of the posting the algorithm is not seeking opinion but to
remember who used the novel techniques first.
Of course meaningful discussion is welcomed, but that also means that
the above statements need more substance.
For example the use of mixer variable is to balance amounts of ones
and zeros for inputs with low entropy (input with all zeros perhaps),
consequently if input has got enough entropy the mixer variable is not
needed.

Regards, Rade

[orz]

On May 27, 3:54 pm, Rade <rade.vucko...@gmail.com> wrote:
> On May 25, 6:16 pm, orz <cdh...@gmail.com> wrote:
>
> > Meh.
>
> > Leftward information flow occurs only in the addition of state->mixer.  Which is very slow.
>
> > Rightward information flow occurs only from the highest few bits.
>
> > Given those two details, I doubt it's possible to get a cryptographic
> > quality hash in much less than 64 rounds, as an attacker could attack
> > the lowest bit in isolation from the upper bits.
>
> The purpose of the posting the algorithm is not seeking opinion but to
> remember who used the novel techniques first.

This is the first time you have have talked about "remembering who
used the novel techniques first" in this thread. Or the linked
threads. Much of what you say doesn't seem to make sense in that
context. For instance, that implies that your previous algorithm was
an "unsuccessful try" because it did not remember who used the novel
techniques first, which seems rather bizarre.

> Of course meaningful discussion is welcomed, but that also means that
> the above statements need more substance.

My previous statements were a meaningful and substantive description
of fatal flaws in the described hash function. Good leftward and
rightward mixing are both essential elements in secure hashes and even
(to a lesser extent) in high quality checksum algorithms. Perhaps you
are unfamiliar with these concepts and/or this was of describing the
issues? Information flow here refers to which bits in one state
depend upon which bits in the prior state. Leftward information flow
here refers to the movement of information from less significant bit
position to more significant bit position, as in a "left shift"
operator in the C language. It happens very slowly during addition/
subtraction, and not at all during xor/and/or, but quickly during left-
shifts and some multiplications. Rightward information flow is the
equivalent in the other direction, as in a "right shift" operator in
the C language. Rightward information flow is a more common source of
problems, since it does not happen at all during any of the faster
standard operations (addition, bitwise xor, bitwise and/or/not, etc)
other than shifts.

Your standard "if (a > b) carry ^= ~c; else carry ^= c;" is equivalent
to "carry ^= c; carry ^= ((int64_t)(b-a)) >> 63;" which has some
rightward information flow, and technically some leftward information
flow as well, but in practice the leftward flow there is negligible
for the purposes of the lower bits, and the rightward is very
limited.

The statements from my previous post make it trivial to find two data
blocks that, when hashed using that algorithm, produce hashes that are
identical in the upper 32 bits of each 64 bit word, but differ in the
lower 32 bits of each 64 bit word. With a little additional work such
techniques could produce an attack that allowed the lowest bit or the
lowest several bits of each output word to be chosen arbitrarily by an
attacker, and independently of the upper bits.

[Rade]

The Motivation of the posting the algorithm is still who did it
first, not how successful the algorithm is.

Since the carry transformation is mentioned, below is short story.
The idea behind the algorithm is utilising McCabe Cyclomatic
Complexity.
Basically the carry is "xor sum" of all other previous elements in
array.
Some array elements are obviously flipped, therefore calculation of
the sum can be in any of 2 ^ size states, meaning that transformation
is exponentially complex (Google above mentioned complexity and impact
of if / else in the program).
Then the carry updates element in array.
In this context statements mentioned above are not meaningful.

Previous try was easy to attack and it was shown by example not by
belief.

Rade

[Noob]

Rade wrote:

> Previous try was easy to attack, and it was shown by example,
> not by belief.

You've just earned 3 crackpot points. Cheers!

[xxein]

xxein: Then this, should not be a problem to decipher. C7|t_PG<<2&!!
x[PP7xmhh^OO2(|_D11rbHH3))"cXXM7(!ooSNN5/p_Q?&&te[[?::sN)c?y]D2{bJJX.
Practice from both ends before you preach.

That was with an entered space. Another space? D8}u`QH==3'""y
\QQ8ynii_PP3)}`E22scII4**#dYYN8)"ppTOO60q`R@''uf\\@;;tO*d@z^E3|cKKYY

Another space somewhere? E9 vaRI>>4(###z]RR9zojj`QQ4* aF33tdJJ5++
$eZZO9*#qqUPP71raSA((vg]]A<<uP+eA{_F4}dLLZZ

Padding? How about the message repeated? 6*ogRC://%wrrkNCC*k`[[QBB
%yoR7$$eU;;&zzsVKK@*yrbbFAA("cRD2wwgXNN2--fAzV2lP7%nU=KKK{oVN9*!
ttj^YYR5**oRGBB8))j`V9|iiL<""kaaZ=22'o`YII-((mgJ9+w^^N?55wrrM(a=wS7|jU<
$2 or otherwise plainly altered?

The source code is needed but it may be altered by sent parameters.
a=2. b=20, c=?. If you miss one communication, you are lost. Every
thing will look like 8"gg\MD8{bbG8|ccNCC3x_E,ppTKAA,""oRMM1vvYG=
$v]CC'""u\LBB4uiL;"v]QFTTT7TftttXu)9EE*Gfttt?''"qhhWB7,,{kRR7(ud[K6y
\R=.|**%tkkNB))uf[Q___&|cWRRH2{kTTM8&rr`QB//{fS:: Something you can't
imagine.

But there is ample leeway when not changing the parameters at all.
What's the nth letter in the code? It may be used as a key. Specify
it in returning correspondence.

[Rade]

For people who might be slower (including myself) and can not decipher
above post, please show a collision example.