Taller: Criptografía asimétrica.

[MasterPunk]

No hace falta que se los sepan, como vos decis "como la tabla de multiplicar", es simplemente para saber de qué estamos hablando y de tener una referencia. No les voy a tomar prueba jajajaj.
Lo que pasa es que uno no puede hablar x ejemplo de PKI, sin entender RSA y diffie-hellman.

Es decir, que la cosa se complica T_T

[APOKLIPTICO]

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.

[MasterPunk]

 
Te has olvidado de nosotros

¿Cómo vas con los estudios? Y lo que es más importante (para nosotros), ¿Como va el tema 3?

=)

[WestOn]

Te has olvidado de nosotros

¿Cómo vas con los estudios? Y lo que es más importante (para nosotros), ¿Como va el tema 3?

=)

¡Yo también quiero el tema 3! jaja

Saludos

[APOKLIPTICO]

Jajaja, está al 50%, hoy lo termino, acabo de llegar de la fiesta por el día de las madres y bueno, ahora me voy a poner a terminarlo jejeje.
Sorry por la tardanza...

[APOKLIPTICO]

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:

DSA (Digital Signature Algorithm).

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.

DSA (Digital Signature Algorithm, en español Algoritmo de Firma digital) es un estándar del Gobierno Federal de los Estados Unidos de América o FIPS para firmas digitales. Fue un Algoritmo propuesto por el Instituto Nacional de Normas y Tecnología de los Estados Unidos para su uso en su Estándar de Firma Digital(DSS), especificado en el FIPS 186. DSA se hizo público el 30 de agosto de 1991, este algoritmo como su nombre lo indica, sirve para firmar y no para cifrar información. Una desventaja de este algoritmo es que requiere mucho más tiempo de cómputo que RSA.

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

Hashes

En informática, hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.

Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo).

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

Criptografía Simétrica

La criptografía simétrica es un método criptográfico  en el cual se usa una misma clave para cifrar y descifrar mensajes. Las dos partes que se comunican han de ponerse de acuerdo de antemano sobre la clave a usar. Una vez ambas tienen acceso a esta clave, el remitente cifra un mensaje usándola, lo envía al destinatario, y éste lo descifra con la misma.

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.

Entropía es un concepto en termodinámica, mecánica estadística y teoría de la información. La entropía se concibe como una "medida del desorden" o la "peculiaridad de ciertas combinaciones". Como la entropía puede ser considerada una medida de la incertidumbre, y la información tiene que ver con cualquier proceso que permite acotar, reducir o eliminar la incertidumbre; resulta que el concepto de información y el de entropía están ampliamente relacionados entre sí, aunque se necesitaron años de desarrollo de la mecánica estadística y de la teoría de la información antes de que esto deviniera aparente.

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.

[bomba1990]

esta muy buena la tercera entrega, hay bastante para leer. despues hare las preguntas de lo que no entienda.

[soplo]

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.

[[D4N93R]]

Genial, Muy muy bueno!!!!!! Aún lo sigo leyendo y ando haciendo unas pruebas x)

EDIT:

Apok, toy haciendo una prueba de rendimiento con la pequeña prueba que tu hiciste en C:

Mira esto:
Calcular 31^100000000 mod 5200:

Código (cpp) [Seleccionar] Expandir


#include <iostream>
#include <ctime>
using namespace std;

int main()
{
   long startime = clock();
   long out = modpow(5200, 31, 100000000);
   cout <<  (float) (clock() - startime) / CLOCKS_PER_SEC;
}

long modpow(long modulus, long base, long exponent)
{
   long Output = 1;
   for(int i = 1; i <= exponent; i++)
   {
       Output = (Output * base)%modulus;
   }
   return Output;
}

Resultados:
C++: 4,391 Segundos.
VB: 58 hs, 20 minutos.

Relación: C++ es 47825 veces más rápido que VB.

PD: Y si uso OpenCL y calculo con la GPU, puedo calcularlo 100 veces más rápido. Esto es en C++.

Eso en C# me ha dado 1.9 segundos, qué equipo tienes tu?

[APOKLIPTICO]

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