Criterio Estricto de Avalancha (SAC)

El Criterio Estricto de Avalancha SAC (Strict Avalanche Criterion), es una medida de las propiedades de confusión y difusión de una función criptográfica y/o hash. Se presentó por A. F. Webster y Stafford E. Tavares en 1.985, ampliado por B. Preneel en 1.991 y generalizado (Orden superior) por Rejané Forré en 1.998. Fue diseñado para medir la cantidad de no linealidad en las Cajas S-BOX, un componente clave de muchos cifradores en bloque.

 

Utilizando una analogía: Es similar al efecto producido cuando jugamos a tirar una piedra a un estanque y tratar de que realice varios saltos en la superficie. Los pequeños cambios que produce se transmiten a todo el estanque, produciendo reiterados cambios que modifican la tensión superficial y el aspecto de toda la superficie.

Para lo que nos interesa, ¿cómo es de grande el efecto? ¿Cuántas rondas necesitamos?, para responder a estas y otras preguntas se formaliza la noción al medir la cantidad de cambio introducido en la salida por un pequeño cambio en la entrada, es decir: cada bit de la salida depende de todos los bits de la entrada de una manera relevante.

 

Tomando la función (Lógica-Booleana f : Fⁿ₂ → F), se obtiene una salida F(x) = y para una entrada x. El bit inicial de x ahora se invierte, dando F(x₀) = y₀. Este proceso se repite para x_1..n, dando como resultado y_1..n .El criterio SAC se cumple cuando la distancia de Hamming entre y e y_0…n  es, en promedio, n/2. Es decir, un cambio de entrada mínimo (un solo bit) se amplifica y produce un cambio de salida máximo (la mitad de los bits) en promedio.

 

La definición original es:

Considerando X y X_i, dos vectores de texto en claro binario de n bits, de manera que X y X_i se diferencian solo en el bit i, 1 < i < n. Supongamos que V_i= Y ⊕ Y_i donde Y = f (X), Yi = f (X_i),  f es la transformación criptográfica. Si f cumple con el estricto criterio de avalancha, la probabilidad de que cada bit en V_i sea igual a 1 debería ser la mitad del conjunto de todos los posibles vectores de texto plano X y X_i. Esto debería ser cierto para todos los valores de i.