Taller: Criptografía asimétrica.

[WestOn]

Buenas, gracias por el tema IV, voy a leerle mas a fondo

probablemente debido a un error de overflow en el módulo

No importa, thx por el code.

Saludos

[MasterPunk]

...

Despues de leer unas cuantas veces el capútulo tres creo que ya estoy preparado para pasar al cuarto =) (y tiene bastante buena pinta  )

Voy un pelín atrasado, pero os observo desde el fondo y no os vais a escapar

[APOKLIPTICO]

Gente, voy corrigiendo los errores del código que voy viendo, y me voy a hacer una función de módulo que acepte números de cualquier tamaño (como strings).

[soplo]

Muy interesante je je je.

Respecto al test de Miller-Rabin lo tengo ya terminado, pero me estoy tomando un tiempo para asegurarme que está bien y no hay errores porque lo he hecho con gmp para números grandes y eso se sale del C estandar, es engorroso y lo ideal sería que la gente se lo pudiera pastear sin mas como una función. Por eso prefiero asegurarme no vaya a ser que en vez de ayudar lo joda todo je je je.

Respecto a los certificados me asalta una duda. Pongo la cosa tal como lo entiendo:

sistema asimétrico
Pongamos que A conecta la primera vez con B para establecer un canal seguro de comunicación. Si solo uso un sistema asimétrico el procedimiento es enviarle mi clave pública y que él me envíe la suya.

Cuando quiero A quiere enviar algún dato a B lo que hace es firmarlo con su clave pública y así solo lo podrá ver B. Igualmente si B quiere enviarme algo a A lo firmará con la clave pública de A y solo lo podrá ver A.

Man in the middle
El problema de esto tal como está expuesto es que un tercero C (de canalla) esté en el medio. Si A envía su clave pública a B la intercepta y en cambio envía la suya. B recibe una clave pública que cree que es de A pero no. Es de C.Cada vez que B firma algo con la clave pública de A en realidad lo  está haciendo con la de C y aunque cree que se lo envia a A en realidad se lo envía a C. Es decir, C se entera de todo.

certificados
La solución para evitar esto es que una tercera parte garantice que la clave pública de A es realmente de A. Para ello lo que hace es firmar la clave pública de A con su propia clave pública y así quien recibe una clave pública de A firmada por la entidad en la que se confía se tiene la seguridad de que esa clave pública es de quien dice ser. Si en esa situación el Canalla intentara lo mismo que antes no funcionaría porque la clave pública que envía a B no está firmada por la entidad de certificados. Esa es la razón por la que la entidad de certificados (CA) debe ser de toda confianza y si alguien consigue la clave privada de ese CA podrá firmar como si fuera ella y por tanto los certificados ya no serán seguros.

¿Es esto? ¿lo tengo bien entendido?

Tengo mas preguntas pero esperaré a ver si esto que he puesto está bien.

[APOKLIPTICO]

Cuando quiero A quiere enviar algún dato a B lo que hace es firmarlo con su clave pública y así solo lo podrá ver B. Igualmente si B quiere enviarme algo a A lo firmará con la clave pública de A y solo lo podrá ver A

Esto en realidad, está incorrecto, con las claves públicas, se cifra. Solo puede firmar una clave la CA.

El problema de esto tal como está expuesto es que un tercero C (de canalla) esté en el medio. Si A envía su clave pública a B la intercepta y en cambio envía la suya. B recibe una clave pública que cree que es de A pero no. Es de C.Cada vez que B firma algo con la clave pública de A en realidad lo  está haciendo con la de C y aunque cree que se lo envia a A en realidad se lo envía a C. Es decir, C se entera de todo.

En esto, lo mismo que te dije antes, con las claves públicas se cifra. Solo el CA firma claves.

La solución para evitar esto es que una tercera parte garantice que la clave pública de A es realmente de A. Para ello lo que hace es firmar la clave pública de A con su propia clave pública y así quien recibe una clave pública de A firmada por la entidad en la que se confía se tiene la seguridad de que esa clave pública es de quien dice ser. Si en esa situación el Canalla intentara lo mismo que antes no funcionaría porque la clave pública que envía a B no está firmada por la entidad de certificados. Esa es la razón por la que la entidad de certificados (CA) debe ser de toda confianza y si alguien consigue la clave privada de ese CA podrá firmar como si fuera ella y por tanto los certificados ya no serán seguros.

En realidad, la CA firma las claves con su clave privada, la clave pública del CA es el certificado de verificación, se utiliza para validar las claves.

Pero bueno, más o menos lo tenés claro.
Esperamos tu código de miller-rabin!.
Un abrazo
APOKLIPTICO

[raul338]

Wow... me voy un rato y ya postean tuto nuevo buenisimo, ya tengo para leer esta semana

[soplo]

Joer no se porque me ha dado por confundir cifrar que firmar je je je.

El código de Miller Rabin no funciona bien de momento. He metido un número que se que es primo y me dice que no lo es. Tengo que hacer algunas pruebas aún pero pienso que mañana estará ja ja ja

En cuanto a los certificados:

Existe la posibilidad de crear yo mi propio CA. Eso es razonable si no necesito interoperar con esos certificados fuera de mi dominio porque obviamente yo confío en mi mismo. El inconveniente de eso es que los demás no confian en mi.

La segunda opción es contratar a una empresa CA externa tal como verisign. El problema de eso es que ellos cobran y si necesito muchos certificados puede ser un problema presupuestario.

Hay varios tipos de certificados: los x509 creo que son aquellos en los que yo tengo mi propia CA pero hay otros.

Por otra parte esté la cuestión del formato de los certificados. El mas utilizado es el PEM y DER que se suelen usar para las claves privadas. Todo esto lo tengo muy confuso. De hecho creo que estos formatos se corresponden con marcas registradas y así el pkcs#12 es el que usa Microsoft, PEM en el mundo unix y DER. Entiendo que esto debe ser un problema porque habrá veces que hay que extraer la información de un DER para convertirlo a PEM o lo que sea.

Aquí un enlace sobre los PEM, DER y pkcs
http://publikaccion.blogspot.com/2007/05/tipos-de-formatos-de-certificados.html

Aquí hay una buena ayuda para openssl (aunque en ingles) que ayuda a ver las distintas opciones y posibilidades.
http://www.madboa.com/geek/openssl/

Aquí hay un resumen de los distintos formatos PKCS
http://es.wikipedia.org/wiki/PKCS

Esto si que es un lio. Dificilo no pero lioso si.

[APOKLIPTICO]

Capítulo V. Este capítulo fue escrito mientras se escuchaba: Foo Fighters (In your honor), Funkadelic (Maggot Brain).

Hola gente! Como va todo?
Bueno, estuve viendo un poco todo lo que es criptoanálisis, bueno es un área bastaaante extensa, pero vamos a tratar de cubrir lo más posible. Empecemos entonces!

Criptoanálisis.

Criptoanálisis (del griego kryptós, "escondido" y analýein, "desatar") es el estudio de los métodos para obtener el sentido de una información cifrada, sin acceso a la información secreta requerida para obtener este sentido normalmente. Típicamente, esto se traduce en conseguir la clave secreta. En el lenguaje no técnico, se conoce esta práctica como romper o forzar el código, aunque esta expresión tiene un significado específico dentro del argot técnico.

"Criptoanálisis" también se utiliza para referirse a cualquier intento de sortear la seguridad de otros tipos de algoritmos y protocolos criptográficos en general, y no solamente el cifrado. Sin embargo, el criptoanálisis suele excluir ataques que no tengan como objetivo primario los puntos débiles de la criptografía utilizada; por ejemplo, ataques a la seguridad que se basen en el soborno, la coerción física, el robo, el keylogging y demás, aunque estos tipos de ataques son un riesgo creciente para la seguridad informática, y se están haciendo gradualmente más efectivos que el criptoanálisis tradicional.

En resumen, el criptoanálisis estudia los algoritmos y los ciphertexts con el fin de encontrar posibles maneras de romper los cifrados o al menos de disminuir su complejidad, también se incluye el análisis de ciphertexts para conseguir el algoritmo de cifrado, en caso de que este se desconozca.

Hay distintos tipos de ataques, dependiendo en la cantidad de información que poseamos sobre el cifrado, es decir, si poseemos el algoritmo, poseemos el máximo de la información posible para el criptoanálisis, ya que con este, podemos hacer nuestros propios ciphertexts con claves que nosotros definamos. Sin embargo, hay un nivel mayor de información, que sucede cuando poseemos de antemano una vulnerabilidad del algoritmo, por ejemplo, dos ciphertexts idénticos originados en base a claves diferentes y plaintexts iguales, lo que significa que hay una colisión en el algoritmo.

Pero antes de empezar a definir los distintos criptoanálisis, vamos a explicar un concepto clave, el de la complejidad.

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

Esto quiere decir, la complejidad es una estimación de los recursos necesarios para determinada tarea. Por ejemplo, la complejidad de un algoritmo de fuerza bruta es exponencial, ya que esta aumenta de dicha manera a medida que aumenta la cantidad de caracteres.

Para definir la complejidad, se utiliza la notación Big "O" ó "Cota asintótica". La complejidad se puede definir en caso de que existan variables probabilísticas como "Cota superior asintótica", "Cota inferior asintótica" y "Cota ajustada asintótica" las cuales sirven para definir respectivamente los peores y mejores casos, y el promedio de casos de complejidad.
Volviendo al ejemplo anterior, la complejidad de un algoritmo de fuerza bruta, es O(C^n) C > 1.
Utilizando ahora como ejemplos los algoritmos de test de primalidad vistos en el capítulo anterior:
Ingenuo sin optimizaciones: O(n).
Ingenuo hasta sqrt(n): O(sqrt(n)).
Ingenuo probando solo primos hasta sqrt(n): O(sqrt(n) / ln(n)).
Miller-Rabin: O(a*log^3(n)). Siendo "a" la cantidad de iteraciones.
Fermat: O(log(n)).
Solovay-Strassen: O(log(n)).
AKS deterministic test: O(log^5(n)).

La complejidad de un algoritmo puede ser (en orden de los más eficientes a los menos eficientes).
Constante O(1).
Logarítmica O(log(n)).
Potencia fraccional O(n^c) 0 < c < 1.
Lineal O(log(n)).
Cuasi-Lineal O(n*log(n)).
Cuadrática O(n^2).
Polinómica O(n^c) c > 1.
Exponencial O(c^n) c > 1.
Factorial O(n!).

De esta manera, se pueden evaluar que tan feasibles son las rupturas de determinado algoritmo.
Fuentes:
http://es.wikipedia.org/wiki/Criptoan%C3%A1lisis
http://en.wikipedia.org/wiki/Computational_complexity_theory
http://es.wikipedia.org/wiki/Cota_superior_asint%C3%B3tica (Ver también artículo en inglés).

Tipos de criptoanálisis.

Ciphertext-only attack.
En este ataque se posee uno o más ciphertexts y se desea conseguir el plaintext o la clave de cifrado. Estos ataques se utilizan cuando no se poseen o no son necesarios los plaintexts para compararlo con el ciphertext. Un caso famoso es el criptoanálisis hecho a la máquina de cifrado "Enigma" utilizada en la segunda guerra mundial. Casos más recientes, incluyen el ataque al protocolo PPTP de microsoft, que utilizaba RC4 y el de WEP que también utiliza el mismo. Como sabemos, el algoritmo de generación de keystream del RC4 contiene fallas que generan colisiones, con suficiente keystream, se puede conseguir la clave y de esta manera conseguir el plaintext.
También cualquier ataque de fuerza bruta, se incluye en esta categoría.

Known-plaintext attack
En este caso, se posee uno o más ciphertexts y sus correspondientes plaintexts. Estos se pueden analizar con el fin de encontrar la clave de cifrado.
Históricamente, el algoritmo Vernam o XOR, es suceptible a este tipo de análisis, ya que si plaintext XOR clave = ciphertext, al ser XOR una operación reversible, ciphertext XOR plaintext = clave.
Algunas versiones del algoritmo de cifrado de ZIP también es suceptible a este tipo de ataques, reduciendo la complejidad del ataque a niveles casi constantes.

Chosen-plaintext attack
En este tipo de ataques, se posee la capacidad de cifrar cualquier plaintext y obtener los ciphertexts, pero no se posee la clave. Y tiene como fin obtener la misma. Este parece un caso poco realista, pero sin embargo, este ataque va a ser el más importante para nosotros, ya que si uno posee una clave pública de un cifrado asimétrico, posee la capacidad de cifrar, pero no de descifrar. Esto es lo que uno va a buscar.
Una variante del Chosen-plaintext attack, es el "Adaptive chosen-plaintext attack" en el cual se cifran determinados plaintexts y basado en la información obtenida, se continúa cifrando.

Chosen-ciphertext attack
En este caso, se posee la capacidad de elegir el ciphertext que se quiere descifrar y obtener su plaintext, pero sin poseer la clave de descifrado ni de cifrado (en caso de un algoritmo asimétrico). Y se pretende obtener las mismas.
ElGamal es un algoritmo que es débil contra este tipo de ataques y se debe modificar para que sea utilizable en estos contextos sin presentar un riesgo de seguridad.
También existe una variante Adaptive de este ataque. En el cual se descifran determinados ciphertexts y basado en la información obtenida, se continúa descifrando ciphertexts hasta obtener la clave.

Related-key Attack
En este ataque, se obtienen diversos ciphertexts cifrados con distintas claves, pero que estas claves tienen alguna relación matemática, por ejemplo que son acumulativas, son múltiplos entre sí o se conoce que una parte de la clave nunca cambia.
El criptoanálisis que se hizo con WEP, está basado en este tipo de ataques.

Ejemplos prácticos

Para más ejemplos prácticos: http://warzone.elhacker.net. Tiene muy buenos desafíos.

Ciphertext-only attack

Algoritmo: Sustitución simple.
Ciphertext:

Jw ahcitosjro jy cr grxaarswgpgxotao ro jyxjtoadjo, cxawazgdo stjucjrxjpjrxj igtg jw gwabao yarxopáxauo djw dowot dj ughjzg, dowot djrxgw, dowot pcyucwgt, powjyxagy dj wg pjryxtcguaor, dowot rjctowofauo dj ugtguxjt wjbj, yardtopj sjhtaw v dowot xtgy uatcfag. Xgphajr yj cyg igtg xtgxgt ucgdtoy arswgpgxotaoy, uopo woy ecj yj itjyjrxgr jr gtxtaxay, gtxtaxay tjcpgxoadj v gtxtaxay foxoyg.
Jy cygdo jr ougyaorjy igtg xtgxgt gurj, djhado g ycy itoiajdgdjy grxaarswgpgxotagy, v lg yado jnijrdadg jr Kgior jr sotpg xoiaug igtg gurj dj gdcwxoy.

Este es uno de los algoritmos de cifrado más simples, que constan en reemplazar con un patrón determinado cada letra por otra letra.
Por ejemplo, la "A" con una "T", la "D" con una "J", etc.
Primero, tenemos que determinar que clase de plaintext estamos tratando de conseguir. En este caso, vamos a asumir que es una oración en español. En un caso real y más complejo, se puede conseguir la información mirando la extensión del archivo, algún encabezado o header o buscando el origen de dicho ciphertext.

Para este ciphertext, vamos a utilizar un ataque conocido como "análisis de frecuencias" que se basa en la premisa de que en un determinado idioma, se utilizan algunas letras más que otras. En el español, estas vienen en este orden: "E A O S R N I D L C T U M P B G V Y Q H F Z J X W K". De la más frecuente a la menos frecuente.

Para esto, podemos utilizar esta herramienta, creada por un Spider-Net usuario de elhacker.net.
http://foro.elhacker.net/programacion_vb/source_the_golden_bug_analisis_de_frecuencia-t231056.0.html
Aunque también podemos utilizar cryptool.

Analizamos la frecuencia, y vemos que la "G" es la que tiene mayor frecuencia, seguida por J O T A X Y R D W C U P I S H F V B Z E K L N M Q. "M" y "Q" no aparecen en el texto, entonces las ponemos al final.
Reemplazamos las primeras 2 letras "JW", y nos queda "AC", parece ser "AL" entonces cambiamos todas las "W" por "L" en vez de "C".
Continuamos analizando las palabras más pequeñas, ya que son las más reconocibles. A medida que vayamos encontrando las sustituciones, vamos a poder ir descifrando cada vez más el texto.
Tengan en cuenta que es posible que sobre todo en textos pequeños, la correlacion de frecuencias no sea exacta. Cuanto más grande es el texto a descifrar, más fácil será hacerlo.
Se lo dejo a uds para que practiquen. Fíjense si lo pueden descifrar (por favor no posteen las soluciones).

Ahora, algo muy importante: Como hago para enseñarle a un programa a interpretar cuando ha conseguido el plaintext?.
Esto es algo muy importante, ya que uno puede fácilmente ver cuando una imagen, documento, texto o programa está correctamente descifrado, pero como hace un programa?
En caso de un texto cifrado, se puede analizar buscando palabras comunes. Si este es una imagen, se pueden buscar patrones que caracterizan a determinada imágenes. Pero sin embargo, uno puede ahorrarse todo esto buscando headers, estos son strings o caracteres que sirven para identificar que un determinado archivo es de determinado tipo. Por ejemplo, los ejecutables comienzan con "MZ" o "PE", los rar dicen "RAR" al inicio del archivo, y así sucesivamente.

Otro de los métodos utilizados para identificar un plaintext, es utilizando la entropía, como ya vimos, la entropía es un análisis del desorden, los algoritmos de cifrado y compresión buenos, suelen tener una salida de entropía casi máxima, sin importar los datos de entrada. Esto nos puede servir si estamos descifrando un texto, para identificarlo, ya que su entropía va a ser muy baja.


Known-plaintext attack

Algoritmo: XOR.
Ciphertext: "25 15 1C 0F 09 49 03 01 49 16 1C 0E 50 00 19 05 0E 19 1A 08 0F 4F 11 11 1D 0A
4C 05 11 54 0F 0C 1D 0C 11 0C 02 9F 07 50 11 07 43 1C 04 17 1A 19 05 0D 11 10
49 07 0A 41 05 01 0A 4C 0A 1F 19 19 02 9E 8C 11 43 4B 2F 1B 09 04 3D 0C 00 0D
50 07 0A 4C 0C 06 1B 05 16 0C 08 1F 01 0A 08 06 50 11 07 43 1A 0F 50 0B 0E 1F
1D 11 17 08 07 00 41 00 1D 04 15 0C 13 00 06 43 0B 04 50 0C 98 08 00 17 1B 49
02 0D 08 15 1D 1F 03 49 00 15 1B 02 4F 15 15 02 0A 1F 49 02 11 05 02 0C 08 1F
01 0A 08 06 03 54 0A 0C 01 41 1C 0E 4B 0F 1B 19 04 1D 0C 08 13 11 09 86 0D 47".

Está en hexa ya que si lo pongo en ascii, no van a poder ver muchos de los símbolos.

Ahora, imagínense que nos revelan la fuente del plaintext por alguna razón.
Plaintext: "Desde su uso original para la formación en seguridad de una compañía, CrypTool ha evolucionado en un destacado proyecto de código abierto para temas relacionados con la criptografía."

Entonces, sabemos que el algoritmo XOR, aplica un or exclusivo byte por byte de esta manera: si el plaintext es "computadora" y la clave "1234":
c o m p u t a d o r a
1 2 3 4 1 2 3 4 1 2 3

El XOR es reversible, osea que si m XOR k = c, entonces, c xor k = m.
Pero también significa que m XOR c = k. Es decir, que plaintext xor ciphertext = clave.
Sabiendo esto, podemos calcular la clave:
Vamos a hacer XOR byte a byte hasta que veamos que la clave empieza a repetirse.
25 15 1C 0F 09 49 03 01 49 03 01 49
44 65 73 64 65 20 73 75 20 75 73 6f
61 70 6f 6b 6c 69 70 74 69 63 6f  61

Entonces vemos que la clave es: "apokliptico".

Chosen-Plaintext Attack.

Realmente no se me pudo ocurrir un ejemplo simple para el Chosen-Plaintext attack, si alguien se le ocurre, por favor avíseme y lo posteamos.
Mientras tanto, para los que se atreven, un documento sobre el ataque Chosen-Plaintext al que fue vulnerable SSL en una de sus versiones:.

Chosen-Ciphertext Attack.

ElGamal es uno de los ejemplos más remarcables de Chosen-Ciphertext Attack.
http://es.wikipedia.org/wiki/Cifrado_ElGamal#Maleabilidad

Related Key Attack.

El ejemplo clásico de este ataque, es el de WEP, este algoritmo utiliza RC4 para generar su keystream, que luego se utilizará para cifrar los datos de la red inalámbrica. Sin embargo, este utiliza vectores de inicialización, es decir bits utilizados para evitar que si se cifra los mismos plaintext con la misma clave de como resultado el mismo ciphertext, demasiado pequeños, causando colisiones y que estos puedan llevar al crackeo de la clave.

Aquí hay una descripción completa de la vulnerabilidad del cifrado WEP.
http://foro.elhacker.net/hacking_wireless/vulnerabilidades_del_cifrado_wep-t54992.30.html



Bueno, aqui termina el Capítulo V, ya la próxima entrega, vamos a continuar con criptoanálisis, utilizando estadística básica, como la moda, la media, las frecuencias, etc.
Como siempre, las preguntas que tengan, posteenlas en este thread. Nos vemos!!
Cualquier error que se llegue a encontrar, por favor comunicarmelo por PM.
Un abrazo
APOKLIPTICO

Toda la información expuesta en este taller, está protegida bajo licencia Creative Commons Attribution-NonCommercial-ShareAlike 2.5.

[ShotgunLogic]

¿Puedo sugerir que los distintos capitulos se pongan en el post principal? Creo que facilitaria mucho la lectura y a tener una referencia.

Por lo demás el post esta genial, se agradece y mucho

Saludos!

[APOKLIPTICO]

Decis ponerlos en un post aparte?