Colisiones, haberlas hay(las). Parte 2

jueves, 17 de mayo de 2018

En nuestra entrada anterior sobre este tema, terminamos el post preguntándonos: ¿Existirán colisiones en los algoritmos utilizados en Bitcoin?, pues vamos a analizarlo.

La criptografía de Bitcoin
Los principales organismos reguladores NIST, FIPS, la misma NSA, el MITRE y los gigantes del sector privado, con Google a la cabeza; se preocupan muy mucho por la seguridad de los criptosistemas de uso general, pero… ¿Quién vela por la seguridad de las criptodivisas como el Bitcoin? ¿Existen colisiones en los algoritmos utilizados en Bitcoin?

El protocolo Bitcoin hace uso de tres algoritmos criptográficos:
  • ECDSA: en la firma y verificación de transacciones, a partir de claves privadas y públicas (criptografía asimétrica).
  • SHA-256 y RIPEMD160: como algoritmos de Hash (resumen criptográfico) en varios usos.

Algoritmo ECDSA
ECDSA es una modificación del algoritmo de Firma Digital DSA para ser utilizado con operaciones sobre “Curvas Elípticas” ECC, en lugar de basarse en sistemas de exponenciación o factorización, como los utilizados por DSA o RSA. Estos requieren un tamaño de clave muy superior para obtener un mismo nivel de seguridad, siendo hasta 400 veces más lentos.

Una curva elíptica es una curva plana definida por una ecuación cúbica de tercer grado de la forma:

y^2=x^3+ax+b

Para sus usos en criptografía se definen sobre un cuerpo finito de números enteros.

Existen diferentes organismos que definen los parámetros de las curvas elípticas empleadas en criptografía. Los principales son: ANSI, IEEE, NIST o Brainpool, siendo el más extendido y reconocido SECG (Standards for Efficient Cryptography Group) por su carácter independiente.

Cada criptosistema de curva elíptica consta de unos determinados “parámetros de dominio” que especifican los valores necesarios para establecer el campo finito, los coeficientes y demás elementos que definen la curva. Se expresan en una séxtupla T = (p, a, b, G, n, h), siendo:
  • El  número de elementos del cuerpo finito (p)
  • Los coeficientes (a y b)
  • Las coordenadas del punto base G (x,y)
  • El orden del punto de la curva (n)
  • El cofactor (h)
Una de las curvas elípticas más utilizadas en criptografía es la “NIST P-256”, igualmente definida por el SECG como “secp256r1”, y por el ANSI X9.62 como “prime256v1”. Esta es la única curva, junto a la P-384 y P-521, que cumple con los requisitos de seguridad de la Suite B de la NSA (estándar de factor para el entorno militar de la OTAN). Sus parámetros son:

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 
a = -3 
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 
x = 48439561293906451759052585252797914202762949526041747995844080717082404635286 
y = 36134250956749795798585127919587881956611106672985015071877198253568414405109 
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369 
h = 1

Podemos ver un ejemplo de utilización de esta curva en la firma de los certificados digitales que emplean las principales webs de Internet. Véase el siguiente correspondiente a google.com:

Firma de certificados digitales Google imagen

No obstante, esta no es la curva que utiliza el protocolo Bitcoin, el cual usa la curva “secp256k1”. Únicamente definida por el SECG, ortográficamente sólo cambia una “r” por una “k”, pero sus parámetros de dominio varían sustancialmente.

La letra “r” hace referencia a “random” ya que sus parámetros de dominio han sido seleccionados de forma “teóricamente” aleatoria. También son conocidas como curvas sobre cuerpos primos o “Prime”.

Sin embargo, la letra “k” hace referencia a “Koblitz”, por tratarse de un tipo de curvas binarias anómalas denominadas así en honor al profesor de matemáticas Neal Koblitz (co-autor junto a Victor S. Miller de la criptografía de curvas elípticas a mediados de los 80’s), cuyos parámetros de dominio no son elegidos al azar, si no, “rígidamente” calculados. También son conocidas como curvas sobre cuerpos binarios, aunque existen curvas sobre cuerpos binarios que no son curvas de Koblitz (ej. NIST B).

Los parámetros de dominio de la curva “secp256k1” utilizada en el protocolo Bitcoin son los siguientes:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 
a = 0 
b = 7 
x = 55066263022277343669578718895168534326250603453777594175500187360389116729240 
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424 
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 
h = 1

Quedando simplificada su ecuación de la siguiente manera:

y^2=x^3+7

Matemáticamente, las curvas de Koblitz son unos pocos bits más débiles que otras curvas. Para obtener el mismo grado de seguridad que una curva Prime con clave de 256 bits, una curva Koblitz requiere una longitud de clave de 283 bits.

La mayor estructura que presentan estas curvas permie realizar ataques más eficientes, además de que el cálculo de multiplicación escalar es mucho más rápido que en otro tipo de curvas.

No obstante, las curvas “secp256r1” y “secp256k1” tienen una seguridad equiparable. Si consideramos solo los ataques conocidos hoy, poseen una seguridad prácticamente idéntica.

Sin embargo, con la excusa de no disponer de suficientes garantías frente al criptoanálisis, ninguna curva de Koblitz, independientemente de su longitud de clave, ha sido recogida en las definiciones de organismos como la NSA, el ANSI, o Brainpool.

Por el contrario, una importante corriente de investigadores denuncia la imposibilidad de verificar la verdadera “aleatoriedad” de los parámetros de dominio definidos para las curvas Prime, como la “secp256r1”, alimentando las sospechas sobre la existencia de una “puerta trasera” introducida por la NSA, desde que en el año 2006 el NIST adoptara varios algoritmos propuestos por la agencia.

Tan solo un año más tarde, en 2007, dos investigadores de Microsoft, Dan Shumow y Niels Ferguson, concluyeron que uno de estos algoritmos de la NSA, el Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) era potencialmente inseguro.

Pero no fue hasta junio de 2013, cuando Edward Snowden, antiguo empleado de la CIA y la NSA, hizo públicos un elevado número de documentos secretos, donde pudo verificarse que se trataba de una puerta trasera de la NSA, e incluso que fue desarrollada por la compañía RSA, al precio de 10 millones de dólares. El algoritmo Dual_EC_DRBG fue inmediatamente retirado y el NIST emprendió una campaña para lavar su imagen, en la que todavía continua inmerso.

De forma similar a cualquier otro criptosistema, los algoritmos de curva elíptica están en constante evaluación mediante diferentes técnicas de criptoanálisis; desde simples ataques de fuerza bruta, hasta los más complejos ataques de Pohlig-Hellman, de Shor, de BGGS (Baby Step, Giant Step), de MOV (Menezes-Okamoto-Vanstone), de Pollard, de Frey-Rück o Index-Xedni-Calculus, pasando por cualquier aplicación de teorías de grupos o giros cuadráticos.

Hasta la fecha, no se han encontrado debilidades, ni vulnerabilidades en el diseño de estos criptosistemas, aunque existen varios casos en los que una implementación deficiente del algoritmo, provocó un importante incidente de seguridad.

Uno de los casos más sonados fue el de Sony con su PlayStation 3. La tercera versión de la popular consola de videojuegos lanzada en 2006, empleaba ECDSA como algoritmo de firma digital para validar el software que podía ser ejecutado, impidiendo así la posibilidad de ejecución de programas y juegos no autorizados.

El proceso de firma digital requiere, además de la clave privada, un número aleatorio que no debe reutilizarse. Sorprendentemente Sony utilizó el mismo valor en todas las firmas de código que emitía. Esta debilidad fue anunciada por el grupo de investigadores “fail0verflow” en 2010, y poco después George Hotz “Geohot” consiguió explotarla para obtener la clave privada de Sony, y la publicó en su web personal; aunque hoy está ya deshabilitada, es bien conocida: “BA9055916861B977EDCBED92005092F66C7A3D8D”.

La generación de números aleatorios es un proceso crítico para cualquier criptosistema. Las autoridades de certificación y otros organismos que requieren de garantía absoluta de aleatoriedad, recurren a hardware específicamente diseñado para este propósito. Pero para un uso ordinario, se delega en el Sistema Operativo la generación de números aleatorios.

Son conocidos varios incidentes de seguridad provocados por una utilización defectuosa de la generación de números aleatorios en procesos criptográficos, aunque no transcendían más allá de una pequeña reseña, normalmente cuando ya estaban corregidos.

La aparente inocencia con la que eran percibidos los defectos de aleatoriedad, se tornó dramática en el verano de 2013, cuando salió a la luz una vulnerabilidad en la clase Java SecureRandom del SDK de Android que afectaba todas las versiones anteriores a la v4.2, lo que en aquella época suponía la práctica totalidad de tablets y smartphones Android (CVE-2013-7372).

El impacto de esta vulnerabilidad fue terrible para los usuarios de wallets de Bitcoin para Android, estando afectados la mayoría de los existentes entonces: Bitcoin Wallet, BitcoinSpinner, Mycelium y Blockchain.info. Todos los fondos depositados en estas carteras fueron sustraídos.

Se alertó desde la web Bitcoin.org, y aunque los desarrolladores publicaron rápidamente actualizaciones que parcheaban el problema, el daño ya estaba hecho. No fue posible cuantificar las cantidades sustraídas al tratarse de un robo que afectaba de forma individual a cada usuario, pero se sabe que fueron miles los que perdieron todos sus bitcoins. Google reconoció el error, corrigiéndolo con celeridad. Pero ya era tarde, no existía posibilidad alguna de recuperar las cantidades usurpadas, ya que las transacciones quedan inmutablemente recogidas en la blockchain.

Se desconocen los verdaderos motivos por los que el creador de Bitcoin eligió para el algoritmo ECDSA una curva de Koblitz en lugar de una curva Prime. Puede que simplemente se fiara más del profesor Neal que de la NSA.

Vitalik Buterin, ferviente seguidor de Bitcoin y la postre creador de Ethereum, comentaba en la Bitcoin Magazine, como Satoshi Nakamoto había encontrado formas inesperadas de esquivar “balas criptográficas”, tanto por elegir una curva de Koblitz, como por definir que las direcciones de pago de Bitcoin como un hash de la clave pública en lugar de la propia clave pública.

Pero, ¿son estas precauciones suficientes?, ¿los algoritmos de hash utilizados SHA-256 y RIPEMD160 son suficientemente seguros?, ¿hay colisiones en las direcciones de Bitcoin? Te lo contaremos todo en la tercera parte, no te pierdas la próxima entrega! Y recuerda que si tienes dudas o quieres discutir más sobre el tema, puedes visitarnos en la Comunidad de ElevenPaths.


» Colisiones, haberlas hay(las). Parte 1
Jorge Rivera
CSA, Chief Security Ambassador

No hay comentarios:

Publicar un comentario