Talk:Avalanche effect

Deep and non-obvious ambiguity

There is a deep and nonobvious ambiguity where the definition refers to probability of flipping output bits: is it an average over specimens of a universal hash function family or over possible inputs or both? Are there subtly different meanings of avalanching?

Matt, I don't think that this is another case of 'the' as in 'the NSA' or not. It may be straighforward use. I agree that the conventional use is 'the av', but it may be misleading in such an article.

First, one may have a case in which the effect seen is more or less than in some other case. So my foo algorithm (for which I have high hopes) shows only 20% of bits flipping in rev 1, but 43% in rev 2. Does either rev exhiibt 'THE' avalanche effect. Or do both exhibit AN av? I think the latter. So 'the avalanche effect' is a pointer to a an effect with a range of outcomes, not a single operational behavior. Should not one distinguish in a discussion of goodness of avalanche effect in foo as opposed to bar, as still further opposed to baz the defined perfect example of av? I think so. The edits I made were intended in that direction. Thoughts?

I've seen "rev 2 exhibits better avalanche", or "the avalanche is complete after 3 rounds", etc. — Matt 17:24, 1 Jul 2004 (UTC)

Sounds like we both agree on the usage in this case. Should I go back through for clarity or do you want to? ww 17:31, 1 Jul 2004 (UTC)

Ah, no: "the avalanche effect" is widely used. — Matt 13:42, 3 Jul 2004 (UTC)

As for Shannon. I don't know that diffusion was the first use of the concept, but it certainly goes back that far. I suspect that the CI criterion Friedman was developing ca WWI was something mathematically homologous, but I didn't want to say so explicitly. It certainly developed in a different context than cypher design, of course.

Can't remember: CI criterion? — Matt 17:24, 1 Jul 2004 (UTC)

Matt, Sometimes quoted as Index of Coincidence, but I've just gone through a BP glossary, so my brain's stuck in 1945 usage. Sorry about that (and about verb agreement -- wooooolgathering. I've

corected it) . ww 17:31, 1 Jul 2004 (UTC)

Oh, OK. I don't see the connection between the Index of coincidence and the idea of avalanche, though? (The index is the probability that two letters picked at random from the entire text are the same. You can use it to gauge the rough length of the period of a polyalphabetic cipher.) BTW, is this BP glossary online? — Matt 17:37, 1 Jul 2004 (UTC)

Matt, Note that this is dredged material and should be treated accordingly. IC is a statistical measure of the cyphertext and can be used to distinguish encryptions of English vs say Italian or whatever. It is in some sense an entropy measure. It was that I had in mind in speaking about possible homology. Nothing more. And yes, you can use it as you suggest during cryptanalysis.

As for the glossary, yes. It's one of Tony Sales' scanning projects. It was produced ca 44 or 45 by an Oxford lexicographer (Hewett?) who worked in the same office as one of the famous crypto types (CHOD Alexander?). It's interesting that the word usage is characteristically just slightly skew (where there are comparable concepts, of course) to current use. Fascinating stuff. You can imagine how startled I was to find a paper (by Alexander I think) talking about IC this and IC that -- from 1944 or thereabouts!

But recall that, in Vannevar Bush's time, it was computers he was trying to replace/supplement with his analog calculating widgets. (They were usually female, and young.) It's a living thing, this language (reification be damned!). It's just that the spelling is (and always has been) stinkin' rott'n. ww 17:57, 1 Jul 2004 (UTC)

Reactions? ww 17:10, 1 Jul 2004 (UTC)

We often call it "full avalanche effect" when all bits are affected. For instance "for full avalanche effect the cipher needs to use 6 rounds". And when not all bits are affected we call it "partial avalanche effect" or "incomplete avalanche effect" or "insufficient avalanche effect", or perhaps more commonly: "did not achieve full avalanche effect". Personally I almost never say "the avalanche effect" but instead "full avalanche effect" to avoid misunderstandings.

And regarding the bit flipping: It refers to when you test the same hash function (or symmetric cipher) with several different inputs. At full avalanche effect, if you change one (or more) input bits, since bits flip "randomly" then on average 50% of the bits will flip, or rather 50% of the bits will by random chance remain the same. But sure, sometimes just some bits flip, sometimes most flip, since it is "random" flipping. So you have to test the function with many different input pairs to see if the average is 50%. If it is less than 50% on average then it is not full avalanche effect, then there is not enough mixing. If it is more than 50% on average then something fishy is going on, since if you mix more than to full avalanche effect it should remain 50% bit flips on average, since more mixing should not make it less random.

--David Göthberg (talk) 10:32, 30 January 2023 (UTC)

Chaos Theory

How about a mention of chaos theory/butterfly effect? It is all about big changes from little variations, which is exactly what avalanche effects are. Synetech (talk) 01:52, 7 September 2009 (UTC)

Annoying gif

I removed this

[[File:AES avalanche.gif|thumb|100px|right|The output of the [[Advanced Encryption Standard|AES]] cipher as the first value of the plaintext moves from 0 to 255 while all other values remain 0. The output changes drastically despite the tiny change at the input.]]

as it displays (as I observe it) an incredibly annoying animation that distracts me in attempting to read the article. While it describes the concept of the article reasonably well, I don't think it can stay on the page when a person without disabilities can't read the text without disabling it. Eroen (talk) 09:43, 25 February 2012 (UTC)

So now animated gifs are allowed to be removed on the grounds that they are "annoying"? --Simpsons contributor (talk) 10:09, 25 February 2012 (UTC)

I don't know the policy in detail, but removed it under WP:BB, with a listing here. The main reason was unreadability of the text. A better solution might be something one could click on to make the thing start and stop the fancy flashing patterns, but I'm not sure how to accomplish that. Did you strongly feel it needed to be there to make the article informative? Eroen (talk) 13:10, 25 February 2012 (UTC)

Animated gifs make sense when used to illustrate a process. E.g. the animated gif on the linear feedback shift register page is helpful to understand how the states of an LFSR are computed. Here, however, I agree with Eroen. There is no inherent time dimension that justifies an animation. The text explaining that a small change in the input results in a large change in the output and the simple example using SHA-1 are more concise and simpler to follow. Therefore, I also think that the animated gif is more a distraction than adding value to the page. 178.195.230.127 (talk) 13:18, 25 February 2012 (UTC)