Numero minimo di bit per prevenire le collisioni di hash? [chiuso]

0

Ora ci sono un certo numero di funzioni di hashing in uso diffuso. Sembra che l'intervallo generale di bit sia da 128 (MD5) a 512 (SHA-2).

Per prevenire diversi tipi di collisioni di hash, quali sono le raccomandazioni & numero minimo di bit?

Collisioni:

  • Identificatori (chiavi PGP, indirizzi bitcoin, ecc ...)
  • File (controlli di integrità)
  • HMAC (integrità di trasmissione)
posta Xeoncross 22.03.2018 - 18:12
fonte

2 risposte

2

Un algoritmo di hashing perfetto produrrà bit casuali per qualsiasi input univoco. Supponendo un algoritmo di hashing perfetto e una quantità infinita di memoria, il numero di hash che è possibile generare prima di osservare (in media) un duplicato è intorno a 1.2*sqrt(2^bits) . Un algoritmo di hashing con una lunghezza di digest di 32 bit, probabilmente produrrà un duplicato dopo 77000 hash. Oppure, se vuoi avere una possibilità solo dello 0,0001% di trovare un duplicato, puoi generare solo 93 hash usando quell'algoritmo. Questo è sicuramente possibile con l'hardware attuale.

Un algoritmo con uscita a 64 bit può già essere utilizzato per oltre 6 milioni di uscite prima di avere una probabilità superiore allo 0,0001% di produrre un duplicato. Ma ancora, possiamo fare 6 milioni.

Quindi, per avere un elevato livello di sicurezza e poter generare tutti gli hash che vuoi, hai bisogno di un certo numero di bit. Ma quanti bit hai bisogno dipende da quale livello di confidenza vuoi raggiungere. 128 bit è un buon livello per quasi tutto.

Un'altra considerazione è la resilienza contro gli attacchi. Spesso, un algoritmo non è completamente rotto, ma solo indebolito sempre di più, fino a quando diventa fattibile realizzare attacchi realistici in tempo reale (se mai). Se il tuo algoritmo di hashing è indebolito, vorrai comunque avere abbastanza confidenza. Ecco perché la maggior parte dei protocolli restituisce un po 'più del necessario, ad esempio 256 bit.

Ulteriori informazioni sulla matematica: link

    
risposta data 23.03.2018 - 10:54
fonte
2

Qualsiasi funzione di hash crittografica ininterrotta n -bit ha una resistenza di collisione di 2 n / 2 . Ciò significa che, se si desidera avere una resistenza di collisione 2 128 , è necessario utilizzare, come minimo, una funzione hash a 256 bit. Dato che 2 operazioni 64 sono raggiungibili, non si vorrebbe usare un hash a 128 bit. Un hash a 160 bit (ovvero un livello di sicurezza 2 80 ) è borderline. L'uso di un hash a 256 bit ti fornirà un livello di sicurezza 2 128 , che dovrebbe essere perfetto per il prossimo futuro. A volte, i punti deboli nella funzione di hash stessa risultano più facili da interrompere rispetto a quanto suggerito dal digest output. La famiglia di hash SHA-2 è un esempio attualmente ininterrotto. SHA-1 d'altra parte è rotto . Ha un output a 160 bit ma "solo" un 2 63 livello di sicurezza contro le collisioni, piuttosto che 2 80 .

Sospetto che tu possa confondere gli attacchi di collisione con altri tipi di attacchi. Un attacco di collisione non consentirà a un utente malintenzionato di trovare un input che ha un valore arbitrario. Le definizioni formali:

  • Attacco preimage - Dato h dove f (m) = h , trova qualsiasi m ' tale che f (m ') = h .
    "Trova l'input che hash su un valore arbitrario."

  • 2 ° attacco preimage - Dato f (m) = h , trova qualsiasi m ' tale che m ≠ m ' e f (m') = h .
    "Modifica un input senza modificare l'hash risultante."

  • Attacco collisione : trova qualsiasi coppia di m e m ' tale che m ≠ m' e f (m) = f (m ') .
    "Trova due input con lo stesso hash."

Ogni attacco ha implicazioni diverse. Un attacco di collisione è problematico per i certificati, in quanto possono essere utilizzati in firme valide sia per versioni benigne che malevoli dello stesso software. Un attacco preimage è problematico per la verifica. Immaginate se un utente malintenzionato possa modificare un eseguibile senza cambiarne l'hash. Chiaramente, un attacco preimage è molto più grave di un attacco di collisione, ma è anche fortunatamente molto più difficile da attuare. L'algoritmo MD4, infame e insicuro, ad esempio, è così dannoso per la resistenza di collisione che è più economico trovare una collisione piuttosto che eseguire la stessa funzione hash due volte. Tuttavia, per quanto sia rotto, gli attacchi preimage contro di esso sono altamente teorici.

Se, d'altra parte, si vuole semplicemente controllare la corruzione accidentale e non si intende proteggere contro un attaccante attivo, allora un CRC con un polinomio opportunamente selezionato sarebbe l'ideale. Un CRC può effettivamente garantire il rilevamento degli errori fino a un punto.

    
risposta data 23.03.2018 - 10:49
fonte

Leggi altre domande sui tag