brainwallets da password

[arulbero]

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:

eta(arulbero,aldo,giovanni,giacomo) nel 2016  --> 37 - 24 - 50 - 43

partenza:blocco 372450, tx 4                       
totale transazioni da estrarre: 3

Per ogni transazione estraggo i seguenti dati:
dati:idtransazione*primo address di partenza*quantità bitcoin trasferiti  (gli asterischi servono solo per facilitare la lettura).

In questo caso:

416f95b89c12b1d8434737de9098cca6c8cbc05618606cbc7d0a2d61baa2f794*12uawNinG9PksdPk6PCCgvoEFUB4FsyZct*0336 <--dati tx1

b0a506c08d6ec17acdc7bf71c46ec41e701c3c148bb93b14a757af2de6655409*1HXfiv2EpL2durJNJuUceBGgHzpewFUH5o*00136486  <-- dati tx 2

2f2a975ddb0b368c21cb2ee7a03476e7b8461722217db62c5ef0d514096ffb29*1HV591kSQ6QC9GPor76UqXnQZrV82Lu7GT*001000077 <-- dati tx 3

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

arulbero+aldo+giovanni+giacomo+416f95b89c12b1d8434737de9098cca6c8cbc05618606cbc7d0a2d61baa2f79412uawNinG9PksdPk6PCCgvoEFUB4FsyZct0336416f95b89c12b1d8434737de9098cca6c8cbc05618606cbc7d0a2d61baa2f79412uawNinG9PksdPk6PCCgvoEFUB4FsyZct0336416f95b89c12b1d8434737de9098cca6c8cbc05618606cbc7d0a2d61baa2f79412uawNinG9PksdPk6PCCgvoEFUB4FsyZct0336b0a506c08d6ec17acdc7bf71c46ec41e701c3c148bb93b14a757af2de66554091HXfiv2EpL2durJNJuUceBGgHzpewFUH5o001364862f2a975ddb0b368c21cb2ee7a03476e7b8461722217db62c5ef0d514096ffb291HV591kSQ6QC9GPor76UqXnQZrV82Lu7GT001000077

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 ...

[reznik15]

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...

[arulbero]

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.

[reznik15]

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?

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...

[arulbero]

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

Per fare un altro esempio, le vecchie versioni di Electrum per generare il loro seed si basavano sulla scelta di 12 parole tra una lista di 1626:
quindi, poiché si avevano 1626^12 possibili combinazioni, l'entropia H = log2(1626^12)=12*log2(1626)=128 bit di entropia (adesso sono passati a una lista di 2048 parole seguendo il bip39, vedi https://www.reddit.com/r/Bitcoin/comments/2jazzc/bip0039_word_list_alert_check_your_backups_now/ per approfondimenti).

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.  

[arulbero]

Poco fa è stato rilasciato Bitcoin Core 0.13.1.

Tra le note di rilascio ho trovato le seguenti:

 
  Increased security for multisig: Bitcoin addresses (both P2PKH addresses
  that start with a '1' and P2SH addresses that start with a '3') use a hash
  function known as RIPEMD-160.  For P2PKH addresses, this provides about 160
  bits of security---which is beyond what cryptographers believe can be broken
  today.  But because P2SH is more flexible, only about 80 bits of security is
  provided per address. Although 80 bits is very strong security, it is within
  the realm of possibility that it can be broken by a powerful adversary.
  Segwit allows advanced transactions to use the SHA256 hash function instead,
  which provides about 128 bits of security  (that is 281 trillion times as
  much security as 80 bits and is equivalent to the maximum bits of security
  believed to be provided by Bitcoin's choice of parameters for its Elliptic
  Curve Digital Security Algorithm [ECDSA].)

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).

[Jack Liver]

è 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

Mounting a successful brute-force collision attack would require at least
O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin
POW has computed more SHA256 hashes than that). But it also requires
O(2^80) storage, which is utterly infeasible (there is something on the
order of 2^35 bytes of storage in the entire world).  Even assuming
doubling every single year (faster than Moore's Law), we're four decades
away from an attacker with THE ENTIRE WORLD's storage capacity being able
to mount a collision attack.

[gbianchi]

...
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.
...

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.

[arulbero]

@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:

La chiave deve essere di una dimensione minima da rendere inutile un potenziale attacco a forza bruta e quindi sicuro il messaggio a meno di furto della chiave o di debolezze strutturali dell'algoritmo. La pratica di rendere pubbliche le specifiche degli algoritmi deriva dall'accettazione del principio di Kerckhoffs formulato da Auguste Kerckhoffs nel 1880 e conosciuto anche come massima di Shannon. Questo principio afferma che bisogna dare per scontato che l'attaccante conosca perfettamente l'algoritmo crittografico e che quindi la sicurezza del messaggio deve dipendere unicamente dalla bontà della chiave.

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.

[Jack Liver]

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  

« Anche se ci piacerebbe che la legge di Moore potesse continuare per sempre, la meccanica quantistica impone alcuni limiti fondamentali sul calcolo computazionale e sulla capacità di memorizzazione di una qualsiasi unità fissa. In particolare è stato dimostrato che un chilo di materia confinata in un litro di spazio può effettuare al massimo 1051 operazioni al secondo su al massimo 1031 bit di informazioni (vedere Seth Lloyd, "Ultimate physical limits to computation." Nature 406, 1047-1054 (2000)). Un pool di storage a 128 bit completamente riempito dovrebbe contenere 2128 blocchi (nibble) = 2137 bytes = 2140 bits; quindi lo spazio minimo richiesto dovrebbe essere (2140 bit) / (1031 bits/kg) = 136 miliardi di kg.

Con il limite dei 1031 bit/kg, l'intera massa di un computer dovrebbe essere sotto forma di energia pura. Secondo l'equazione E=mc2, l'energia residua dei 136 miliardi di kg è di 1,2x1028 J. La massa dell'oceano è circa 1,4x1021 kg. Occorrerebbero 4.000 J per aumentare la temperatura di 1 kg di acqua per 1 grado Celsius e circa 400.000 J per bollire 1 kg di acqua ghiacciata. La fase di vaporizzazione richiede altri 2 milioni di J/kg. L'energia richiesta per bollire l'oceano è circa 2,4x106 J/kg * 1,4x1021 kg = 3,4x1027 J. Quindi, riempire uno storage a 128 bit dovrebbe richiedere più energia che bollire gli oceani. »

[arulbero]

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  

« Anche se ci piacerebbe che la legge di Moore potesse continuare per sempre, la meccanica quantistica impone alcuni limiti fondamentali sul calcolo computazionale e sulla capacità di memorizzazione di una qualsiasi unità fissa. In particolare è stato dimostrato che un chilo di materia confinata in un litro di spazio può effettuare al massimo 1051 operazioni al secondo su al massimo 1031 bit di informazioni (vedere Seth Lloyd, "Ultimate physical limits to computation." Nature 406, 1047-1054 (2000)). Un pool di storage a 128 bit completamente riempito dovrebbe contenere 2128 blocchi (nibble) = 2137 bytes = 2140 bits; quindi lo spazio minimo richiesto dovrebbe essere (2140 bit) / (1031 bits/kg) = 136 miliardi di kg.

Con il limite dei 1031 bit/kg, l'intera massa di un computer dovrebbe essere sotto forma di energia pura. Secondo l'equazione E=mc2, l'energia residua dei 136 miliardi di kg è di 1,2x1028 J. La massa dell'oceano è circa 1,4x1021 kg. Occorrerebbero 4.000 J per aumentare la temperatura di 1 kg di acqua per 1 grado Celsius e circa 400.000 J per bollire 1 kg di acqua ghiacciata. La fase di vaporizzazione richiede altri 2 milioni di J/kg. L'energia richiesta per bollire l'oceano è circa 2,4x106 J/kg * 1,4x1021 kg = 3,4x1027 J. Quindi, riempire uno storage a 128 bit dovrebbe richiedere più energia che bollire gli oceani. »

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.

[Jack Liver]

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.

[arulbero]

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?

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.

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.

[picchio]

...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?
...

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.

...

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.

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.

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

[arulbero]

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...

[picchio]

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.

[gbianchi]

...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?
...

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.

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.

[picchio]

...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?
...

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.

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?

[Jack Liver]

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.

[arulbero]

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?

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:

Baby Step Giant Step Algorithm: This algorithm is a time memory trade-off of the method of exhaustive search.
It requires storage for about radq(n) points, and its running time is roughly radq(n) steps in the worst case

Pollards Rho Algorithm: This algorithm due to Pollard is a randomized version of the baby step giantstep algorithm It has roughly the same expected running time (radq(n/2) steps) as the baby-step giant-step algorithm, but is superior in that it requires a negligible amount of storage