El sistema RSA

El primer algoritmo de cifrado de clave pública (cifrado asimétrico) fue desarrollado por R. Merckley M. Hellman en 1977. Gracias al trabajo de los famosos analistas criptográficos Shamir, Zippel yHerlestman, se quedó obsoleto rápidamente.

En 1978 apareció el algoritmo de clave pública creado por Rivest, Shamir y Adelman (de aquí el nombre RSA). Este algoritmo todavía se usaba en 2002 para proteger los códigos de las armas nucleares de Estados Unidos y Rusia.

Cuando se envía un mensaje, el emisor busca la clave pública de cifrado del receptor y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.

Los mensajes enviados usando el algoritmo RSA se representan mediante números y el funcionamiento se basa en el producto de dos números primos grandes (mayores que 10100) elegidos al azar para conformar la clave de descifrado.

La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.

Ejemplo

  • El algoritmo RSA funciona de la siguiente manera:

Inicialmente es necesario generar aleatoriamente dos números primos grandes, a los que llamaremos p y q.

A continuación calcularemos n como producto de p y q: n = p * q

  • Se calcula fi: fi(n)=(p-1)(q-1)
  • Se calcula un número natural e de manera que MCD(e, fi(n))=1 , es decir e debe ser primo relativo de fi(n).
  • Es lo mismo que buscar un numero impar por el que dividir fi(n) que de cero como resto.
  • Mediante el algoritmo extendido de Euclides se calcula d: e.d mod fi(n)=1 Puede calcularse d=((Y*fi(n))+1)/e para Y=1,2,3,… hasta encontrar un d entero.
  • El par de números (e,n) son la clave pública.
  • El par de números (d,n) son la clave privada.
  • Cifrado: La función de cifrado es C = M^e mod n
  • Descifrado: La función de descifrado es M = C^d mod n

Ejemplo con números pequeños

  • Escogemos dos números primos, por ejemplo p=3 y q=11.
  • n = 3 * 11 = 33
  • fi(n) = (3-1) * (11-1) = 20
  • Buscamos e: 20/1=0, 20/3=6.67. e=3
  • Calculamos d como el inverso multiplicativo módulo z de e, por ejemplo, sustituyendo Y por 1,2,3,… hasta que se obtenga un valor entero en la expresión: d = ((Y * fi(n)) + 1) / e = ( Y * 20 + 1) / 3 = 21 / 3 = 7
  • e=3 y n=33 son la clave pública
  • d=7 y n=33 son la clave privada
  • Cifrado: Mensaje = 5, C = M^e mod n = 5^3 mod 33 = 26
  • Descifrado: M = C^d mod n = 26^7 mod 33 = 8031810176 mod 33 = 5

RSA y DSA

La diferencia entre ambos reside en los tiempos obtenidos para la generación, firmado y comprobación de las claves públicas. Usando este benchmark (podéis usar cualquier IDE con la última versión del JDK) se obtuvieron los siguientes tiempos:

Algoritmo Generación de llaves * 1(ms.) Firmado * 100 (ms.) Verificación*100(ms.)
RSA 512 544.61 915 160
RSA 1024 1120.46 4188 263
DSA 512 6.62 634 988
DSA 1024 17.87 1775 3397

El algoritmo DSA es más rápido para generar la firma que para verificarla, al contrario de lo que sucede con RSA. Por lo que para realizar la autentificación en nuestro servidor SSH usaremos este último.

Además, si comparamos el tamaño de las llaves generadas por ambos algoritmos, comprobaremos cómo las utilizadas por RSA son superiores a las de DSA.

  • Configuración del servidor

Comprobamos si el equipo donde tenemos instalado sshd tiene activada la versión 2 del protocolo SSH y que esté habilitada la opción para utilizar claves RSA. Para ello buscamos las siguientes directivas en el fichero /etc/ssh/sshd_config:

Protocol 2
RSAAuthentication yes
AuthorizedKeysFile .ssh/authorized_keys

  • Para cada usuario que vaya a conectarse, debe existir el directorio /home/usuario/.sshy en él el archivo authorized_keys. En caso de no ser así deberemos crearlo de forma manual y posteriormente iniciar el servidor.

cd ~
mkdir .ssh
touch .ssh/authorized_keys
sudo /etc/init.d/sshd start

  • Generación de los pares de claves RSA

Como antes comentamos, SSH nos permite generar indistintamente claves RSA o DSA (en nuestro caso usaremos la mencionada en primer lugar), creándose para ambas una clave pública y una clave privada.

Dichas claves, pueden generarse en el propio servidor, en el ordenador cliente, o en cualquier otra máquina.

Al final sólo la clave pública debe aparecer en el fichero .ssh/authorized_keys del servidor al que queremos conectarnos.

  • El usuario interesado en generar el par de claves usará ssh-keygen. En el proceso, se nos pedirá introducir un passphrase, lo que viene a ser una contraseña para poder generar unas claves más fuertes y seguras.

En nuestro caso, vamos a usarla y a explicar posteriormente como indicarle al sistema que sólo nos la pida una vez por sesión, y no cada vez que nos autentifiquemos en el sistema.

$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/sebas/.ssh/id_rsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/sebas/.ssh/id_rsa.
Your public key has been saved in /home/sebas/.ssh/id_rsa.pub.
The key fingerprint is:
63:de:92:6d:00:fa:d9:17:55:45:ce:bc:25:42:8b:4c sebas@TheWorkstation
The key’s randomart image is:
+–[ RSA 2048]—-+
| E . .oo|
| o o o + |
| . o + . =|
| . . . . .o|
| . S . . |
| . = * . |
| o = = |
| + |
| |
+—————–+

El anagrama que produce esta versión de ssh-keygen, se denomina randomart y se trata de una representación visual de la huella digital de nuestra clave, para que sea más legible para el ojo humano y para dispositivos ópticos.

Si lo deseas, puedes usar la herramienta visprint que a través de técnicas de fractales, te permitirá obtener otro tipo de randomart.

  • Instalación de clave pública y protección de la clave privada

Para validar todo este proceso es necesario colocar nuestra clave pública en el servidor donde tenemos pensado autentificarnos.

Existen varias posibilidades de hacerlo, una de ellas es por ejemplo hacer uso del siguiente comando (Cliente):

[usuario1@localhost usuario1]$ ssh usuario @host_remoto \’cat >> .ssh/authorized_keys’ < .ssh/id_dsa.pub

Con este comando añadimos directamente la clave al fichero authorized_keys del servidor remoto de forma automática, ahorrándonos así un poco de trabajo.

También podemos usar (Cliente):

$ ssh-copy-id usuario_remoto@host_remoto

  • Pero ya que estamos haciendo todo con paso firme y decidido, continuemos haciendo las cosas con buen pie. Así que vamos a usar el comando scp, que trae incluido OpenSSH para hacer una transacción de ficheros entre el cliente y el servidor remoto de la forma más segura posible. Así que usaremos la siguiente orden (Cliente)

$ cd ~/.ssh
$ scp id_rsa.pub usuario@host_remoto/

  • Recuerda que la clave pública debe ser incluída en el fichero ~/.ssh/authorized_keysde cada máquina donde queramos usar dicha autentificación.

Ahora que ya tenemos la clave pública en el servidor, falta añadirla al fichero authorized_keys de éste (algo que comentamos anteriormente que se podría conseguir de forma directa utilizando el primer comando) (Servidor).

$ cd ~/.ssh
$ cat id_rsa.pub >> authorized_keys
$ shred -v  –remove id_rsa.pub

SHA1

El SHA (Secure Hash Algorithm, Algoritmo de Hash Seguro) es una familia de funciones hash de cifrado publicadas por el Instituto Nacional de Estándares y Tecnología (NIST). La primera versión del algoritmo fue creada en 1993 con el nombre de SHA, aunque en la actualidad se la conoce como SHA-0 para evitar confusiones con las versiones posteriores. La segunda versión del sistema, publicada con el nombre de SHA-1, fue publicada dos años más tarde. Posteriormente se han publicado SHA-2 en 2001 (formada por diversas funciones: SHA-224, SHA-256, SHA-384, y SHA-512) y la más reciente, SHA-3, que fue seleccionada en una competición de funciones hash celebrada por el NIST en 2012.

El SHA-1 toma como entrada un mensaje de longitud máxima 264 bits (más de dos mil millones de Gigabytes) y produce como salida un resumen de 160 bits. Este número es mayor que el que se utilizaba en el algoritmo SHA original, 128 bits. Ya existen nuevas versiones de SHA que trabajan con resúmenes de 224,256,384 e incluso 512 bits.

Vulnerabilidades

Así, a priori, podemos establecer dos posibles vulnerabilidades de las funciones HASH:

  • Que sea posible realizar la operación:

h-1(b)=a

Habitualmente, a la operación de invertir la función HASH comprobando todas las posibilidades para los bits de salida se le llama ataque de fuerza bruta. Esto es lo que debe ser computacionalmente impracticable. Supondría aplicar la función HASH 2n veces hasta encontrar la coincidencia (n es el número de bits de salida de la función).

  • Que se hallen colisiones:

h(a)=b y h(c)=b, a distinto de c

 

Tipos de ataques

  • Ataque Tipo 1: El atacante es capaz de encontrar dos mensajes al azar que colisionan pero es incapaz de hacerlo de forma sistemática. Si es capaz de dar sólo con dos mensajes que provocan colisión, esta no es razón suficiente para tildar el algoritmo de ineficiente.
  • Ataque Tipo 2: El atacante es capaz de generar dos mensajes distintos de forma que sus HASH colisionen, pero sin saber a priori qué hash resultará. Es decir, el atacante no podría generar “queriendo” el HASH que necesite para fines maliciosos.
  • Ataque Tipo 3: El atacante es capaz de construir un mensaje sin sentido de forma que su HASH colisione con el de un mensaje con sentido. Si éste es el caso, el agente malicioso puede atacar algoritmos de encriptación asimétricos con firma digital, haciendo que se firmen mensajes sin sentido, y que el destinatario los acepte como fidedignos.
  • Ataque Tipo 4: El atacante es capaz de crear un segundo mensaje falso que tiene sentido y cuyo hash colisiona con el del mensaje verdadero. En este caso, el atacante puede actuar con total impunidad, puede falsificar certificados, firmar mensajes…El resultado sería desastroso.

Si aumentamos el número de bits de salida del algoritmo, el ataque de fuerza bruta será más impracticable y también lo será encontrar los mensajes que colisionen, pues teóricamente se cumple que para confiar en que podemos encontrar dos mensajes que colisionen no hay que realizar 2n operaciones, sino sólo 2n/2.

  • Realicemos algunos cálculos para realizar ataques de fuerza bruta:

Para una clave de 12 dígitos, escrita con un teclado con 97 caracteres (base 97), habría que realizar (esto no tiene nada que ver con los algoritmos de HASH):

9712 = 693.842.360.995.438.000.295.041 comprobaciones.

  • Trabajemos ahora con los ataques basados en búsqueda de colisiones:

Para el algoritmo SHA 1, cuya salida es de 160 bits:

280=1.208.925.819.614.629.174.706.176 operaciones.

SHA-1 ha sido examinado muy de cerca por la comunidad criptográfica pública, y no se ha encontrado ningún ataque efectivo. No obstante, en el año 2004, un número de ataques significativos fueron divulgados sobre funciones criptográficas de hash con una estructura similar a SHA-1; lo que ha planteado dudas sobre la seguridad a largo plazo de SHA-1.

MD5

En criptografía, MD5 (abreviatura de Message-Digest Algorithm 5, Algoritmo de Resumen del Mensaje 5) es un algoritmo de reducción criptográfico.

Este algoritmo fue desarrollado por Ronald Rivest en 1995 y está basado en dos algoritmos anteriores MD2 y MD4. Todos estos protocolos producen un número de 128 bits a partir de un texto de cualquier longitud.

MD4 fue desarrollado para mejorar el rendimiento de MD2 , sin embargo, varios problemas fueron detectados y en 1996 fueron publicados elementos que hacen hoy en día inservible el algoritmo. MD5 sustituyó a MD4 y aunque no tiene el rendimiento de su antecesor, hasta el momento no han sido publicados elementos que comprometan su integridad y funcionamiento.

MD5 comienza rellenando el mensaje a una longitud congruente en módulo 448 mod 512. Es decir la longitud del mensaje es 64 bits menos que un entero múltiplo de 512. El relleno consiste en un bit en 1 seguido por cuentos bits en 0 sean necesarios. La longitud original del mensaje es almacenada en los últimos 64 bits del relleno.

Codificación

La codificación del MD5 de 128 bits es representada típicamente como un número de 32 dígitos hexadecimal. El siguiente código de 28 bytes ASCII será tratado con MD5 y veremos su correspondiente hash de salida:

  • MD5(“Generando un MD5 de un texto”) = 5df9f63916ebf8528697b629022993e8

Un pequeño cambio en el texto (cambiar ‘5’ por ‘S’) produce una salida completamente diferente.

  • MD5(“Generando un MDS de un texto”) = e14a3ff5b5e67ede599cac94358e1028

Otro ejemplo serí­a la codificación de un campo vací­o:

MD5(“”) = d41d8cd98f00b204e9800998ecf8427e

Pasos

  1. Adición de bits de relleno.

El mensaje es rellenado con n bits, de tal manera que le falte a su longitud 64 bits para ser múltiplo de 512. El primer de los nbits es 1 y el resto son 0.

  1. Adición de la longitud.

La nueva longitud es una representación de 64 bits y es añadida en forma de dos palabras de 32 bits, en primer lugar se muestran los bits menos significativos. Si la longitud del mensaje es mayor que 264, se usan los 64 bits menos significativos.

  1. Inicializar cuatro bufferes, A,B,C y D, que son registros de 32 bits.

Inicializados con los sigs. valores

A: 01 23 45 67

B: 89 ab cd ef

C: fe dc ba 98

D: 76 54 32 10

  1. Procesar el mensaje en bloques de 16 bits (se tendra una entrada y salida de 32 bits).

F(X,Y,Z) = (X AND Y) OR ((NOT(X)) AND Z)

G(X,Y,Z) = (X AND Z) OR (Y AND (NOT(Z))

H(X,Y,Z) = X XOR Y XOR Z

I(X,Y,Z) = Y XOR (X OR (NOT(Z)))

Se usa una tabla de 64 elementos T[1 … 64] construida con la función seno, siendo Ti la parte entera de 294967296 * abs(sen(i)) (i en radianes).

Mensaje producido por A, B, C, D, empezando con los bits menos significativos de A y terminando con los más significativos de D. Independientemente de la longitud del mensaje, su tamaño será de 128 bits.