Debilidad de nodo de hoja en Bitcoin Merkle Tree Design Bitlogs Comprar bitcoin con Paypal

Este documento describe una debilidad en el diseño de Bitcoin que reduce la seguridad de las pruebas SPV y, por lo tanto, las carteras SPV. La debilidad fue descubierta por mí en agosto de 2017, pero durante el proceso de divulgación responsable, supe que algunos miembros prominentes del Bitcoin Core equipo. Usando esta debilidad, un atacante puede crear una prueba de SPV válida para un pago falso a una víctima que está usando una billetera SPV, el monto del pago es un número arbitrario de bitcoins, y engañar a la víctima para que acepte este pago como válido. Afortunadamente, explotar este error requiere una fuerza bruta de entre 69 y 73 bits (dependiendo de la inversión inicial), siendo cada operación un doble SHA2, y hay protecciones probabilísticas muy simples que las carteras SPV pueden implementar fácilmente. Por ejemplo, un ataque puede llevarse a cabo con una inversión de 3 millones de USD (*). Se supone que la mayoría de las carteras SPV serán vulnerables a este ataque. También son vulnerables los sistemas automatizados que aceptan pruebas SPV (como el sidechain de Blockstream Elements en modo no federado y el contrato RSK Bridge). Un parche simple que ni una bifurcación suave ni una dura puede prevenir el ataque descrito. Además, un segundo ataque que teje el Bitcoin blockchain se presenta, requiriendo la fuerza bruta de 225 bits, por lo que solo tiene interés teórico.

El árbol de Bitcoin Merkle no distingue entre los nodos internos y los nodos hoja. La profundidad del árbol está implícitamente dada por la cantidad de transacciones. Los nodos internos no tienen un formato específico y tienen 64 bytes de longitud. Por lo tanto, un atacante puede enviar al blockchain una transacción que tiene exactamente 64 bytes de longitud y luego forzar a un sistema víctima a volver a interpretar esta transacción como un nodo interno del árbol. Por lo tanto, un atacante puede proporcionar una prueba SPV (una rama Merkle) que agrega un nodo hoja adicional que extiende la doble transacción / nodo y proporciona prueba de pago de cualquier transacción que desee.

Cabe señalar que un problema recíproco a esto fue identificado por Andrew Miller [1]. Se dio cuenta de que los nodos internos podrían reinterpretarse como transacciones, pero parece que no publicó (o no descubrió) el ataque opuesto: transacciones reinterpretadas como nodos. Tenga en cuenta que para la transacción de la base de monedas, esta debilidad no es válida: para lograr que una transacción de coinbase se interprete como un hash de dos transacciones, se requiere fuerza bruta de al menos 216 bits (por lo que es inviable, a diferencia de esta debilidad).

Primero, el atacante procede con una segunda mitad de T. En la segunda mitad, algunos campos son fijos, algunos libres y otros parcialmente libres. El valor de LockTime también está parcialmente forzado por fuerza bruta: el atacante se asegura de que el uint32 forzado por el bruto esté entre 500000000 y 1501843940 (hoy como marca de tiempo Unix) o entre 0 y 479042 (la altura actual del bloque). Esto implica que ha transcurrido LockTime. La amplitud del rango numérico combinado es 1002322982, que está cerca de 2 30. Por lo tanto, solo necesita aplicar fuerza bruta a 2 bits del LockTime. Los bits más altos del índice de salida de Previn tx son fuerza bruta, por lo que el índice siempre es inferior a 32768.

El valor es solo parcialmente forzado por fuerza bruta. De los 64 bits de campo, 35 bits se eligen libremente (porque el atacante tiene 2 ^ 36-1 satoshis, por lo que 35 bits libres pueden representar cualquier número menor que la cantidad), mientras que los 29 bits MSB deben ser cero. Si el atacante tiene más BTC, puede reducir el número de bits a fuerza bruta al consumir más BTC en A. Tenga en cuenta que la cantidad no se pierde: como el atacante es un minero, puede cobrar las tarifas de transacción y consumir la transacción produzca y recupere todos los fondos (sin embargo, la creación de la salida Cualquiera-puede-gastar y una transacción T de alto costo pondrá al atacante en el riesgo de que otro minero revierte la cadena de bloques para volver a minar este bloque y recolecte tanto la tarifa como la producción en T ) El atacante puede extraer varios bloques en privado (extracción egoísta) para evitar retrocesos.

El atacante intenta crear una transacción falsa F cuya identificación de transacción coincide con esta segunda mitad de T. Una forma fácil de hacerlo es crear una transacción falsa que tenga un resultado para el pago falso a la víctima y escanear todos los valores posibles para lock_time campo; cuando se agota el espacio, la secuencia de comandos de entrada se modifica ligeramente y se crea un nuevo espacio de 32 bits de valores lock_time. De nuevo, se puede utilizar una técnica similar a AsicBoost para guardar un programador de mensajes de la operación de doble SHA2.

En esta segunda etapa, el atacante intenta forzar la fuerza bruta de la primera mitad de 32 bytes de T. Sea Q el índice de salida de tx elegido en la primera etapa. Él crea una gran cantidad de transacciones que consumen la entrada A y que tienen Q salidas cada una. El último producto será consumido por T. El atacante realiza pequeños cambios en la cola de la transacción y vuelve a realizar hash para obtener el ID, por lo tanto, la creación de nuevos identificadores de transacción requiere solo dos compresiones SHA2 (una para finalizar el hash de transacción y el doble picadillo). Lock_field se puede usar para iterar. El atacante intenta encontrar una transacción cuyos ID de transacción terminan en la cola de 5 bytes elegida en la primera etapa. Llamemos a esta transacción P. Esta transacción consume una salida controlada por el atacante que tiene fondos A. Se necesitarán realizar aproximadamente 2 ^ 40 operaciones para encontrar P. Se puede usar una técnica similar a AsicBoost para guardar un programador de mensajes de la operación de doble SHA2.

Curiosamente, la mitad bruta de la transacción creada en la primera etapa puede reutilizarse tantas veces si se vuelve a realizar la segunda etapa. Los ataques pueden llevarse a cabo en diferentes momentos, en diferentes bloques. Por lo tanto, los siguientes ataques solo requieren fuerza bruta de 40 bits cada uno. Si el número de salidas en P es 33K, el costo amortizado del ataque corresponde aproximadamente a la fuerza bruta de solo 65 bits. Se agrega una transacción final E en el mismo bloque para consumir la producción de T y recuperar los fondos en riesgo.

Un estado del arte Minero Bitcoin alcanza 14 TH / sy cuesta $ 1300 USD. Un atacante que compra 1000 unidades, invirtiendo 1.3 millones de dólares en hardware, puede escanear un espacio de 72 bits en 4 días. Se puede requerir un 1M-10M USD adicional para el diseño y la salida de cinta ASIC, dependiendo de la densidad del nodo. Si ya existe un chip que puede realizar una búsqueda de coincidencia de patrón programada (en lugar de búsqueda de prefijo cero), se guardan los costos de diseño / grabación.

La minería de varios bloques en privado para confirmar la transacción falsa puede ser necesaria para evitar que los otros mineros reorganicen la cadena de bloques para robar las tarifas y el resultado de la transacción T. Si el atacante no está en connivencia con el 51% de los mineros, entonces este le puede costar al atacante millones en potencia de hash alquilada, si está disponible. Si el atacante se confabula con el 51% de los mineros, no hay un costo adicional.

Por lo tanto, en condiciones favorables para el atacante, el ataque puede ser rentable si el atacante puede engañar a uno o más usuarios por 1.3 millones de USD o más en total. Como cualquier actor racional que reciba una gran cantidad de BTC volverá a verificar la recepción utilizando un nodo completo, solo los sistemas autónomos que dependen de las pruebas SPV (como la cadena de bloques Elementos y el puente RSK) pueden sufrir estos ataques.

La misma vulnerabilidad permite que un atacante bifurque la cadena de bloques de Bitcoin en dos sin reconciliación, sin embargo, este ataque cuesta 2 ^ 240 operaciones dobles de SHA2, por lo que el ataque no es práctico. El ataque requiere que el atacante extraiga un bloque A con solo una transacción de coinbase especialmente diseñada de 64 bytes y cree un bloque B competidor con 2 transacciones donde el par de ID de transacción en B se hereda con la transacción de coinbase en A. Ambos bloques se transmiten simultáneamente a diferentes partes de la Red Bitcoin. Por lo tanto, aproximadamente el 50% de la red recibe A y el otro 50%, B. Los dos conjuntos de transacciones en A y B se crean para que consuman diferentes UTXO y / o creen diferentes UTXO, y por lo tanto ambos bloqueos son válidos, pero incompatibles .

Una solución fácil de no bifurcación es que las billeteras SPV verifiquen que cada nodo interno de 64 bits de la prueba SPV no sea una transacción válida. Primero, no hay ninguna transacción de Bitcoin de 64 bytes que pase las verificaciones estándar, por lo que la presencia de dicha transacción debería generar una alarma. Incluso si tales transacciones fueran normales, la probabilidad de que un fragmento aleatorio de 64 bytes se vuelva sintácticamente válido Bitcoin la transacción está cerca de 2 ^ -6. Por lo tanto, el cliente de SPV puede señalar la presencia de dicho nodo de transacción dual como un ataque, y rehusarse a aceptar la prueba de SPV.

Otra forma de arreglar billeteras SPV es exigir, junto con una prueba de Merkle de la inclusión de una transacción E, una prueba de Merkle para la transacción de la base de monedas. Porque construyendo un nodo dual de transacción para el transacción de coinbase requiere una fuerza bruta de 225 bits, mostrando una base de monedas válida y su correspondiente prueba de inclusión de Merkle es suficiente para descubrir la altura del árbol. Tanto la rama E como la rama de la base de monedas deben tener las mismas profundidades de árbol.

Este método tiene un inconveniente: la transacción coinbase puede ser grande, por lo que el método requiere espacio no logarítmico. Si la transacción de coinbase es mayor que 64 bytes, podríamos mostrar como evidencia solo el último estado medio de SHA2 de la primera aplicación SHA2 a la transacción de la base de monedas y la longitud de la transacción en bytes: con estos dos campos se puede reconstruir el id de coinbase, porque SHA2 incrusta la longitud de bit en el último bloque de mensajes. Esto permite que la verificación distinga efectivamente entre un nodo de 64 bytes y la transacción de la base de monedas. La seguridad de estas construcciones es más débil y se basa en la inviabilidad para encontrar pre-imágenes SHA2 de inicio libre. Para complicar las cosas, aún es posible (durante los próximos 145 años) que un minero malintencionado incluya una base de monedas con exactamente 64 bytes. Por lo tanto, el cliente SPV también debe realizar una verificación especial en caso de que la base de monedas tenga exactamente 64 bytes de longitud: en este caso, debe verificar que el campo previn contenga 256 bits cero (de los cuales 216 están almacenados en la mitad izquierda). Actualmente no es factible obtener una imagen previa de un resumen de hash con 216 bits finales.

Sin embargo, otra solución que mantiene la restricción de espacio logarítmico para las pruebas de Merkle es presentar una prueba de inclusión para la ID de transacción más adecuada. En caso de que el número de transacciones no sea una potencia de 2 (un árbol completo), esta identificación aparece duplicada en los dos últimos nodos del árbol, de modo que se puede inferir la altura del árbol. Una solución completa requeriría Bitcoin bifurcación suave para evitar bloques que tienen un árbol completo, que es desagradable.

Otra solución de bifurcación suave es requerir que una nueva “profundidad” de campo que requiera 4 bits esté incorporada en el campo de versión de bloque. Estos nuevos campos deben especificar la profundidad del árbol Merkle menos uno. Al usar 4 bits, se puede especificar un árbol de profundidad 16, que contiene hasta 65K transacciones. Los nodos completos comprueban que la profundidad real del árbol coincide con el valor de “profundidad”. Los nodos SPV pueden verificar que el campo “profundidad” coincida con la longitud de rama de Merkle recibida.

13 de junio de 2018: Luke Dashjr se puso en contacto conmigo y me dijo que ya sabía sobre esta debilidad. Confío en la palabra de Luke que este es el caso, y como dije en el primer párrafo, la debilidad ya era conocida por algunos desarrolladores. Pero todavía no entiendo (1) por qué tanta gente lo sabía, pero lo subestimó mal, (2) por qué no hubo ningún intento de solucionarlo.

banner