Creando una base de datos ultra ligera de publickeys para fuerza bruta

[mcdouglasx]

Creando una base de datos superligrera.

Cuando trabajamos en los puzzles de BTC, pensamos de inmediato en la logica de que teniendo muchas keys en una base de datos aumenta nuestra probabilidad de exito, y esto es cierto.

pero luego nos topamos con que abarcan mucho espacio en disco.

les traigo esta posible solucion.

existe pubkeys pares o impares, y no existe un patron secuencial entre ellas por lo tanto se me ocurrio guardar en secuencia restando al target secuencias "x" cantidades de llaves.

solo que almacendo de manera binaria:

0=pubkey par,
1=pubkey impar.

eso nos permite reducir el espacio en disco de la base de datos a un bit por pubkey, para hacernos una idea 32 millones de pubkeys serian 3.81MB en disco(impresionante).

para esta base de datos necesitamos usar este script de python.

para una sola llave publica

Code:

#@mcdouglasx
import secp256k1 as ice
from bitstring import BitArray
import bitcoin


print("Making Binary Data-Base")


target_public_key = "030d282cf2ff536d2c42f105d0b8588821a915dc3f9a05bd98bb23af67a2e92a5b"

target = ice.pub2upub(target_public_key)


num = 10000 # number of keys.

sustract= 1 #amount to subtract each time, If you modify this, use the same amount to scan.

Low_m= 10

lm= num // Low_m
print(lm)

sustract_pub= ice.scalar_multiplication(sustract)

res= ice.point_loop_subtraction(lm, target, sustract_pub)
binary = ''
for t in range (lm):

    h= (res[t*65:t*65+65]).hex()
    hc= int(h[2:], 16)
       
       
    if str(hc).endswith(('0','2','4','6','8')):
        A="0"
        binary+= ''.join(str(A))
           
    if str(hc).endswith(('1','3','5','7','9')):
        A="1"
        binary+= ''.join(str(A))
       

my_str = bytes(BitArray(bin=binary))

binary_file = open('data-base.bin', 'ab')
binary_file.write(my_str)
binary_file.close()

for i in range (1,Low_m):
    lm_upub= sustract_pub= ice.scalar_multiplication((lm*i)*sustract)

    A1= ice.point_subtraction(target, lm_upub)

    sustract_pub= ice.scalar_multiplication(sustract)

    res= ice.point_loop_subtraction(lm, A1, sustract_pub)
   
    binary = ''
    for t in range (lm):

        h= (res[t*65:t*65+65]).hex()
        hc= int(h[2:], 16)
           
           
        if str(hc).endswith(('0','2','4','6','8')):
            A="0"
            binary+= ''.join(str(A))
               
        if str(hc).endswith(('1','3','5','7','9')):
            A="1"
            binary+= ''.join(str(A))
           

    my_str = bytes(BitArray(bin=binary))

    binary_file = open('data-base.bin', 'ab')
    binary_file.write(my_str)
    binary_file.close()

Si desea crear una base de datos más larga de lo que admite tu memoria ram.

Por ejemplo, 1000 millones de claves y su límite de memoria es 100 millones, divida entre 10 cambiando esta variable:

Code:

Low_m= 10

 debes usar numeros asi, sin residuos.

Code:

num = 10000000000000
Low_m= 10000

Code:

num = 20000000000000
Low_m= 2000

Evite hacer esto o encontrará claves privadas con los últimos números modificados.

Code:

num = 14678976447
Low_m= 23

lo hicimos!

Disponemos de una base de datos enorme, con poco espacio en disco.

Debido a que no existe una secuencia entre claves públicas pares e impares, podemos establecer un margen de colisión de 64, 128, 256...
Con esto quiero decir que a medida que aumenta el margen de colisión, la probabilidad de encontrar una secuencia binaria idéntica disminuye.


¿De qué sirve esto?

Solo necesitamos generar secuencias binarias aleatoriamente y verificar si existen en la
base de datos.

buscando una sola clave pública

Code:

#@mcdouglasx
import secp256k1 as ice
import random
from bitstring import BitArray



print("Scanning Binary Sequence")

#Pk: 1033162084
#cPub: 030d282cf2ff536d2c42f105d0b8588821a915dc3f9a05bd98bb23af67a2e92a5b

#range
start= 1033100000
end=   1033200000
       

while True:

    pk= random.randint(start, end)
   
    target = ice.scalar_multiplication(pk)

    num = 64 # collision margin.

    sustract= 1 # #amount to subtract each time.

    sustract_pub= ice.scalar_multiplication(sustract)

    res= ice.point_loop_subtraction(num, target, sustract_pub)
   
    binary = ''
   
    for t in range (num):
       
        h= (res[t*65:t*65+65]).hex()
        hc= int(h[2:], 16)
       
       
        if str(hc).endswith(('0','2','4','6','8')):
            A="0"
            binary+= ''.join(str(A))
           
        if str(hc).endswith(('1','3','5','7','9')):
            A="1"
            binary+= ''.join(str(A))
   
       
    my_str = binary

    b = bytes(BitArray(bin=my_str))
   

    file = open("data-base.bin", "rb")

    dat = bytes(file.read())
   
    if b  in dat:
        s = b
        f = dat
        inx = f.find(s)*sustract
        inx_0=inx
        Pk = (int(pk) + int(inx_0))+int(inx_0)*7
       
        data = open("win.txt","a")
        data.write("Pk:"+" "+str(Pk)+"\n")
        data.close()
        break

para multiples pubkeys

tambien es posible, aunque la base de datos debe ser secuencial esto no implica que no se puedan guardar multiples pk.

ejemplo:
si tenemos 10 targets y queremos una base de datos de 1.000.000.000 de pubkeys dividimos

base de datos/targets

y cada target individualmente abarcara 100 millones de keys.

script en progreso, estoy corrigiendo unos detalles, pronto lo subire.


Este código es sólo una demostración que puede no estar optimizado correctamente, preferiblemente cree su propia versión en C.


No olvide decir gracias, para motivarme a contribuir con otras ideas.

[albert0bsd]

No olvide decir gracias, para motivarme a contribuir con otras ideas.

Gracias.

Este código es sólo una demostración que puede no estar optimizado correctamente, preferiblemente cree su propia versión en C.

Correcto, no esta optimizado pero la idea se entiende bien!

Code:

#@mcdouglasx
    b = bytes(BitArray(bin=my_str))
    file = open("data-base.bin", "rb")
    dat = bytes(file.read()) 
    if b  in dat:

Esa parte del codigo es el mayor problema

Code:

    if b  in dat:

No hay una manera eficiente e instantea para buscar un sub-array de bits en un array extremadamente grande.

No estoy hablando de una busqueda en 3 o 4 MB estoy hablando de una busqueda en un array de 128 GB o tal vez hasta un 1 Terabyte

La idea es buena no lo niego, le he dado vueltas desde que la lei pero mientras mas grande es la base de datos mas tarda cada busqueda.

Menciono 128 GB por que es lo que se necesita para 2^40 publickeys para ser almacenadas con ese metodo de 1 llave por bit

Code:

>>> 2**40 // 8 // 1024 // 1024 // 1024
128

Un metodo que se me occurre para realizar busquedas mas eficientes es almacenar cada 16 o 32 bytes de tu  base de datos en un bloom filter, de esta manera la base de datos original de 2^40 llaves publicas que requiere 128 GB en disco, puede ser dividida en 4294967296 items de 32 bytes o 8589934592 items de 16 bytes los cuales pueden ser almacenados en 14 GB de RAM para una busqueda mas eficiente en un bloom filter

Code:

>>> 2**40 // 8 // 32 * 29  // 8 // 1024 // 1024 // 1024
14
>>> 2**40 // 8 // 32
4294967296
>>> 2**40 // 8 // 16
8589934592

De esta manera cada que exista un hit en el bloom filter  (1 de cada 100 Millones por motivos de falso positivo) ahora si se realizara la busqueda full en tu base de datos de 2^40 items (128 GB)

Estaba pensado en algun otro tipo de busqueda probabilistica que no sea tan exhaustivo pero aun no doy con nada.

Saludos!

[seoincorporation]

Muy buen artículo colegas, personalmente no lo entiendo al 100% pero si tengo una idea de lo que están hablando.

Desde mi punto de vista este problema ya fue resuelto por el software brainflayer a través de la creacion de los archivos bloom.blf, los cuales nos ofrecen 3 puntos en general.

1.- Optimización de la búsqueda: El archivo Bloom permite realizar búsquedas rápidas y eficientes en grandes conjuntos de datos. Esto es crucial en el contexto de Brainflayer, donde se están probando numerosas combinaciones para encontrar una clave privada válida.

2.- Reducción del tiempo de búsqueda: Al utilizar un archivo Bloom, se puede reducir significativamente el tiempo necesario para buscar y probar claves potenciales. Esto puede hacer que el proceso de fuerza bruta sea más rápido y eficiente.

3.- Ahorro de recursos: El uso de un archivo Bloom puede ayudar a reducir la carga en los recursos del sistema, ya que se pueden realizar búsquedas de manera más eficiente. Esto es valioso en situaciones donde la velocidad y la eficiencia son críticas.

Aún así sigo pensando que hacer fuerza bruta a las llaves privadas es como buscar un grano de arena específico en una playa de kilometros, podríamos intentarlo durante toda la vida sin éxito y si alguien encuentra una forma efectiva de hacer fuerza bruta a las llaves privadas, eso representaría el final no solo para las criptomonedas sino que para el encriptado sha256.

[albert0bsd]

Aún así sigo pensando que hacer fuerza bruta a las llaves privadas es como buscar un grano de arena específico en una playa de kilometros, podríamos intentarlo durante toda la vida sin éxito y si alguien encuentra una forma efectiva de hacer fuerza bruta a las llaves privadas, eso representaría el final no solo para las criptomonedas sino que para el encriptado sha256.

La analogia correcta seria buscando un atomo en especifico en todo el universo visible, pero se entiende

En el programa que desarrolle si utiliza Bloom filters no es el mismo que utiliza brainflayer pero si es la misma estrucutura de datos con algunas variaciones.

El detalle es que los items en estos blooms necesitan de 20 a 30 bits por elemento ingresado en el bloom esto varia dependiendo de la cantidad de hashes realizados en funcion del ratio de error (Falsos positivos) que tengamos generalmente uno en cada 10 millones o algo similar.

Lo que se discute aqui es utilziar una nueva base de datos que solo utilize UN SOLO BIT por item en la base de datos lo cual seria fantastico, pero el problema en este caso es el tiempo de busqueda en la base dados para encontrar una coincidencia.

[mcdouglasx]

No olvide decir gracias, para motivarme a contribuir con otras ideas.

Gracias.

Este código es sólo una demostración que puede no estar optimizado correctamente, preferiblemente cree su propia versión en C.

Correcto, no esta optimizado pero la idea se entiende bien!

Code:

#@mcdouglasx
    b = bytes(BitArray(bin=my_str))
    file = open("data-base.bin", "rb")
    dat = bytes(file.read()) 
    if b  in dat:

Esa parte del codigo es el mayor problema

Code:

    if b  in dat:

No hay una manera eficiente e instantea para buscar un sub-array de bits en un array extremadamente grande.

No estoy hablando de una busqueda en 3 o 4 MB estoy hablando de una busqueda en un array de 128 GB o tal vez hasta un 1 Terabyte

La idea es buena no lo niego, le he dado vueltas desde que la lei pero mientras mas grande es la base de datos mas tarda cada busqueda.

Menciono 128 GB por que es lo que se necesita para 2^40 publickeys para ser almacenadas con ese metodo de 1 llave por bit

Code:

>>> 2**40 // 8 // 1024 // 1024 // 1024
128

Un metodo que se me occurre para realizar busquedas mas eficientes es almacenar cada 16 o 32 bytes de tu  base de datos en un bloom filter, de esta manera la base de datos original de 2^40 llaves publicas que requiere 128 GB en disco, puede ser dividida en 4294967296 items de 32 bytes o 8589934592 items de 16 bytes los cuales pueden ser almacenados en 14 GB de RAM para una busqueda mas eficiente en un bloom filter

Code:

>>> 2**40 // 8 // 32 * 29  // 8 // 1024 // 1024 // 1024
14
>>> 2**40 // 8 // 32
4294967296
>>> 2**40 // 8 // 16
8589934592

De esta manera cada que exista un hit en el bloom filter  (1 de cada 100 Millones por motivos de falso positivo) ahora si se realizara la busqueda full en tu base de datos de 2^40 items (128 GB)

Estaba pensado en algun otro tipo de busqueda probabilistica que no sea tan exhaustivo pero aun no doy con nada.

Saludos!

esa es la parte complicada manejar la base de datos, las dos posibles cosas que se me ocurren ahora implican generar 4096 keys por cada busqueda de 2**40:

con esto quiero decir que puedes

1- convertir cada 64 bits de la base de datos original en decimales, ordenar los numeros ,para facilitar su busqueda, en el script de busqueda serian 4096 keys para asegurarnos que no nos saltemos una posible concidencia:

ejemplo:

si tenemos esta porcion de bits obtenidos en el script de busqueda

1110000011011000111000000100000101100010010010010000101111111110001011100101001 0011010101111010001010101100101000101001001101001100101000011101010011001011100 100011100111001010101011101110100110000010

para encontrar

1000010111111111000101110010100100110101011110100010101011001010= 9655461591863929546 (presente en db ordenada)
   
debemos tranformar en numeros porciones de 64 bits, 64 veces



11100000110110001110000001000001011000100100100100001011111111100010111001010010011010101111010001010101100101000101001001101001100101000011101 010011001011100100011100111001010101011101110100110000010

 
111000001101100011100000010000010110001001001001000010111111111000101110010100100110101011110100010101011001010001010010011010011001010000111010 10011001011100100011100111001010101011101110100110000010

   
1110000011011000111000000100000101100010010010010000101111111110001011100101001001101010111101000101010110010100010100100110100110010100001110101 0011001011100100011100111001010101011101110100110000010

64 veces o hasta coincidir
                                                                                     
1110000011011000111000000100000101100010010010010000101111111110001011100101001001101010111101000101010110010100010100100110100110010100001110101001100101110010001110011100101010101110111010 0110000010

asi asegurarnos que no nos saltemos una posible concidencia.

es decir 64 busquedas en la base de datos ordenada y 4096 keys para cubrir un rango de 2**40

2: puedes usar bf usando como referencia el metodo 1, almacenando cada 64bits.

pero una cosa es la teoria y otra la practica, ni idea de que tan eficiente pueda ser.

[albert0bsd]

1- convertir cada 64 bits de la base de datos original en decimales, ordenar los numeros ,para facilitar su busqueda, en el script de busqueda serian 4096 keys para asegurarnos que no nos saltemos una posible concidencia:

Si, pensé en este y otras variaciones pero ninguna es eficiente, sin un método eficiente de búsqueda la base de datos no se puede utilizar