El futuro de la criptografía

[kub0x]

Hace tiempo que no escribo para este subforo, todavía queda gente interesada en la criptografía e intento participar en las conversaciones. Creo que es útil explicar un poquito para donde está llendo el estudio pues en unos años el que no se renueva ahorá tendrá que hacerlo.

En la década de los 70 se descubrió el concepto de PKC (criptografía de clave pública), destacando el algoritmo de intercambio de claves de Diffie-Hellman y el hecho por Merkle en acertijos o puzzles (está tecnica se sigue utilizado en protocolos de commitment). Más tarde vino RSA, DSA, ElGamal y un poquito más tarde las curvas elípticas. Hoy día entendemos bastante bien el problema del logaritmo discreto en grupos cíclicos, pues un generador de estos grupos tiene un periodo/orden que está estrechamente relacionado con la factorización del orden del grupo. Lo mismo sucede con los residuos cuadráticos, estos permiten la factorización.

Entonces logaritmo discreto y factorización son equivalentes. El problema de la factorización se ha estudiado bastante durante la historia, genios como Gauss, Euler, Fermat, Riemann... dedicaron tiempo a ello y en el s.XX con la llegada de las máquinas, muchos otros a destacar Pollard y Shor se han dedicado a ello también, desde la parte computacional, es decir, como optimizar una máquina para buscar factores de un número. Con la llegada del ordenador cuántico esta tarea es factible para los tamaño de claves utilizados hoy día. Si nosotros aumentasemos el tamaño de la clave el doble, entonces sería resistente. Es decir, un ordenador cuántico de 2048 qubit puede factorizar un semiprimo de 1024 bits utilizado en RSA, si utilizamos un entero de 2048 bit entonces necesitaremos 4096 qubit. No sabemos si en el futuro la capacidad de aumentar qubits es factible, pero vemos que aparentemente existe una relación del doble. Lo mismo pasaría con Diffie-Hellman y derivados.

Con las curvas elípticas sucede que son más veloces a la hora de computar por ser de 128-256 bit. Un ordenador cuántico necesitaria 6 veces más qubit es decir para una de 256 pues 1530 qubits. Vemos incluso que es más factible romper una curva que resolver la factorización.

Desde los 90 se propusieron nuevas variantes del concepto de clave pública, por ejemplo: la criptografía de clave pública no conmutativa, la criptografía de clave pública multivariada, lattices, curvas elípticas supersingulares, criptografía basada en código (code-based). De esta forma, se intenta crear nuevos protocolos y criptosistemas basados en problemas matemáticos existentes o no. Analizando la complejidad de reducir el problema a otro o bien de resolverlo directamente, podemos establecer si el criptosistema/protocolo es seguro y plantear su uso futuro. Suponemos que los anteriormente dichos son resistentes a ataques en ordenadores cuánticos porque no tenemos ninguna solución para ellos, o la que tenemos no es factible ni en un clásico ni en un cuántico.

Estos campos son muy jóvenes, cada vez reciben más atención por parte de la comunidad y empresas como Google, Amazon, Microsoft, CloudFlare, Apple y guvernamentales como la NSA están ya contribuyendo a la implementación de estos. Se espera que para el año 2023 y antes de la década del 2030 anden funcionando dentro del protocolo TLS como cipher suite. El problema que los tamaños de las claves públicas son bastante más grandes que los clásicos ECC, DH, RSA.. pero hoy día la tecnología es capaz de manejarlos rápidamente sin verse afectada, y ya no te digo en el futuro...

Una conclusión bastante aparente es que la información que está siendo intercambiada, la cual es generada por la inmensa mayoría de librerías criptográficas, será legible en un futuro relativamente cercano cuando la cuántica se torne realidad. Evidentemente, la información confidencial se trata de distinta forma, y con tamaños de clave pública que por el momento retrasarían los ataques en máquinas cuánticas, pero es cuestión de tiempo.

Entonces, todo apunta a una transición en la criptografía de clave pública, un plan renove que busca asegurar los tres principios básicos de cara al futuro: confidencialidad, integridad y autenticación.

Para acabar, guste o no, nuestra capacidad de romper y descifrar en criptografía depende enteramente de nuestra habilidad para entender los problemas matemáticos subyacentes. Es imposible crear o destruir sin conocer las herramientas que te lo permiten. Puede que la criptografía sea un campo incomprendido, marginado por la mayoría de instituciones de nuestro país, pero si no estamos a la vanguardia del cambio, será imposible entenderlo, e iremos aun más por detrás.

P.D: El tema va sobre el futuro de la crypto, no cabe mención para el espionaje, backdoors y criptoanálisis realizado de forma indiscriminada por ciertas entidades.

Saludos a todos.

[warcry.]

Enigma: un sofisticado sistema con 1.252.962.387.456 combinaciones

problemas matemáticos subyacentes.

Principio fundamental de la criptografia, y a la vez talón de aquiles, luego el futuro es el mismo que cuando existía la maquina enigma.

obviamente, para que haya una encriptacion y después una desencriptacion tiene que existir un resultado optimo al problema, y por tanto en los modelos matemáticos de criptografia se reduce al tiempo de procesar todas las opciones posibles contra el algoritmo de cifra.

PD: Se agradece leer algo fuera del offtopic

[ace99]

Hablando de enigma... Hay una película sobre enigma y Alan Turing muy interesante. Es bastante famosa, e imagino que la mayoría la conoceréis pero no está de más dejar un link al tráiler.

[youtube=640,360]
https://www.youtube.com/watch?v=694Gt_c4X7w
[/youtube]

El título es "The imitation game" y está protagonizada por Benedict Cumberbatch.

La podéis encontrar en diversas plataformas como por ejemplo Netflix.

Siento desviarme del tema.

Muchas gracias por leerme. Un saludo

[@XSStringManolo]

Pues enigma no fue de lo más eficaz en su día. Debido a que los Alemanes usaban una clave única cada día había días que los ingleses por probabilidad craqueaban la nueva clave bien tempranito y escuchaban todas las comunicaciones cifradas de los alemanes por el resto del día hasta que al día siguiente cambiaban la clave. Por no decir que todas las claves estaban en una libreta por lo que algún alemán podría vendérsela a los ingleses y descifrar las comunicaciones día sí y día también.
Aquí un artículo bastante extenso sobre el tema. http://home.bt.com/tech-gadgets/cracking-the-enigma-code-how-turings-bombe-turned-the-tide-of-wwii-11363990654704

[kub0x]

Es bien cierto que Enigma fue un rompecabezas para algunos. Pero hay que tener en cuenta que la matemática en el siglo XIX estaba bien avanzada en teoría de grupos y permutaciones. Enigma es reversible por el poseedor del diseño, la máquina y la configuración, es decir, eres capaz de descifrar con la clave o la configuración de la máquina Enigma, en este caso.

Siempre hago hincapié en la misma frase, pero no sabeís lo importante que es: "Todo criptosistema se puede escribir como un conjunto de ecuaciones lineales o multivariadas (sobre un campo/cuerpo finito)". En este caso, lo mismo sucedió con Enigma. El principio de Kerchoff nos dice que el atacante conoce el criptosistema, pero es seguro pues no tiene vulnerabilidades aparentes. Bueno, una vez los aliados se hicieron con unas cuantas máquinas, manuales y configuraciones, los criptólogos hicieron su trabajo:

In December 1932, the Bureau provided Rejewski with some German manuals and monthly keys. The material enabled Rejewski to achieve "one of the most important breakthroughs in cryptologic history"[46] by using the theory of permutations and groups to work out the Enigma scrambler wiring.[47][48]

Rejewski could look at a day's cipher traffic and solve for the permutations at the six sequential positions used to encipher the indicator. Since Rejewski had the cipher key for the day, he knew and could factor out the plugboard permutation. He assumed the keyboard permutation was the same as the commercial Enigma, so he factored that out. He knew the rotor order, the ring settings, and the starting position. He developed a set of equations that would allow him to solve for the rightmost rotor wiring assuming the two rotors to the left did not move.[49]

Vamos, que cuando quería recuperar el plaintext para otra configuración, sólo tenía que modificar el sistema de ecuaciones. Resulta que nosotros utilizamos teoría de grupos y permutaciones, entre otros, para hallar el recorrido de la trapdoor-permutation. De esta forma, por ejemplo, en el logaritmo discreto, podemos recuperar el exponente o clave privada. Existe un paper que publiqué el año pasado donde concluyo que el log discreto depende del degree o grado del grupo, el cual, es gigante por lo tanto mi método sólo vale para estudio y/o recreación. Pero es aplicable a cualquier cifrado, o estructura algebraíca cíclica, pues todo grupo es linearizable hacía un algebra lineal mediante la teoría de la representación.

Hoy día, todo esto es ampliamente tenido en cuenta, pues tu puedes hacer un cifrado "que te cagas" y tener una estructura de permitutación débil,  pudiendo recuperar el input. Os dejo esta pregunta que respondí en crypto.SE no hace mucho en la que ilustro una forma de encontrar el input de una función sin tener que hacer todo el recorrido, sino sólo trabajando en un ciclo:

https://crypto.stackexchange.com/questions/77970/if-you-iterate-a-cryptographic-permutation-long-enough-will-you-map-the-input-to/77976#77976

Saludos.

[kub0x]

Por ejemplo, si trabajamos con permutaciones en el grupo de enteros multiplicativos modulo 19 (primo), en vez de hacer g^x mod 19 vamos a hacer s^x donde s es una permutacion. ¿Pero cómo? Bueno, cada elemento de este grupo finito y cíclico es a su vez una permutación, por lo tanto este grupo es isomorfo (o equivalente) a un grupo de permutaciones. EN CRISTIANO vamos a intentar romper un ejemplo sencillo de Diffie-Hellman de una manera diferente aprovechando el tema de las permutaciones y teoría de grupos.

Si mi valor privado x=13 y g=2 (el generador, este grupo tiene 6 en concreto), entonces el valor público es 2^13 mod 19 = 3. Vale, vamos a buscar el exponente x sabiendo sólo el 3.

Alguien ajeno a la criptografía podría iterar desde 2 hasta 17, para determinar el valor, fuerza bruta con 16 posibles valores.
Alguien más avispado puede hacer uso de las simetrías del exponente y computar 8 posibles valores.
Un matemático podría aplicar el cálculo de índices (index calc) que es lo recomendable para módulos con bit size grandes.
Otro enfoque matemático es hacer el cálculo de permutaciones como os voy a mostrar (teorema de cayley en teoría de grupos. Todo grupo es representable mediante permutaciones si la accion G x G es faithful):

Empezamos sacando la tabla del 2 mod 19 : 2 4 6 8 10 12 14 16 18 1 3 5 7 9 11 13 15 17 (pares-impares no tiene misterio, multiplicar 2*i es hacer sumas de dos "i" veces)

De aquí sacamos el ciclo de permutación. Es una permutación porque los símbolos del 1 al 18 no se repiten en la secuencia. Dicho ciclo es:

(1,2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10) y se lee en 2^0 es 1, 2^1 es 2  2^ 2 es 4, 2^3 es 8 ... WOPS SI SON las exponenciales de 2^x mod 19. Y sólo haciendo sumas y sacando el ciclo, vemos como el valor público 3 está en la posicion 14, le restamos 1 porque empezamos por 2^0 si recordaís, entonces nos da 13, el valor x que buscabamos. Para sacar el ciclo (no me lo he inventado je je) debeís coger la permutacion que empieza por 2 4 6 8 ... y pensar, posición 1 está el 2, posición 2 el 4, en la 4 el 8, en la 8 la 16 etc y os sale el susodicho.

Podemos ir más allá, y sacar ciclos exponenciales como expliqué por aquí: https://crypto.stackexchange.com/questions/71258/what-can-be-said-about-the-self-power-map-on-groups-based-on-dlp

En ese post podemos ver que no hay que computar toda la permutación, y está garantizado que se recupera "x" pero su coste operacional debe estar por la raiz de la longitud media de un ciclo, cuya longitud depende del número de ciclos de la permutación (concepto contenido en random permutation statistics).

Saludos  

[Usuario887]

A los sistemas critpograficos lo que pinturas han hecho los pintores. A pesar de las limitaciones para con las herramientas que se utilizan para emular matematicamente lo que se imagina como una forma de transformar informacion, lo unico que permanece omnipotente es la imaginacion. Para mi el critpoanalisis es fundamentalmente lo mismo que observar una pintura hasta ver las manos del pintor, y seguira siendo asi hasta que pueda expresarse (de la misma forma) el azar en una ecuacion.

[B€T€B€]

No estoy muy puesto en la materia, pero lo que si se es que los ordenadores cuánticos lo único nuevo que aportan es una gran capacidad de cálculo.

Por un lado se podría intentar volver más complejo el cifrado; intentando dejar "no funcional" la capacidad de cálculo de los ordenadores cuánticos.

Otra opción sería tirar de imaginación (no me preguntéis cómo) volver inútil esa inmensa capacidad de cálculo.

[@XSStringManolo]

No estoy muy puesto en la materia, pero lo que si se es que los ordenadores cuánticos lo único nuevo que aportan es una gran capacidad de cálculo.

Por un lado se podría intentar volver más complejo el cifrado; intentando dejar "no funcional" la capacidad de cálculo de los ordenadores cuánticos.

Otra opción sería tirar de imaginación (no me preguntéis cómo) volver inútil esa inmensa capacidad de cálculo.

Si no sabes lo que tienes que encontrar da igual lo bueno que seas buscando no?
Cifrados por obscuridad. Ahora mismo son todo lo contrario al camina al seguir, pero si nos ponemos en el hipotético caso de super computadores...

[kub0x]

Vaya, si que va tomando forma el tema. Publicad lo que veaís conveniente, si conoceis alguna historia asociada a la criptografía o cualquier tema asociado, pues sed libres de comentar.

Por un lado se podría intentar volver más complejo el cifrado; intentando dejar "no funcional" la capacidad de cálculo de los ordenadores cuánticos.
Otra opción sería tirar de imaginación (no me preguntéis cómo) volver inútil esa inmensa capacidad de cálculo.

Por ahí van los tiros. Por ejemplo, esquemas basados en lattices se basan en el problema del vector más cercano (SVP), en cripto multivariada se basan en el MQ problem (multivariate quadratic polys) y el IP (Isomorphism of Polynomials). En las curvas supersingulares, tenemos el claw finding problem (el mejor ataque tiene coste operacional bajado a la raiz cuarta sobre el primo p, not bad).

Un ordenador cuántico no sabe interpretar estos problemas, al igual que el clásico, lo que se pretende para "romper" estos criptosistemas es puramente rebajar la seguridad unos bits, o bien, encontrar vulnerabilidades de DISEÑO. De aquí deducimos que un ordenador clásico y un cuántico están en las mismas condiciones, hasta que alguien consiga diseñar un circuito especial para estos problemas. Ya veremos lo que dicta el tiempo, probablemente esta década me toque estudiar física y computación cuántica para programar algoritmos.

Si no sabes lo que tienes que encontrar da igual lo bueno que seas buscando no?

Hay una frase para ilustrar esto: Cuando el ingenío se queda pequeño, no basta con poner empeño, sólo el talento consigue el diseño. Y lo que quiere decir, es da igual cuanto te esfuerces, sino eres creativo, jamás llegarás a tu meta. Teniendo ingenio + empeño, tampoco llegas a nada, necesitas el talento y eso son años de estudio en el ámbito de la criptografía. Los antiguos filósofos ya debetían sobre si el genio era talentoso o iba más alla. Buscad por docta ignorancia en YT.

Cifrados por obscuridad. Ahora mismo son todo lo contrario al camina al seguir, pero si nos ponemos en el hipotético caso de super computadores...

Como bien recalcas, ahora es todo lo contrario a la oscuridad. Es una de las normas del principio de Kerchoff: se conoce el diseño y la funcionalidad del criptosistema. Por lo tanto el atacante tiene todos los detalles, pero no tiene los valores privados, él ha de buscarlos. La oscuridad es un término neandertal que ya no vale en lo profesional. Puede valer para ciertas aplicaciones, pero en criptografía es considerado un pecado, así como implementar tu propia criptografía o implementar criptografía ya existente, en fin hay tantos pitfalls.

CONSEJO PERSONAL: Cuando empecé a intersarme por las matemáticas de la criptografía (año 2014), ví que me faltaba una base abrumadora, ya no sólo es teoría de números, sino de grupos, de cómputo operacional, de algebra combinatorial, lineal, algebra geométrica, teoría rep, simetrías, matemática discreta, finita, no lineal y a eso sumarle ser experto (o casi) en el manejo de Wolfram Mathematica y C++ para poder hacer tangible mi estudio. Tienes que estar al día con una decena de campos (matemáticos y el state of art en crypto), sino, te pasará lo mismo que a mí hace 5 años, harás criptoanálisis muy básico y "descubrirás" propiedades y métodos ya existentes en literatura. Por el momento, no he ganado un duro con esto y supongo que seguirá siendo así hasta que "yo lo pete", sin prisas.

Saludos.