2019/10/31

Threat Hunting: De presas a cazadores

Buenas a todos, en el post de hoy vamos hablaros de una actividad que cada vez va cobrando mayor relevancia en aquellas organizaciones que presentan un nivel de madurez alto en la capacidad de detección y respuesta, el Threat Hunting.


¿Que es el Threat Hunting?

El Threat Hunting es una actividad de defensa activa, basada en la búsqueda iterativa y proactiva a través de la red, con el fin de detectar y aislar amenazas avanzadas que están evadiendo las soluciones y controles de seguridad existentes.

Para esta actividad, nace la figura del Threat hunter, un analista de amenazas de ciberseguridad que utiliza métodos proactivos para descubrir incidentes de seguridad que no están siendo detectados.


Nivel de madurez

Antes de empezar a realizar cualquier campaña de Threat Hutning, hay que plantearse si nuestra organización esta preparada o no para realizar este tipo de actividades, y para ello, lo primero es determinar nuestro nivel de madurez.

El nivel de madurez vendrá definido por una serie de factores como son:
  • La cantidad y calidad de los datos que se recopilan de nuestra infraestructura TI.
  • De qué manera se pueden visualizar y analizar los diferentes tipos de datos recopilados.
  • Qué tipo de análisis automatizado se puede aplicar a los datos para mejorar la información que reciben los analistas


Ciclo de caza

El ciclo de caza, es el proceso mediante el cual vamos a poder realizar nuestras operaciones de cacería:

1.- Toda cacería comienza con la creación de una hipótesis sobre algún tipo de actividad que podría estar ocurriendo en la organización. Ejemplos:
    • Los usuarios que han viajado recientemente al extranjero tienen un riesgo elevado de ser objetivo de actores maliciosos patrocinados por el estado, por lo que pueden comenzar su búsqueda planeando buscar indicadores de compromiso en sus portátiles o asumiendo que sus cuentas han sido comprometidas para ser utilizadas en la red.
    • Búsqueda de movimientos laterales dentro de la red mediante técnicas de Pass the Hash (Método de autenticación sin necesidad de conocer la contraseña, solo se necesita el hash).
2.- En segundo lugar, las hipótesis se investigan a partir de diversas fuentes y técnicas:
    • Fuentes como:
      • Alertas de usuarios
      • Informes de amenazas externas e internas
      • Todo tipo de Logs: firewalls, IDS,  aplicaciones, proxies, bases de datos de malware, etc.
    • Técnicas como :
      • Búsqueda
      • Clustering
      • Grouping
      • Stack Counting

3.- Las herramientas y técnicas descubren nuevos patrones maliciosos de comportamiento y TTPs . Esta es una parte crítica del ciclo de caza. Un ejemplo de este proceso podría ser:
    • Una investigación previa reveló que una cuenta de usuario se estaba comportando de manera anómala, y que la cuenta generaba una gran de tráfico saliente. 
    • Después de realizar esta investigación, se descubre que la cuenta del usuario se vio comprometida inicialmente a través de un exploit dirigido a un proveedor de servicios externo de la organización.
    • Este TTP (compromiso inicial a través de un sistema de terceros a través de un tipo particular de malware) debe registrarse, compartirse (tanto interna como externamente) y rastrearse dentro del contexto de una campaña de ataque mayor. 
4.- Por último, las búsquedas exitosas forman la base para informar y enriquecer los análisis automatizados. Una vez que encuentre una técnica que funcione para encontrar amenazas, hay que automatizarla mediante su análisis para que su equipo pueda continuar concentrándose en la próxima nueva cacería. No hay que hacer perder el tiempo del equipo de hunting en realizar las mismas cacerías una y otra vez, por lo que en la optimización, está la clave.
    En próximos artículos iremos profundizando en este apasionante tema.

    Un saludo y happy hunting!!!!
    Leer más
        email this       edit

    2019/10/30

    Analizando dominios con Binaryedge.io

    Por Juan Antonio Calles el 2019/10/30 con 1 comentario
    Buenas a todos, en el post de hoy queríamos compartiros un servicio online muy interesante para el análisis de dominios, que se une a otros que ya os hemos presentado en Flu Project, como Onyphe, Censys o Shodan. Nos referimos a Binaryedge.io, una plataforma que según sus propietarios contaría con 1,1 PetaBytes de información en su base de datos.

    El servicio puede ser accedido desde el siguiente enlace:


    Tendréis que registraros y autenticaros, y una vez dentro, os encontraréis con un simple buscador, en el que podréis aplicar una serie de filtros básicos.

    En las siguientes capturas encontraréis una búsqueda en la que hemos solicitado los servidores web y BBDD alojados bajo microsoft.com:



    La versión gratuita incluye hasta 250 peticiones y acceso al API, lo cual puede ser más que suficiente para un uso moderado. A niveles profesionales, es recomendable adquirir alguna de las licencias de pago. Cuentan con 2 paquetes estandarizados para 5.000 peticiones (por $50/mes) y para 55.000 peticiones (por $500/mes), que además dan acceso a información histórica (lo cual es muy interesante) y a dataleaks que confirman tener.

    Yo ya la tengo en mi listado de marcadores del navegador :)

    Saludos!
    Leer más
        email this       edit

    2019/10/29

    Explotando BlueKeep con Metasploit

    Por el 2019/10/29 con 2 comentarios
    Muy buenas a todos!

    En este post nos vamos a centrar en cómo desplegar y ejecutar el módulo de Bluekeep desarrollado por zerosum0x0 que ha sido añadido recientemente en Metasploit. Aunque todavía no está desarrollado en su totalidad (se encuentra en pull request en GitHub aún), está en disposición de ser utilizado con unos ligeros retoques. En este caso, nuestros objetivo será una máquina Windows 2008 R2, obviamente, vulnerable a BlueKeep (CVE-2019-0708).

    Un poco de historia

    Pero antes de empezar lo divertido... ¿Qúe es Bluekeep? Según lo define el equipo de Microsoft, es una vulnerabilidad de ejecución de código remoto existente en el servicio de Escritorio Remoto. Esta funcionalidad puede ser explotada por un atacante sin autenticar mediante el envío de peticiones especialmente construidas. Si un atacante consiguiera explotar satisfactoriamente esta vulnerabilidad, tendría acceso a la máquina de la víctima como usuario NT Authority/System. 

    El 14 de Mayo de 2019, Microsoft lanzó varios KBs para solucionar esta vulnerabilidad en equipos Windows 7 SP1, Windows 2008 R2 SP1 y SP2 y Windows Vista respectivamente (KB4499175 y KB4499180).

    Montando el laboratorio

    Para realizar lo descrito en este post se ha utilizado:
    • Virtualbox 6.0.1 para crear la máquina virtual objetivo. 
    • Una VMWare de Kali Linux Rolling 2019.3 8 amd64 (descárgala aquí) con Metasploit en la versión 5.0.53-dev. IP: 192.168.1.4. 
    • Una VM con una imagen .iso de Windows Server 2008 R2 64 bit vulnerable (descárgala aquí). IP: 192.168.1.37 
    Para confirmar que el despliegue se ha realizado correctamente y que la máquina no presenta los parches antes citados, podemos ejecutar el comando systeminfo en una cmd/powershell. Como se observa en la siguiente imagen, la máquina W2008 tiene un único parche instalado (KB976902) por lo que, a priori, es vulnerable a BlueKeep.
    Fig 1: Salida del comando systeminfo
    El siguiente paso será habilitar el Escritorio Remoto ya que, por defecto, no viene activado.
    Fig 2: Habilitar RDP

    Fig 3: Permitiendo cualquier tipo de conexión


    Nota 1: En el despliegue de la máquina Windows, se ha realizado la instalación por defecto y no se han aplicado actualizaciones del sistema. 

    Nota 2: Docker en una Kali con arquitectura x86 me dio problemas para montar el contenedor, tuve que usar una com arquitectura x86_64.

    Seleccionando el módulo de BlueKeep

    Como hemos comentado antes, se ha usado una Kali Rolling 2019.3 con la última versión disponible de Metasploit (5.0.53-dev), la cual incluye el exploit de BlueKeep por defecto. Para actualizar a la última versión de Metasploit disponible, basta con usar el comando apt-get install metasploit-framework en la consola. Una vez terminado el proceso, bastará con lanzar el comando version dentro de Metasploit para confirmar cual se está ejecutando.
    Fig 4: Versión de Metasploit

    A continuación, mediante el comando use exploit/windows/rdp/cve_2019_0708_bluekeep_rce podemos seleccionarlo. Con show info podemos confirmar con exactitud que es el exploit deseado
    Fig 5: Información sobre el exploit

    Probando el exploit 

    De todas las opciones que se nos ofrece por pantalla para rellenar, sólo es necesario incluir el parámetro RHOSTS con la IP de la máquina destino (en nuestro caso 192.168.1.37) y seleccionar el TARGET correctamente. Como bien se indica en la página de Rapid 7, el módulo aún es manual, por lo que si no se modifica este valor, el exploit no funcionará. Al ser nuestro objetivo un Windows 2008 R2 corriendoVirtualbox 6, tendremos que seleccionar el TARGET 2. Como payload, usaremos una reverse tcp de meterpreter.
    Fig 6: Opciones selecionadas
    Si echamos un ojo a los comentarios del exploit (localizado en /usr/share/metasploit-framework/modules/exploits/windows/rdp/cve_2019_0708_bluekeep_rce.rb), para las versiones superiores a Windows 7, el registro HKLM\SYSTEM\CurrentControlSet\Control\TerminalServer\Winstations\RDP-Tcp\fDisableCam tiene que valer 0. Además, en los Windows Server 2008 R2 debe ser asignado manualmente.
    Fig 7: Cambiando el registro
    Si lanzamos el exploit tras cambiar el registro, observaremos que todo se ejecuta correctamente, sin embargo, la máquina Windows 2008 habrá sufrido un pantallazo azul.
    Fig 8: Fallo de paginación
    Nota: Puede ocurrir que el exploit se ejecute correctamente. Sin embargo, es recomendable seguir leyendo para garantizar una tasa de éxito más elevada.

    Ajustando Bluekeep

    El pantallazo azul indica un fallo de paginación del sistema, es decir, una pagína de memoria no ha sido asignada correctamente y el sistema no ha podido recuperarse. Para poder arreglar esta situación, es necesario modificar el valor GROOMBASE del script para que apunte al valor NPP (Non Paged Pool Area) de nuestra máquina virtual. Esto se debe a un comentario incluido en el interior de script:
    Fig 9: Explicación NPP obtenida del script
    O lo que es lo mismo, según que máquina virtual se esté usando, el inicio de la NPP puede encontrarse en un rango cercano al puntero incluido por defecto en GROOMBASE o, encontrarse a "kilómetros" de el, impidiendo que el exploit funcione correctamente (es por eso que ha veces funciona sin modificar y, otras veces, nunca genera una shell). La solución (a día de hoy) es bastante "sencilla"; basta con obtener el puntero NPP de nuestra máquina virtual y sustituirlo en el script. Para obtenerlo, es necesario realizar un volcado de memoria y emplear el plugin pools de Rekall.

    Realizando el volcado de memoria

    Para realizar el volcado de memoria, aprovecharemos el ejecutable VBoxmanage.exe incluido en los archivos de programa Virtualbox por defecto.
    • cmd> C:\Program Files\Oracle\VirtualBox>VBoxManage.exe debugvm "W2008 R2" dumpvmcore --filename="C:\Users\%USERNAME%\Desktop\files"
    Donde "W2008 R2" es el nombre asignado a la máquina Windows.
    Fig 10: Nombre de la  VM

    Obteniendo la dirección de NPP

    Primero, actualizamos docker (o instalaremos) en nuestra Kali mediante el comando apt-get install docker.io. A continuación, creamos un contenedor de Docker con Rekall, docker pull remnux/rekall

    lo levantamos con:
    • docker run --rm -it -v files:/home/nonroot/files remnux/rekall bash
    Por último, mediante el comando rekall -f files poolsobtenemos el valor de NPP.
    Fig 11: Valor de NPP
    Editando el script

    Una vez tenemos el valor de NPP de la máquina Windows 2008, sólo nos falta por editar el contenido del script y cambiar el valor de GROOMBASE por el nuevo. En nuestro caso, al ser una máquina virtual corriendo en VBox, cambiaremos el GROOMBASE del Target 2 (línea 128 del script).

    Nota: Rekall nos muestra la posición en memoria con una sola "f", debemos añadir el valor al script con todas las "f", si no, volverá a generarse un error al lanzar el exploit.
    • 0xfa8001802000 => 0xfffffa8001802000
    Fig 12: Cambiando GROOMBASE

    Lanzando el exploit definitivo

    Antes de lanzar el exploit, debemos volver a cargar el módulo en exploit. Existen varias maneras diferentes, ya sea usando el comando reload, el comando reload_all o, ante la duda, la vieja confiable, reiniciar Metasploit (esta es la mejor opción, así no hay dudas de que se cargan correctamente los cambios). Una vez dicho esto, si ejecutamos el exploit (con la misma configuración que antes)... la preciada shell aperece.
    Fig 13: System!

    Happy Juancking!


    Referencias
    1. https://pentest-tools.com/blog/bluekeep-exploit-metasploit/
    2. https://klaus.hohenpoelz.de/playing-with-the-bluekeep-metasploit-module.html

    Leer más
        email this       edit

    2019/10/28

    Analizando el mapa de los restaurantes madrileños inspeccionados en 2019

    Por Juan Antonio Calles el 2019/10/28 con 0 comentarios
    Buenas a todos, hace algunas semanas analizamos en Flu Project el Mapa de la renta de los españoles que fue publicado por el diario El País, y estuvimos sacando partido a la información contenida desde el punto de vista de Inteligencia. Pues bien, en esta ocasión le ha tocado el turno a los restaurantes de Madrid, ya que Maldito Dato ha accedido a la base de datos de inspecciones higiénico-sanitarias de los locales de restauración de Madrid y lo ha plasmado en un curioso mapa que ha sido lanzado desde Civio:


    Este mapa dará mucho que hablar, y seguro que ocasiona problemas a los hosteleros de la ciudad. Por ejemplo, os comparto a continuación un trozo del mapa referente a la zona de Arganzuela.



    Según relata la noticia, el 44% de los bares y restaurantes madrileños inspeccionados en 2019 presentó problemas de higiene, por lo que imaginaros el alto valor de la información contenida en este mapa para cualquier investigación que implique a uno de estos locales, socios e inversores, empleados y/o dueños.

    A continuación os compartimos el mapa, para que podáis analizarlo en detalle.




    Saludos!
    Leer más
        email this       edit

    2019/10/25

    Evadiendo cerraduras físicas con SEARAT

    Por Juan Antonio Calles el 2019/10/25 con 0 comentarios
    Buenas a todos, en el post de hoy quería hablaros de una herramienta que descubrí hace algunas semanas por Twitter, diseñada para abrir cerraduras de una forma muy curiosa. Se trata de la utilidad SEARAT, del fabricante Ignition USA:



    Estamos acostumbrados a las ganzúas, muchos de vosotros las manejaréis con soltura y las utilizaréis en vuestro día a día. Recuerdo durante la HoneyCON del año pasado, donde presentamos el reto del cofre pirata, que un asistente me comentaba que las ganzúas era un juego para la gente de nuestro sector. Sin embargo, la realidad puede sorprender a mucha gente, y nosotros (al igual que otras empresas imagino), hemos tenido que tirar de ellas durante algún Red Team, para emular actores maliciosos físicos y demostrar deficiencias en los controles de acceso a determinadas salas, CPDs, etc.

    Esta herramienta no deja de ser un gancho para abrir los resbalones de las puertas, pero su funcionamiento es genial para determinadas cerraduras más o menos sencillas, que requieran de una apertura rápida.

    Cómo una imagen vale más que mil palabras, y un vídeo más que cien mil, os comparto uno donde podréis ver SEARAT en funcionamiento:



    Saludos!
    Leer más
        email this       edit

    2019/10/24

    OpenLibra: una biblioteca online gratuita con numerosos recursos de desarrollo, sistemas, redes y seguridad

    Por Juan Antonio Calles el 2019/10/24 con 0 comentarios
    Buenas a todos, hace unos días, leyendo los blogs habituales vi una interesante publicación de maslinux.es, en la que hablaban de la biblioteca online OpenLibra,

    OpenLibra es un repositorio con cientos de libros, en PDF y que puedan ser descargados libremente. Se trata de una fuente de información muy interesante, en la que he encontrado tanto libros, como manuales de nuestro sector.


    Los libros son clasificados mediante un sistema de puntuación, y cuentan con una página dedicada con información referente al autor, contenido, tamaño, etc. Muy útil para hacernos una idea antes de comenzar su lectura.


    Sin duda un repositorio para tener siempre a mano en los bookmarks del navegador.

    Saludos!
    Leer más
        email this       edit

    2019/10/23

    Emails temporales para labores de Inteligencia

    Por Juan Antonio Calles el 2019/10/23 con 0 comentarios
    Buenas a todos, los emails temporales son un recurso muy útil que suele ser utilizado para registrarse en cualquier portal de Internet sin necesidad de utilizar nuestros emails reales, lo que nos evita acabar en miles de listas de spam, suscritos a cualquier newsletter o, lo que puede ser más importante, evitar dar datos reales que podrían ser utilizados para vincularnos a cualquier identidad en el futuro, o expuestos ante potenciales leaks por las escasas medidas de seguridad de las organizaciones que hospedan o gestionan dichos portales.

    Los beneficios son muchos, y el coste nulo, por lo que es una opción muy interesante que también utilizamos de forma habitual para labores de Inteligencia.

    Existen multitud de correos gratuitos por Internet "de usar y tirar", pero por facilitaros la tarea, os listaré algunos de los que suelo utilizar.



    Este servicio de correo me gusta mucho por 2 motivos, se destruye pronto pero permite aumentar el tiempo, por si tardase en llegarnos el email esperado, y además, permite recuperar el correo más adelante, conociendo únicamente el identificador aleatorio que nos fue asignado cuando entramos.




    Este servicio da algo más de tiempo, y permite además modificar parte del nombre del correo, por lo que podríamos personalizarlo para "adaptarnos" a nuestro objetivo. Sin embargo, en el dominio figura claramente que es una cuenta temporal. Por lo que es una opción válida para determinadas circunstancias.




    Este servicio no nos apabulla con tantos anuncios, y sus emails son bastante "creíbles" para pasar los filtros de algunos servicios online que obligan a no utilizar correos gratuitos (cuando se requieren emails profesionales). Se auto destruye a la hora exacta.




    Este servicio nos permite generar emails que duren hasta 2 semanas. Lo que puede ser útil para determinados "globos sonda" que no esperemos recibir a corto plazo :)

    Existen decenas de servicios similares en Internet y que podréis encontrar de forma sencilla en Google bajo búsquedas como "Temporary Email". De vez en cuando voy probando algunos nuevos, para ver que nuevas opciones nos aportan a los diferentes usos que les damos. Por lo que si conocéis alguno que sea diferencial, no dudéis en compartírnoslo y lo publicaremos en posteriores posts.

    Saludos!
    Leer más
        email this       edit

    2019/10/22

    UFED Cellebrite: una gran opción para los forenses de dispositivos móviles

    Por Juan Antonio Calles el 2019/10/22 con 0 comentarios
    Muy buenas a todos, los procesos de análisis forense digital de dispositivos móviles pueden convertirse en muchas ocasiones en verdaderas odiseas, debido a la gran variedad de marcas y modelos, sus importantes diferencias (aún teniendo el mismo sistema operativo base), y los requerimientos de root/jailbreak para poder acceder a ciertas partes del dispositivo (tal y como os hemos hablado largo y tendido en Flu Project). Por ello, recurrir a tecnologías que nos automaticen todo lo posible esta labor, es una necesidad, sobretodo para las empresas que todas las semanas necesitamos realizar algún forense a algún dispositivo móvil, o recuperar ciertos detalles de smartphones y tablets durante un pentest o Red Team. 

    Desde Zerolynx trabajamos con varias soluciones, y una de las que más nos gusta tirar es de UFED Cellebrite, del fabricante israelita Cellebrite Mobile Synchronization. Es una de las soluciones punteras del sector, junto a otras tecnologías propietarias como Oxygen Forensic, del fabricante Oxyen Forensics, dirigido bajo el paraguas de Oleg Federov y Oleg Davydov, y XRY, del fabricante sueco MSAB, y el que por cierto es uno de los más longevos, cuya compañía vio la luz hace 35 años. De todas estas soluciones os iremos hablando en posteriores artículos del blog.

    Cellebrite ofrece su producto estrella bajo distintas posibilidades, algunas más adaptadas a fuerzas y cuerpos de seguridad, y otras más adaptadas al sector privado. A nosotros, la opción que más interesante nos resulta es la 4PC, ya que puede ser instalada en cualquier ordenador. Por ejemplo, nosotros la tenemos en una máquina portátil muy potente, lo que nos permite clonar y analizar dispositivos en poco tiempo, y desde cualquier lugar, sin depender del hardware limitado ofrecido en las soluciones hardware. Esto también permite cambiar simplemente el portátil cuando se quede obsoleto, sin tener que adquirir de nuevo la solución (la cual por cierto, tiene también un coste de mantenimiento anual).

    La solución se compone de 3 partes principales (entre otras muchas), por una lado el software de extracción forense, por otro lado el de análisis (UFED Physical Analyzer) y por otro lado el de lectura (Cellebrite Reader), este último muy útil por si no tenemos el dongle para validar la License Key a mano, por ejemplo, cuando un compañero tiene que llevarse la clonadora a un forense, y en paralelo, otro compañero analizar otro móvil (ya clonado) desde el laboratorio.

    Uno de los PROs de este fabricante es la alta velocidad con la que sacan nuevas versiones y nuevos updates para la gran variedad de móviles que salen a la luz cada mes. También cabe destacar su sencillez de uso. Con una interfaz muy similar a la de Autopsy, nos permitirá acceder de forma rápida y sencilla a imágenes, mensajes de whatsapp, emails, contraseñas, y un largo etc. con unos pocos clics.

    A continuación, os he dejado algunas capturas de pantalla de los resultados obtenidos tras una extracción lógica de un iPad, para que podáis apreciar las capacidades de análisis de la solución:




    En estas capturas puede verse a la izquierda el árbol principal de elementos recuperados del dispositivo, y en la parte derecha, el detalle de los items seleccionados. Por ejemplo, os hemos dejado un par de capturas referentes al apartado de contraseñas y al historial de navegación.

    La suite completa de soluciones de Cellebrite puede ser adquirida en España desde el distribuidor OnRetrieval. Para los que nos seguís desde fuera de España, os recomendamos consultar directamente a su central, para que os deriven al partner local.

    También tienen un programa formativo muy completo, el cual podéis consultar desde el siguiente enlace: 


    Por nuestra parte, nos fue sencillo hacernos con el uso de las diferentes soluciones del fabricante, pero siempre es útil formarse con expertos y conocer detalles y trucos (que los tiene), para realizar tareas más rápidamente, o poder resolver problemas sin necesidad de llamar a soporte.

    En posteriores posts os presentaremos más detalles de este producto, y os hablaremos de las otras soluciones destacadas que existen en el mercado.

    Saludos!
    Leer más
        email this       edit

    2019/10/21

    Generación de claves RSA y selección de los números primos. Parte 3

    Por Juan Antonio Calles el 2019/10/21 con 0 comentarios

    De cara a finalizar el artículo, y con el objetivo de comprobar los contenidos previos, se debe tener en cuenta que todos los detalles descritos previamente a lo largo del presente artículo sobre los números p y q y las claves RSA pueden ser analizados y corroborados de forma práctica mediante la generación de un par de claves RSA, pública y privada, empleando OpenSSL [15] (los ejemplos hacen uso de macOS, pero los resultados serán muy similares en Windows o Linux). El siguiente comando permite la generación del par de claves RSA, pública y privada, de 2.048 bits mediante OpenSSL (sin proteger o cifrar el fichero resultante que contiene la clave privada):

    $ openssl genrsa -out privada.pem 2048
    Generating RSA private key, 2048 bit long modulus
    .......................................................................................................................+++
    .............+++
    e is 65537 (0x10001)
    $ ls -l
    -rw-r--r--  1 siles  staff  1679 Sep  1 00:00 privada.pem
    $ file privada.pem
    privada.pem: PEM RSA private key

    NOTA: Si se procede a la generación de claves RSA de mayor tamaño, por ejemplo de 8.192 bits, se apreciará cómo el tiempo medio necesario para encontrar los números primos p y q aumenta significativamente (por ejemplo, de 0,14s a 14s), y cómo el número de iteraciones de los test de primalidad disminuye (ver FIPS 186-4).

    Los signos, o símbolos, asociados al carácter "." y "+" que se muestran durante la generación de la clave indican el progreso en la selección de los números primos p y q. Tal como indica la página del manual (man) del comando genrsa de OpenSSL , el "." indica cada número candidato que ha pasado una criba inicial como posible número primo, y el "+" indica que el número candidato ha pasado una iteración del test de primalidad de Miller-Rabin. Un carácter de nueva línea indica que el número ha pasado todos los tests de primalidad. En base a estos detalles, parece que en la versión de OpenSSL empleada en los ejemplos con macOS Mojave 10.14.x (LibreSSL19 2.6.520), únicamente se llevan a cabo 3 iteraciones del test de primalidad de Miller-Rabin para cada número primo p y q cuando estos son de 1.024 bits (a diferencia de las 5 iteraciones esperadas según el código fuente de OpenSSL, tal como se detalla posteriormente).

    Si en su lugar se hace uso de la versión de OpenSSL disponible en Linux, por ejemplo 1.1.0h, es posible corroborar que se llevan a cabo las 5 iteraciones del test de primalidad de Miller-Rabin esperadas (indicadas en la salida del siguiente comando por los 5 signos "+"):
    $ openssl genrsa -out privada.pem 2048
    Generating RSA private key, 2048 bit long modulus
    ...+++++
    ...+++++
    e is 65537 (0x010001)
    Si se inspecciona el fichero "privada.pem" generado, es posible identificar que contiene una clave RSA privada (en formato base64) mediante el texto "-----BEGIN RSA PRIVATE KEY-----":
    $ cat privada.pem
    -----BEGIN RSA PRIVATE KEY-----
    MIIEpAIBAAKCAQEAtxNesQq1i5i/4BBWWe5JBc02+E6GaRLeVbSaYS3+OKWzPCKb
    ...
    zTIN1f91C1/t2/rYQGWEumCqKnq/UIQTLVeOOg0+wcolnHLMoeVGKg==
    -----END RSA PRIVATE KEY-----
    El siguiente comando de OpenSSL permite obtener una versión en formato texto de la clave privada RSA generada, con todos los parámetros asociados:
    $ openssl rsa -in privada.pem -text -out privada.txt
    writing RSA key
    $ ls -l
    -rw-r--r--  1 siles  staff  1679 Sep  1 00:00 privada.pem
    -rw-r--r--  1 siles  staff  5681 Sep  1 00:01 privada.txt
    $ cat privada.txt
    Private-Key: (2048 bit)
    modulus:
        00:b7:13:5e:b1:0a:b5:8b:98:bf:e0:10:56:59:ee:
        <… +15 líneas …>
        39:00:4b:4a:65:3f:90:13:f3:11:2a:ce:48:61:f8:
        77:6b
    publicExponent: 65537 (0x10001)
    privateExponent:
        00:99:86:bd:de:fc:1b:18:b1:05:1f:72:b3:e7:80:
        <… +15 líneas …>
        5e:cf:6b:7e:11:7c:9d:ca:56:e2:6b:16:17:35:13:
        ca:31
    prime1:
        00:df:bb:4c:7b:56:b1:71:9b:c8:10:9f:a8:65:8b:
        <… +6 líneas …>
        ab:15:56:ab:b5:af:8f:65:ef:63:bc:6a:a9:7b:82:
        26:ac:71:79:a1:71:aa:63:a9
    prime2:
        00:d1:7a:f4:da:fb:74:c1:1b:19:df:7d:cc:07:d1:
        <… +6 líneas …>
        c1:9d:ee:57:2f:22:9c:67:8f:59:82:bf:9b:9f:41:
        ee:fd:5b:a6:a1:c0:e7:ae:f3
    exponent1:
        00:86:97:05:26:79:7b:9b:8d:8c:68:3b:b3:b1:0a:
        <… +6 líneas …>
        5d:9c:23:9c:7e:5a:d3:98:0d:cf:e0:ec:05:72:f0:
        53:d5:8f:1a:0d:7d:f4:73:a9
    exponent2:
        0a:ec:d8:bc:5b:04:f9:d5:4a:02:27:f3:6e:2c:f0:
        <… +6 líneas …>
        92:b0:0d:87:fd:cc:1e:72:91:7e:8a:33:b9:98:9c:
        b8:46:01:68:ca:40:cb:15
    coefficient:
        23:d5:3c:97:e5:8b:34:0f:4c:51:6e:b9:12:72:3c:
        <… +6 líneas …>
        aa:2a:7a:bf:50:84:13:2d:57:8e:3a:0d:3e:c1:ca:
        25:9c:72:cc:a1:e5:46:2a
    -----BEGIN RSA PRIVATE KEY-----
    MIIEpAIBAAKCAQEAtxNesQq1i5i/4BBWWe5JBc02+E6GaRLeVbSaYS3+OKWzPCKb
    ...
    zTIN1f91C1/t2/rYQGWEumCqKnq/UIQTLVeOOg0+wcolnHLMoeVGKg==
    -----END RSA PRIVATE KEY----- 

    NOTA: Los valores se muestran empleando 15 pares de caracteres hexadecimales (o 15 bytes) por cada fila.

    Se puede ver como las claves RSA generadas por OpenSSL hacen uso del número 4 de Fermat para la clave pública e = 65.537 (0x10001), tanto en el proceso de generación de las claves, como al inspeccionar sus detalles.

    Los detalles en formato texto de la clave privada permiten obtener el tamaño de la clave privada, 2.048 bits, junto al módulo n (modulus, compuesto por 257 bytes o 2.056 bits), los valores del exponente público e (65.537) y del exponente privado d, pudiendo apreciarse la diferencia en tamaño entre ambos (17 bits y 2.056 bits, o 257 bytes, respectivamente), los números primos p (prime1, compuesto por 129 bytes o 1.032 bits) y q (prime2, también compuesto por 129 bytes o 1.032 bits), y la clave privada RSA en formato base64 al final (al no hacer uso de la opción "-noout").

    Adicionalmente, OpenSSL proporciona otros parámetros como exponent1 (dp, compuesto por 129 bytes o 1.032 bits), exponent2 (dq, compuesto por 128 bytes o 1.024 bits) y coefficient (qInv, también compuesto por 128 bytes o 1.024 bits) que son utilizados, junto a los números primos p y q, en la fórmula de Garner [0] como parte de las  optimizaciones empleadas al aplicar el TRC en el proceso de descifrado de RSA.

    Curiosamente, el tamaño en bits (o bytes) de los diferentes elementos involucrados en la clave privada RSA no coinciden con los esperados. Ello se debe a que OpenSSL, con el formato de fichero DER (Distinguished Encoding Rules, que es realmente el formato binario que es codificado en base64 en los ficheros ".pem", Privacy Enhanced Mail, PEM), añade un byte inicial con el valor 0x00 que debe ser eliminado. Como resultado, tanto el módulo n como el exponente privado d pasarían a estar formados por un byte menos, es decir, 2.048 bits (o 256 bytes), los números primos p y q pasarían a estar compuestos por 1.024 bits (o 128 bytes), al igual que el exponent1 (dp). De esta forma, el tamaño de todos los valores mostrados coincide con el esperado.

    El motivo de este byte adicional se debe a que el formato de representación binaria ASN.1 que es utilizado por el formato de fichero DER codifica los números enteros (ASN.1 INTEGER) con signo, en formato big endian. Como todos los números empleados en RSA son enteros positivos, y dado que son números cuya longitud es múltiplo de 8 bits (o un byte), como 1.024 o 2.048 bits, OpenSSL los antecede por la izquierda con el valor 0x00. En caso contrario, la codificación ASN.1 de estos valores podría representar números enteros negativos (en codificación de complemento a 2, donde el bit más significativo representa el bit de signo, indicando un bit con valor 1 un número negativo). Se debe hacer notar que en el ejemplo previo no se ha añadido ese byte 0x00 adicional para los valores de exponent2 y de coefficient (que presentaban el tamaño esperado de 1.024 bits), y se deja como ejercicio para el lector descubrir cuál es el motivo. Alternativamente, el siguiente comando de OpenSSL (asn1parse) permite obtener los valores numéricos sin el valor 0x00:
    $ openssl asn1parse -in privada.pem
    Por otro lado, es posible exportar únicamente la clave pública (opción "-pubout") a un fichero, mediante el siguiente comando de OpenSSL21:
    $ openssl rsa -in privada.pem -outform PEM -pubout -out publica.pem
    writing RSA key
    $ ls -l
    -rw-r--r--  1 siles  staff  1679 Sep  1 00:00 privada.pem
    -rw-r--r--  1 siles  staff  5681 Sep  1 00:01 privada.txt
    -rw-r--r--  1 siles  staff   451 Sep  1 00:02 publica.pem
    $ file publica.pem
    publica.pem: ASCII text

    NOTA: Como se puede ver, el tamaño del fichero con la clave pública es significativamente más pequeño que el tamaño del fichero con la clave privada.

    Si se inspecciona el fichero "publica.pem", es posible identificar que contiene una clave RSA pública (en formato base64) mediante el texto "-----BEGIN PUBLIC KEY-----":

    $ cat publica.pem
    -----BEGIN PUBLIC KEY-----
    MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAtxNesQq1i5i/4BBWWe5J
    ...
    awIDAQAB
    -----END PUBLIC KEY-----
    Al igual que anteriormente se ha hecho con la clave privada, es posible mediante el siguiente comando de OpenSSL obtener una versión en formato texto de la clave pública RSA generada (opción "-pubin"), con todos los parámetros asociados:

    $ openssl rsa -in publica.pem -text -pubin -out publica.txt
    writing RSA key
    $ ls -l
    -rw-r--r--  1 siles  staff  1679 Sep  1 00:00 privada.pem
    -rw-r--r--  1 siles  staff  5681 Sep  1 00:01 privada.txt
    -rw-r--r--  1 siles  staff   451 Sep  1 00:02 publica.pem
    -rw-r--r--  1 siles  staff  1369 Sep  1 00:03 publica.txt

    $ cat publica.txt
    Public-Key: (2048 bit)
    Modulus:
        00:b7:13:5e:b1:0a:b5:8b:98:bf:e0:10:56:59:ee:
        <… +15 líneas …> 
        39:00:4b:4a:65:3f:90:13:f3:11:2a:ce:48:61:f8:
        77:6b
    Exponent: 65537 (0x10001)
    -----BEGIN PUBLIC KEY-----
    MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAtxNesQq1i5i/4BBWWe5J
    ...
    awIDAQAB
    -----END PUBLIC KEY-----

    Los detalles en formato texto de la clave pública permiten obtener el tamaño de la clave pública, 2.048 bits, junto al módulo n, con exactamente el mismo valor que el de la clave privada (modulus, compuesto por 256 bytes o 2.048 bits, eliminando el valor 0x00 inicial), junto al valor del exponente público e (65.537), y de la clave pública RSA en formato base64 al final (al no hacer uso de la opción "-noout").

    Complementariamente se puede hacer uso del software educativo genRSA [16] (actualmente en su versión 2.1), ampliamente referenciado en la certificación CriptoCert Certified Cripto Analyst, para llevar a cabo el estudio y los cálculos relativos a los números primos p y q y a las claves RSA asociadas, tanto de manera manual como automática, para la obtención de las Claves Privadas Parejas (CPP), así como para la realización de diferentes ataques sobre las claves RSA. genRSA incluye los tests de primalidad de Miller-Rabin y de Fermat. Complementariamente, se puede seguir el cuaderno 4 del proyecto CLCript (junto a otros cuadernos también focalizados en RSA), centrado en la generación de claves RSA con genRSA v2.1 [17].

    Comentarios

    20 Obtenida mediante el comando "openssl version".
    21 Posteriormente se podría convertir la clave pública de formato PEM a formato DER: "openssl rsa -pubin -inform PEM -in publica.pem -outform DER -out publica.der".

    Referencias:


    Artículo cortesía de Raúl Siles (raul@criptocert.com) - CriptoCert - www.criptocert.com

    Agradecimientos: Jorge Ramió (jorge@criptocert.com) y Alfonso Muñoz (alfonso@criptocert.com)


    Leer más
        email this       edit

    2019/10/18

    Generación de claves RSA y selección de los números primos. Parte 2

    Por Juan Antonio Calles el 2019/10/18 con 0 comentarios

    La idea general empleada por las implementaciones reales se basa en que verificar si un número es primo con una muy alta probabilidad es mucho más rápido que factorizar dicho número, y dado que la existencia de números primos no es infrecuente cuando los números son grandes, es decir, es fácil encontrar números primos incrementando el número candidato y probando de nuevo, los tests de primalidad son muy eficientes (sin entrar en los detalles de cómo funcionan estos tests internamente, por ejemplo, verificando si un número es compuesto mediante el teorema de Fermat12, junto a otras comprobaciones adicionales). A modo de referencia, y sin entrar en sus detalles, existen otros tests de primalidad adicionalmente al de Miller–Rabin, como Lucas (mencionado posteriormente en FIPS 186-4), Baillie-PSW, o Solovay-Strassen.

    Adicionalmente, otras implementaciones basadas en el estándar FIPS 186-4 [4] (analizado posteriormente), concretamente en el apartado B.3.1 (centrado en la generación del par de claves empleadas por RSA; requisito 2(d)), una vez generados los números p y q, comprueban que la diferencia entre ambos números primos sea mayor a m bits, siendo m igual a 2 elevado a la mitad de la longitud del módulo n ("nlen") menos 100 (|p-q|>2(nlen/2)-100), para que no se trate de números primos "muy" cercanos, lo que facilitaría factorizar el módulo n13 [13]. Por otro lado, los números primos p y q empleados no pueden ser iguales, ya que si p=q sería trivial factorizar n calculando la raíz cuadrada de n (n=p*q=p2=q2), lo que permitiría conocer p y q, y por tanto poder calcular Φ(n) = (p-1)(q-1), y como resultado obtener la clave privada d = inv(e,Φ(n)).

    La documentación oficial de la certificación CriptoCert Certified Crypto Analyst (https://www.criptocert.com/#cert-analyst) profundiza en otros aspectos del algoritmo RSA, incluyendo la existencia de Claves Privadas Parejas (CPP) y Claves Públicas Parejas y sus cálculos asociados, los números o mensajes no cifrables, el Teorema Chino del Resto (TCR), etc. En relación con las preguntas que nos ocupan, es interesante conocer que si ambos números primos p y q son seguros, sólo existirá una Clave Privada Pareja (el valor mínimo posible y más recomendable desde un punto de vista criptográfico).

    Un breve artículo introductorio centrado en la elección de los números primos utilizados en la criptografía de clave pública es "Prime Numbers in Public Key Cryptography" [5], de Gerald Crow, publicado en 2003 en la SANS Reading Room, que describe ciertas propiedades asociadas a los números primos, ciertos tipos de números primos como los de Mersenne (2n-1) o el concepto de números primos relativos o coprimos1 (o números primos entre sí), y algunos teoremas relacionados, como el pequeño teorema de Fermat, que permite excluir si un número es o no primo, o el teorema de Euler.

    La tesis "The properties of RSA key generation process in software libraries" de Matúš Nemec (Masaryk University - Faculty of Informatics) [1], publicada en 201614, realiza un análisis muy completo y exhaustivo de las diferentes aproximaciones y algoritmos empleados por las implementaciones de múltiples librerías criptográficas a la hora de generar las claves del algoritmo RSA (comparándolas con los requisitos definidos por estándares internacionales, como NIST FIPS 186-4, detallado posteriormente, ANSI X9.31 y X9.44, IEEE 1363-2000, RSAES-OAEP y otros), la selección de los números primos p y q asociados, y los tests de primalidad empleados para su verificación. La tesis profundiza en las peculiaridades de las distintas implementaciones analizadas, comparándolas entre sí, y en algunas optimizaciones existentes que intentan, por ejemplo, minimizar el número de invocaciones al generador de números (pseudo)aleatorios. Adicionalmente, describe trabajos previos, potenciales ataques sobre las claves RSA, algoritmos y métodos de factorización, e identifica propiedades comunes a claves débiles. Como conclusión, algunas implementaciones aumentan su eficiencia en el proceso de generación de las claves sacrificando unos pocos bits de entropía, pero sin un impacto significativo en la seguridad de las claves generadas.

    En el caso de OpenSSL, la tesis indica (en el apartado 4.2) lo comentado anteriormente tras realizar un breve análisis de su código fuente, es decir, que hace uso de una búsqueda incremental basada en la división del número candidato por algunos números primos pequeños (ya que llegar hasta la raíz cuadrada del número candidato no es práctico, por la cantidad de cálculos requeridos), teniendo en cuenta que los cálculos de división se realizan tanto para p como para p/2 (para emplear primos seguros). Sin embargo, los tests de primalidad no se realizan sobre p/2, lo que parece un bug, hecho que permite identificar claves RSA generadas por OpenSSL (v1.0.2g). La tesis también detalla el uso de OpenSSL con el módulo de compatibilidad FIPS.

    Dentro de los estándares internacionales de referencia más relevantes para la generación de claves RSA, con carácter público y oficial, se encuentra la publicación del NIST conocida como FIPS 186-4, "Digital Signature Standard (DSS)", de julio de 2013 [4], y asociada a la firma digital (la certificación CriptoCert Certified Crypto Analyst cubre esta temática en el módulo 9, tal como se puede consultar en su temario: https://www.criptocert.com/CriptoCert_Analyst.html). En concreto, la sección 5.1 de FIPS 186-4, y especialmente el apéndice B.3.1, detallan los requisitos formales y más restrictivos (en comparación a otras implementaciones) para la generación del par de claves RSA y de la selección de los números primos p y q, y las relaciones entre estos, en base a FIPS 186-4 (referenciadas como IFC, Integer Factorization Cryptography). En resumen, se debe hacer uso de un generador de números aleatorios, o bits, de confianza, y los números primos p y q de 1.024 bits deben ser primos provables o probables  (en inglés), o satisfacer un conjunto de condiciones (primos con condiciones), asociadas a factores primos denominados primos auxiliares, que deben cumplir también unos requisitos de longitud mínima (> 140 bits) y máxima (su sumatorio debe ser, según si son provables, <494 bits, o probables, <1.007 bits). El estándar también define los requisitos del exponente público e y del exponente privado d, y su relación respecto a los valores de p y q. La generación de números primos provables y probables, y de primos de ambos tipos con condiciones, se describe en los apéndices B.3.2, B.3.3, B.3.4, B.3.5 y B.3.6 respectivamente (en base a los requisitos de A.1 y A.2), empleando una semilla aleatoria o tests de primalidad probabilísticos (según el apéndice C.3). Los tests de primalidad probabilísticos referenciados en FIPS 184-6 son Miller-Rabin (C.3.1), una versión mejorada de éste (C.3.2), y Lucas (C.3.3), sugiriéndose la utilización de un número mínimo de iteraciones de Miller-Rabin (según la longitud en bits de p y q y la probabilidad de error que se considera aceptable), o para más certeza (por ejemplo en DSA frente a RSA), su uso combinado, aplicando un test de Lucas adicional. El motivo es que no se conocen valores de números no primos que satisfagan el número de iteraciones del test Miller-Rabin indicadas, y también satisfagan el test de Lucas. En el caso de RSA, y como referencia, el número de iteraciones del test Miller-Rabin es de 5 siendo p y q números primos de 1.024 bits (con una probabilidad de error de 2-112).

    Los dos números primos p y q son habitualmente generados aleatoriamente con una longitud de 1.024 bits y posteriormente se comprueba su primalidad (tal y como se ha descrito anteriormente). Algunas implementaciones, incluyendo OpenSSL, generan un número aleatorio de 1.024 bits, asegurándose de que es un número impar (es decir, su bit menos significativo debe ser 1) y, por tanto, potencialmente primo. Adicionalmente se aseguran de que su bit más significativo también es 1 (el número comienza por 1 en binario) para estar seguros de que el número es de 1.024 bits, y no de 1.023 bits, asegurándose así también de que el módulo n será de 2.048 bits (o al menos de 2.047 bits16). Respondiendo a la pregunta {P2}, teóricamente no necesariamente ambos números p y q deben ser de 1.024 bits, para que su producto n sea de 2.048 bits, sino que uno de ellos podría ser algo más pequeño (por ejemplo, p de 1.020 bits), y el otro algo más grande (por ejemplo, q de 1.028 bits), siendo el producto n de ambos también de 2.048 bits. El conocer de antemano la longitud (1.024 bits) de ambos números primos p y q no facilita los ataques por factorización del módulo n. Lo importante es que el módulo n sea de 2.048 bits. De hecho ocurriría lo contrario, si uno de los dos números primos p o q fuera significativamente más pequeño, se facilitarían los ataques de factorización, que se centrarían en ese número más pequeño o débil. Se debe tener en cuenta que se está trabajando con números de gran tamaño y que la cantidad de números primos de 1.024 bits que existe es muy elevada. Además, por el teorema de Dirichlet, los números primos están uniformemente distribuidos en el módulo n.

    Una vez elegidos los números primos p y q, es posible calcular n, junto a Φ(n), y se pueden por tanto generar las claves pública y privada, e y d, o (e,n) y (d,n). Se podría pensar que dado que los datos que se cifran con la clave pública se pueden descifrar con la clave privada, y teniendo en cuenta que ambas claves permiten realizar operaciones matemáticas inversas, una vez generadas ambas claves, se podría indistintamente seleccionar inicialmente cualquiera de ellas para que actuase como la clave pública y/o como la clave privada, siendo la otra clave su inversa. Es decir, cuando un software con soporte para RSA, como por ejemplo OpenSSL, genera las dos claves, se podría pensar que es posible elegir indistintamente una u otra como clave pública o privada, aunque en realidad no es así. Planteado de otra forma, se podría pensar que el exponente público e (de la clave pública) y el exponente privado d (de la clave privada) son de un tamaño en bits similar, tal y como ocurría con p y q.

    En realidad, y respondiendo a la pregunta {P4}, se recomienda elegir un valor de clave pública e pequeño en relación con el módulo n [0], ya que esto asegura que el valor de la clave privada d será muy grande, y potencialmente más segura, al dificultarse su obtención mediante fuerza bruta. En la práctica, se toma como valor único y conocido del exponente público e el número 65.537, conocido como número 4 de Fermat o F4.

    Tomando los dos números primos p y q de 1.024 bits, y el módulo n de 2.048 bits, al igual que Φ(n), y dado que d = inv (e, Φ(n)) y que e es el valor 65.537 (compuesto por 17 bits), por concepto de inversos, el valor de d será como mínimo de 2.031 bits (2.048-17 bits).

    Adicionalmente, el número 4 de Fermat, empleado en e, presenta propiedades muy interesantes para las operaciones de cifrado de RSA. Debido a que el número 65.537 sólo tiene dos bits con valor 1 (y 15 bits con valor 0), 0x10001 en hexadecimal, al aplicar el algoritmo de exponenciación rápida en las operaciones de cifrado, donde e actúa de exponente, C = Me mod n, debido a que está compuesto de muchos ceros , permite agilizar las operaciones de cálculo [0], mejorando la eficiencia del proceso de cifrado de RSA. Por tanto, las operaciones de cifrado con la clave pública e en RSA son mucho más eficientes y rápidas que las operaciones de descifrado con la clave privada d.

    En resumen, la clave pública basada en el exponente público e es de reducido tamaño, los 17 bits del número 4 de Fermat, mientras que la clave privada basada en el exponente privado d tiene un tamaño cercano al módulo n (2.048 bits).

    Para agilizar las costosas operaciones de exponenciación con números grandes involucradas en el proceso de descifrado de RSA empleando la clave privada d se hace uso del Teorema del Resto Chino (TRC), descrito en detalle en la documentación de la certificación CriptoCert Certified Crypto Analyst. El destinatario de un mensaje cifrado, al disponer tanto de d, como de los números primos p y q, podrá realizar los cálculos de aritmética modular en los grupos de p y q, de 1.024 bits, en lugar de en el grupo del módulo n, de 2.048 bits, reduciendo el tiempo de cómputo (en unas 4 veces [0]). Como se verá posteriormente de forma práctica, OpenSSL proporciona ciertos valores adicionales a la hora de generar las claves RSA que permiten hacer uso del TRC en el proceso de descifrado

    Comentarios

    13 Si los números primos p y q son "muy" cercanos, sería trivial factorizar n simplemente obteniendo su raíz cuadrada y buscando números impares, por arriba y por debajo de ese valor, que fuesen primos.
    14 El autor de la tesis estuvo involucrado en el descubrimiento y publicación de la vulnerabilidad ROCA [18] en el año 2017.
    15 En teoría de números, los números primos provables son aquellos que se ha calculado que son primos mediante algoritmos que permiten comprobar que no son números compuestos (garantizan que son primos), mientras que los números primos probables son aquellos que han pasado tests de primalidad probabilísticos y que muy probablemente (pero no con total certeza) son primos [1].
    16 Posteriormente se describirá como OpenSSL se asegura en realidad de que los dos primeros bits de los números primos p y q tienen el valor 1, por lo que el módulo n será del tamaño esperado, 2.048 bits.
    17 Técnicamente se indica que F4 tiene un peso de Hamming bajo: https://en.wikipedia.org/wiki/Hamming_weight

    Referencias:


    Artículo cortesía de Raúl Siles (raul@criptocert.com) - CriptoCert - www.criptocert.com

    Agradecimientos: Jorge Ramió (jorge@criptocert.com) y Alfonso Muñoz (alfonso@criptocert.com)


    Leer más
        email this       edit

    2019/10/17

    Generación de claves RSA y selección de los números primos. Parte 1

    Por Juan Antonio Calles el 2019/10/17 con 0 comentarios

    Artículo cortesía de Raúl Siles (raul@criptocert.com) - CriptoCert - www.criptocert.com

    Agradecimientos: Jorge Ramió (jorge@criptocert.com) y Alfonso Muñoz (alfonso@criptocert.com)

    ¿Cómo se generan y/o eligen los dos números primos p y q empleados en RSA a la hora de generar el par de claves, pública y privada?... y otras cuestiones interesantes asociadas a la generación de las claves en RSA ;-)

    Otras preguntas relacionadas que también surgieron, y que es lógico que se plantee cualquier mente inquieta y ávida de sabiduría son, ¿al generar un par de claves RSA de 2.048 bits, la longitud de los número primos p y q es exactamente de 1.024 bits para cada uno, o puede haber ligeras variaciones en su longitud, sin que sean necesariamente números exactamente de la misma longitud? {P2}, ¿cómo se generan y/o eligen los números primos p y q empleados en RSA por parte de un software de referencia en la industria como, por ejemplo, OpenSSL? {P3} y, por último, ¿una vez generadas las dos claves, pública y privada, se podría elegir indistintamente una u otra para jugar el papel de clave pública o privada? {P4}

    A continuación vamos a intentar responder a todas estas preguntas y a proporcionar referencias adicionales para quienes estén interesados en profundizar aún más en las respuestas asociadas.
    De manera breve e introductoria (para más información se recomienda la lectura del libro "Cifrado de las comunicaciones digitales. De la cifra clásica al algoritmo RSA" de Jorge Ramió y Alfonso Muñoz, cuya 2ª edición ha sido publicada en 2019 [0]), el algoritmo de cifra asimétrico RSA permite tanto cifrar la información (proporcionando confidencialidad), como firmarla (proporcionando autenticidad e integridad). Centrándonos en las operaciones de cifrado, es posible cifrar un mensaje M mediante la clave pública del destinatario (n,e) empleando la siguiente operación de exponenciación en aritmética modular, así como descifrar el mensaje cifrado C mediante la clave privada del destinatario (n,d) para obtener de nuevo el mensaje M original:

    Cifrado: C = Me mod nDescifrado: M = Cd mod n
    Imagen del certificado digital de la web de CriptoCert (https://www.criptocert.com), con módulo de 2.048 bits, obtenido mediante Firefox en macOS.

    La fortaleza de RSA reside en la dificultad computacional de factorizar un número compuesto muy grande, es decir, el módulo n, compuesto por el producto de los dos números primos p y q.

    Sin profundizar en los detalles matemáticos, una vez se dispone de p y q, y por tanto de n, se calcularán el resto de valores (e y d) en base a ciertas fórmulas matemáticas como, por ejemplo, el indicador de Euler del módulo n, f(n) = (p-1)(q-1), un valor trampa secreto que permite elegir el exponente público e en el rango 2 < e < f(n), coprimo1 con f(n). Como detalle adicional, el indicador de Euler f(n) proporciona el orden, es decir, la cantidad de números enteros positivos menores o iguales a n y coprimos con n, es decir, el tamaño del "grupo de cifra" definido por el módulo n. Teóricamente, cada usuario elegirá un valor de e para su clave pública asegurándose de que existe un inverso multiplicativo2, es decir, un valor d para poder disponer de una clave privada asociada:
    d = inv(e,f(n)) o d = e-1 mod f(n).
    En resumen, a la hora de generar sus claves RSA, cada usuario elige dos números primos p y q y los mantiene en secreto, obtiene el módulo n=p*q, que es público, genera la clave pública e, o (n,e), y calcula el indicador de Euler f(n) que actúa como valor trampa secreto para poder calcular la clave privada asociada d, o (n,d)3. El hacer públicos los valores e y n no pone en peligro la clave privada d, ya que para calcular d es necesario conocer el valor secreto trampa f(n), es decir, los números primos p y q.

    La pregunta inicial planteada {P1} centrada en cómo se eligen los números primos p y q es común y se ha repetido en foros y grupos de discusión de criptología a lo largo de los años. Conocer los detalles para elegir p y q correctamente es fundamental para cualquier desarrollador que quiera hacer uso de RSA en su software sin emplear librerías criptográficas o software de terceros, o que aun haciendo uso de éstas, quiera verificar que se hace un uso correcto de RSA. Tal como se describe en la nota 4.51 del capítulo 4 del libro "Handbook of Applied Cryptography" de A. Menezes, P. vanOorschot, y S. Vanstone, publicado en 1996 [2], y como se resume en [3], el algoritmo genérico empleado para la obtención de los números primos p y q en RSA es el siguiente:
    1. Generar un número impar p (condición necesaria para que potencialmente sea un número primo4) aleatorio de 'n' bits, siendo 'n' = 1.024 bits para las claves RSA de 2.048 bits comúnmente empleadas hoy en día. Si el número generado no es impar, se le suma 1.
    2. Comprobar si p es un número primo. Para llevar a cabo esta comprobación se pueden emplear diferentes métodos de verificación denominados tests de primalidad, descritos posteriormente.
    3. Si p no es primo, se puede tomar p = p+2 (búsqueda incremental) y volver a realizar la verificación del paso 2, o tomar un nuevo valor de p aleatorio (paso 1) y realizar de nuevo la verificación del paso 2.
    Los tests de primalidad [9] utilizados actualmente para números grandes (de cientos o miles de bits) son test probabilísticos5, es decir, comprueban con una muy alta probabilidad si un número grande es primo o no. Para ello tienen en cuenta ciertas propiedades conocidas que cumplen los números primos en base a la teoría de números. Si se ejecutan varias veces sobre un mismo número candidato con distintos valores semilla de entrada, y todas las ejecuciones ratifican que el número parece ser primo, se dispondrá de un mayor nivel de certeza. A un mayor número de ejecuciones del test, mayor certeza de que el número candidato realmente es primo.

    El test de primalidad más comúnmente empleado en la actualidad para verificar si un número es primo es el de Miller-Rabin6. Este tipo de tests son bastante rápidos de calcular y, de media, a la hora de comprobar si un número de 1.024 bits es primo, sólo tienen que verificar unos cientos de candidatos posibles, ya que la densidad de números primos en un rango de números cualquiera es bastante elevada (definida por aproximadamente 1/ln(n)). El teorema de los números primos [6] refleja que la distancia entre números primos, por ejemplo de 1.024 bits, es aproximadamente 1.024*ln(2), es decir, 710. Dado que sólo hay que comprobar los números impares como posibles números primos, la verificación o test de primalidad necesitaría comprobar unos 355 candidatos (710/2) antes de encontrar el siguiente número primo de manera incremental. Como referencia, la probabilidad de que Miller-Rabin detecte si un número es primo en una ejecución o ronda es del 75% [7], por lo que tras 64 ejecuciones, la probabilidad de error es muy pequeña, del orden de 2-128.

    En el caso de OpenSSL [7], respondiendo a la pregunta {P3}, es posible consultar su código fuente7 [8] para ver que hace uso de numerosos tests, encontrándose referencias a un primer filtrado mediante un algoritmo determinista de criba rápida (cuyo código está basado en la implementación y código de PGP [8]), donde se divide al número candidato por algunos números primos pequeños (los primeros 2.048 números primos8, para descartar rápidamente si el candidato es primo o no), y si el número candidato pasa ese filtro, se emplean principalmente varias ejecuciones9 del test de Miller-Rabin y de su versión mejorada (mencionada posteriormente en el estándar FIPS 186-4, C.3.1 y C.3.2), así como finalmente ciertas comprobaciones para hacer uso de números primos seguros (en inglés, safe primes), es decir, donde (p-1)/2 también es un número primo10 [10]. La utilización de primos seguros puede mitigar ciertos ataques cuando estos números son utilizados con el algoritmo de intercambio de clave de Diffie-Hellman, así como minimizar el número de Claves Privadas Parejas (CPP) asociadas a las claves RSA

    A modo de curiosidad, ciertas versiones de OpenSSL para claves con un reducido número de bits (128 bits), no utilizadas en la práctica actualmente, no verifican adecuadamente los números primos p y q empleados para la generación de las claves, lo que da lugar a claves RSA incorrectas, tal como se detalla en el artículo publicado en 2018 por Jorge Ramió: "¿Son correctas las claves RSA que generamos con Win64 OpenSSL1.1.0g? Intentando cifrar con RSA cuando p y q no son primos" [14].

    Algunos estándares de la industria para la generación de claves RSA robustas, como ANSI X9.3111
    , requerían que los números primos p y q empleados fuesen además primos fuertes (en inglés, strong primes), es decir, en teoría de números, un número primo que está más cerca del siguiente número primo que del número primo que le precede. En criptografía, un primo fuerte cumple ciertas condiciones relacionadas con el número primo que le precede y con el siguiente número primo [11]. El uso de primos fuertes en RSA se recomendó para minimizar los ataques de factorización mediante el algoritmo de Pollard p-1, aunque no protegen frente a otros métodos de factorización del módulo n, como Lenstra (basado en curvas elípticas) o la criba numérica o NFS (Number Field Sieve, o GNFS, General Number Field Sieve), por lo que algunos criptógrafos como Ron Rivest desaconsejaron su utilización ya en 2001 [12], debido también al mayor tiempo de búsqueda necesario para encontrar estos números primos y los limitados beneficios que aportan. En la actualidad, las implementaciones hacen uso de primos fuertes sólo si deben cumplir una certificación que lo impone como requisito (por ejemplo, IEEE 1363).

    A modo de curiosidad, el record público actual de factorización de un módulo n de RSA es de 768 bits, conseguido mediante el método NFS a finales del año 2009 y documentado en "Factorization of a 768-bit RSA modulus" [19], asociado al RSA Factoring Challenge [20] (desafío que fue retirado previamente, en el año 2007).


    Comentarios

    1 Los números coprimos son números enteros (positivos), por ejemplo, a y b, que no tienen ningún factor primo en común, es decir, que su único divisor común es el 1. Dos números son coprimos si su máximo común divisor (MCD) es igual a 1 (mcd [a, b] = 1).
    2 mcd [e, f(n)] = 1 (es decir, e y f(n) son números coprimos)
    3 La clave privada d se calcula mediante el algoritmo extendido de Euclides.
    4 Todos los números primos (números enteros positivos) mayores que 2 son impares.
    5 A diferencia de las comprobaciones o tests determinísticos, como la criba de Eratóstenes, mucho más lento de calcular, o como el test AKS: https://es.wikipedia.org/wiki/Test_de_primalidad_AKS
    6 Complementariamente, existen algoritmos para la generación de números primos, como el algoritmo de Maurer (apartado 4.4.4 [2]), empleado para la generación de primos provables: https://pdfs.semanticscholar.org/3df0/e64897ebbed46a6d034196f9b3962ca45b07.pdf
    7 La versión actual de OpenSSL disponible en GitHub en el momento de elaboración del presente artículo era la 3.0.0-dev, mientras que la versión estable principal era la 1.1.1c.
    9 El número de ejecuciones o iteraciones del test de primalidad de Miller-Rabin depende de la longitud en bits del número primo (tal y como también establece el estándar FIPS 186-4, descrito posteriormente).
    10 Un número primo seguro se define habitualmente como un número de la forma 2p+1, donde p también es primo como, por ejemplo, 23 = 2*11+1, al ser 11 también un número primo.

    Referencias:

    Leer más
        email this       edit