Confusión y difusión

En criptografía, la confusión y la difusión son dos propiedades del funcionamiento de un cifrado seguro identificadas por Claude Shannon en su informe clasificado de 1945 Una teoría matemática de la criptografía. . Estas propiedades, cuando están presentes, trabajan juntas para frustrar la aplicación de estadísticas y otros métodos de criptoanálisis.

La confusión en un cifrado simétrico oscurece la correlación local entre la entrada (texto sin formato) y la salida (texto cifrado) al variar la aplicación de la clave a los datos, mientras que la difusión oculta las estadísticas del texto sin formato al distribuirlo en un área más grande de texto cifrado. Aunque los cifrados pueden ser de sólo confusión (cifrado de sustitución, libreta de un solo uso) o de sólo difusión (cifrado de transposición), cualquier cifrado "razonable" El cifrado en bloque utiliza tanto confusión como difusión. Estos conceptos también son importantes en el diseño de funciones hash criptográficas y generadores de números pseudoaleatorios, donde la descorrelación de los valores generados es la característica principal, la difusión (y su efecto de avalancha) también es aplicable a funciones hash no criptográficas.

Definición

Confusión

La confusión significa que cada dígito binario (bit) del texto cifrado debe depender de varias partes de la clave, oscureciendo las conexiones entre los dos.

La propiedad de confusión oculta la relación entre el texto cifrado y la clave.

Esta propiedad dificulta encontrar la clave en el texto cifrado y si se cambia un solo bit en una clave, el cálculo de la mayoría o de todos los bits en el texto cifrado se verá afectado.

La confusión aumenta la ambigüedad del texto cifrado y es utilizado tanto por cifrados de bloque como de flujo.

En las redes de sustitución-permutación, la confusión la proporcionan los cuadros de sustitución.

Difusión

Difusión significa que si cambiamos un solo bit del texto sin formato, entonces aproximadamente la mitad de los bits del texto cifrado deberían cambiar, y de manera similar, si cambiamos un bit del texto cifrado, entonces aproximadamente la mitad de los bits del texto sin formato deberían cambiar. Esto equivale a la expectativa de que los esquemas de cifrado exhiban un efecto de avalancha.

El propósito de la difusión es ocultar la relación estadística entre el texto cifrado y el texto plano. Por ejemplo, la difusión garantiza que cualquier patrón en el texto sin formato, como bits redundantes, no sea evidente en el texto cifrado. Los cifrados en bloque logran esto "difundiendo" la información sobre la estructura del texto sin formato en las filas y columnas del cifrado.

En las redes de sustitución-permutación, la difusión la proporcionan cajas de permutación (también conocidas como capa de permutación). A principios del siglo XXI apareció un consenso en el sentido de que los diseñadores preferían que la capa de permutación estuviera formada por funciones booleanas lineales, aunque también se pueden utilizar funciones no lineales.

Teoría

En las definiciones originales de Shannon, confusión se refiere a hacer que la relación entre el texto cifrado y la clave simétrica sea lo más compleja y complicada posible; difusión se refiere a disipar la estructura estadística del texto sin formato sobre la mayor parte del texto cifrado. Esta complejidad generalmente se implementa a través de una serie bien definida y repetible de sustituciones y permutaciones. La sustitución se refiere al reemplazo de ciertos componentes (generalmente bits) por otros componentes, siguiendo ciertas reglas. La permutación se refiere a la manipulación del orden de los bits según algún algoritmo. Para que sea eficaz, cualquier falta de uniformidad en los bits de texto sin formato debe redistribuirse en estructuras mucho más grandes del texto cifrado, lo que hace que esa falta de uniformidad sea mucho más difícil de detectar.

En particular, para una entrada elegida al azar, si se invierte el bit i, entonces la probabilidad de que el bit de salida j cambie debería ser de uno. la mitad, para cualquier i y j; esto se denomina criterio estricto de avalancha. De manera más general, se puede requerir que al invertir un conjunto fijo de bits se cambie cada bit de salida con una probabilidad de la mitad.

Uno de los objetivos de la confusión es hacer que sea muy difícil encontrar la clave, incluso si se tiene una gran cantidad de pares de texto sin formato y texto cifrado producidos con la misma clave. Por lo tanto, cada bit del texto cifrado debe depender de la clave completa y, de diferentes maneras, de diferentes bits de la clave. En particular, cambiar un bit de la clave debería cambiar el texto cifrado por completo.

Aplicaciones prácticas

El diseño de un cifrado de bloques moderno utiliza tanto la confusión como la difusión, con confusión al cambiar los datos entre la entrada y la salida aplicando una transformación no lineal dependiente de clave (los cálculos lineales son más fáciles de revertir y, por lo tanto, más fáciles de romper).

La confusión implica inevitablemente cierta difusión, por lo que un diseño con una caja S de entrada muy amplia puede proporcionar las propiedades de difusión necesarias, pero su implementación será muy costosa. Por lo tanto, los cifrados prácticos utilizan cajas S relativamente pequeñas, que operan en pequeños grupos de bits ("paquetes"). Por ejemplo, el diseño de AES tiene cajas S de 8 bits, Serpent de 4 bits, BaseKing y 3 vías de 3 bits. Las cajas S pequeñas casi no proporcionan difusión, por lo que los recursos se gastan en transformaciones de difusión más simples. Por ejemplo, la estrategia de sendero ancho popularizada por el diseño de Rijndael implica una transformación de mezcla lineal que proporciona una alta difusión, aunque las pruebas de seguridad no dependen de que la capa de difusión sea lineal.

Una de las estructuras ciféricas más investigadas utiliza la red de substitución-permutación (SPN) donde cada ronda incluye una capa de permutaciones locales no lineales (S-boxes) para confusión y una difusión lineal transformación (generalmente una multiplicación por una matriz sobre un campo finito). Los cíferos de bloques modernos siguen principalmente el modelo de capa de confusión/difusión, con la eficiencia de la capa de difusión estimada utilizando el denominado número de rama, un parámetro numérico que puede alcanzar el valor ${displaystyle s+1}$ para s paquetes de entrada para la transformación perfecta de la difusión. Puesto que las transformaciones que tienen altos números de rama (y por lo tanto requieren un montón de paquetes como insumos) son costosas en la implementación, la capa de difusión es a veces (por ejemplo, en la AES) compuesta de dos subcapas, "difusión local" que procesa subconjuntos de los paquetes en una forma de albañil (cada subconfiguración) y "despersión" que hace que los bits que fueron subconjuntos

Análisis de AES

El Estándar de cifrado avanzado (AES) tiene una excelente confusión y difusión. Sus tablas de búsqueda de confusión son muy no lineales y buenas para destruir patrones. Su etapa de difusión distribuye cada parte de la entrada a cada parte de la salida: cambiar un bit de entrada cambia en promedio la mitad de los bits de salida. Tanto la confusión como la difusión se repiten varias veces para cada entrada para aumentar la cantidad de codificación. La clave secreta se mezcla en cada etapa para que un atacante no pueda calcular previamente lo que hace el cifrado.

Nada de esto sucede cuando una simple codificación de una etapa se basa en una clave. Los patrones de entrada fluirían directamente hacia la salida. Podría parecer aleatorio a simple vista, pero el análisis encontraría patrones obvios y el cifrado podría romperse.