Come possono i cracker ricostruire gli hash delle password salate 200k così velocemente?

34

Sto facendo ricerche per un breve discorso sulla sicurezza del web e ho trovato un articolo sull'hack di formspring, che mi ha incuriosito. Loro rivendicano di aver usato SHA-256 + salt

We were able to immediately fix the hole and upgraded our hashing mechanisms from sha-256 with random salts to bcrypt to fortify security (July 10th, 2012)

... tuttavia gli attaccanti hanno richiesto hanno trovato ~ 200k password all'interno dei 400k dataset pubblicati (hanno 11 milioni di utenti, è IMHO probabile che molti di loro siano stati copiati).

About half of the 400,000 hashes have already been reconstructed by password crackers. (July 11th, 2012)

Questo mi sembra sospetto. So che senza usare PKCS # 5 o tecniche simili, la sicurezza di SHA-256 è limitata, ma quanta potenza di calcolo avrebbero bisogno di trovare così tante password così veloci?

La mia ipotesi è che la formaprodasse mentendo sull'hashing. Qualcuno ha qualche intuizione su questo?

    
posta Patrick Cornelissen 29.07.2012 - 17:22
fonte

7 risposte

34

Nessuna delle risposte esistenti copre la parte critica di questa domanda in modo soddisfacente: che dire dei sali?

Se sono stati pubblicati solo i valori hash della password, altri cracker non possono sapere:

  1. Il valore di sale effettivo per password (presumibilmente casuale, per sorgente)

  2. Come si salina il sale con la password nel codice.

Tutto quello che hanno è l'hash finale, risultante!

Ci sono molti modi la password e il sale possono essere combinati per formare l'hash:

sha256(pass + salt)
sha256(salt + pass)
sha256(sha256(pass) + sha256(salt))
sha256(pass + sha256(salt))
sha256(sha256(...(salt + pass + salt)...))

Ma se il sale è consigliato 8 caratteri di pura casualità ...

sha256("monkey1" + "w&yu2P2@")
sha256("w&yu2P2@" + "monkey1")

... questo significa che una "tipica" password di 7 o 8 caratteri diventa estremamente difficile a forza bruta, perché ha effettivamente 15 o più caratteri! Inoltre, per craccare la password gli hash che tu conosci sono salati, a meno che tu non abbia anche il sale, non hai altra scelta tranne la forza bruta!

Basato su ricerca che ho fatto usando il cracking della GPU , ho raggiunto 8213,6 M c / s utilizzando due schede ATI di fascia alta con brute force cracking MD5 hash delle password. Nel mio benchmarking ciò significava che potevo provare:

all 6 character password MD5s   47 seconds
all 7 character password MD5s   1 hour, 14 minutes
all 8 character password MD5s   ~465 days
all 9 character password MD5s   fuggedaboudit

Si noti che SHA-256 è il 13% della velocità di MD5 su GPU utilizzando Hashcat . Quindi moltiplica questi numeri di circa 8 per vedere quanto tempo sarebbe necessario.

Se i sali erano non conosciuti , significa che sei essenzialmente un bruto che forza l'equivalente di 12+ password di caratteri. Questo è molto al di là del dominio di qualsiasi potenza computazionale nota.

Ora se vuoi sostenere che ...

  1. Anche i cracker originali hanno ottenuto i sali, ma hanno scelto di non pubblicarli.

  2. Anche i cracker originali hanno il codice sorgente (o è open source) in modo che sappiano come vengono salate le password, ma hanno scelto di non pubblicare tali informazioni.

  3. La falsa forma sta mentendo e le loro password non sono state salate o salate in modo errato in modo tale che i sali non hanno avuto alcun effetto.

... allora sì, è possibile crackare 200k di hash delle password di 400k in pochi giorni.

    
risposta data 30.07.2012 - 10:22
fonte
16

Modifica: tutti i seguenti presuppongono che i sali siano noti, perché è il uso standard del settore della parola salt (terza riga) .

Proprio come un esempio di come questo spesso appare nel database, dai un'occhiata a questa cripta Unix SHA-256 output:

$5$rounds=80000$wnsT7Yr92oJoP28r$cKhJImk5mfuSKV9b3mumNzlbstFUplKtQXXMo4G6Ep5

.. dove wnsT7Yr92oJoP28r è il sale in testo semplice. La documentazione di Python Passlib ha una buona descrizione di molti formati di password hash comuni , e la maggior parte di questi memorizza i sali del testo in chiaro concatenati insieme a la rappresentazione della password con hash.

Il " non noto per l'attacker salt" che @Jeff Atwood discute viene spesso definito un "pepe". Vedi Password Hashing aggiungi sale + pepe o sale abbastanza?

Nel 2009 Daniel J. Bernstein ha scritto un'implementazione SHA-1 altamente ottimizzata per il framework CUDA di NVIDIA. Allora hanno gestito 690 milioni di hash SHA-1 al secondo su un singolo server utilizzando quattro schede grafiche.

Gli attacchi di forza bruta contro le password con hash sono un "carico di lavoro imbarazzante" . Nel 2010 Thomas Roth ha dimostrato forza bruta attaccando ~ 10 hash per ~ 2 $ utilizzando Amazon EC2. Questo potrebbe facilmente essere scalato, se il tasso non è abbastanza alto, quindi aggiungere solo più istanze EC2.

Quindi in sostanza non si tratta di quanto tempo ci vorrà per rinforzare le password. È più una questione di quanta potenza computazionale l'attaccante è disposto o in grado di pagare per ottenere risultati più velocemente.

the attackers claimed they have found ~200.000 passwords

Una spiegazione ragionevole è che gli attaccanti non hanno preso di mira specifiche rappresentazioni di hash, ma hanno semplicemente optato per il "frutto basso appeso". In altre parole, cercavano solo password facili da indovinare. Forse qualcosa come:

  • Un elenco di le parole d'ordine più comuni in chiaro, creato da elenchi pubblicati di password utente effettive. (Nel corso degli anni ci sono stati diversi perdite di password utente reale .)
  • E forse hanno anche provato tutte le password minuscole pronunciabili fino a un limite superiore inferiore, ad esempio fino a 6 caratteri. (Nel dataset di MySpace del 2006 è stato rilevato che il 17% di tutte le password degli utenti finali erano di 6 o meno caratteri.)

My guess is that formspring was lying about the hashing.

Se comprendo correttamente i tuoi collegamenti, gli hash sono stati scoperti su un forum il 7 luglio. Ma avrebbero potuto essere rubati da settimane o mesi di Formspring prima?

Dato quello che ho descritto sopra, non mi sembra irragionevole che sia stato utilizzato un singolo round di SHA256 con un unico salt per password, come ha detto Formspring.

Dipende tutto da quanto tempo e sforzo gli aggressori mettono nel cracking della forza bruta. Ma all'interno delle risorse che potrebbe avere un piccolo gruppo di singoli hacker, sembra plausibile scoprire 200.000 password deboli da un set di dati di 11 milioni di semplici rappresentazioni di hash SHA-256.

    
risposta data 29.07.2012 - 19:10
fonte
8

Rompere gli hash non salati è abbastanza banale: basta cercare l'hash in una tabella pre-calcolata e trovare la risposta. Non ha senso impazzire il resto perché le tue tabelle arcobaleno coprono già il tuo dizionario forza-forza.

Ma il cracking delle password salate è ancora semplice; più lento ma ancora semplice. Nella maggior parte degli attacchi di forza bruta, l'attaccante va per ampiezza e non profondità. Invece di provare 1 miliardo di password contro 1 account, prova decine o centinaia o migliaia di password comuni contro TUTTI gli account. Certamente i tavoli arcobaleno sono più veloci, ma il sale da solo non impedisce la classica metodologia a forza bruta. Inizia nella parte superiore del tuo dizionario e prova la password con tutti gli account: questo ovviamente comporta la ricomposizione dell'hash per ogni account, ma d'altra parte, le probabilità di un hit sono piuttosto alte (è proprio quello che significa "password comune" , Comunque). Successivamente, prendi la tua password più comune successiva, quindi quella successiva, ecc.

Alla fine, si possono ottenere solo migliaia di password, ma statisticamente parlando ci sono probabilmente centinaia di account con la password "123456" nella lista, e un numero abbastanza grande che usa "password1" e "111111" e "test".

200 K su 11 milioni sono credibili; solo circa il 2%. 200.000 su 400.000 meno. Non impossibile ma non altrettanto probabile. La legge dei rendimenti decrescenti prende a calci lì dentro da qualche parte; Non sono sicuro di quanto sia lontano, ma probabilmente è un rapporto molto semplice come 1 / e o qualcosa del genere. Oltre a ciò, sono scettico.

    
risposta data 30.07.2012 - 11:04
fonte
7

Sta dentro la ragione che non stanno mentendo.

  1. Poiché @Jeff ha notato che l'accesso al sale è essenziale per il cracking veloce, ma come @ Remus Rusanu ha osservato: "se hanno ottenuto gli hash, è difficile per me vedere come potrebbero non ottenere il sale", poiché devono essere conservati in modo tale che possano essere associati tra loro. Suppongo che: almeno gli hacker iniziali avessero accesso al sale. 1

  2. @Jeff afferma anche che devono avere accesso al codice sorgente per sapere come vengono combinati il sale e la password. Propongo un approccio diverso per scoprire come vengono combinati il sale e la password:

    1. supponiamo che abbiano un account formspring prima dell'attacco (una supposizione abbastanza ragionevole)
    2. cerca l'account specifico (sale, hash) nell'elenco ottenuto
    3. conoscendo la password, il sale e l'hash risultante, dovrebbe essere facile creare un piccolo script per testare tutti i modi ragionevoli (e alcuni irragionevoli) di combinare password e sale (non più di qualche migliaio di modi?)
    4. ???
    5. L'utile!
  3. affermano di avere "decine di milioni di membri" che rendono @Jesper frutti a foglia bassa la teoria suona molto ragionevole.

Ok, possono ancora mentire, ma almeno sembra ragionevole che non lo siano.

1. Se questa ipotesi è sbagliata - gli hacker iniziali non hanno pubblicato il sale E non hanno provato a crackare le password stesse - il resto potrebbe non essere possibile.

    
risposta data 30.07.2012 - 12:34
fonte
4

hashcat può fare poco più di 1 miliardo di hash SHA256 al secondo su Radeon HD7970, che è solo metà della velocità di SHA1 e un quarto della velocità di MD5. Tuttavia, questo non è nemmeno il collo di bottiglia :

One more thing before we move on; did you notice the speed of the cracking was “only” 258.7M per second? What happened to the theoretical throughput of a couple of billion SHA1 hashes per second? The problem is that the higher throughput can only be achieved with “mutations” of the password dictionary values or by working through different password possibilities directly within the GPU. In other words, if you let the GPU take a dictionary value then transform it into a number of different possibilities it can work a lot faster. The GPU can’t be fed passwords fast enough to achieve the same level of throughput so effectively having a list of passwords is bottleneck.

Quindi usare SHA256 (o anche SHA512) non è più sicuro dell'utilizzo di SHA1 o MD5 contro questo tipo di attacchi.

    
risposta data 30.07.2012 - 05:39
fonte
3

Nessuno dei due post fa menzione del fatto che i perpetratori abbiano o meno ottenuto l'accesso al codice sorgente di Formspring. Se questo fosse il caso, il metodo di costruzione dell'hash e la generazione casuale dei sali sarebbero disponibili per gli aggressori. Ciò renderebbe il compito di cracking notevolmente più semplice, in particolare se il metodo di generazione dei sali "casuali" li limitasse a valori di set relativamente piccoli.

Data l'apparente velocità con cui questo set limitato è stato rotto, la mia ipotesi migliore sarebbe che sia così.

    
risposta data 30.07.2012 - 10:42
fonte
1

Se stavano usando gli hash con un unico salt per password, normalmente ci sarebbe voluto molto tempo prima che qualcuno potesse violare queste password. A meno che le password fossero estremamente deboli o le password fossero parole nel dizionario. Pure bruteforcing sembra un po 'improbabile se fossero forti.

L'hardware di Tom ha un articolo su password GPGPU cracking. Le password deboli ( not più di 10 caratteri, tra cui maiuscole, minuscole, segni, ...) possono essere violate in pochi minuti, anche con un sale se il sale è noto.

Altrimenti ci vorranno molti giorni, mesi, password più lunghe anche migliaia di anni. Ma questo è senza sale. Con un sale ci vorrà per sempre.

    
risposta data 29.07.2012 - 18:08
fonte

Leggi altre domande sui tag