Sicurezza di SHA256 e Bitcoin

10

La rete Bitcoin usa SHA256 come componente principale del suo design. Non sono esperto di crittografia, ma a me sembra che di solito sia solo questione di tempo prima che vengano scoperte le vulnerabilità della sicurezza (MD5 ad esempio e molte altre).

Quali sono le probabilità che vengano scoperte vulnerabilità simili in SHA256 ad un certo punto e quanto sarebbe dannoso per la rete Bitcoin?

    
posta Gilles 09.06.2011 - 11:06
fonte

6 risposte

12

L'unico modo noto per accertare la sicurezza di un algoritmo crittografico è di lasciarlo sotto stretta sorveglianza di centinaia di crittografi per diversi anni, e vedere cosa viene fuori. Quindi la prospettiva giusta qui è storica.

MD5 era pubblicato nel 1992 ; in realtà è stato progettato l'anno prima (1991). Nel 1993 vennero individuati i primi punti deboli, poi maggiori debolezze nel 1996 (collisioni sulla funzione di compressione, rilevate da Dobbertin). Ci sono voluti 8 anni per trasformare queste debolezze in collisioni reali da parte di Wang, nel 2004. Sette anni dopo, nel 2011, possiamo creare collisioni MD5 a volontà (e in modo molto più efficiente rispetto al metodo originale di Wang), ma preimage e seconde Le resistenze di preimage di MD5 sono ancora migliori di sempre.

Da questo possiamo dedurre che quando le debolezze si trovano nella funzione di hash, non compaiono da un giorno all'altro: abbiamo abbastanza tempo per reagire. Inoltre, le prime debolezze dell'MD5 sono state scoperte solo un anno dopo la sua pubblicazione, e questo era nei primi anni '90 quando la ricerca pubblica in crittografia coinvolgeva molte meno persone di oggi.

Vediamo cosa offre questo SHA-256: pubblicato per la prima volta nel 2001; dieci anni dopo (2011), non abbiamo ancora alcun indizio sul minimo accenno a una debolezza. Ciò sarebbe indicativo del fatto che SHA-256 sia effettivamente robusto e le collisioni per SHA-256 non sono proprio dietro l'angolo. Inoltre, non ho guardato nel dettaglio i dettagli del protocollo Bitcoin, ma sembra che le collisioni non rappresentino un pericolo reale per Bitcoin: dipende piuttosto dalla resistenza di pre-acquisizione, per cui non solo SHA-256 è solido come roccia, ma anche MD5 sarebbe essere ancora affidabile.

Tuttavia , è pericoloso creare statistiche su una singola misura. Nel 2007, è stato stimato che c'era un rischio relativamente alto che gli attacchi a MD5 potessero essere trasportati a SHA-1 e poi a SHA-256/512 - questo ha spinto il NIST a organizzare il Concorso SHA-3 . Si è scoperto che gli attacchi a SHA-1 hanno in qualche modo smesso di progredire, e non c'è alcun attacco su SHA-2. Se questo è dovuto al fatto che SHA-2 è veramente robusto, o perché tutti i crittografi sono impegnati a tentare di violare i candidati SHA-3, non è noto (ma la mia opinione è la prima: SHA-2 è un algoritmo di hash sicuro). p>     

risposta data 29.09.2011 - 22:47
fonte
7

Le vulnerabilità possono verificarsi a diversi livelli qui.

1) Si può scoprire un attacco teorico che riduce la complessità necessaria per un attacco riuscito, ma non abbastanza basso da essere pratico. Cioè da un POV tecnico l'algoritmo è considerato rotto, ma è comunque sicuro per qualsiasi uso pratico.

2) Viene scoperto un attacco che riduce la complessità a un livello che può essere praticamente eseguito da un attacco distribuito di grandi dimensioni entro un tempo ragionevole. L'algoritmo può ancora essere utile per scopi specifici (ad esempio MD5 per identificare gli errori di download di un file), ma è un No Go per qualsiasi cosa che richieda sicurezza a lungo termine, come le firme digitali.

3) L'algoritmo è completamente rotto, chiunque può farlo sul suo PC di casa. Dimenticalo e tutto ciò che lo utilizza come componente centrale. La verifica del download potrebbe essere ancora OK, ma non molto oltre.

Ci sono alcune leggi fondamentali che dovrebbero essere considerate qui. In primo luogo, non puoi provare che un algoritmo sia sicuro, puoi solo provare che non è sicuro, anzi, cracciandolo. Secondo, gli attacchi migliorano sempre, non peggiorano mai. Cioè la conoscenza approfondita degli attacchi precedenti non sarà dimenticata.

Per le possibilità, una scoperta può essere fatta domani. O tra due anni. O tra vent'anni. SHA-1 è rotto (http://en.wikipedia.org/wiki/SHA-1) e da qualche parte tra 1 e 2, e SHA256 utilizza una struttura di base simile. Ma ancora non si conoscono attacchi contro SHA256, AFAIK.

    
risposta data 09.06.2011 - 12:10
fonte
7

Sembra che il funzionamento interno di Bitcoin sia che firma, utilizzando l'algoritmo ECDSA, il doppio applicato (il primo hash è stato nuovamente cancellato) SHA256 hash della transazione.

È sempre questione di tempo prima che vengano rilevate vulnerabilità di sicurezza. Ma tende ad essere più vulnerabilità di sicurezza da una cattiva implementazione del miglior algoritmo che da una buona implementazione di un algoritmo accettabile.

Oppure, il peggiore dei due mondi, una scarsa implementazione di un algoritmo scadente. È stato utilizzato un attacco SQL injection per ottenere i dettagli dell'account sul Monte. Exchange Bitcoin Gox, dove stavano memorizzando gli hash MD5 delle password nel loro database, inclusi quelli degli amministratori di exchange.

Che non ha assolutamente nulla a che fare con la sicurezza crittografica di SHA256, ma è stato un po 'dannoso per la rete Bitcoin.

    
risposta data 21.08.2011 - 15:38
fonte
4

Ci sono un paio di cose da capire.

Il primo è capire la forza di un algoritmo di hashing. Per replicare un hash, il livello di difficoltà è la dimensione completa della chiave hash. Quindi, se hai già un hash MD5 e vuoi trovare un pattern che lo abbini, il difficile è un 128 bit completo. Ma a causa di problemi rilevati, potremmo riuscire a farlo con solo 100 bit di difficoltà. Ma il massimo che possiamo fare è 60 bit di difficoltà. Quindi, crack MD5 nel modo è ancora impossibile con la conoscenza / hardware di oggi.

Ma c'è una seconda preoccupazione per gli algoritmi di hash: quello di creare due cose che hanno un nuovo valore hash. È una specie di attacco di tipo "meet-in-the-middle". È metà del numero di bit di difficoltà, quindi per un algoritmo a 128 bit, è solo 64 bit di difficoltà. Con i bug noti in MD5, questa difficoltà diventa più simile a 50 bit, ben all'interno della capacità dei computer moderni.

Questo problema di meet-in-the-middle significa che SHA-256 ha solo 128 bit di difficoltà. Ciò che questo significa per Bitcoin consiste nel creare due transazioni con hash allo stesso valore.

Come MD5, non spezzeremo tutto in una volta. Invece, le persone si raderanno un po 'di difficoltà alla volta, proprio come hanno recentemente rasato 2 bit di difficoltà per AES. Quindi, passerà da 128 bit di difficoltà, a 125, a 120, a 115 e così via.

Con la legge di Moore che aggiunge un po 'di potenza di cracking (60 bit oggi, 61 bit l'anno prossimo, 62 bit l'anno dopo) e SHA-256 che perdono un po' di forza incontrollata nel mezzo ogni anno Ciò significa che ci restano circa 30 anni prima che diventi possibile creare transazioni Bitcoin.

Bitcoin fa alcune cose per renderlo più difficile, ma probabilmente nei prossimi 30 anni qualcuno troverà un modo per aggirare questi problemi. Quindi, immagino casualmente che Bitcoin abbia una durata di 30 anni.

Questo è più della valuta per molti paesi mal gestiti.

    
risposta data 24.08.2011 - 08:04
fonte
3

Il tempo può forse essere indovinato basandosi su quanto tempo sono sopravvissuti altri algoritmi ampiamente utilizzati prima di essere trovati difettosi, ma ovviamente non significa che tu possa fare previsioni utili.

Una soluzione intelligente che un mio amico ha spiegato per un grande progetto era semplicemente utilizzare due algoritmi di hashing in parallelo (cioè, a ciascun file erano associati due hash), quindi scambiare uno se è rotto. La possibilità che gli algoritmi due siano interrotti nello stesso tempo, e che la combinazione dei due sia anche fragile, è probabilmente 10 ^ lotti ^ molto più piccola della possibilità che ogni dato singolo l'algoritmo ever si rompe e come bonus hai un po 'di tempo per occuparti della transizione verso un nuovo hash quando uno di questi è rotto.

    
risposta data 09.06.2011 - 14:50
fonte
0

MD5 è un valore hash di 128 bit mentre SHA256 è 256 bit. Quindi la possibilità di una cosiddetta collisione è molto più piccola per SHA256 rispetto a MD5.

Anche MD5 è un vecchio veterano degli anni '90 che presumo mentre SHA256 ha circa un decennio e avrebbe bisogno di qualche calcolo fantastico per ottenere una collisione. Ma nel caso succedesse, sarebbe graduale e credo che ci sarebbe un po 'di tempo ( SHA-3 sarebbe fuori per allora ) e loro (BitCoin) potrebbero quindi migrare ma poi questo è un compito mastodontico da solo e ci sono altre persone con le competenze per analizzare quella parte (non mi adatto affatto)

Ancora un sacco di tempo per un tale compromesso su SHA256.

    
risposta data 09.06.2011 - 12:07
fonte

Leggi altre domande sui tag