¿Cuál es el modelo matemático detrás de las afirmaciones de seguridad de los cifrados simétricos y los algoritmos de resumen?

No puedo darte una respuesta que te dejará perfectamente satisfecho, porque no hay tal respuesta. ¿Cómo sabemos que nuestros algoritmos son seguros? Estrictamente hablando, no lo hacemos. No tenemos ninguna prueba de que SHA256, AES o RSA estén seguros. Se cree que son seguros, pero no podría darle una prueba matemática de ese hecho, y quién sabe, siempre es posible que existan creencias generalizadas. mal.

Nuestra creencia en la seguridad de estos algoritmos proviene del hecho de que muchas personas realmente inteligentes y conocedoras se han esforzado por romper estos algoritmos, sin hacer una gran diferencia. Por supuesto, esto no es una garantía de que no exista un ataque inteligente; siempre es posible que haya un ataque abreviado matemático increíblemente astuto que nadie haya sido lo suficientemente inteligente como para encontrarlo, pero cuantas más personas intenten encontrar uno y fracasen, Menos probable que se vea. Por motivos prácticos, parece poco probable que un atacante de variedades de jardín descubra un ataque que docenas de personas realmente inteligentes trataron de encontrar y fallaron.

Tu reacción inmediata podría ser, ¿qué diablos? ¿Por qué esos criptógrafos son tan cojos? ¿Por qué no pueden probar que alguno de sus algoritmos es seguro? ¿Son entumecidos? La respuesta es que hay razones fundamentales que hacen que sea muy difícil probar que un algoritmo de cifrado o una función hash es seguro (excepto en casos especiales). En términos generales, probar que un algoritmo como AES o RSA o SHA256 es seguro parece ser al menos tan difícil como prueba de que P ! = NP (un problema infame en la informática). Tenemos muy pocas herramientas para demostrar que una tarea algorítmica no puede no completarse de manera eficiente. En esencia, esto es lo que hace que sea difícil demostrar que SAT no se puede resolver en tiempo polinomial (es decir, difícil de demostrar que P ! = NP ), y hace que sea difícil probar que no hay un ataque abreviado en AES (es decir, que AES no se puede romper). Entonces, no es solo que los criptógrafos sean cojos, es que estamos enfrentando problemas muy difíciles en los que nadie sabe cómo avanzar.

Tenga en cuenta que nada de lo que dije anteriormente es específico de las funciones hash o de la criptografía de clave simétrica. Se aplica a toda la criptografía de seguridad computacional, incluido el cifrado de clave simétrica, el cifrado de clave pública, las firmas digitales, las funciones hash y muchas otras primitivas estándar que damos por sentado.

Su última pregunta fue: ¿Puede alguien enseñarme la teoría de cómo se analizan y se analizan los algoritmos de clave simétrica? ¿Cómo los analizan los criptógrafos? ¿Cómo funcionan los ataques? No, no puedo enseñarte esto dentro de las limitaciones de tiempo y espacio aquí. Hay un campo de investigación completo construido alrededor de estas preguntas, con una literatura intelectualmente profunda sobre técnicas para el análisis de algoritmos de clave simétrica. (Consulte, por ejemplo, las conferencias FSE , CRYPTO y EUROCRYPT ). Se requieren años de estudio dedicado para aprender este material. Desafortunadamente, no puedo enseñarte todo eso en el espacio disponible aquí. La versión más corta es: los criptógrafos han desarrollado un gran conjunto de técnicas de ataque, y como punto de partida, cualquier primitiva nueva se analiza primero para ver si alguno de esos ataques funcionará. Si la primitiva resiste todas las técnicas de ataque conocidas, los criptógrafos pasan tiempo intentando diseñar ataques personalizados o personalizados contra la primitiva. Los criptógrafos también estudian versiones debilitadas artificialmente de la primitiva (por ejemplo, con menos rondas), para conocer los mejores ataques contra esas versiones debilitadas en un intento de extrapolar al máximo. Si después de muchos años-persona de esfuerzo, nadie tiene éxito en atacar el esquema, entonces la gente comienza a ganar más confianza. Más recientemente, también se han realizado investigaciones sobre la seguridad de que la estructura de alto nivel es sólida o que se garantiza que todos los ataques de una clase en particular fallarán, utilizando ideas de la comunidad de seguridad demostrable.

Pero al final del día, es un arte tanto como una ciencia. Revisar una nueva primitiva es extremadamente caro : requiere de décadas de esfuerzo por parte de especialistas con talento intenso. Por esta razón, los usuarios inteligentes de criptografía generalmente intentan usar primitivas existentes y examinadas, en lugar de inventar las suyas propias. Si inventas tu propio esquema, es extremadamente improbable que puedas organizar tanto análisis y verificación de tu propio esquema como los que ya han recibido los estándares, así que no hagas eso. No "ruedes tu propio". En su lugar, cree en primitivos existentes, estándar, aceptados, como AES, SHA256, RSA, etc.

@ D.W. lo dice bien en pocas palabras: la única forma conocida de considerar un algoritmo criptográfico es que cientos de criptógrafos lo mastiquen durante algunos años. En última instancia, esto no es satisfactorio, intelectualmente hablando, pero aún se puede trabajar con eso (toda la Medicina, por ejemplo, está construida sobre una base aún más inestable, pero sigue siendo un arte muy útil).

Para los detalles (es decir, cómo se elige una caja S, qué es el "efecto de avalancha", cómo estudiar cosas con álgebra ...), vea (como siempre) el Handbook of Applied Cryptography , que comienza a ser un poco antiguo pero sigue siendo una muy buena referencia y se puede descargar de forma gratuita. Otro buen libro es Criptoanálisis algorítmico de Antoine Joux.

  

Una de mis preguntas sigue sin resolverse. Todavía no sé por qué XOR, cambio de bits y similares se utilizan para hashes y cifrados en primer lugar: si hay algún razonamiento matemático detrás de esto, ¿por qué son exactamente estas operaciones y nada más?

Una de las razones por las que se usa exactamente XOR es que XOR tiene una propiedad importante: la reversibilidad. Si usted XOR un número con una clave y luego XOR el resultado con la misma clave nuevamente, obtendrá su número original.