Re: Avalanche Depth of hash functions

Keith Lockstone (klockstone@cix.compulink.co.uk)
Sun, 11 Oct 98 22:27 BST-1

• Next message: mgraffam@idsi.net: "easier authentication?"
• Previous message: Peter Gutmann: "Re: Securing data in memory"
• Maybe in reply to: Simon R Knight: "Securing data in memory"

In-Reply-To: <361DDB57.6CD0AC2B@stud.uni-muenchen.de>
David Wagner <daw@cs.berkeley.edu> wrote:
> This is also an interesting measure for block ciphers...
>
> For instance, DES has avalanche depth just over 2
> (depending upon how close to 0.5 you require; assuming
> you're talking only about 1-bit changes in the plaintext).

I'd heard a figure of about 3 - but it's all an approximation.

>From mok-kong.shen@stud.uni-muenchen.de enquired:
> > Let's start by defining a measure: 'Avalanche Depth' which is 1
> > when there is just enough avalanche to make the input/output
> > probability of a function 0.5. If there is enough avalanche for
> > this to happen twice over, then the Avalanche Depth is 2 etc. I
>
> It is not very clear what you mean by 'to happen twice over'
> since there is only one single function. Could you explain a bit?

At some point in the algorithm, full avalanche is achieved - but
the process carries on. This is just an expression of how many
times over full avalanche occurs.

Anonymous <nobody@replay.com>,
> I really don't think this is a good way to evaluate an algorithm.
> It's more of an intelligent way to count an algorithm's rounds
> than a new measure of its security.
>
> It's already a common practice to look at the security of
> stripped-down versions of algorithms, which is much more useful
> than just looking at the avalanche; it's trivial to make a hash
> function with very "deep" avalanche which cryptographers would
> immediately find weak. In addition, defining the metric itself
> can become tricky when the function's structure doesn't allow a
> simple stripping-down.
>
> If you're looking for something to guide your choice of hash
> function, listen to some experts' opinions or get the all the
> info necessary to take a good, deep look at the question
> yourself. Metrics like that just don't work for measuring
> algorithm security.

I agree with your point of view. However, avalanche is part of
the picture - and I wanted some numbers to get a feel for that
particular aspect of the problem.

I find it interesting that no one has come up with any numerical
answers, whereas for instance in the AES designs submitted,
avalanche gets mentioned quite a few times, occasionally with
numerical estimates. Could it be that hash designers have
ignored this altogether? Perhaps I should email them all and ask
the question .... BTW who is responsible for SHA?

Keith Lockstone.

• Next message: mgraffam@idsi.net: "easier authentication?"
• Previous message: Peter Gutmann: "Re: Securing data in memory"
• Maybe in reply to: Simon R Knight: "Securing data in memory"