Hola% username%!
Recientemente regresamos de la conferencia EuroCrypt 2019, donde conocimos a personas extremadamente inteligentes y al mismo tiempo aprendimos datos nuevos y extremadamente ofensivos sobre GOST SBox.
Entonces, este es el segundo enfoque del proyectil. Corregido y complementado.
Esta vez no habrá diapositivas rojo-azul incomprensibles, pero habrá documentos originales del comité ISO con explicaciones de los autores de Grasshopper.
¡E incluso el desafío al final!
Vamos
Primer programa educativo. En el artículo anterior no era, esta vez lo corrijo.
Ataque de texto sin formato elegido (CPA)
Comenzamos con el modelo de ataque básico en cifrados de bloque.
En este modelo, el atacante sabe todo sobre el sistema de cifrado, excepto la clave de cifrado. Puede crear cualquier texto sin formato, obtener los textos cifrados correspondientes y su tarea es calcular la clave, porque Esta es la única variable.
El cifrado de bloque en esta situación puede considerarse como una sustitución pseudoaleatoria. Una función que hace coincidir un bloque de texto sin formato con un bloque de texto cifrado de tal manera que es imposible determinar la relación entre ellos.
Un cifrado de bloque ideal se puede imaginar como una mesa grande, donde horizontalmente habrá todas las claves posibles de 000 ... 000 a 111 ... 111, verticalmente, todos los textos abiertos posibles también de 000 ... 000 a 111 ... 111 , y en el lugar de su intersección, textos cifrados generados aleatoriamente que asociarían de forma exclusiva un par de "texto sin formato clave". Crear una tabla de este tipo en la vida real no es posible debido a su tamaño, por lo que se emula utilizando varios algoritmos de cifrado de bloques.
El ataque al cifrado de bloque puede llamarse exitoso si podemos determinar la "aleatoriedad" con la que el algoritmo selecciona los cifrados que corresponden a los textos claros. Esta aleatoriedad permite en el peor de los casos calcular la clave de cifrado.
(No) linealidad
El proceso de cifrado en el cifrado de bloque puede representarse mediante una fórmula simple
C = M x K
donde C es texto cifrado, M es texto sin formato, K es la clave de cifrado y x es el cifrado de bloque.
Esta fórmula es visualmente similar a la fórmula escolar de la ecuación lineal y = kx + b, cuya gráfica es una línea recta.
Cualquier línea recta se puede restaurar en solo dos puntos. Y al mismo tiempo,
realmente no queremos que en dos pares de texto sin formato: texto cifrado, pueda restaurar la clave de cifrado. Para esto, se agregan capas especiales a los algoritmos de cifrado que son responsables de la
no linealidad. Estas capas están diseñadas para evitar la posibilidad de calcular la relación entre texto sin formato, texto cifrado y la clave.
Su calidad es crítica para la seguridad del algoritmo.¿Qué es SBox?
Esta es la misma capa no lineal. Una función que, en el caso de Grasshopper y algunas otras cifras, asigna de forma exclusiva un byte a otro byte.
Muy a menudo se establece mediante una tabla de correspondencia simple, por ejemplo esto:
Porque de lo contrario no se puede describir. A primera vista.
¿Por qué es importante SBox?
Porque es la
única función no lineal en todo el cifrado. Sin él, romper un cifrado no será fácil, sino muy simple, presentándolo como un sistema de ecuaciones lineales. Por lo tanto, la función de sustitución tiene tanta atención. Incluso hay ejercicios
prácticos para hackear AES con SBox lineal.
¿Por qué no puedes crear un SBox seguro?
El problema es que la criptografía no es una ciencia exacta. El único algoritmo de cifrado demostrablemente fuerte es una
plataforma de una sola vez . Todo lo demás son intentos tímidos para adaptarse al rango de conocimiento disponible para nosotros, cuyo conjunto no es tan bueno.
No sabemos con seguridad si RSA o AES o las curvas elípticas son resistentes, pero sabemos que tal y tal cosa
definitivamente no es posible . Todo en el medio es creatividad.
De ahí la constante paranoia sobre las diversas "constantes mágicas" y otros puntos que los autores de los algoritmos presentan como seguros, pero
no pueden probarlo .
¿Cómo crear SBox?
Las diversas variantes de SBox son 256 !, que es aproximadamente 2
1684 . La elección es grande y a lo largo de los años de criptoanálisis, se han desarrollado métricas y características que SBox debería tener, resistentes a los ataques conocidos de hoy. Por supuesto, los creadores de las tablas piensan en los años venideros e intentan crear sustituciones que sean resistentes incluso a los ataques inventados en 5-10 años. Pero esto es más de la categoría de magia y chamanismo.
Hay dos enfoques fundamentalmente diferentes para crear SBox.
El primero es una búsqueda aleatoria. Los desarrolladores generan tablas aleatorias, observan sus características y filtran las que no son adecuadas. Esto continúa hasta que los desarrolladores estén satisfechos con lo que han encontrado.
En el mundo civilizado, esto sucede, por ejemplo, de la siguiente manera:
- Se toma algún valor inicial, por ejemplo, una cita de un libro o los primeros dígitos de Pi
- Corre a través de un hash
- El resultado hash se usa como datos para formar el SBox.
- Si SBox no encaja, tome el hash actual y regrese al paso 2
Por lo tanto, cualquiera puede reproducir este proceso y asegurarse de que se cumplan al menos los requisitos mínimos para la búsqueda pseudoaleatoria.
¿Sabes a dónde van las semillas del algoritmo simétrico principal del país?
Perdido Pensé que no se los dijeron específicamente, el secreto está ahí o algo así, pero los colegas rusos en EuroCrypt dijeron que durante el desarrollo del algoritmo en 2007, por alguna razón, nadie pensó que sería necesario justificar el diseño de la tabla de búsqueda, y los valores de los que salió fueron para siempre perdido La historia es hermosa, solo no olvides que el algoritmo fue creado no en la escuela en un receso, sino en las entrañas del FSB.
La segunda forma es crear el SBox usted mismo, guiado por el aparato matemático disponible. Eso es
lo que hicieron
los autores de AES, y lo hicieron bastante bien. Si comparamos la no linealidad de SBox AES, SM4 (estándar chino) y Grasshopper (usa el mismo SBox que el hash Stribog), entonces el resultado no estará a favor de este último
No linealidad AES (min, max) = (112.0, 112.0)
SM4 no linealidad (min, max) = (112.0, 112.0)
No linealidad de Streebog (min, max) = (102.0, 110.0)
El código de cálculo de no linealidad utiliza la Transformación de Walsh y está disponible
aquí.Docs
Tengo dos documentos de ISO. En el
primero, los diseñadores de Grasshopper explican cómo crearon SBox, en
otro, el comité discute sus argumentos.
desde el primer documento nos interesan dos citas:
y
Espero que el tema con "Leo Perrin mismo haya tenido la idea de que los autores buscaron SBox al azar" ahora está cerrado.
De las explicaciones de los diseñadores se deduce que
- Realmente buscaron el SBox de forma pseudoaleatoria (dados los criterios de seguridad)
- Al parecer, no se colocó ninguna estructura oculta en ella.
Y en este lugar se equivocaron completamente.
¿Qué es una estructura?
Una estructura aplicada a una tabla de búsqueda es un algoritmo que describe esta tabla.
El documento mencionaba AES. Pero la tabla de búsqueda para AES se creó originalmente no mediante búsqueda aleatoria, sino con la ayuda de varias técnicas matemáticas que nos permitieron describir una capa no lineal con
varias fórmulas . Esto, por cierto, es la singularidad de AES.
Por el contrario, si está buscando SBox al azar, entonces no debería
haber tales estructuras y el problema con Grasshopper SBox es que las palabras de los diseñadores de algoritmos son muy diferentes de los hechos. Escribí sobre la estructura de un saltamontes llamado TKLog en un
artículo anterior , esta vez hablemos de las estructuras en general.
Complejidad de Kolmogorov
Este es el resultado de la investigación del
último artículo de Leo Perrin sobre Grasshopper.
El principal argumento en contra de los artículos sobre estructuras en Grasshopper SBox es que "en casi cualquier SBox puede encontrar alguna estructura si lo desea". Y "aunque la probabilidad de encontrar la estructura que Leo encontró es insignificante, si hubiera otro SBox, entonces habría otro, también con una probabilidad insignificante".
Digamos que esto es así. Pero Al final resultó que, es posible derivar un cierto "grado de estructuración" de SBox, que no depende de la probabilidad de caer en una u otra estructura.
¡Pero depende del tamaño del algoritmo que se necesita para generar este SBox!
Esto se llama la complejidad de Kolmogorov.
Si imagina SBox como una cadena de bytes, en el caso de una cadena aleatoria, no debería haber un algoritmo que genere esta cadena y al mismo tiempo sea más pequeña que esta cadena.
Para un saltamontes
Entonces, el tamaño de SBox es de 256 bytes. Aquí hay una versión legible del código de autoría de Leo Perrin, que implementa la tabla Grasshopper. En la entrada está el byte de origen, en la salida está el byte correspondiente del Grasshopper SBox. La condición principal para tal algoritmo es la prohibición del uso de estructuras de lenguaje o plataforma que reducen el tamaño del programa. Por ejemplo, si en algún lugar dentro de la biblioteca estándar hay una constante que contiene la mitad de SBox, entonces no puede usarla.
Desafío: escriba un programa que sea más pequeño que SBox.
unsigned char p(unsigned char x){
unsigned char
s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
if(x) {
unsigned char l=1, a=2;
while(a!=x) {
a=(a<<1)^(a>>7)*29;
l++;
}
if (l%17) return 252^k[l%17]^s[l/17];
else return 252^k[l/17];
}
else return 252;
}
, SBox «» , , SBox. 416 , .
, :
p(x){
unsigned char
*t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
a=2,l=0,b=17;
while(x && (l++,a^x)) a=2*a^a/128*29;
return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}
196 , 23% SBox. . , :
p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}
SBox :
int main() {
for(int i = 0; i < 256; i++){
if (i % 16 == 0){
printf("\n");
}
printf("%d, ", (unsigned char)p(i));
}
}
, SBox .
153 . — ANSI, 7 , 8. 1071 ~134 . , .
, Cortex-M4
80 ( ).
,
64 .
, ?
, , .
, 4 Sbox, SBox , .
.
, « » AES (
60 , GolfScript), .
— . , — .
— SBox. , . ,
.
( ),
, 4 , SBox. , — , . 4 , , , . , , , 11 , , . , side project ¯\_(ツ)_/¯.
ISO . . .
, , , SBox . . , , .
Curve25519 Daniel J. Bernstein Tanja Lange, ISO . , , , SBox. . .
, .
, . ISO, , EuroCrypt.
, ( SBox), RFC 7801, .
, SBox, (, ). , , , . V2 .
. , « , ».
, ? , AES - .
, , , , . .
Challenge!
SBox , , . , 256 .
. . — , .
—
58 Stax. « » SBox.
.