La criptografía no es tan segura como se creía

B

[Borrado] #1 Ago '13

Ando un poco escaso de tiempo, pero acabo de leer este artículo que a lo mejor os interesa.

Dejo el link aquí

Y el link al paper aquí

Y ahora resumo un poco:

El tema es que hasta ahora se utilizaba la entropía de Shannon para mirar la efectividad de un sistema criptográfico. Resumiendo y siendo muy poco riguroso, se observaba que en un caso promedio el sistema criptográfico funcionaba bien. Siendo un caso promedio ese en el cual los carácteres estaban distribuidos "uniformemente". Esto es muy útil en comunicaciones y compresión porque al fin y al cabo vas a tener muchos datos comunicandose o comprimiendose y se parecerán bastante a un caso promedio al cabo del tiempo.

Pero en criptografía no te interesa que en general haya una buena seguridad, sino que en el peor caso haya una buena seguridad. Es decir, si se utilizan definiciones de información y entropía que tengan más en cuenta los casos "poco probables" (peor caso, es decir que el atacante descubra una correlación entre el mensaje encriptado y sin encriptar que le sea útil por ejemplo), cambian todas estas nociones de seguridad.

No sólo eso sino que con estos "peores casos", el hecho de alejarse aunque sea un poco de una distribución uniforme (utilizar con más probabilidad ciertas letras que otras, que sea más probable cierto tipo de ruido que otro, por ejemplo), hace bajar mucho la seguridad de estos sistemas si no se mira con la entropía de Shannon.

El artículo acaba comentando que no convierte en totalmente inseguros los sistemas actuales, pero reduce drásticamente su complejidad (siguen siendo exponenciales). Lo chuli es que hay nuevas técnicas para analizar estos sistemas y nos permitirá entender un poco mejor qué significa seguridad :-)

Espero que os interese, si queréis alguna explicación más detallada de la entropía de Shannon y otros tipos de entropía y su relación con la información, intentaré responder lo mejor que pueda.

Saludos,

4

elkaoD #2 Ago '13

Alguien ha pillado un paper interesante y le ha colocado un título sensacionalista NUNCA hay que fiarse de los titulares de prensa. MIT PRESS I BLAME YOU.

Me he leído abstract, introducción y un poco por encima el resto, y lo que entiendo es que en realidad contradice algunos (escasos) papers, no "la criptografía" en general.

De hecho me parece un poco raro que se asuma una distribución uniforme, es la primera vez que lo he visto en lo (poco) que he leído de cripto. Por lo que he entendido, la uniformidad no se refiere a las claves (que tiran de PRNGs así que son en teoría uniformes) sino a los plaintexts. ¿Desde cuándo el plaintext es uniforme?

Entiendo que no habla de las claves porque precisamente es lo más conocido (véase el fiasco de Cryptocat y su bug en el PRNG que lo hacía no-uniforme) y por eso se usan PRNGs en la generación de claves.

En cualquier caso: la criptografía no es probablemente (como en "provably", con v) segura. Sólo confiamos en que las funciones de una dirección que usamos lo son, pero no hay ninguna prueba de ello, ¿no?

1 respuesta

B

[Borrado] #3 Ago '13

#2 bueno, el tema es que si usas entropía de Shannon estás haciendo la esperanza del logaritmo, así que miras casos promedios y el caso promedio no difiere mucho si el lenguaje es uniforme o no (hasta donde yo entiendo eso es lo que comentan). Si usas entropías que le den más fuerza a casos no tan probables entonces lo que supones como seguro ya no lo es tanto.

Lo que comenta en el paper es que cuando se estudia generalmente un sistema criptográfico asumes que el conjunto en el que trabajas es uniforme y supones que "si no lo es tampoco pasa gran cosa", aquí se comprueba que sí que cambian los resultados suponiendo que no es del todo uniforme. El título es sensacionalista sí pero ya ves el caso que se le hace igualmente xDDD, ahora en serio se lo dejé porque no me leí el paper xD. Ahora me lo estoy leyendo y es una crítica al procedimiento estándar de análisis de seguridad más que otra cosa, pero igualmente las conclusiones que saca son interesantes!

Y sobre tu pregunta, efectivamente el único sistema criptográfico que es demostrablemente seguro es el cifrado de Vernam, pero entonces tienes el problema de transmitir la clave xD. El resto sí, confiamos en que las funciones que sin la clave son de una dirección sean seguras. De todas formas esto también está un poco abierto a discusión siguiendo el tema del artículo de manera un tanto burda, decimos que es demostrablemente seguro porque dado el mensaje encriptado C, tenemos que para cualquier mensaje original M, P(M) = P(M|C). Para mí esto está claro que es seguro pero a lo mejor (yo creo que no) tenemos la definición mal xD.

2 respuestas

PandragoQ #4 Ago '13

#3 Y cual es exactamente el problema de transmitir una clave? Te coges la clave que usaste para Vernam (o puestos, para un algoritmo simetrico en condiciones), la encriptas con RSA o ECC y andando...

3 respuestas

Gnos1s #5 Ago '13

#4 Que es lo que se suele hacer ahora mismo:

Clave jodida para la firma, clave sencilla para la encriptación.

1 respuesta

B

[Borrado] #6 Ago '13

#4 que pierdes la demostrabilidad de la seguridad. En Vernam (supongo que ya lo sabes pero para los que no) tienes una clave tan larga como el mensaje y haces XOR bit a bit con el mensaje, así que lo mismo da probar claves hasta dar con la correcta que probar mensajes hasta dar con el correcto xD.

En cualquier otro método tener el mensaje codificado te da información y disminuye la entropía, incluso en métodos de clave privada como RSA, y por eso no es "provably secure". Piensa que hablo a nivel teórico, evidentemente y como dice #5 es lo que se hace, se encripta de forma asimétrica la clave simétrica porque la encriptación RSA es más costosa que un AES por ejemplo. Pero en todos estos métodos tener un mensaje codificado o incluso conocer la longitud de la clave reduce la entropía, porque si tienes un mensaje por ejemplo de 20000 bits y sabes que la clave es de 256, te resulta más "fácil" probar todas las claves que todos los mensajes y por tanto digamos que ganas información. Es una explicación un poco basta xDD pero supongo que se me entiende.

1 1 respuesta

elkaoD #7 Ago '13

#3 "Lo que comenta en el paper es que cuando se estudia generalmente un sistema criptográfico asumes que el conjunto en el que trabajas es uniforme"

A eso me refiero, nunca he visto que se asuma el conjunto del plaintext como uniforme (porque no lo es). Me parece más bien una metedura de pata de los papers que enlaza. Que está bien, oye, pero es un "rebuttal" a esos papers, no a la cripto en general.

#4 si transmites una clave usando cualquier otro algoritmo, estás reduciendo la complejidad a romper el segundo algoritmo así que pierdes la gracia de usar Vernam.

De ahí que siga siendo insegura (hasta que se demuestre lo contrario) la cripto, porque no hay forma de transmitir un one-time-pad por un canal inseguro y usar PK para transmitir el OTP hace que instantáneamente se reduzca la complejidad a romper el algoritmo de PK y no el OTP.

EDIT: justo #6 xD

1 respuesta

B

[Borrado] #8 Ago '13

#7 ah vale ya veo lo que quieres decir. En el paper se refieren estrictamente a la "Asymptotic Equipartition Property" que se usa junto al "typical set" es lo que se asume en el criptoanálisis actual para guessing supongo (edit: O los papers que enlaza como bien dices xD) y dicen que no se puede. No conozco los detalles de esta propiedad xD ni tampoco he trabajado con el "typical set" este, así que no te puedo decir mucho más de momento.

La criptografía no es tan segura como se creía

Usuarios habituales

Tags