Cosa rende "sicuro" un algoritmo di hashing?

19

Dopo aver letto questa domanda interessante , Mi sentivo come se avessi una buona idea di quale algoritmo di hashing insicuro userei se ne avessi bisogno, ma non ho idea del perché potrei usare un algoritmo sicuro.

Quindi qual è la distinzione? L'output non è un numero casuale che rappresenta la cosa con l'hash? Cosa rende sicuri alcuni algoritmi di hashing?

    
posta CodexArcanum 26.04.2012 - 20:12
fonte

6 risposte

34

Ci sono tre proprietà desiderate da ogni funzione di hash crittografica H :

  • resistenza preimage : dato h , dovrebbe essere difficile trovare qualsiasi valore x con h = H(x) .

  • seconda resistenza preimage : dato x1 , dovrebbe essere difficile trovare x2 != x1 con H(x1) = H(x2) .

  • resistenza alle collisioni : dovrebbe essere difficile trovare due valori x1 != x2 con H(x1) = H(x2) .

Con le funzioni hash utilizzate nei linguaggi di programmazione comuni per le tabelle hash (di stringhe), in genere nessuna di queste viene fornita, esse forniscono solo:

  • resistenza di collisione debole : per i valori selezionati casualmente (o "tipicamente") del dominio, la possibilità di collisione è piccola. Questo non dice nulla su un utente malintenzionato che tenta intenzionalmente di creare collisioni o di cercare pre-immagini.

Le tre proprietà di cui sopra sono (tra) gli obiettivi di progettazione per ogni funzione di hash crittografica. Per alcune funzioni (come MD4, SHA-0, MD5) è noto che questo non è riuscito (almeno parzialmente). La generazione corrente (SHA-2) è considerata sicura e la successiva ("Secure Hash Algorithm 3") è attualmente in fase di standardizzazione , dopo un concorso .

Per alcuni usi (come l'hashing della password e la derivazione delle chiavi dalle password), il dominio dei valori effettivamente utilizzati x è così piccolo che forzare brute questo spazio diventa fattibile con normali (veloci) sicure funzioni hash, e questo è quando vogliamo anche:

  • esecuzione lenta : data x , ci vuole una quantità minima (preferibilmente configurabile) di risorse per calcolare il valore H(x) .

Ma per la maggior parte degli altri usi, questo non è voluto, si preferisce invece:

  • esecuzione veloce : dato x , il calcolo del valore di H(x) è il più veloce possibile (mentre è ancora sicuro).

Ci sono alcune costruzioni (come PBKDF2 e scrypt) per creare una lenta funzione hash da una veloce ripetendola spesso.

Per ulteriori dettagli, dai un'occhiata al tag hash sul nostro sito gemello Cryptography Stack Exchange.

    
risposta data 26.04.2012 - 22:34
fonte
3

Sicuro significa che qualcuno che vuole indurti a commettere un errore usando una collisione (cioè il fatto che due fonti siano sottoposte a hashing dello stesso valore) avrà delle difficoltà.

Alcune caratteristiche:

  • conoscendo l'hash, la creazione di un file che ha un hash su quel valore è difficile (variante, parte del nuovo file è fornita così come l'hash desiderato)

  • costruire due file diversi con hash allo stesso valore (variante, parte dei file è data)

risposta data 26.04.2012 - 20:19
fonte
3

La differenza principale è piuttosto semplice: un normale hash è pensato per ridurre al minimo il numero di collisioni accidentali, nella misura in cui è possibile senza rallentare un intero lotto nel processo.

Un hash sicuro che intendeva prevenire le collisioni, anche quando qualcuno fa del suo meglio per causarne uno. Generalmente non vuoi scambiare nessuna possibilità di collisione per operazioni più veloci. In effetti, rendere l'operazione intenzionalmente lenta ha alcuni vantaggi in termini di sicurezza, anche se non rende più difficile trovare le collisioni.

Per un esempio di quest'ultimo: se il calcolo di un hash richiede 50 ms, non avrà un impatto materiale sul login di un utente normale (ad esempio, la maggior parte degli utenti non noterà una differenza di 50 ms quando accedono). Allo stesso tempo, se un attaccante vuole fare un attacco di dizionario, essere in grado di produrre solo 20 hash al secondo è un handicap grave . In altre parole, all'interno di una sorta di ragione, per un hash sicuro, è più lento è meglio.

    
risposta data 26.04.2012 - 21:12
fonte
3

Leggi questo link spiegherà tutto molto meglio di quanto potrei mai spiegarlo . Ecco le due intestazioni più importanti dell'articolo che indirizzano direttamente la tua domanda:

  • Gli hash protetti sono progettati per essere a prova di manomissione
    • cambia radicalmente l'output con piccole modifiche a bit singolo ai dati di input
  • Gli hash protetti sono progettati per essere lenti

La sua sezione TL; DR alla fine:

If you are a user:

Make sure all your passwords are 12 characters or more, ideally a lot more. I recommend adopting pass phrases, which are not only a lot easier to remember than passwords (if not type) but also ridiculously secure against brute forcing purely due to their length.

If you are a developer:

Use bcrypt or PBKDF2 exclusively to hash anything you need to be secure. These new hashes were specifically designed to be difficult to implement on GPUs. Do not use any other form of hash. Almost every other popular hashing scheme is vulnerable to brute forcing by arrays of commodity GPUs, which only get faster and more parallel and easier to program for every year.

    
risposta data 26.04.2012 - 21:07
fonte
2

Un hash "sicuro" è un hash che si crede sia difficile "falsificare" in modo formulaico, riproducibile senza una precedente conoscenza del messaggio usato per creare l'hash. Poiché tali informazioni sono generalmente segrete, quindi la necessità di un hash, questa è una buona proprietà di una funzione di hashing intesa per l'uso nell'autenticazione.

Un hash è generalmente considerato "sicuro" se, dato un messaggio M, una funzione hash hash () e un valore hash H prodotto da hash (M) con una lunghezza in bit L, nessuno dei seguenti può essere eseguito in meno di O (2 L ) tempo:

  • Dato hash () e H, produce M. (pre-resistenza)
  • Dato hash () e M, produce un diverso M 2 tale che hash (M 2 ) == H. (resistenza a collisione debole)
  • Dato hash (), produce qualsiasi M 1 e M 2 tale che hash (M 1 ) == hash (M 2 ). (strong resistenza di collisione)

Inoltre, un hash "sicuro" deve avere una lunghezza hash L tale che 2 L non sia un numero ammissibile di passaggi per un computer da eseguire dato l'hardware corrente. Un hash intero a 32 bit può avere solo 2,1 miliardi di valori; mentre un attacco preimage (trovare un messaggio che produce un hash H specifico) richiederebbe un po 'di tempo, non è impossibile per molti computer, specialmente quelli nelle mani di agenzie governative noleggiate con il codice. Inoltre, un algoritmo che crea e memorizza i messaggi casuali e i loro hash farebbe, secondo la probabilità, un colpo del 50% nel trovare un hash duplicato con ogni nuovo messaggio dopo aver provato solo 77.000 messaggi, e avrebbe una probabilità del 75% di colpire un duplicare dopo solo 110.000. Anche gli hash a 64 bit hanno ancora il 50% di possibilità di scontrarsi dopo aver provato solo circa 5 miliardi di valori. Tale è il potere dell'attacco di compleanno su piccoli hash. Al contrario, un computer in cerca di collisioni in un hash a 256 bit (SHA-256) non avrebbe nemmeno una possibilità in un miliardo per il prossimo messaggio che ha cercato di scontrarsi fino a quando non ha provato 15 decillion numeri (1.5 * 10 34 ).

Gli attacchi più dimostrati sugli hash crittografici sono stati attacchi di collisione e hanno dimostrato la capacità di generare messaggi in collisione in meno di 2 L (la maggior parte sono ancora stati esponenziali, ma riducendo l'esponente di la metà è una significativa riduzione della complessità poiché rende un hash a 256 bit facile da risolvere quanto un 128 bit, un 128 bit facile da risolvere come un 64 bit, ecc.)

Oltre alle piccole dimensioni dell'hash, altri fattori che possono rendere un hash dimostrabilmente insicuro sono:

Lavoro scarso - un hash progettato per essere utilizzato da un hashtable o per altri scopi di tipo "checksum" sono solitamente progettati per essere computazionalmente economici. Ciò rende molto più facile un attacco a forza bruta.

"Sticky State" (Stato appiccicoso) - La funzione di hashing è soggetta a schemi di input in cui il valore hash corrente di tutti gli input fino a quel momento non cambia quando viene fornito un particolare byte di input aggiuntivo. Avere "sticky state" rende le collisioni facili da trovare, perché una volta identificato un messaggio che produce un hash "sticky state" è banale generare altri messaggi che hanno lo stesso hash aggiungendo byte di input che mantengono l'hash nel suo "stato appiccicoso" ".

Diffusione - Ogni byte di input del messaggio dovrebbe essere distribuito tra i byte del valore hash in un modo altrettanto complesso. Alcune funzioni di hash creano modifiche prevedibili a determinati bit dell'hash. Ciò rende nuovamente banale la creazione di collisioni; dato un messaggio che produce un hash, le collisioni possono essere facilmente create introducendo nuovi valori nel messaggio che riguardano solo i bit che cambiano in modo prevedibile.

    
risposta data 26.04.2012 - 23:45
fonte
0

Utilizza l'algoritmo giusto per l'attività in corso.

I CRC vengono utilizzati per il rilevamento / correzione degli errori.

I digest di messaggi crittografici come SHA2 vengono utilizzati come blocco predefinito per i costrutti crittografici (firme digitali, MAC, funzioni di hashing della chiave di derivazione / password) e protocolli di sicurezza.

Nelle tabelle hash / dizionari / mappe usa SipHash .

Ciò che chiamate algoritmi di hashing non sicuri non dovrebbe essere utilizzato nelle tabelle hash , come dimostrato dalle seguenti voci CVE: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011-4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375

    
risposta data 15.10.2013 - 11:33
fonte

Leggi altre domande sui tag