Dictionary of Meaning
<<Back
Please select a letter:
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |
0-9
Click here for Shopping
Avalanche effect
*** Shopping-Tip: Avalanche effect
:''This article is about
cryptography; for other meanings, see
snowball effect and
avalanche (disambiguation)''.
In
cryptography, the
avalanche effect refers to a desirable property of cryptographic
algorithms, typically
block ciphers and
cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly (for example, flipping a single bit) the output changes significantly (eg, half the output bits flip). In the case of quality block ciphers, such a small change in either the
key (cryptography) key or the
plaintext should cause a drastic change in the
ciphertext. The actual term was first used by
Horst Feistel, although the concept dates back to at least
Claude Shannon Shannon's ''
diffusion (cryptography) diffusion''.
If a block cipher or cryptographic hash function does not exhibit the avalanche effect to a significant degree, then it has poor randomization, and thus a
cryptanalyst can make predictions about the input given only the output. This may be sufficient to partially or completely break the algorithm. It is thus not a desirable condition — at least from one point of view.
Constructing a cipher or hash to exhibit a substantial avalanche effect is one of the primary design objectives. This is why most block ciphers are
product ciphers. It is also why hash functions have large data blocks. Both these features allow small changes to propagate rapidly through iterations of the algorithm, such that every
bit of the output should depend on every bit of the input before the algorithm terminates.
Strict avalanche criterion
The '''Strict Avalanche Criterion''' ('''SAC''') is a property of
boolean functions of relevance in
cryptography. The SAC builds on the concepts of
completeness (cryptography) completeness and
avalanche (cryptography) avalanche, and was introduced by Webster and Tavares in 1985.
Definition
A function is said to satisfy the strict avalanche criterion if, whenever a single input bit is
complemented, each of the output bits should change with a probability of one half.
Bit independence criterion
The '''Bit independence criterion (BIC)''' states that output bits ''j'' & ''k'' should change independently when any single input bit ''i'' is inverted, for all ''i'', ''j'' and ''k''.
See also
*
Confusion and diffusion
References
* A. F. Webster, Stafford E. Tavares: On the Design of S-Boxes. CRYPTO 1985: 523-534
{{Block_ciphers}}
{{cryptographic hash functions}}
Category:Cryptography
fr:Effet avalanche
*** Shopping-Tip: Avalanche effect
