...

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

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.

 

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

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!


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.


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).

---

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.

---

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

Ciphertext-only attack

Algoritmo: Sustitución simple.
Ciphertext: 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.

Decis ponerlos en un post aparte?