Discussion:
\$1000 to break this Wheeler-Needham-style compression function
D. J. Bernstein
2004-09-07 03:26:27 UTC
Raw Message
Here's a simple function that hashes 512 bits, in[0] through in[15],
down to 256 bits, out[0] through out[7], using out[8] through out[15] as
temporaries:

void slash(uint32 out[16],const uint32 in[16])
{
int i, r;
uint32 sum = 0, x = in[15];
for (i = 0;i < 16;++i) out[i] = in[i];
for (r = 0;r < 32;++r) {
sum += 0x9e3779b9;
for (i = 0;i < 16;++i)
x = out[i] += ((x + sum) ^ ((x << 7) | (x >> 25)));
}
for (i = 0;i < 8;++i) out[i] = in[i] ^ out[i + 8];
}

I'll pay \$1000 to the first person to find a collision in this function,
or an input whose output begins with 128 bits of 0's.

This function takes a few thousand cycles on typical CPUs, like the
SHA-256 compression function. It has 512 very simple rounds, sweeping
through each of the 16 input words 32 times, rather than 64 rounds of a
more complicated operation. A differential can keep slightly more than
128 of the first 256 rounds inactive but disintegrates after that.

Some ways to vary SLASH without destroying its spirit: a slightly wider
(less serial) computation would take better advantage of the parallelism
of typical CPUs; a slightly less regular order of word accesses would
provide faster avalanche in the initial rounds.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago
Michael Amling
2004-09-11 12:58:59 UTC
Raw Message
Post by D. J. Bernstein
Here's a simple function that hashes 512 bits, in[0] through in[15],
down to 256 bits, out[0] through out[7], using out[8] through out[15] as
void slash(uint32 out[16],const uint32 in[16])
{
int i, r;
uint32 sum = 0, x = in[15];
for (i = 0;i < 16;++i) out[i] = in[i];
for (r = 0;r < 32;++r) {
sum += 0x9e3779b9;
for (i = 0;i < 16;++i)
x = out[i] += ((x + sum) ^ ((x << 7) | (x >> 25)));
}
for (i = 0;i < 8;++i) out[i] = in[i] ^ out[i + 8];
}
I'll pay \$1000 to the first person to find a collision in this function,
or an input whose output begins with 128 bits of 0's.
This function takes a few thousand cycles on typical CPUs, like the
SHA-256 compression function. It has 512 very simple rounds, sweeping
through each of the 16 input words 32 times, rather than 64 rounds of a
more complicated operation. A differential can keep slightly more than
128 of the first 256 rounds inactive but disintegrates after that.
Some ways to vary SLASH without destroying its spirit: a slightly wider
(less serial) computation would take better advantage of the parallelism
of typical CPUs; a slightly less regular order of word accesses would
provide faster avalanche in the initial rounds.
What do you think of Bruce Schneier's suggestion that NIST issue an
AES-like call for new hash functions? If NIST had such a competition,
would you enter SLASH (iterated) in the 256-bit category?

--Mike Amling
D. J. Bernstein
2004-09-17 09:55:15 UTC
Raw Message
Post by Michael Amling
What do you think of Bruce Schneier's suggestion that NIST issue an
AES-like call for new hash functions?
Here's the real question: How unhappy are we with the current NIST/NSA
hashing standard, SHA-256?

People were quite unhappy before AES. DES was breakable. Triple-DES was
painfully slow, over 100 Pentium cycles per byte. Nothing other than
Triple-DES attracted enough users to become a new de-facto standard.
Even worse, Triple-DES and most other DES replacements stuck to the
64-bit DES block size; many applications started leaking quite a lot of
information after a few gigabytes of data.

The hashing situation now isn't as awful as the encryption situation
before AES---but it looks bad enough to justify pouring new energy into
hash-function research, and maybe bad enough to justify building a new
standard.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

[Moderator's footnote: A general discussion on what we need in terms of crypto
primitives/mechanisms is probably best dealt with as
part of the ongoing thread on this topic in sci.crypt]
D. J. Bernstein
2004-12-14 07:48:46 UTC
Raw Message
disintegration of the industrial system. But if this happens we'll be
very lucky. It's far more probably that the transition to a
nontechnological society will be very difficult and full of conflicts
and disasters.

33. (Paragraph 195) The economic and technological structure of a
society are far more important than its political structure in
determining the way the average man lives (see paragraphs 95, 119 and
Notes 16, 18).

34. (Paragraph 215) This statement refers to our particular brand of
anarchism. A wide variety of social attitudes have been called
"anarchist," and it may be that many who consider themselves
anarchists would not accept our statement of paragraph 215. It should
be noted, by the way, that there is a nonviolent anarchist movement
whose members probably would not accept FC as anarchist and certainly
would not approve of FC's violent methods.

35. (Paragraph 219) Many leftists are motivated also by hostility, but
the hostility probably results in part from a frustrated need for
power.

36. (Paragraph 229) It is important to understand that we mean someone
who sympathizes with these MOVEMENTS as they exist today in our
society. One who believes that women, homosexuals, etc., should have
equal rights is not necessarily a leftist. The feminist, gay rights,
etc., movements that exist in our society have the particular
ideological tone that characterizes leftism, and if one believes, for
example, that women should have equal rights it does not necessarily
follow that one must sympathize with the feminist movement as it
exists today.

If copyright problems make it impossible for this long quotation to be