Keyhunt (Hilo en Español)

[albert0bsd]

Mirror del hilo en Ingles ( Keyhunt - development requests - bug reports)

Quiero abrir este Tema para hablar de la herramienta para CPU de Codigo abierto que he dessarrollado Keyhunt disponible en github

Keyhunt utiliza el algoritmo BSGS para intentar encontrar llaves privadas mediante el uso de la llave publica de una direccion de bitcoin. El principal objetivo de esta herramienta es tratar de encontrar los desafios/rompecabezas de bitcoin descritos en Bitcoin puzzle transaction ~32 BTC prize to who solves it Acutalmente los desafios tienen mas de 800 bitcoin pendientes por reclamar

Keyhunt tambien utiliza otros metedos tambien como: address, rmd160, xpoint

Version actual 0.2.230430 Satoshi Quest

Como Utilizarlo

Descarga y compila (Sigue la documentacion en Ingles   )
Ejecutalo contra el puzzle 66 (modo address)

Code:

./keyhunt -m address -f tests/66.txt -b 66 -l compress -R -q -s 10

Se necesita agregar el parametro -t <Numero de Hilos> para mejorar la velocidad

Ejecutalo contra el puzzle 130 (modo BSGS)

Code:

./keyhunt -m bsgs -f tests/130.txt -b 130 -q -s 10 -R

Se necesita agregar el parametro -t <Numero de Hilos> para mejorar la velocidad, asi mismo como el parametro -k <factor>

[DdmrDdmr]

No me he interesado en demasía con anterioridad por los rompecabezas del estilo, por lo que me iría bien conocer la respuesta a algunas preguntas básicas que me surgen (exponiendo mi pleno desconocimiento del asunto de paso):

Q1) ¿Quiénes y por qué motivo montan estos puzles a resolver?

Q2) ¿Alguien ha llegado a resolver alguno históricamente?

Q3) ¿Estamos hablando de obtener la clave privada a partir del conocimiento de la clave pública o de la dirección pública?

Q4) Si Q3 es cierto ¿qué diferencia hay entre intentar resolver un puzle e intentar obtener la clave privada de una dirección con TXs realizadas?

Q5) Entiendo que por BSGS te refieres a ésto. ¿Puedes explicar los principios fundamentales en términos llanos?

[albert0bsd]

Historia de los desafios/rompecabezas de bitcoin.

Especificamente los que nacieron con la TX 08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

El 15 de Enero del 2015 una transacción fue realizada con un solo input hacia 256 output con UXTOS secuenciales de 0.001 BTC hasta 0.256 BTC.

La dirección que recibió 0.001 BTC es 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH la cual pertenece al Punto generador de la Curva Elíptica Secp256k1 llave privada numero 1

Alguien pensó que las demás direcciones estaban de cierta forma ordenadas de alguna forma y comenzaron a ir resolviendo los rompecabezas de menor denominación.

El único patrón discernible que se consiguió en su momento fue que cada dirección se encontraba en un rango de bit específico, es decir que la dificultad para resolver cada dirección crecía exponencialmente

Nota que se le llamaron rompecabezas ya que se pensaba que tenían algún orden o manera de resolverse ya sea mediante regresión lineal o alguna otro patrón oculto, sin embargo ahora se sabe que son desafíos.

Durante el transcurso del año 2017 un usuario en bitcointalk, apuntó que el rompecabezas era bastante extraño ya que si se trataba de resolver direcciones solo por fuerza bruta las direcciones arriba de 160 bits no tenían sentido dado que la seguridad de las direcciones esta limitada por el hash rmd160 ya que si en teoria tienes el poder de cómputo para resolver una dirección de 160 bits, realmente serias capaz de encontrar cualquier dirección.

En este momento el autor del desafío/rompecabezas sale a luz y publica su primer y único mensaje en el foro bajo el usuario de saatoshi_rising indicando que es un desafío realizado llaves privadas aleatorias confirmando que cada llave está en un rango de bit diferente. Asimismo indico que movería los balances de los desafíos del 161 al 256, asi como también incrementar los desafíos no resueltos en un factor de 10

This puzzle is very strange. If it's for measuring the world's brute forcing capacity, 161-256 are just a waste (RIPEMD160 entropy is filled by 160, and by all of P2PKH Bitcoin). The puzzle creator could improve the puzzle's utility without bringing in any extra funds from outside - just spend 161-256 across to the unsolved portion 51-160, and roughly treble the puzzle's content density.

If on the other hand there's a pattern to find... well... that's awfully open-ended... can we have a hint or two?

I am the creator.

You are quite right, 161-256 are silly.  I honestly just did not think of this.  What is especially embarrassing, is this did not occur to me once, in two years.  By way of excuse, I was not really thinking much about the puzzle at all.

I will make up for two years of stupidity.  I will spend from 161-256 to the unsolved parts, as you suggest.  In addition, I intend to add further funds.  My aim is to boost the density by a factor of 10, from 0.001*length(key) to 0.01*length(key).  Probably in the next few weeks.  At any rate, when I next have an extended period of quiet and calm, to construct the new transaction carefully.

A few words about the puzzle.  There is no pattern.  It is just consecutive keys from a deterministic wallet (masked with leading 000...0001 to set difficulty).  It is simply a crude measuring instrument, of the cracking strength of the community.

Finally, I wish to express appreciation of the efforts of all developers of new cracking tools and technology.  The "large bitcoin collider" is especially innovative and interesting!

Se sabe que si es el autor del desafio ya que el incremento que el menciono si sucedio TX: 5d45587cfd1d5b0fb826805541da7d94c61fe432259e68ee26f4a04544384164

En el año 2019 otro movimiento que el autor realizó fue liberar las llaves públicas de los desafíos no resueltos que terminaban en 5 y 0 es decir desafios  65, 70, 75, … 160.
TX: 17e4e323cfbc68d7f0071cad09364e8193eedf8fefbcbd8a21b4b65717a4b3d3

Tras este ultimo cambio varios de esos desafios fueron resuletos inmediatemente o en los dias posteriores.

Para este momento tenemos 2 tipos de desafíos:
-Los que solo se conoce su dirección, de los cuales solo se ha resuleto hasta el desafio de 64 bits, Sigiente en la lista es el de 66 bits
-Los que tienen también llave pública disponible, de estos solo se ha resuelto hasta el desafio 125, siguiente en la lista es el de 130 bits

Recientemente este año, los desafíos no resueltos hasta el momento fueron incrementados una vez mas en un factor de 10.
https://mempool.space/tx/12f34b58b04dfb0233ce889f674781c0e0c7ba95482cca469125af41a78d13b3

Asi ahora el desafío de 66 bits tiene 6.6 BTC y el desafío de 160 bits tiene 16 BTC

No me he interesado en demasía con anterioridad por los rompecabezas del estilo, por lo que me iría bien conocer la respuesta a algunas preguntas básicas que me surgen (exponiendo mi pleno desconocimiento del asunto de paso):

Q1) ¿Quiénes y por qué motivo montan estos puzles a resolver?

Q2) ¿Alguien ha llegado a resolver alguno históricamente?

Q3) ¿Estamos hablando de obtener la clave privada a partir del conocimiento de la clave pública o de la dirección pública?

Q4) Si Q3 es cierto ¿qué diferencia hay entre intentar resolver un puzle e intentar obtener la clave privada de una dirección con TXs realizadas?

Q5) Entiendo que por BSGS te refieres a ésto. ¿Puedes explicar los principios fundamentales en términos llanos?

Excelenes preguntas.

R1) Posiblemente satoshi o alguien con la misma filosofia que el, el motivo tal como se cito en el unico mensaje del autor es medir la el poder de computo de la comunidad, posiblemente se trate de medir cuando es tiempo de realizar algun HardFork para otro esquema de cifrado posiblmenente algun cifrado post-cuantico.

R2) La mayoria de los que resolvieron los desafios no lo hicieron publico con Excepcion de JeanLucPons y Zielar que resolvieron los desafios de 90, 95, 100, 105, 110 y 115 bits.
https://en.wikipedia.org/wiki/Discrete_logarithm_records

On 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software [39] based on the Pollard Kangaroo on 256x NVIDIA Tesla V100 GPU processor and it took them 13 days. Two weeks earlier - They used the same number of graphics cards to solve a 109-bit interval ECDLP in just 3 days.

R3) Como se comento al principio solo se trataba direcciones sin llave publica expuesta, sin embargo esto cambio cuando se liberaron las llaves publicas en el año 2019.
Entonces ahora tenemos 2 variantes para resolver los desafios, fuerza bruta pura para las direcciones y tenemos kangaroo y BSGS para las llaves publicas.

R4) La diferencia es que en este caso se espera que las llaves privadas esten en un rango menor de bits (Menores a 160) y actualmente estamos atorados con 130 bits.
Sin embargo las llaves de las carteras que no entran en este desafio (Carteraas reales) se espera que esten en un rango de 256 bits La diferencia es abismal ya que crece exponencialmente.

R5) Si ese es, te dejo otro link Elliptic Curve Cryptography: breaking security and a comparison with RSA
Aqui va mi explicacion, basicamente se trata de generar una table de datos precalculados, estos datos son las llaves publicas que estan ligadas a las llaves privadas desde 1 hasta N, donde N puede ser un numero cercano a los 4 mil millones o mucho mas, aqui el limite es la cantidad de memoria RAM disponible.
Una vez que ya tienes esta tabla en memoria, el siguiente paso es realizar restas a las llaves publicas objetivo, con el fin de Moverlas del rango esperado al rando de nuestra tabla y comparar si el resultado de la resta se encuentra en nuestra, si esto se cumple es facil calcular el valor de la llave privada.

Ejemplo, digamos que nuestra tabla tiene las llaves publicas del 1 al 1000
Nuestra llave obejtivo es 2048, aqui van las restas y comparaciones
2048 - 0 = 2048, Esta el resultado en nuestra tabla? NO
2048 - 1000 = 1048, Esta el resultado en nuestra tabla? NO
2048 - 2000 = 48, Esta el resultado en nuestra tabla? SI, posicion  48, Calculando la llave privada es 48 + 2000

En el link que pase se encuentra mejor explicado: Elliptic Curve Cryptography: breaking security and a comparison with RSA

[DdmrDdmr]

Gracias por las explicaciones detalladas @albert0bsd. No es que sea un asunto trivial de seguir, pero con las explicaciones dadas creo que hay una buena base para poder profundizar en mayor grado cuando uno tenga disponibilidad de tiempo a tales efectos.

En relación a R4, no sé si conoces alguna estimación del tiempo de resolución, y de la incidencia de alguna parametrización del algoritmo en dicho tiempo (por tener alguna noción al respecto). Lógicamente dependerá del equipo utilizado, pero aun así, para un equipamiento tipo determinado (el que digas), ¿por dónde irían los plazos esperados?

[seoincorporation]

R2) La mayoria de los que resolvieron los desafios no lo hicieron publico con Excepcion de JeanLucPons y Zielar que resolvieron los desafios de 90, 95, 100, 105, 110 y 115 bits.
https://en.wikipedia.org/wiki/Discrete_logarithm_records

On 16 June 2020, Aleksander Zieniewicz (zielar) and Jean Luc Pons (JeanLucPons) announced the solution of a 114-bit interval elliptic curve discrete logarithm problem on the secp256k1 curve by solving a 114-bit private key in Bitcoin Puzzle Transactions Challenge. To set a new record, they used their own software [39] based on the Pollard Kangaroo on 256x NVIDIA Tesla V100 GPU processor and it took them 13 days. Two weeks earlier - They used the same number of graphics cards to solve a 109-bit interval ECDLP in just 3 days.

Personalmente tenía esta duda desde hace varios meses y no encontraba información al respecto, creo que a todos nos extraña el echo de que se resolvieran estos numeros del puzzle dando saltos de 5 en 5, como si hubiera cierta lógica en los números. Y ver el poder de procesamiento que han usado para esta tarea es algo impresionante. No dudo que con los BTC que obtuvieron de esos acertijos invirtieron mas en tarjetas de video para seguir buscando esas llaves privadas.

Gracias por el hilo en español, este acertijo es how en día el mayor desafío en Bitcoin que tenemos y cada día se une mas gente. Personalmente me gusta usar esta página para ver si alguien mas ha encontrado una nueva clave: https://privatekeys.pw/puzzles/bitcoin-puzzle-tx

[darbitmobilerecovery]

La verdad que no entiendo nada del tema, me parece chino basico, pero igualmente dejo mis felicitaciones para vos, por haber desarrollado el programa, traer el hilo desde el ingles, y ademas explicar todas estas cuestiones de forma detallada.

Gran incorporacion la tuya a las filas del local español!

[seoincorporation]

La verdad que no entiendo nada del tema, me parece chino basico.

Suena como un tema complejo ya que involucra cryptografía y fuerza bruta, cuando te lo explican de forma simple es fácil de entender.

Estamos ablando de un acertijo en el que alguien generó llaves privadas de forma aleatoria en ciertos rangos numérico:

Code:

2^0 ≤ random key < 2^1 — 0.001 
2^1 ≤ random key < 2^2 — 0.002 
2^3 ≤ random key < 2^3 — 0.003
...
2^255 ≤ random key < 2^256 — 0.256

Así que las primeras llaves privadas fueron fácil de encontrar en exadecimal:

Code:

0000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000003
0000000000000000000000000000000000000000000000000000000000000007
... hasta que llegamos al acertijo 65 ya resuelto:
000000000000000000000000000000000000000000000001a838b13505b26867

Siendo un total de 159 direcciones aún quedan muchos premios por reclamar, y las mas complejas tienen un premio de 15BTC cada una.

Es por esto que se requiere software especializado para el acertijo, y es ahí donde entra Keyhunt el cual es un software que busca la llave privada el el rango mencionado. Pero como la complejidad actual es muy grande se requiere de mucha gente para encontrarla, incluso hay ciertos "Pools" en donde grupos de personas unen su hardware para la búsqueda.

[albert0bsd]

En relación a R4, no sé si conoces alguna estimación del tiempo de resolución, y de la incidencia de alguna parametrización del algoritmo en dicho tiempo (por tener alguna noción al respecto). Lógicamente dependerá del equipo utilizado, pero aun así, para un equipamiento tipo determinado (el que digas), ¿por dónde irían los plazos esperados?

Es una Loteria Galactica

Ya vamos a empezar a hablar de temas tristes, realmente las posibilidades son muy bajas, sin embargo si no se participa las posibilidades son Cero.

Hace tiempo publique un pequeño codigo para estaimar las velocidades: https://github.com/albertobsd/simulations#speeds

Ahi mismo puedes date una idea del tiempo necesario dependiendo de la velocidad que se tenga y del desafio o nivel de bits que se quiere romper, por ejemplo:

Code:

Puzzle 64 @ 1 Gigakeys/s  (10^9):       292 years
Puzzle 64 @ 1 Terakeys/s  (10^12):      0 years
Puzzle 68 @ 1 Gigakeys/s  (10^9):       9359 years
Puzzle 68 @ 1 Terakeys/s  (10^12):      9 years

Puzzle 63 resuelto el 7 de Junio de 2019
Puzzle 64 resuelto 9 de septiembre de 2022

En este caso se trata para desafios de solo fuerza bruta. El calculo es lineal, y cada nivel de bit adicional incrementa en un factor de 2 el desafio previo.

Para el caso de las llaves publicas ni lo quiero mencionar:

Para BSGS los tiempos son los siguientes:

Code:

Puzzle 120 @ 1 Exakeys/s  (10^18):      21074771622 years
Puzzle 125 @ 1 Exakeys/s  (10^18):      674392691925 years
Puzzle 130 @ 1 Exakeys/s  (10^18):      21580566141612 years

Puzzle 120 resuelto el 27 de Febrero de 2023
Puzzle 125 resuelto el 9 de Julio de 2023

Cabe mencionar que estos 2 ultimos rompecabezas fueron resueltos por la misma persona/organizacion: 3Emiwzxme7Mrj4d89uqohXNncnRM15YESs

Por lo tiempos de resolucion posiblemente fueron resueltos utilizando Kangaroo y alguna granja de GPUs or algun otro hardware especializado, sin embargo la persona que los resolvio no se pronunciado en ningun lado, por lo menos no publicamente.

Dejo aqui una lista de todos estos desafios con vario datos como llaves publicas, direcciones, fecha de resolucion en caso de aplicar etc: Bitcoin Challenges