Discussion:
a new very fast hash algorithm (160 bits), with a technique of "overlapping sums"
Claudio
2004-09-28 07:30:26 UTC
Hello,

This is a method for a hash function, based on a new technique (I
think it's new, but this should be validated).

#define UL unsigned long
#define LEFT 13
#define RIGHT 19

void round()
{
hash[4] += hash[0] >> RIGHT;
hash[0] += hash[0] << LEFT;
hash[0] += hash[1] >> RIGHT;
hash[1] += hash[1] << LEFT;
hash[1] += hash[2] >> RIGHT;
hash[2] += hash[2] << LEFT;
hash[2] += hash[3] >> RIGHT;
hash[3] += hash[3] << LEFT;
hash[3] += hash[4] >> RIGHT;
hash[4] += hash[4] << LEFT;
}

void processBlock(const UL in[25])
{
int i, j, r, s;
for (i = 0; i < 5; i++)
{
s = 0;
for (r=0; r<5; r++)
{
for (j = 0; j < 5; j++)
{
hash[j] ^= in[j+s];
hash[j]++;
}
round();
s += 5;
}
}
}

It processes blocks of 800 bits. The same block is processed 3 times.
Each time, a sub-block of 160 bits is XORed with the hash block, and the
result is mixed with itself (round() function), by making the 32 bits
integers overlap with themselves (overlapping, and then addition modulo
232).

Can anybody tell me whether this idea is completely bad or very
interesting ??

The facts:
- The avalanche effect seems OK after 5 rounds. This has been
empirically checked with the tests programs: ENT, NIST , DIEHARD (I
generated a set of hashvalues, from a given 800-bits block where a
32-bits integer at a given position was incremented before generating
the next hashvalue. I chosed the following integers: in[0] and in[24]).

- fast algorithm. In Assembly, the inner loop will take about 40 cycles
by using MMX instructions, and by storing the hash block in MMX
registers (6 cycles per DWORD processed). The processBlock() function
will therefore take about 40*5*5 = 1000 cycles, for 100 bytes => about
10 cycles / byte, which is just a little bit slower than MD5.

Thanks a lot in advance for your remarks (sorry for my non-perfect
english).
Nick Maclaren
2004-09-28 09:10:23 UTC
In article <***@uni-berlin.de>,
Claudio <***@numericable.fr> writes:
|>
|> Can anybody tell me whether this idea is completely bad or very
|> interesting ??

Probably. Not me.

|> The facts:
|> - The avalanche effect seems OK after 5 rounds. This has been
|> empirically checked with the tests programs: ENT, NIST , DIEHARD ...

It is not as widely known as it should be, but it has been known
for 70 years that generic test programs are necessarily very weak.
I can produce seriously flawed random number generators that will
pass those with flying colours.

Another, similar, point is that it is easy to prove that almost all
semi-uniform hash functions will be 'reasonable' - for several very
different meanings of the word reasonable.

The first question to ask is what sort of attack you are allowing
for. I use a really simple, VERY fast multiplicative congruential
hash function that is extremely reliable against accident (i.e. an
unintelligent opponent). You then get onto an attack by an
opponent that doesn't know your hash function, knows the function
but not the initial data, or knows everything.

Regards,
Nick Maclaren.
Nick Maclaren
2004-12-14 04:14:28 UTC
making a fuss.

23. We emphasize that the foregoing does not pretend to be an accurate
description of everyone who might be considered a leftist. It is only
a rough indication of a general tendency of leftism.

OVERSOCIALIZATION

24. Psychologists use the term "socialization" to designate the
process by which children are trained to think and act as society
demands. A person is said to be well socialized if he believes in and
obeys the moral code of his society and fits in well as a functioning
part of that society. It may seem senseless to say that many leftists
are over-socialized, since the leftist is perceived as a rebel.
Nevertheless, the position can be defended. Many leftists are not such
rebels as they seem.

25. The moral code of our society is so demanding that no one can
think, feel and act in a completely moral way. For example, we are not
supposed to hate anyone, yet almost everyone hates somebody at some
time or other, whether he admits it to himself or not. Some people are
so highly socialized that the attempt to think, feel and act morally
imposes a severe burden on them. In order to avoid feelings of guilt,
they continually have to deceive themselves about their own motives
and find moral explanations for feelings and actions that in reality
have a non-moral origin. We use the term "oversocialized" to describe
such people. [2]

26. Oversocialization can lead to low self-esteem, a sense of
powerlessness, defeatism, guilt, etc. One of the most important means
by which our society socializes children is by making them feel
ashamed of behavior or speech that is contrary to society's
expectations. If this is overdone, or if a particular child is
especially susceptible to such feelings, he ends by feeling ashamed of
HIMSELF. Moreover the thought and the behavior of the