Colisiones, haberlas hay(las). Parte 4.

sábado, 2 de junio de 2018

En la entrada anterior sobre este tema, analizamos cómo las claves privadas de Bitcoin son suficientemente seguras, siempre que se utilicen de forma correcta. Pero, ¿qué sucede con las claves públicas y sobre todo, con los algoritmos de hash SHA-256 y RIPEMD-160?, ¿serán suficientemente seguros para impedir colisiones en las direcciones de Bitcoin? ¡Vamos a verlo!

Claves públicas y direcciones de Bitcoin
En los criptosistemas de curva elíptica, cada clave pública es un punto de la curva referenciado por sus coordenadas (x,y), el cual ha sido obtenido a parir de la clave privada. En el caso de Bitcoin y su curva “secp256k1”, las coordenadas “x” e “y” son dos números de 256 bits de tamaño.

La clave pública puede expresarse de dos formas, según se utilicen una (x), o las dos coordenadas (x,y), generalmente en codificación hexadecimal:
  • Sin comprimir (uncomppressed) 65 bytes:            “04” + x + y  
  • Comprimida (compressed) 33 bytes:                     “02 o 03” + x (02 si X es par o 03 si es impar)
Desde la primera versión del protocolo Bitcoin se soportan dos “métodos de pago” o posibles salidas de una transacción:
  • P2PK (Pay to Public Key):                   Pago a una clave pública
  • P2PKH (Pay to Public Key Hash):       Pago al hash de una clave pública (dirección de Bitcoin)
Un P2PKH es lo que se conoce generalmente por “dirección” (address) de Bitcoin. Se obtiene realizando un “doble Hash” (a veces llamado HASH160). Primero un hash SHA-256 sobre la clave pública, ya sea comprimida o sin comprimir, y sobre el resultado de este, un nuevo hash RIPEMD-160. Posteriormente, se le añade un byte de versión al inicio y cuatro de suma de verificación al final, y se codifica todo en Base58.

Comienzan siempre por un “1” si la versión se corresponde con la red real de Bitcoin. No es posible distinguir si la clave pública de origen está en formato comprimido o sin comprimir; únicamente para facilitar su gestión, se puede expresar una misma clave privada en formato WIF de dos maneras diferentes: cuando comienzan por “L” o “K” para generar la dirección comprimida, y cuando comienzan por “5” para generar la dirección sin comprimir.

En 2012, mediante la adopción del BIP0016, se añadió la posibilidad de realizar el pago a un hash de script o P2SH (Pay to Script Hash) lo que permite, por ejemplo, definir las direcciones, monederos o carteras multifirma, como destino de una transacción. Los hashs de script se identifican fácilmente, ya que al codificar el hash en Base58 siempre comienzan con un “3” en lugar de con un “1” como lo hacen los hashs de clave pública. A día de hoy, los P2SH representan aproximadamente el 25 % de las salidas en transacciones de Bitcoin. Este dato está disponible en tiempo real en la web informativa p2sh.info.
llave púbica de bitcoin imagen


Satoshi Nakamo debió recelar ante los avances en computación cuántica, sobre todo, a raíz de la implementación del algoritmo de Shor. Este mismo temor inquieta a la NSA, ya que cada vez está más próximo el día en que los ordenadores cuánticos dispongan de los “qubits” suficientes para reventar los criptosistemas actuales. Ignacio Cirac, director de la División Teórica para la Óptica Cuántica del Instituto Max-Planck desde 2001b , y desde 2016 consejero adjunto de Telefónica, lo explica de forma clara y amena en cualquiera de sus conferencias. Si quieres saber más, no te pierdas esta.

Para evitar este riesgo, implementó el método de “pago a hash de clave pública” P2PKH, en detrimento del pago directo a clave pública P2PK. De esta forma, la clave pública sólo se expone en el momento de “gastar”, utilizar los bitcoins en el input de una transacción, pero no al recibirlos en el output de una transacción previa; y siguiendo la recomendación de no reutilizar direcciones, se suprime toda posibilidad de ataque al algoritmo ECDSA.

El hash de P2PKH es doble; por si un sólo hash SHA-256 (256 bits) no fuese suficiente, al resultado se le hace otro hash, pero en este caso un RIPEMD-160 (160 bits). 160 bits, ¡menuda reducción!.

Puede entenderse que quisiera redoblar la seguridad con un segundo hash, y que eligiera RIPEMD por su origen Europeo en contraste con los SHA Norteamericanas que vimos en la primera parte de la serie, como el equivalente de 160 bits “SHA-1” propuesto por la NSA es vulnerable al encontrarse la forma de generar colisiones. Pero, la reducción de 256 bits a 160 bits tiene notables consecuencias, que además, podían haberse evitado simplemente con utilizar la variante RIPEMD-256, aunque las direcciones de Bitcoin resultasen un poco más largas.

¿Qué implica reducir de 2^256 posibles valores, a 2^160 posibles valores? Colisiones, sí, y muchas. Exactamente (2^256 / 2^160) = 2^96. Es decir, para cada dirección de Bitcoin existen casi “ocho mil cuatrillones” de claves públicas que generan la misma dirección. Esto es más de 10^28. Hay muchas más claves que generan una misma dirección de Bitcoin que estrellas en el Universo.

Entonces, si el protocolo de Bitcoin prevé un volumen tan ingente de colisiones, ¿no hay nadie buscando alguna? Probablemente habrá muchos proyectos, aunque por diferentes cuestiones, no son públicos y, por tanto, tampoco conocidos, pero merece la pena mencionar uno tan peculiar como controvertido: el “Gran Colisionador de Bitcoin”.

pool performance imagen

El LBC es un pool que agrupa a diferentes workers que han unido su capacidad de trabajo en busca de una colisión de claves de Bitcoin. Lo hacen de una forma un tanto peculiar, ya que para comprobar que han encontrado una colisión real, sólo comparan las direcciones que generan con direcciones ya utilizadas en la cadena de bloques, y que además aun contengan bitcoins sin gastar, con la esperanza de que el propietario original reclame los fondos, pudiendo entonces verificar que se trata de dos claves diferentes y no de una misma.

Para solucionar la problemática que implica la comparación de las direcciones generadas con una muestra valida, dicen utilizar una estructura de datos probabilística conocida como “filtro de Bloom”. Pero, tanto la elaboración del filtro como cualquier otro detalle del funcionamiento del pool, no es compartido, y la mayor parte del software está ofuscado, por lo que pese a que han publicado varios casos de existo en su sección de “trofeos”, no puede considerarse un proyecto serio. Mantiene, eso sí, una fiel copia de directory.io.

Aunque, posiblemente sean los generadores de direcciones de vanidad el intento que más se aproxime a la búsqueda de una colisión. Se conocen como direcciones de vanidad a aquellas direcciones de Bitcoin que comienzan o contienen una secuencia específica de caracteres, cuya única forma de encontrar es mediante fuerza bruta, generando miles de millones de direcciones e ir comparándolas con el patrón especificado, normalmente con una expresión regular.

Si bien comenzó como una curiosidad, el software para generar estas direcciones ha evolucionado considerablemente, implementándose en OpenCL para ser ejecutado en los cientos o miles de núcleos disponibles en las GPUs, y extendiéndose a otras criptomonedas.

Pese a la elevada capacidad de computo que se alcanza con la implementación en GPUs, el número de intentos requeridos para encontrar un pequeño texto es tan enorme, que el tiempo necesario, literalmente, se eterniza. Por ejemplo, dar con una dirección de Bitcoin que comience por “11Paths” como “11PathsQEx9FmFSiGY873i4BtTtDdYcKh”, necesitaría un billón de intentos (10^12), que pueden realizarse en menos de un día. Pero con tan solo dos cárteres más “11Paths11”, los intentos necesarios se acercan al trillón (10^18), elevándose el tiempo necesario a varios años.

Si tienes una tarjeta gráfica de última generación, y en lugar de participar en una competición online, decides ponerla a generar, tan solo, los ocho mil cuatrillones (10^28) de claves que serían necesarios tener, una probabilidad razonable de encontrar una colisión de dirección completa, tardarías unos 10000 millones de años, que es algo menos de la edad del Universo. La edad del Universo está estimada entre 13761 y 13835 millones de años.

Dada la extrema dificultad que conlleva generar direcciones de vanidad, existen pooles para agrupar el trabajo de varios usuarios, e incluso webs que lo ofrecen como un servicio de pago. De cualquier forma, utilizar estas direcciones es una práctica totalmente desaconsejada, sobre todo si te la provee un tercero, ya que será conocedor de la clave privada correspondiente.

En términos generales, el grueso de los usuarios de Bitcoin se ciñen a las practicas recomendadas en la especificación del protocolo, generando las direcciones de forma totalmente aleatoria y no reutilizándolas en más de una ocasión. La mayoría de las más de 100 millones de direcciones que figuran en la cadena de bloques, solo tiene dos transacciones, una primera de entrada y una segunda de salida. Esto, sumado a que cada vez es mayor el uso pago a hash de script P2SH, hacen que el riesgo de pérdida de bitcoins por una colisión de dirección sea prácticamente nulo.

Podemos concluir por tanto que, los algoritmos criptográficos utilizados en Bitcoin, ECDSA curva “secp256k1”, hash SHA-256 y hash RIPEMD-160, son suficientemente seguros al no existir vulnerabilidades conocidas, y pese a que el protocolo de Bitcoin prevé un importante número de colisiones de dirección, la probabilidad de verse afectado por una es insignificante.

Como usuarios finales, la criptografía que hay detrás del Bitcoin no debería preocuparnos, pero sí que debemos tener otras muchas precauciones, incluso si utilizamos wallets físicos;. En anteriores ocasiones, comentamos la facilidad con la que un mal uso te hace perderlo todo.

Recuerda que si tienes dudas o quieres discutir más sobre el tema, puedes visitarnos en la comunidad de ElevenPaths.

Jorge Rivera 
CSA, Chief Security Ambassador 

» Colisiones, haberlas hay(las). Parte 1
» Colisiones, haberlas hay(las). Parte 2
» Colisiones, haberlas hay(las). Parte 3

No hay comentarios:

Publicar un comentario