Bitcoin Forum

Cosa significa creare un  brainwallets da una password? ??? ??? ??? ???

Significa generare un indirizzo bitcoin (o meglio, una coppia di chiavi pubblica/privata, da cui ottenere l'indirizzo) a partire da una passphrase nota (in teoria...) solo al proprietario.
Metodo generalmente sconsigliato in quanto troppo a rischio di perdita/compromissione della password.

... per capire meglio,
la generazione avviene da passphrase (12 parole) e non avviene da password (una singola parola), Vero?
A parita di passphrase si ottiene lo stesso indirizzo BTC. Vero?

 ??? :-[ ::)

ti stai confondendo: le 12 parole sono usate per generare il seed di Electrum, quello non ha niente a che fare con un brainwallet

Come faccio a generare un indirizzo BTC da una sola parola?
Con quale software?  :o :o

Scaricati in LOCALE una copia del "Bitcoin Paper Wallet Generator (https://bitcoinpaperwallet.com/)".
Dopodichè lo puoi usare (ricordati in LOCALE e preferibilmente scollegato da Internet) per generare paper wallet usando una password.

Per farlo, una volta che hai caricato la pagina locale del generatore, skippa la parte del generatore di numeri casuali (non ti serve giacchè userai una password per creare le chiavi) e clicca sulla tab "Validate or Decrypt". A quel punto puoi inserire la password. Lui s'incazzerà un pelo e ti dirà che quello che hai inserito non corrisponde ad una chiave privata ecc. e ti chiederà se vuoi usare il testo inserito come password per generare il wallet... tu clicca su OK e il gioco è fatto. Più in basso nella pagina ti stamperà le chiavi private e pubbliche in formato standard (e volendo anche in compresso). Et voilà.

Come ti è stato detto sopra, non è il metodo più sicuro per creare dei paper wallet... se la password è troppo semplice o magari è complicata ma, ad esempio, proviene da una frase di un libro, un passaggio di una poesia, una parte di una canzone ecc. o comunque da materiale pubblico rischi che qualcuno ti svuoti il wallet.

è ben più di un rischio con brainflayer possono processare milioni di password, senza contare che c'è probabilmente una intera botnet dedicata allo scopo di rubare bitcoin dai brainwallets.

se siete interessati guardatevi, Stealing Bitcoin with Math

http://livestream.com/internetsociety/hopeconf/videos/130745035

a un certo punto fanno un test durante la conferenza live dove depositano qualche decina di dollari su un indirizzo generato con brainwallet e in meno di un minuto qualcuno si frega l'intera somma.

Copay utilizza 12 parole di vocabolario per generare il Portafoglio, le stesse che bisogna rimettere nell'ordine corretto per recuperarlo: mi volete dire che questo è un brain wallet e, come tale, vulnerabile?

il discorso è differente visto che in quel caso si utilizza un vocabolario con centinaia di parole e che l'entropia del seed sia abbastanza forte, invece l'utente dream46go si riferiva alla creazione di una password da una sola parola il rischio è altissimo.


qui c'è un esempio molto noto di un brainwallet generato da un oscuro poema in lingua Afrikaans a cui furono derubati ben 4 BTC è un post di ben tre anni fa nel frattempo saranno almeno raddopiate le potenze di calcolo delle botnet.

https://www.reddit.com/r/Bitcoin/comments/1ptuf3/brain_wallet_disaster/

Ehm, scusate sempre la mia niubbaggine: cioè?

vuol dire che il dizionario da dove sono prese le parole che compongono il seed ha così tante parole diverse tra le 12 scelte in fase di generazione da rendere difficlie un attacco di forza bruta, richiedendo tempi di elaborazione nell'ordine di anni e costi nell'ordine di milioni di dollari.

Secondo me sono tutti brainwallet la differenza sta nell'entropia. Se il seed e cioè la sequenza di 12 parole da un dizionario di 2048 parole generato casualmente è uguale alla password nel senso che hanno la stessa entropia allora non c'è differenza tra l'uno e l'altro.

Per farmi capire se il seed è di 128 bit di entropia che dovrebbe corrispondere a 12 parole casuali su un dizionario di 2048 parole allora è equivalente a una password esadecimale casuale del tipo 1234abcd6789cdef1234abcd6789cdef (se è casuale ha 128 bit di entropia).

Per esempio il mio generatore di password mi da una password del tipo: jmMysp5fRSvvszR9Zwp2eWC93EwvHzYa e se uno riesce a memorizzarla allora è perfettamente equivalente al seed di 12 parole casuali che da electrum. Quindi la password e il seed sono equivalente stante il fatto che l'entropia ci sia tutta quando si generano le password/seed e che l'entropia sia di 128 bit.

Questo può interessarvi
https://bitcointalk.org/index.php?topic=1162593.0

lo sono entrambi uno è gerarchico e l'altro no ma a quel punto tanto vale memorizzarsi la private key no ? a complessità siamo li più o meno  ;D

Forse e dico forse il vantaggio rispetto a memorizzarsi direttamente la private key è che uno può scegliersi il grado di sicurezza ed evitare di memorizzarsi una password lunghissima come la private key.

Se uno ritiene che 128 bit di entropia siano sufficienti allora può limitarsi a una password relativamente più breve della private key.

P.S. quanti bit ha la private key?

la private key è di 256 bit, i primi brainwallet nascevano con lo scopo di utilizzare qualcosa di semplice da ricordare come una canzone o una filastrocca ecc finchè poi non sono arrivati con le botnet.

comunque sarebbe sempre un bello sforzo per ritrovarsi alla fine con un singolo indirizzo, mentre per ragioni di sicurezza e privacy è sempre meglio usarne di nuovi come puoi fare con i wallet gerarchici.

Ho letto la storia dell'efficacia di queste botnet, molto carina.

Però avrei da ridire sul fatto che una filastrocca non possa essere utilizzata proficuamente per conservare una password. Per esempio se genero casualmente una password del tipo:
zgrvuhstmdtg5218
poi posso generare (inventarmi) una filastrocca del tipo:
Zoe Grugniva Ruspando Velocemente Un Hash. Stava Timidamente Mangiando Del Tartufo Grigio. 5218

Posso sapere anche quanti bit di entropia ha e pure posso calcolare il valore della password qui sopra: 20 milioni di euro. Supposto il caso in cui ogni tentativo corrisponda a calcolare un hash.

Questo un mio articolo su questo tema che comprende l'esempio citato:

http://www.kensan.it/articoli/Password_sicurezza.php

lo strenght test mi dice che quella password è di "soli" 66.7 bit di entropia mentre la filastrocca che usi per ricordala è di ben 487.7 bit sarebbe meglio usare quella ;D

http://rumkin.com/tools/password/passchk.php


se ti interessa qui c'è il pdf di Ryan Castellucci con le sue considerazioni alle pagine 34-35-36 ci sono esempi di costi e delle potenze in gioco converrebbe usare almeno password a 128 bit di entropia per stare sicuri

https://rya.nc/cracking_cryptocurrency_brainwallets.pdf

Interessante il pdf. Pare che non si usino gli hash e quindi occorre aumentare la lunghezza della password, quindi usare una password casuale da 128 bit.

Sul programma per calcolare l'entropia ci andrei cauto, occorre essere molto conservativi.

21^12*10^4
73558275113866410000

è l'entropia della password del mio esempio supposto che il mio generatore di numeri casuali usi l'entropia del mio Sistema operativo. Sono circa 66 bit (2^66) che coincide con quel che dice il sito.

Sull'entropia della passphrase ci andrei cauto, prima di tutto non sono parole scelte a caso da un dizionario ma, per esempio la prima parola è un nome proprio e non un articolo o un verbo. La seconda frase inizia con un verbo ma non un articolo. Tutto questo riduce l'entropia ma il programma non lo calcola. Meglio essere conservativi e pensare all'entropia di solo 66 bit.

Oppure si possono prendere il numero di nomi propri (Zoe) da un dizionario semplice (1000 parole ad esempio), moltiplicarli per il numero di verbi (grugniva), ancora per il numero di verbi (Ruspando), gli avverbi (Velocemente), ecc. Bisognerebbe essere bravi in grammatica cosa che io non lo sono... :)
Il calcolo è così preciso.

usano le maschere per le pass basate sul comportamento umano è molto probabile che un umano scriva una parola o tutta minuscola o con una maiuscola all'inizio e come segni grafici per pigrizia andra sui soliti: trattini, underscore, chiocciole, asterischi, cancelletti ecc. questo abbatte pesantemente il numero di password da elaborare.

Qual è il metodo per voi più sicuro per generare, memorizzare e conservare una chiave privata?

Il modo più "semplice" (dal punto di vista logico, non pratico) di creare una chiave sarebbe quello di lanciare 256 volte una moneta perfettamente simmetrica, ottenendo una stringa lunga 256 caratteri del tipo 10011100011100....

Ovviamente questo metodo ha tra gli altri il grosso svantaggio derivante dal fatto che la memorizzazione del risultato per un essere umano è praticamente impossibile.
Visto che il dato deve stare su un supporto che sia potenzialmente indistruttibile (no file su hard disk/chiavette, no foglio di carta, niente di fisico) e deve essere facilmente recuperabile all'occorrenza, perchè non utilizzare i dati presenti nella blockchain stessa?

Nella blockchain sono presenti decine di milioni di indirizzi utilizzati almeno una volta (sui circa 2^160 possibili). Questi indirizzi sono in qualche modo messi in relazione tra loro mediante le transazioni che modificano le associazioni indirizzi/bitcoin. Le transazioni sono memorizzate in blocchi. Ci sono al momento circa 450k blocchi e centinaia di milioni di transazioni.

L'idea è quella di selezionare, all'interno di questo enorme "vocabolario", alcune parole chiave, come le id di alcune transazioni, primo address di una transazione, la quantità di bitcoin trasferiti...

I dati della blockchain saranno sempre disponibili (e se non lo fossero allora i vostri btc sarebbero persi in ogni caso), bisogna quindi individuare solo un modo personalizzato di estrarre queste informazioni.

Per mantenere alta l'entropia ognuno dovrebbe scegliere per sè un algoritmo personalizzato e andare a pescare i dati che gli interessano, creando così delle specie di "frasi" particolari molto facili per lui da recuperare all'occorrenza.

Faccio un esempio (ma ovviamente è solo un esempio):
decido di memorizzare l'anno corrente (2016) e il nome di 4 persone (arulbero, aldo, giovanni, giacomo).

Di queste 4 persone, che io ovviamente devo conoscere, so per esempio l'età oggi (e questo è un dato che tranquillamente ricorderò anche tra 10 anni)

età (arulbero,aldo,giovanni,giacomo) nel 2016  --> 37 - 24 - 50 - 43 (sono gli unici dati da memorizzare, oltre l'algoritmo)

A questo punto, nel mio algoritmo, le prime 3 coppie di cifre indicano il blocco da cui inizio a estrarre i dati (372450) e le ultime due cifre corrispondono rispettivamente alla prima transazione (la numero 4 del blocco) e al numero di transazioni totali che estrarrò dalla blockchain


Riassumendo:
In questo caso:


Risultato finale, aggiungo i miei 4 nomi ai dati estratti dalla chain:


Ne faccio hash256 e ottengo la chiave privata:

d3f1ab1fae102c81c6e05b4b7944ac986feafc43a66f47e0a1b6afe40de86f0d (esadecimale)

da cui l'address   1DQ4PbcHB3EUt9gRZbcFwaWZty3SkX9bxt

(per fare i calcoli ho utilizzato i seguenti tool online  http://www.xorbin.com/tools/sha256-hash-calculator  e
 
https://gobittest.appspot.com/Address  ma ovviamente nel caso reale andrebbe fatto tutto in locale).



Potrebbe funzionare o secondo voi l'entropia finale sarebbe troppo bassa?
E' pur vero che alla fine ho solo scelto 3 transazioni consecutive (tx1 --> tx 2 --> tx3) ma l'arbitrarietà dei dati che ho scelto di estrarre da ogni tx e il fatto di combinare stringhe pubbliche con dati personali non dovrebbero garantire una sicurezza sufficiente?
Si potrebbero ovviamente pescare più tx e farlo in modo che siano maggiormente slegate tra loro ...

Seguo con interesse...
Io avevo pensato di fare una cosa simile utilizzando il testo di fumetti famosi sempre reperibili, o come arretrati o nei mercatini dell'usato...

Quindi collegheresti i fumetti alla blockchain?

Io penso che il concetto di "sempre reperibili" soprattutto per oggetti fisici sia discutibile. Per questo ho scelto due insiemi di dati estremamente diversi come caratteristiche da collegare insieme:

1) la mia testa, per definizione privata; ovviamente avendo delle limitazioni posso memorizzare solo alcuni dati personali/familiari molto ma molto semplici e estremamente significativi per me (meglio se sono significativi solo per me, più privati sono i dati meglio è, già le date di nascita a cui alludevo nel post precedente sono in realtà un po' troppo "pubbliche", nel senso di facilmente reperibili; non metterei a questo livello mai informazioni pubbliche tipo squadra del cuore, nome di band, fumetti, record del mondo sportivi, testi canzoni, film, libri --> tutte cose già pubbliche e quindi note!!)

2) la blockchain, pubblica, immodificabile e "eterna" (finchè esiste la blockchain ci sono ancora i miei bitcoin, se non c'è non ci sono più neanche i bitcoin) ma estremamente complessa e ricca di dati  (inoltre con il passare del tempo le sue dimensioni aumentano e di conseguenza dovrebbe aumentare la possibilità di scelta/entropia nella generazione della chiave privata)

Resta da verificare matematicamente quanto sia solida una scelta di questo tipo.

No... pensavo di utilizzare informazioni da ricordare per individuare albo e pagina, poi un algoritmo mentale per ricavare dal testo della pagina una sequenza di caratteri da cui poi ricavare l'hash... solo che non sono mai stato sicuro della validità della cosa.
Quella di usare la blockchain invece, visto la mole di dati e la sua immortalità, mi sembra un'idea migliore.
Ripeto... seguo con interesse...

La scelta di una chiave privata equivale alla scelta di un numero compreso tra 1 e n-1, dove

n=115792089237316195423570985008687907852837564279074904382605163141518161494337 che è circa 2^256.

Questo numero rappresenta il numero di punti della curva ellittica secp256k1, curva usata nella generazione delle chiavi pubbliche e quindi degli address bitcoin (e usata anche nella firma e nella verifica delle transazioni, vedi https://bitcointalk.org/index.php?topic=1339031.0).

Ogni punto della curva ellittica corrisponde a una chiave pubblica, mentre la chiave privata indica la "posizione relativa" che il punto a cui si riferisce occupa rispetto al punto base G (ad esempio il punto numero 1 corrisponde a G, il punto numero 2 corrisponde a G+G=2*G,  la chiave privata 3 <-> punto 3*G,  chiave privata 4 <-> punto 4*G e via dicendo...)

Quindi scegliere una chiave privata equivale dal punto di vista della sicurezza a scegliere un valore a caso tra n valori (dove n è quasi 2^256)? Cioè, dal punto di vista del numero di tentativi che uno sconosciuto dovrebbe fare per indovinare il numero scelto da me, è come se io lo avessi pescato da un sacchetto di 2^256 numeri?

Se così fosse, in media sarebbero necessari 2^256/2 tentativi per indovinare il mio numero, e al massimo in 2^256 tentativi la mia chiave sarebbe scoperta con certezza:  la sicurezza della mia chiave privata sarebbe quindi effettivamente di 256 bit.

Ma in realtà non è così.

Si può dimostrare infatti che l'entropia di una chiave privata nel sistema ECC usato dal bitcoin è di "soli" 128 bit (sostanzialmente il migliore algoritmo Rho di Pollard ha bisogno in media di 2^128 tentativi per poter ricavare la chiave privata da quella pubblica, per approfondire la differenza tra la lunghezza di una chiave in bit e i bit di entropia/sicurezza vedi --> http://crypto.stackexchange.com/questions/26791/how-many-bits-of-entropy-does-an-elliptic-curve-key-of-length-n-provide).

Questo significa in parole povere che l'associazione tra la lista di tutte le chiavi private (numeri) e la lista di tutte le chiavi pubbliche corrispondenti (punti della curva) non è affatto completamente casuale/imprevedibile. (A voler essere pignoli è anche peggio: ad oggi si dice che la sicurezza di ciascuna chiave privata è di 128 bit poiché si conoscono solo algoritmi risolutivi dell'ordine di O(2^(n/2)), ma se un domani si scoprisse l'esistenza di un algoritmo risolutivo dell'ordine di O(2^(n/4)), improvvisamente l'entropia delle nostre chiavi private scenderebbe a 256/4= 64 bit! Di fatto possiamo affermare con certezza solo che l'entropia di queste chiavi non può essere superiore a 128 bit, ma non siamo in grado di dimostrare che non sia minore).

Riassumendo, quando si sceglie una chiave privata di 256 bit su una curva ellittica, la possibilità di un malintenzionato di recuperarla risalendo dalla chiave pubblica è la stessa che avrebbe di indovinare un numero scelto a caso tra 1 e 2^128 (128 bit di entropia).

Come si calcola l'entropia?

L'entropia H è data dal logaritmo in base 2 del numero di possibili combinazioni (equiprobabili), in questo caso è
H= log2(2^128) = 128 bit


A questo punto quale sarebbe l'entropia di una chiave che si basasse sulla scelta di 4 transazioni a caso in un insieme di 10^8 transazioni possibili?

H = log2((10^8)^4)=4*log2(10^8)=4*26,5 = 106 bit

Se (e quando) le transazioni saranno 10^9, allora si aggiungeranno all'entropia iniziale 4*log2(10) = circa 12 bit, per un totale di 118 bit.

Se invece si scegliessero 5 transazioni a caso nella blockchain attuale avremmo:

H = log2((10^8)^5)=5*log2(10^8)=5*26,5 = 132 bit.

Quindi scegliere 1 chiave privata a caso tra tutte le n possibili equivale a scegliere 5 transazioni a caso nella attuale blockchain

La questione delicata a questo punto (a meno che non abbia fatto errori di calcolo finora) è proprio sul come selezionare veramente a caso 5 transazioni nella blockchain (e in un modo tra l'altro facilmente memorizzabile per un singolo essere umano ma difficilmente ricostruibile dagli altri esseri umani).   A naso la mia idea è che bisogna puntare sul fatto che molte vicende significative ma private di ciascuno di noi sono del tutto inaccessibili alla quasi totalità del resto del genere umano, e quindi bisognerebbe partire da lì per costruire un modo personalizzato di selezionare le transazioni.  

Poco fa è stato rilasciato Bitcoin Core 0.13.1.

Tra le note di rilascio ho trovato le seguenti:

Non sapevo che gli indirizzi P2SH avessero una sicurezza diversa da quella dei più tradizionali indirizzi P2PKH e soprattutto non immaginavo che questa sicurezza potesse essere così più bassa ("solo" 80 bit).
Allora l'anello debole della catena che protegge un indirizzo P2SH non sarebbe più ECDSA a questo punto, come si ritiene invece di solito.  Discorso da approfondire.

Da notare inoltre come venga ribadito che i 128 bit di sicurezza delle chiavi private relative a ECDSA sono in realtà solo una stima della sicurezza effettiva di ECDSA (la quale potrebbe essere anche minore).

è di solo 80bit se sei uno dei signer che vuole trovare la collisione tra i due indirizzi per fregarsi tutti i fondi, altrimenti è di 160bit come al solito.


Gavin Anderse in questo post spiega bene le difficoltà di questo tipo di attacco:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012198.html

secondo me e' il punto debole del ragionamento.

Magari uno e' convinto di aver scelto un algoritmo "furbo", e poi si scopre
che buona parte delle persone poco avvezze a questo genere di cose
sceglie algoritmi simili (che so, eta' mia + eta' mamma + eta' babbo ovviamente per fare un esempio)

Inomma lasciare in mano all'untente questo genere di scelta puo' abbassare incredibilmente
il livello di entropia della chiave generata.

@Jack Liver

Grazie per il link.
In pratica la sicurezza dipenderebbe dal fatto che, insieme ai bit, si riduce parallelamente in maniera drastica anche la platea dei possibili attaccanti (allora la cosa ha un senso). Inoltre non avevo considerato il problema dello spazio di archiviazione dei dati, stavo pensando solo alla potenza computazionale necessaria.


@gbianchi :   mi sa che hai proprio centrato il punto. Ho trovato il seguente principio di crittografia:

Il principio di Kerckhoffs --> https://it.wikipedia.org/wiki/Principio_di_Kerckhoffs è esattamente opposto al principio che stavo seguendo io, detto principio della sicurezza mediante segretezza https://it.wikipedia.org/wiki/Sicurezza_tramite_segretezza

Secondo me però ci sono dei dati personali che non possono essere conosciuti da quasi nessun altro, quindi in questo caso la segretezza avrebbe un suo senso. Sicuramente l'esempio delle età non era dei migliori, forse qualcosa legato al dna?

Io in sostanza vorrei fondere un dato pubblico come la blockchain (accessibile a tutti) con un dato privato (e quindi segreto alla stragrande maggioranza dei possibili attaccanti del mondo), quindi vorrei lavorare con un algoritmo semiprivato/semipubblico, unendo (ammesso che sia possibile) i benefici dei due principi.

In pratica chi mi conosce magari può accedere facilmente al mio dna, ma non ha la potenza computazionale necessaria / le competenze per mettere in piedi un attacco decente, chi non mi conosce non può, nonostante possa essere bravissimo e avere ingenti risorse computazionali, accedere ai miei dati personali.

le necessità di spazio di bruteforce per i 128 bit di entropia varrebbe la stessa risposta che Bonwick diede per giustificare i "soli" 128bit di indirizzamento del filesystem ZFS  ;D

Quindi c'è un proprio un limite fisico anche ben calcolato ...
Ma quando si parla invece di "qubit" e di computer quantici, valgono sempre gli stessi limiti? A me sembrava di aver capito che teoricamente dovrebbe essere possibile costruire dei computer quantici nel futuro che risolvano chiavi a 128 bit senza usare una quantità di energia del genere, ma potrei aver capito male io.

sì qualcuno dice entro una trentina d'anni ma già esiste una post-quantum cryptography con svariati algoritmi già pronti e studi a riguardo.

https://en.wikipedia.org/wiki/Post-quantum_cryptography

http://www.etsi.org/images/files/ETSIWhitePapers/QuantumSafeWhitepaper.pdf


per come il Bitcoin è progettato finché non viene speso un indirizzo con il conseguente inserimento nella blockchain della chiave pubblica e la signature, si dovrebbe essere abbastanza quantum-proof già adesso.

Una domanda e una considerazione:

1) ma allora qual è il senso dell'articolo "Ultimate physical limits to computation", se in realtà sarà fisicamente possibile effettuare quel tipo di calcolo? Il limite fisico è solo sulla dimensione dello stoccaggio dei dati ma non sulla potenza di calcolo?

2) come notava già 3 anni Vitalik Buterin --> https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150 c'è anche il problema del tempo di conferma delle transazioni.
In sostanza, poichè nel momento in cui decidi di spendere i tuoi bitcoin sei costretto a esporre la tua chiave pubblica e la tua transazione prima di essere confermata rimane per un po' di tempo sospesa (da pochi secondi a delle ore), l'unica protezione che rimane in quel momento è quella data da ECDSA, non da RIPEMD160. Ovviamente si fa affidamento sul fatto che nessuno, a maggior ragione in un lasso di tempo così esiguo, sia in grado di violare questa protezione.

Non capisco a cosa serva memorizzare le chiavi private in un attacco bruteforce. Io immagino: prova la chiave, funziona? no? allora chiave++ e via senza memorizzare nulla.

In caso di ingenti quantità di BTC puoi minarti il blocco che la contiene o affidarti ad un miner che dia questo servizio.

Come è possibile minarsi il blocco da soli? O si possiede l'hardware adatto (cioè si è un miner), ma praticamente quasi nessuno soddisfa questa condizione!
La seconda opzione è quella di affidarsi a un servizio terzo, ma allora la questione della sicurezza e soprattutto del meccanismo trustless di funzionamento del protocollo bitcoin va a farsi benedire...

Stiamo parlando dell'eventualità che cracchino una chiave da 256 bit in meno di 10-60 minuti quindi lo sforzo dovrebbe essere mirato ad importi considerevoli dove immagino possa convenire anche solo affittare potenza di calcolo necessaria a minare un blocco e poi ti tieni anche il premio e le revenue. Al miner mandi solo il merkle da processare che poi contenga la tua transazione e altre non lo sa proprio.
Un miner potrebbe offrire il servizio e non affideresti i tuoi BTC a lui ma solo la transazione che oggi e' pubblica. Se lui cracca sha e ti fotte i soldi almeno sai chi e' stato e potrebbe avere dei BTC depositati a garanzia presso un escrow.

Nella ricerca di collisioni (ossia nella categoria di problemi analoghi al paradosso dei compleanni) bisogna
memorizzare gli elementi "gia' setacciati" proprio per poter verificare le collisioni.

Se cerco due chiavi che portino allo stesso indirizzo mi quadra il dover memorizzare i dati ma se cerco una chiave che associata ad un altro indirizzo (noto) porta al public address che senso ha memorizzare i tentativi falliti?
Come possono essere utili alla soluzione del problema?

forse per produrre una rainbow table oppure per avventurarsi in un bruteforce multi-hash su tutta la blockchain, l'esempio di Andersen comunque non si riferiva ai computer quantistici ma a potenze che già adesso sarebbero disponibili ( tipo botnet ) e che potrebbero crackare una chiave in 2-3 anni.

Se pensi a un brute force attack allora hai ragione tu. Ma nel caso di ECDSA non avrebbe senso, ci sono 2^256 chiavi!

Si tratta di affrontare il problema del logaritmo discreto, per risolvere il quale ci sono algoritmi che hanno bisogno in media di 2^128 operazioni, quindi in tal caso ha ragione gbianchi, serve anche un po' di memoria per lo stoccaggio dati (ma neanche così tanta se l'algoritmo è buono).

Il problema del logaritmo dicreto è: dati P e Q, trova x tale che

                                                          xP = Q

Nel caso di bitcoin, x è la chiave privata, P è il punto G (fissato) della curva ellittica secp256k1, Q la chiave pubblica.
In sostanza, per quante volte devo sommare G con se stesso per ottenere la chiave privata Q?

G + G + .... + G = Q     dove x è il numero di addendi del primo membro (la chiave privata).

Ora l'algoritmo di Pollard (inizialmente studiato per la fattorizzazione dei numeri primi http://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf  e poi adattato al caso del logaritmo discreto di ECDSA) consiste in questo caso nel trovare 2 coppie di numeri (A,B) e (a,b) tali che:

                                                  aP+bQ=AP+BQ

Se trovi queste due coppie di valori numerici allora è fatta, hai trovato anche x (la chiave privata).

Infatti:
                      aP+bQ   =  AP+BQ
                      aP+bxP  =  AP+BxP
                      (a+bx)P = (A+Bx)P
                      (a-A)P    = (B-b)xP

-->                 (a-A) = (B-b)x              mod n (dove n è l'ordine della curva)
                         x = (a-A)(B-b)^-1      mod n

Tradotto:  bisogna impostare una sequenza (a,b) di numeri pseudo-casuali, si otterrà una sequenza di punti della forma aP+bQ;  mi fermo quando trovo un'altra coppia di (a,b) che produce un punto già calcolato in precedenza, cioè quando nella mia lista ci sono 2 volte lo stesso punto: è questa la collisione trovata (di qui l'applicazione del paradosso del compleanno http://www.mat.uniroma2.it/~geo2/pollardro.pdf), che non è tra due chiavi della stessa chiave pubblica (-> indirizzo bitcoin).

Chiamo le due coppie di numeri che producono lo stesso punto (a,b) e (A,B) e con il ragionamento precedente ricavo così la chiave privata x che costituisce il collegamento tra P e Q (cioè tra G e la chiave pubblica).

EDIT:

Da qui (http://residentrf.ucoz.ru/_ld/0/34_Digital_Signatu.pdf pag. 27) capisco che in realtà l'algoritmo Pollard Rho non occupa troppo spazio/memoria:

[/quote]

Il pollard roh funziona su un altro principio, un percorso sui quadrati fino alla chiusura di un "circolo" quadratico
(di qui il nome roh che indica appunto questa convergenza circolare che graficamente assomiglia alla lettera greca roh)
e per questo non necessita la memorizzazione. Ma sfrutta una proprieta' delle forme quadratiche modulari.

Hai ragione, Baby Giants - Pollard - Pollard Roh ... quante distinzioni!

E dire che avevo linkato anche il file http://www.mat.uniroma2.it/~geo2/pollardro.pdf con la spiegazione  ::)

EDIT: @gbianchi sei sicuro che i moduli quadratici non si usino solo nella fattorizzazione dei numeri primi ma non nel problema del logaritmo discreto?

Io ho guardato qui a pag.7

https://www.google.it/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiLt--qg4DQAhUJcRQKHfaHDToQFgghMAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D8EF3BF1FB7E6DA875FF3D8F4904BC0AD%3Fdoi%3D10.1.1.114.5683%26rep%3Drep1%26type%3Dpdf&usg=AFQjCNHbmP8spzOswu9cJWbePXZZmMBspA

e viene descritto il metodo così come lo ho spiegato io, senza quadrati... Anche in questo caso si forma la rho greca.

Dunque se ricordo bene nei logaritmi discreti si usa un "adattamento" dell'algoritmo che individua un gruppo ciclico
relativo ad una certa base modulare.... non e' uguale all'algoritmo usato per la fattorizzazione, ma il nocciolo
e' sempre l'individuazione di un gruppo ciclico, cosa che permette di evitare la memorizzazione degli elementi gia' setacciati...

Come calcola (B-b)^-1 ?

Per trovare l'inverso di un numero mod n si può usare l'algoritmo di Euclide che si usa di solito per trovare il MCD tra 2 numeri (se poi dal punto di vista dell'implementazione nel calcolatore ci sono dei modi più efficienti non lo so).

Ad esempio:   n = 31  
Qual è l'inverso di 7 modulo 31?

Il problema può essere riscritto così:   7 * s = 1  mod 31  

Ora 7 e 31 sono coprimi, e si può quindi dimostrare che esistono s e t tali che 7s + 31t = 1 (mod 31)

Se riesco a trovare i 2 numeri "s" e "t"  tali che 7s + 31t = 1 (mod 31), allora ho finito, infatti in tal caso

7s = 1 (mod 31) e  s è l'inverso di 7.


L'algoritmo euclideo  (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) permette, dati due numeri
 a e b, di trovare il loro MCD mediante una combinazione lineare:

a*s + b*t = MCD(a,b)  (e nel nostro caso MCD(a,b) = 1 poichè sicuramente ogni numero è coprimo con n che è primo!)

Questo è lo pseudocodice:

 
      

Allora, riguardando bene:
nella scelta dei parametri a' e b' necessari per passare da un elemento

                                   Y = aP + bQ  al successivo elemento Y'= a'P + b'Q

si usa effettivamente una specie di quadrato (ogni elemento Y viene raddoppiato in Y+Y=2Y , almeno se si trova in una certa parte dello spazio, il che equivale ad elevare alla seconda). La scelta dei parametri (a',b')  è ovviamente deterministica ma soprattutto dipende solo dai valori (a,b) dell'elemento precedente.

Quindi si simula solo la classica passeggiata casuale nello spazio di tutti gli elementi della curva.  

Si può quindi non tenere traccia di tutti gli elementi Y=aP+bQ generati poichè si sa che a un certo punto si deve entrare in un "sottogruppo" ciclico della curva ellittica (la parte chiusa della lettera rho, anche se non è propriamente un sottogruppo nel senso matematico del termine; non appena si genera una collisione gli elementi per forza iniziano a ripetersi a causa del modo univoco con cui viene generato un elemento a partire dal precedente).
L'entrata nel ciclo (o la sua "chiusura", se si immagina visivamente la lettera rho greca) è causata quindi da una prima collisione (vedi paradosso dei compleanni, che avviene in media dopo rad(n) passi), prima collisione però (e qui c'è il punto importante) che non è necessario che sia rilevata (quindi non c'è necessità di memorizzare enormi montagne di dati!). A partire da quella prima collisione si genera quindi (a causa del metodo deterministico) sempre la stessa sequenza di elementi (che formano appunto un ciclo); da notare che il ciclo è una sottosequenza del percorso effettuato per arrivare alla prima collisione, quindi il ciclo stesso non è costituito da più di rad(n) punti.

Per rilevare una qualsiasi ripetizione tra due elementi (percorrendo il ciclo si deve tornare ogni volta sugli stessi elementi, non serve individuare il primo elemento che si ripete, quello che ha chiuso il ciclo!) è sufficiente usare un buffer con pochissimi dati in memoria; i dati vengono aggiornati di tanto in tanto mediante un algoritmo che non impatta in maniera sostanziale sul lavoro computazionale complessivo fino a che non si realizza una collisione anche all'interno del buffer di memoria (collisione che deve arrivare per forza quando si è dentro un ciclo, si registra così una collisione utilizzabile dal punto di vista pratico per ricavare la chiave privata).

L'algoritmo di rilevazione della collisione all'interno del buffer nel caso migliore trova la collisione appena si è entrati nel ciclo, nel caso peggiore impiega un numero di iterazioni ulteriori pari alla lunghezza del ciclo stesso

L'algoritmo è il seguente (tratto da https://maths-people.anu.edu.au/~brent/pd/rpb231.pdf):