Garantías de dureza para AES

14

Muchos criptosistemas de clave pública tienen algún tipo de seguridad demostrable. Por ejemplo, el criptosistema Rabin es probablemente tan difícil como factorizar.

Me pregunto si existe ese tipo de seguridad comprobable para los criptosistemas de clave secreta, como AES. Si no es así, ¿cuál es la evidencia de que romper tales criptosistemas es difícil? (aparte de la resistencia a los ataques de prueba y error)

Observación: estoy familiarizado con las operaciones AES (AddRoundKey, SubBytes, ShiftRows y MixColumns). Parece que la dureza de AES proviene de la operación MixColumns, que a su vez debe heredar su dificultad de algún problema difícil sobre Galois Fields (y, por lo tanto, el álgebra). De hecho, puedo volver a formular mi pregunta como: "¿Qué problema algebraico difícil garantiza la seguridad de AES?"

MS Dousti
fuente

Respuestas:

8

MIXCOLUMNS evita ataques que se centran en solo unos pocos cuadros S, porque la mezcla de las columnas requiere que todos los cuadros S participen en el cifrado. (Los diseñadores de Rijndael llamaron a esto una "estrategia de sendero amplio"). La razón por la cual el análisis de un S-box es difícil se debe al uso de la operación de inversión de campo finito. La inversión "suaviza" las tablas de distribución de las entradas de S-box, por lo que las entradas parecen (casi) uniformes, es decir, indistinguibles de una distribución aleatoria sin la clave. Es la combinación de las dos características lo que hace que Rijndael sea seguro contra ataques conocidos.

Como comentario aparte, el libro The Design of Rijndael es una muy buena lectura y analiza la teoría y la filosofía de la criptografía.

Aaron Sterling
fuente
1
Buena explicación. Gracias. De hecho, tuve acceso al libro, pero no sabía qué parte leer (con respecto a mi pregunta). ¿Sugieres algún capítulo o sección especial?
MS Dousti
3
Lo leí hace más de dos años, en una biblioteca, así que no tengo la tabla de contenido frente a mí, y no estoy seguro de poder dar una respuesta concreta a su pregunta, excepto que me gustó la forma diseñaron los S-boxes para que sean fácilmente implementables. Sin embargo, una cosa que puedo sugerir es la explicación de Stinson de AES y otras redes de sustitución-permutación en Criptografía: teoría y práctica. Es el Capítulo 3 de la edición que tengo, y parece que puedes descargar el libro gratis en este enlace: ebookee.com/…
Aaron Sterling el
1
Gracias por sugerir el libro de Stinson. ¿Podría también buscar la Tabla de contenido de El diseño de Rijndael y ver si recuerda algo útil?
MS Dousti
2
Gracias por el enlace! :-) Sí, la sección 3.6 y el capítulo 5 fueron muy interesantes para mí, porque discutieron "por qué", no solo "qué".
Aaron Sterling el
10

Como dijo David, no tenemos tales reducciones para AES. Sin embargo, esto no significa que Rabin o RSA cryptosystem sean más seguros que AES. De hecho, confiaría en la seguridad (al menos unidireccional, probablemente también pseudoaleatoria) de los cifrados de bloque como AES / DES, etc. (tal vez con un poco más de rondas que las utilizadas habitualmente) más que la suposición de que la factorización es difícil, precisamente porque no hay una estructura algebraica y, por lo tanto, es más difícil imaginar que habrá algún tipo de algoritmo innovador.

Se pueden construir cifrados de bloque directamente a partir de funciones unidireccionales, lo cual es una suposición mínima para gran parte de la criptografía, pero la construcción resultante será terriblemente ineficiente y, por lo tanto, no se utilizará.

Boaz Barak
fuente
Gracias Booz Creo que la construcción Luby-Rackoff es una que proporciona pseudoaleatoriedad demostrable basada en estructuras similares a DES, ¿verdad?
MS Dousti
3
si. Más exactamente, comienza con una función unidireccional, la convierte en un generador pseudoaleatorio usando Hastad, Impagliazzo, Luby, Levin, luego la convierte en una función pseudoaleatoria usando Goldreich, Goldwasser, Micali, luego de hecho usa Luby-Rackoff, conviértela una permutación pseudoaleatoria (es decir, bloque ci pher)
Boaz Barak
6

Dado que uno puede convertir cualquier esquema de cifrado de clave pública en un esquema de clave secreta de forma genérica, puede obtener esquemas de clave secreta con garantías de seguridad comprobables similares.

Pero esa respuesta es pedante: para el típico blockcipher desplegado no tenemos un análisis de seguridad demostrable en el sentido de reducción a problema computacional. Se han presentado propuestas para blockciphers con reducciones de seguridad, pero el equipaje computacional necesario para facilitar una reducción los hace poco competitivos con esquemas más eficientes como los algoritmos AES.

Curiosamente, la comunidad de seguridad comprobable generalmente ha acordado que es correcto tomar la seguridad de blockcipher (permutación pseudoaleatoria) como una suposición, y luego reducirla al analizar protocolos de nivel superior que emplean a blockcipher como componente. Es decir, a diferencia de otros desafíos en el diseño de protocolos seguros, parece suficiente confiar en la intuición de seguridad de los criptoanalistas cuando se trata de blockciphers.

David Cash
fuente