Sisi, se viene más jodido en las próximas entregas. Depende de como venga con el estudio, este finde es posible que ya salga.

¡Yo también quiero el tema 3! jaja

Saludos

Capítulo III. Este capítulo fue escrito mientras se escuchaba: Yes (The Ladder + Fragile + Union) y Genesis (Foxtrot + From Genesis to revelation + Nursery crime).

Continuamos entonces con lo dejado en el capítulo anterior, faltaba describir DSA, luego vamos a hacer un pequeño vistazo sobre hashes y algoritmos de cifrado simétricos, no tanto en profundidad como los asimétricos, pero suficiente como para que puedan entender la siguiente entrega (Public Key Infraestructure, Certificados y sistemas de autenticación).

Comenzemos entonces:
NOTA: Para los que no tienen ni idea de lo que es un hash, recomiendo que lean primero esa parte, y luego comenzar con DSA, ya que este tiene contenidos sobre hashes.


Como ven, estamos hablando de un algoritmo de firma digital, no de cifrado. Una firma digital, es una manera de comprobar que un archivo determinado está siendo enviado por la persona correcta. Es decir, evitar que un documento sea manipulado mientras se transmite por canales inseguros.

Generación de claves:
1) Se elige un algoritmo de Hash estándar, generalmente se suele usar SHA-1 o SHA-256, para más seguridad.
2) Se elige la longitud de la clave en bits, utilizando dos valores "L" y "N", siendo "L" un múltiplo de 64, generalmente por una cuestión de seguridad de más de 1024 bits, y "N" la longitud de la salida del Hash.
3) Se elige un número primo "q" de como máximo "N" bits de longitud.
4) Se elige un número primo "p" de como máximo "L" bits de longitud, que se utilizará como módulo. (p-1) debe ser múltiplo de "q".
5) Se calcula "g" de esta manera: g = h^((p-1) /q) mod p, siendo "h" un número arbitrario entre [2, p-1). Si esta fórmula da como resultado "1" se debe elegir otro "h". Generalmente por cuestiones de eficiencia se suele elegir h = 2.

Se publican "p" "q" y "g" a los demás usuarios del sistema, estos serán los parámetros que les permitirán a los demás usuarios calcular sus propias claves autenticadas:

1) Se elige "x" por un método suficientemente aleatorio tal que 0 < x < q.
2) Se calcula y = g^x mod p.
La clave pública será (p, q, g, y). La privada es "x".
Recordemos que la exponenciación modular es calculable utilizando la fórmula ya expuesta, y que no es necesario calcular primero la exponenciación y luego el módulo.

Firmando.
1) Ya se conoce la función hash utilizada "H".
2) Se genera un número aleatorio "k" creado para el mensaje tal que 0 < k < q. Se descarta este "k" una vez utilizado.
3) Se calcula r = (g^k mod p) mod q.
4) Se calcula s = (k^-1 * (H(m) + x*r)) mod q. Recordemos que H(m) es la función de hash aplicada al mensaje a firmar "m".
5) Se debe recalcular la firma en caso de que r = 0 o s = 0, a pesar de que dichos escenarios son bastante poco probables.

La firma digital será entonces (r, s).

Verificando la firma.
1) La firma será inválida si las condiciones "0 < r < q" y "0 < s < q" no son satisfechas.
2) Se calcula w = s^-1 mod q.
3) Se calcula u1 = (H(m) * w) mod q.
4) Se calcula u2 = (r*w) mod q.
5) Se calcula v = ((g^u1 * y^u2) mod p) mod q.

Aclaración: k^-1 mod q, representa el inverso multiplicativo de "k", que en este caso, no es solo 1/k.
k^-1 mod q se define tal que k^-1 * k mod q = 1.
Por ejemplo: k = 21 q = 100. k^-1 mod 100 = 81. Ya que 21 * 81 mod 100 = 1.
Se puede calcular tanto con fuerza bruta (lo que puede llevar mucho tiempo), como con el algoritmo de euclides extendido (el mismo que se utiliza para calcular el exponente privado de RSA).

La firma se valida si v = r.

Como ven, en este algoritmo la clave privada se utiliza para firmar, y la pública se utiliza para comprobar la firma. Los parámetros

Ejemplo:
Generamos una clave:
1) Elijo como algoritmo de Hash uno ficticio, por cuestiones de practicidad para el ejemplo.
2) Como longitud de claves en bits, elijo L = 64 y N = 8. Devuelta, para hacerlo práctico para el ejemplo.
3) Elijo un número primo "q" de hasta 8 bits. q = 97.
4) Elijo un número primo "p" de hasta 64 bits, que se utilizará como módulo tal que (p-1) es múltiplo de "q". p = 389. 388 = 97 * 4.
5) g = 2^((389-1)/97) mod 389 = 16.
Tenemos entonces los parámetros (389, 97, 16).

Ahora calculamos las claves:
1) Elegimos "x" = 25.
2) Calculamos y = 16^25 mod 389 = 142.
Clave pública = (389, 97, 16, 142).
Clave privada = 25.

Firmamos un mensaje:
1) Tenemos la función de hash ficticia con una salida de 8 bits. Supongamos que H(m) = 75.
2) Se genera un número aleatorio "k" = 66.
3) Se calcula r = (16^66 mod 389) mod 97 = 76.
4) Se calcula s = (66^-1 * (75 + 25*76)) mod 97 = 2 (66^-1 mod 97 = 25).
5) Se debe recalcular la firma en caso de que r = 0 o s = 0, a pesar de que dichos escenarios son bastante poco probables.
La firma entonces va a ser (76, 2).

Verificamos la firma.
1) 0 < 76 < 97 y 0 < 2 < 97.
2) Se calcula w = 2^-1 mod q = 49.
3) Se calcula u1 = (75 * 49) mod 97 = 86.
4) Se calcula u2 = (76*49) mod 97 = 38.
5) Se calcula v = ((16^86 * 142^38) mod 389) mod 97= 76.
6) r = v --> Firma verificada!.

Fuentes:
http://www.itl.nist.gov/fipspubs/fip186.htm
http://es.wikipedia.org/wiki/DSA

---

No se dejen confundir con la palabra "claves", esta no tiene nada que ver con las claves que se utilizan en criptografía para cifrar o descifrar datos. Probablemente la definición de wikipedia sea un poco confusa al principio, asi que vamos a hecharle un poco de claridad:

Tenemos un texto, documento o cualquier información, la llamaremos "m".
Tenemos también una función de hash o resumen, la llamaremos H().
Entonces:
Cuando se aplica H(m), se realizan un conjunto de operaciones matemáticas, que dan como resultado un resumen del mensaje original, que en un algoritmo real y seguro, debe tener las siguientes características:
- Determinado. Esto quiere decir, que dado un valor de entrada igual, la salida debe de ser igual, es decir:
Si se calcula H(m) = x
Y luego H(m) = y
Entonces x = y.
- Uniforme. Esto siginifica que la salida debe de ser lo más uniforme posible, es decir se debe utilizar todo el rango de salida de manera pareja y maximizando la entropía.
- Irreversible. Si se calcula H(m) = x, resultará infeasible calcular "m" teniendo "x". Esto se puede lograr utilizando funciones "trampa" como el módulo y los operadores binarios "AND" "OR" y "NOT".
- No relación entre tamaños de salida/entrada. Esto singifica que el tamaño de la salida no debe ser afectado por el tamaño de la entrada, ya sea que la entrada es muy pequeña, o muy grande, el tamaño de salida no debe de estar conectado con el de entrada.
- Tamaño máximo de salida fijo. Esto significa que cada algoritmo debe ajustarse a un tamaño de salida estandarizado, los valores no pueden superar este tamaño máximo. Por ejemplo, en MD5, el tamaño máximo es 128 bits.
- Eficiente. Se busca que el algoritmo de hash consuma la menor cantidad de recursos, sin perder seguridad.


Algoritmos de Hash más conocidos:
GOST             256 bits
HAS-160         160 bits
HAVAL            128 to 256 bits
MD2                    128 bits
MD4                    128 bits
MD5                    128 bits       
RadioGatún            Up to 1216 bits
RIPEMD-64            64 bits
RIPEMD-160    160 bits
RIPEMD-320    320 bits
SHA-1            160 bits
SHA-224            224 bits
SHA-256            256 bits
SHA-384            384 bits
SHA-512            512 bits
Skein            256, 512 or 1024 bits
Snefru            128 or 256 bits
Tiger                    192 bits
Whirlpool            512 bits
FSB                    160 to 512 bits
ECOH            224 to 512 bits
SWIFFT            512 bits

Colisiones de Hash.

Una colisión de Hash, es cuando la salida de un algoritmo de hash, es idéntica para dos mensajes diferentes, es decir:
H(m1) = x
H(m2) = y
x = y.
m1 <> m2.
Probabilísticamente hablando, es imposible crear una función de hash que tenga una salida diferente para cada mensaje, ya que el tamaño del valor de entrada puede ser [0, inf) y la salida, puede ser [0, Hmax] siendo Hmax el tamaño máximo de salida de un Hash. Sin embargo, se considera generalmente infeasible encontrar dos mensajes diferentes m1 y m2 tal que H(m1) = H(m2), debido a la regla de uniformidad y irreversibilidad, que asegura que la salida no va a tener ninguna correlación aparente con la entrada.
Calcular con fuerza bruta una colisión de hash, requiere muchísimos recursos, se ha logrado únicamente utilizando redes de cómputo.
Por ejemplo, MD5, tiene una salida de 128 bits, eso significa que hay 2^128 posibilidades distintas o 256^16.
Utilizando software de cracking que utiliza la GPU para crackear, yo puedo calcular 950 Millones de hashes por segundo, aún así, si quisiese calcular el espectro entero de md5, tardaría aproximadamente 11358 trillones de años en calcularlo.

Sin embargo, se han encontrado vulnerabilidades de hashes, que hacen que crear colisiones con ataques especializados sean no solo feasibles, sino extremadamente simples de lograr. Como ejemplo, el algoritmo de hashing md5, fue quebrado por Tao Xie y Dengguo Feng de tal manera que se puede calcular una colision en una fracción de segundo.

Por si les interesa crackear hashes con su GPU: http://foro.elhacker.net/criptografia/rompiendo_hashes_y_passwords_rar_con_la_gpu-t277060.0.html

Fuentes:
http://en.wikipedia.org/wiki/Hash_function (La versión en español no es muy buena).
http://es.wikipedia.org/wiki/Colisi%C3%B3n_%28hash%29
http://en.wikipedia.org/wiki/MD5

---

Como ya vimos en otras entregas, generalmente se suele utilizar la criptografía simétrica conjunta con la asimétrica, ya que la asimétrica provee un canal seguro para compartir la clave, pero no posee la eficiencia y velocidad de un algoritmo simétrico.

Ejemplos de algoritmos simétricos muy usados son:
Twofish 128, 192 o 256 bits.
Serpent 128, 192 o 256 bits
AES (Rijndael) 128, 192 o 256 bits
Blowfish 8–448 bits en múltiplos de 8 bits.
CAST5 40-128 bits.
RC4 40–2048 bits
TDES 168, 112 o 56 bits
IDEA 128 bits

Por qué utilizar criptografía simétrica?
- Mayor velocidad.
Si analizamos un cifrado asimétrico muy común como RSA con uno simétrico como AES, veremos que AES utiliza pocas operaciones y estas operaciones son generalmente lineales, es decir, se computan rápidamente. Las claves generadas para AES, se generan pseudoaleatoriamente y no deben tener ninguna característica especial.
Sin embargo, RSA utiliza bastantes operaciones que requieren exponenciación modular, que con exponentes grandes, necesitará miles de veces la cantidad de ciclos que se utilizan para una operación de AES. Por otro lado, la generación de claves para RSA requiere test de primalidad que requieren mucha capacidad de cómputo y esta aumenta de manera no lineal con el tamaño de las claves, es decir, calcular una clave de 2048 bits va a tardar mucho más que el doble que una de 1024 bits.

- Mayor seguridad con claves más pequeñas.
Debido a que se reducen las posibles claves con RSA debido a que los valores generadores son números primos, este requiere que sean mucho más grandes que si fuese una clave simétrica, que puede ser cualquier número.
Una clave de 1024 bits de un algoritmo asimétrico, da la misma seguridad que una clave de aproximadamente 80 bits de un algoritmo simétrico, una de 2048 bits asimétrica da la misma seguridad que una de 112 bits simétrica y una de 3072 bits es equivalente a una de 128 bits. Esto varía dependiendo de los cifrados involucrados.
Por otro lado, una clave de 256 bits simétrica, solo se iguala con una clave de 15360 bits asimétricos. Calcular una clave de tal tamaño, puede tardar muchisimo tiempo computacional.

- Poseen un riesgo mucho menor de ser rotos por la computación cuántica.
En este momento se están haciendo investigaciones sobre la siguiente era de la información, la computación cuántica, gracias al algoritmo de Shor, se podría factorizar una multiplicación de dos primos utilizando una de estas computadoras feasiblemente, dando por concluida la era de los algoritmos asimétricos actuales. En otras palabras, se tardaría el mismo tiempo en utlizar una clave asimétrica en una computadora normal, que crackearla en una computadora cuántica equivalente. Los algoritmos simétricos, reducirían su complejidad de crackeo a la mitad gracias a la computación cuántica, es decir que una clave de 128 bits, equivaldría a una de 64 bits en seguridad. Sin embargo, esto se puede solucionar duplicando el tamaño de las claves, a expensas de un tiempo de cómputo ligeramente mayor.
Esto quiere decir: Si van a guardar información cifrada por mucho tiempo, utilizen un algoritmo simétrico y claves muy grandes.

Fuentes:
http://en.wikipedia.org/wiki/Advanced_Encryption_Standard (Muy bueno).
http://www.mscs.dal.ca/~selinger/md5collision/
http://es.wikipedia.org/wiki/Criptograf%C3%ADa_sim%C3%A9trica
http://en.wikipedia.org/wiki/Key_size

---

Apéndice A: Entropía.

Vamos a explicarlo con un ejemplo práctico:
Tenemos un archivo, este archivo, puede contener cualquiera de los caracteres en el código ascii, cada uno representado por un número del 0 al 255.
Podemos entonces contar la cantidad de cada caracter en ese archivo, es decir la frecuencia.
Por ejemplo: "0" = 10, "1" = 3, "2" = 1, (...), "254" = 4, "255" = 0.
Una vez contados la cantidad de caracteres, calculamos las frecuencias relativas, es decir, xi/n, siendo "n" el tamaño del archivo en bytes. Por ejemplo: "0" = 0.025, "1" = 0.050, etc.
Una vez que hicimos todos esos cálculos, calculamos la entropía del archivo:

Entropia = sum(-xir[ i ] * log(xir[ i ], 2))
Siendo: xir[ i ] la frecuencia relativa de cada elemento "i", log(x,y) es el logaritmo de "x" base "y" y sum() es la sumatoria.

Esto va a dar un número entre 0 y 8. Este número, representa la entropía del archivo, siendo "0" sin entropía y "8" con entropía máxima, es decir que existe la misma cantidad de los 256 caracteres.
Los buenos algoritmos de compresión y de cifrado, dan como salida una entropía cercana a 8, sin importar la entropía de la entrada.
Este es el primer criterio que se utiliza para el criptoanálisis de un algoritmo, ya que si su entropía de salida es baja, se considera que no es lo suficientemente seguro.

Fuente:
http://es.wikipedia.org/wiki/Entrop%C3%ADa_%28informaci%C3%B3n%29

Les paso un código que hice: http://foro.elhacker.net/criptografia/calcular_entropia_de_un_archivo_en_c-t237720.0.html

---

Bueno, la siguiente entrega, vamos a tratar sistemas criptográficos como PKI, Certificados y sistemas de autenticación, vayan leyendo, posteen sus preguntas y como siempre, cuando no haya más preguntas, posteo la siguiente entrega.
Un abrazo
APOKLIPTICO

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

Como siempre muy interesante APOKLIPTICO. Mucho por leer y por madurar pero ahora mismo me asalta una duda

Actualmente pensamos en un plain text como una colección de caracteres ascii pero ¿qué pasa si el texto a cifrar por muy plain que sea está en unicode?

Porque ahí cada caracter es representado por un mínimo de dos códigos y en el caso de ideogramas chinos hasta cuatro según tengo entendido. Desde un punto de vista criptográfico da igual cifrar algo que tenga 8 bytes que algo que tenga 16 pero desde el punto de vista de la desencriptación no.

¿o es que tengo mal entendido el unicode?

Lo demás ya lo iré leyendo con calma que este es un tema que hay que tomar a pequeños sorbos.

 

Muy buena pregunta, Unicode como vos decis, utiliza más de 1 byte para representar un caracter. Sin embargo, desde un punto de vista criptográfico, ese caracter, se puede dividir en dos bytes, y así tratarlo.
Esto me da el pie para explicar la diferencia entre un block-cipher y un stream-cipher.
Verán, un block-cipher, divide el plaintext en bloques de una longitud determinada, de esta manera, se pueden tratar los archivos grandes y pequeños sin problemas.
Por otro lado, los stream-cipher, son algoritmos que cifran byte a byte, es el caso del rc4, que da un keystream que luego es utilizado para cifrar el plaintext utilizando XOR.

Un abrazo
APOKLIPTICO