En criptografía , el efecto avalancha es una propiedad deseable de los algoritmos criptográficos , típicamente los cifrados de bloque [1] y las funciones hash criptográficas , en las que si se cambia ligeramente una entrada (por ejemplo, invirtiendo un solo bit), la salida cambia significativamente (por ejemplo, la mitad de los bits de salida se invierten). En el caso de los cifrados de bloque de alta calidad, un cambio tan pequeño en la clave o en el texto simple debería causar un cambio drástico en el texto cifrado . El término real fue utilizado por primera vez por Horst Feistel , [1] aunque el concepto se remonta al menos a la difusión de Shannon .
Si un cifrador de bloques o una función hash criptográfica no exhibe el efecto de avalancha en un grado significativo, entonces tiene una aleatorización deficiente y, por lo tanto, un criptoanalista puede hacer predicciones sobre la entrada, teniendo solo la salida. Esto puede ser suficiente para romper parcial o completamente el algoritmo. Por lo tanto, el efecto de avalancha es una condición deseable desde el punto de vista del diseñador del algoritmo o dispositivo criptográfico. La falta de incorporación de esta característica lleva a que la función hash quede expuesta a ataques, incluidos ataques de colisión , ataques de extensión de longitud y ataques de preimagen . [2]
La construcción de un cifrado o hash que presente un efecto de avalancha sustancial es uno de los principales objetivos de diseño, y matemáticamente la construcción aprovecha el efecto mariposa . [3] Esta es la razón por la que la mayoría de los cifrados de bloque son cifrados de producto . También es la razón por la que las funciones hash tienen grandes bloques de datos. Ambas características permiten que los pequeños cambios se propaguen rápidamente a través de iteraciones del algoritmo, de modo que cada bit de la salida dependa de cada bit de la entrada antes de que el algoritmo termine. [ cita requerida ]
El criterio estricto de avalancha ( SAC ) es una formalización del efecto avalancha. Se cumple si, siempre que se complementa un único bit de entrada , cada uno de los bits de salida cambia con una probabilidad del 50%. El SAC se basa en los conceptos de completitud y avalancha y fue introducido por Webster y Tavares en 1985. [4]
Las generalizaciones de orden superior de SAC implican múltiples bits de entrada. Las funciones booleanas que satisfacen el SAC de orden más alto son siempre funciones dobladas , también llamadas funciones máximamente no lineales, también llamadas funciones "no lineales perfectas". [5]
El criterio de independencia de bits ( BIC ) establece que los bits de salida j y k deben cambiar independientemente cuando se invierte cualquier bit de entrada i , para todos los i , j y k . [6]
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )