O efeito avalanche (ou "efeito avalanche") é uma propriedade desejada em cifras de bloco e em algoritmos de funções criptográficas de hash. Em termos simples, o efeito avalanche exige que uma pequena alteração na entrada provoque uma alteração grande e imprevisível na saída. Na prática, isso significa que, em uma boa cifra de bloco, uma pequena mudança na chave ou no texto em quadrícula deve produzir uma mudança substancial no texto em cifra. Para funções de hash, a mesma propriedade quer dizer que alterar um único bit da entrada deve mudar aproximadamente metade dos bits do resumo (hash).

O termo efeito avalanche foi introduzido por Horst Feistel (Feistel 1973) e está intimamente ligado à propriedade da confusão de Shannon. A ideia básica é que pequenas diferenças se espalhem rapidamente pelo processamento do algoritmo à medida que são aplicadas múltiplas iterações (rounds), de modo que cada parte da saída dependa de todas as partes da entrada. Esse espalhamento é frequentemente conseguido por combinações de operações de substituição (S-boxes), permutações e camadas de difusão (mixing), como nas cifras de produto e em redes de substituição-permutação.

Como se mede e critérios associados

O efeito avalanche é quantificado observando-se o número de bits alterados na saída quando um bit da entrada é invertido. Um valor ideal é que, em média, cerca de 50% dos bits da saída mudem — sinal de boa randomização. Entre critérios formais usados para avaliar esse comportamento estão:

  • Strict Avalanche Criterion (SAC): cada saída deve mudar com probabilidade 1/2 sempre que qualquer bit de entrada é invertido.
  • Bit Independence Criterion (BIC): mudanças em bits de saída devem ser independentes entre si quando um bit de entrada é invertido.

Por que é importante

Se uma cifra de bloco ou uma função de hash não apresenta um efeito avalanche forte, a randomização da saída é fraca. Isso deixa padrões e correlações que um criptanalista pode explorar para fazer previsões sobre a entrada a partir da saída, ou para reduzir a complexidade de um ataque. Técnicas de criptoanálise diferencial e linear, por exemplo, procuram exatamente esse tipo de relação entre pequenas mudanças na entrada e o comportamento da saída; portanto, uma má difusão pode tornar um algoritmo vulnerável e até levá-lo a ser quebrado parcial ou completamente.

Como projetistas obtêm avalanche

Ao projetar uma cifra forte ou uma função criptográfica de hash, os engenheiros visam obter um efeito avalanche robusto. Para isso empregam:

  • múltiplos rounds iterativos, de modo que pequenas diferenças se ampliem exponencialmente;
  • componentes não-lineares (como S-boxes) para evitar relações lineares simples entre entrada e saída;
  • camadas de difusão e permutações que misturam bits de diferentes posições;
  • blocos de dados suficientemente grandes e funções de compressão bem projetadas em hashes para espalhar mudanças por todo o estado interno.

Matematicamente, esse espalhamento lembra o chamado efeito borboleta de sistemas dinâmicos, daí o uso da analogia. Por essa razão muitas cifras de bloco seguem a estrutura de cifras de produto (combinação de confusão e difusão) e as funções de hash processam grandes blocos de dados para aumentar a difusão entre bits.

Exemplos e prática

Algoritmos amplamente usados, como AES e as funções SHA, são projetados para ter forte efeito avalanche: uma pequena mudança na chave ou no texto simples afeta profundamente o texto cifrado ou o digest. Testes práticos de avalanche são parte do processo de avaliação de novos candidatos a cifras e funções de hash — avaliando-se estatisticamente quantos bits da saída mudam ao inverter bits da entrada em múltiplos vetores de teste.

Resumo

O efeito avalanche é um requisito fundamental para garantir que um algoritmo criptográfico produza saídas que pareçam aleatórias e que não exponham correlações exploráveis. Projetistas buscam atender critérios como SAC e BIC por meio de não-linearidade, permutações e rounds suficientes; criptanalistas, por sua vez, procuram qualquer violação desse comportamento para reduzir a segurança do esquema.