Qual è la differenza di sicurezza tra l'utilizzo di una parte della funzione di hash del digest dei messaggi o tutta la funzione di hash del digest dei messaggi? e c'è qualche equazione in grado di calcolare la sicurezza per la parte o l'intero messaggio digest?
Ci sono tre caratteristiche principali che sono cercate in una funzione hash:
Per qualsiasi funzione di hash, indipendentemente dalla sua forza crittografica, esiste un attacco generico che funziona sempre e si chiama luck . Per trovare un preimage (o un secondo preimage), basta provare i messaggi casuali fino a quando non viene trovata una corrispondenza. Per trovare una collisione, hash molti messaggi casuali fino a quando due di questi producono lo stesso valore di hash. Per un output n -bit, la fortuna funziona con lo sforzo medio 2 n per le pre-immagini e le seconde pre-immagini, 2 n / 2 per le collisioni (quindi è sostanzialmente più facile trovare collisioni rispetto alle pre-immagini).
Ciò che è effettivamente necessario in una funzione hash dipende dal protocollo. Ad esempio, gli algoritmi firma digitale (quelli veri, come RSA o DSA) iniziano con una chiamata di funzione hash e l'hash il valore viene quindi utilizzato nell'algoritmo corretto. Le firme digitali funzionano sulla preimage e sulla seconda pre-resistenza, a meno che non ci si trovi in una configurazione in cui un potenziale attaccante può scegliere i dati di alcuni messaggi da firmare, nel qual caso è necessario anche resistere alle collisioni.
Come regola generale , attenersi all'output n -bit tale che 2 n / 2 invocazioni di la funzione di hash è troppo grande. Ciò significa n = 160 o così. Usando una funzione di hash con soli 128 bit di output significa che si possono trovare collisioni con lo sforzo 2 64 , che è piuttosto costoso ma tecnologicamente fattibile (un tale sforzo è stato eseguito almeno una volta ma ci sono voluti quattro anni e migliaia di contributori).
Per alcuni protocolli è sicuro ignorare le collisioni (che non otterrebbero nulla per l'attaccante) e quindi ridurre l'output a 80 bit (o giù di lì). E l'esempio è quando la funzione di hash viene usata come parte di HMAC per i controlli di integrità, ma solo fino a quando il la funzione di hash sottostante è solida . Infatti, HMAC si basa su alcune proprietà interne della funzione di hash che non sono direttamente collegate con la resistenza alle pre-immagini o alle collisioni. Se la funzione di hash è SHA-256, le cose vanno bene; HMAC / SHA-256 troncato a 96 bit (si tronca l'output di HMAC, non la funzione di hash interna) offrirà sicurezza fino a 2 96 , che è più che sufficiente . Se la funzione hash è MD5 o SHA-1, allora ... le cose sono meno chiare.
Ci vuole un crittografo esperto per dirti quale uso di una funzione di hash tollera il troncamento e quale no. Questo dipende dalla funzione hash stessa, da come viene usata e in quale contesto. Molti crittografi addestrati risponderanno "non farlo" nella maggior parte dei casi, comunque, perché gran parte della formazione sulla crittografia consiste nel rendersi conto che un singolo essere umano non sarà mai in grado di pensare a tutto. Sono un crittografo esperto e quindi ti dico: non farlo .
Utilizzare solo parte del digest significa ridurre le dimensioni dello spazio di digest. Ciò significa in pratica dipende da cosa stai usando il digest per.
Per l'hashing delle password basato sul web, sarei tentato di dire che non avrà alcun impatto significativo finché non inizierai a utilizzare un sottoinsieme veramente piccolo del digest. Ciò è dovuto al fatto che anche i 16 bit sono probabilmente più grandi dello spazio delle password in cui risiede il 99% degli utenti. È anche dovuto al fatto che sebbene l'uso di un sottoinsieme del digest renda le collisioni più probabili in teoria, non lo fa renderli più facili da creare nella pratica. Se la tua funzione hash ha ancora una resistenza ininterrotta del secondo preimage, come la famiglia SHA2, le collisioni non saranno più una preoccupazione - di nuovo fino a che non si scende a sottoinsiemi di digest molto piccoli, a quel punto le collisioni diventano facilmente forzate a forza.
Detto questo, non sembra una buona idea. E certamente non lo difenderei in niente diverso da un ambiente di controllo delle password molto lento come l'autenticazione web remota.
Per quanto riguarda una definizione formale di quanto sia sicura, dipende molto dalla tua applicazione. Se rimaniamo con l'hashing della password e pensiamo che stiate facendo tutto il resto bene - salendo, usando un metodo hash lento, difendendo il server del database in modo appropriato - allora la vostra unica preoccupazione inizia quando la lunghezza del digest che state usando si avvicina (dall'alto) picco entropia della password della vostra base di utenti, compreso il sale. A quel punto inizi a ferire la forza delle password degli utenti, che è uno scenario sbagliato.
Una funzione di hash crittografica ha due principali fonti di sicurezza:
H(x) è calcolabile non deducibile per dedurre qualsiasi informazione su x . H(x) = H(y) dove x e y non siano uguali. Riducendo la dimensione dell'output della funzione H , riduci la quantità di sforzo richiesta per trovare una collisione. Ad esempio, una funzione di hash crittografica perfetta con un output a 8 bit ha una probabilità di collisione 1-in-256 (0,391%) tra due qualsiasi plaintint selezionati casualmente. Per un output a 32 bit, che scende a 1-in-2 32 o 0,0000000233%.
Per garantire una collisione, devi calcolare 2 n +1 hash, dove n è il numero di bit nell'output. Il numero previsto di hash prima che venga trovata una collisione è 2 n-1 , poiché è qui che la metà di tutte le uscite hash possibili sono state calcolate sqrt (2 n ), che significherebbe 2 64 operazioni per un hash a 128 bit (grazie a Thomas per questa correzione). Le moderne funzioni di hash tendono a utilizzare ovunque tra 160 e 512 bit, il che si traduce in costose scoperte di collisioni a forza bruta.
Tuttavia, se si tronca l'output hash su un numero minore di bit, si perde parte della resistenza di collisione. Per ogni byte eliminato, il costo dell'attacco diminuisce di un fattore di 256. Ora, questo non è un grosso problema se si tagliano solo un paio di byte dalla fine di un hash SHA256, ma se si usa SHA1 e controlla solo metà dell'hash, stai riducendo uno spazio 2 160 fino a 2 80 , l'ultimo dei quali si avvicina ai reami di fattibilità in termini di forza bruta individuazione collisione.
La più grande domanda è perché vorresti farlo. Posso vedere solo due ragioni, una delle quali è fuorviata:
x se conosci solo H(x) . Questa non è una buona idea, dal momento che qualsiasi hash crittografico moderno sarà stato progettato per essere al sicuro in questo settore. Non c'è motivo di troncare per questo. Le brevi risposte alle tue domande sono "molte" e "sì".
Molto semplicemente, un digest di hash ha teoricamente una quantità di imprevedibilità, o entropia, uguale alla sua lunghezza in cifre binarie. Ciascuno di questi bit potrebbe essere 1 o zero, indipendentemente da qualsiasi altro senza schema apparente. Una "funzione di hash a 128 bit", ad esempio, produce digest di messaggi lunghi 128 bit e quindi teoricamente con 128 bit di entropia. Per i nostri scopi etichettiamo il numero di bit di entropia come B .
Data la funzione di hash H , qualsiasi messaggio arbitrario M , e il digest risultante D = H (M) che è B di lunghezza, l'hash sicuro ideale (che i nostri hash crypto del mondo reale cercano di essere) ha i seguenti comportamenti fondamentali:
Ad esempio, data una funzione hash a 128 bit, la ricerca di un messaggio che produrrebbe un dato hash digest richiederebbe 2 calcoli hash 128 = 3.4 * 10 38 . Questo è un lotto di lavoro; più di quanto qualsiasi sistema di calcolo coordinato attualmente disponibile potrebbe produrre nel corso della nostra vita. Tuttavia, la ricerca di due messaggi che hanno prodotto lo stesso digest, indipendentemente dal contenuto dei messaggi o del digest, è dell'ordine di 2 64 = 1.8 * 10 19 . Questo, che ci crediate o no, è ben all'interno del regno delle possibilità; il cluster distributed.net è stato in grado di attraversare lo spazio delle chiavi a 64 bit in circa 5 anni per decifrare un codice a 64 bit, che equivale in complessità alla ricerca di una collisione a 128 bit.
Il risultato di tutto ciò è che l'utilizzo di un digest di hash più piccolo, incluso l'utilizzo di una porzione di un hash digest più grande, ridurrà il numero di bit di entropia, riducendo esponenzialmente la difficoltà di trovare una collisione o un preimage. se prendi, per esempio, metà di questo hash a 128 bit, riduci la complessità di romperlo di un importo esponenziale; 2 128 = 2 64 * 2 64 , quindi usando solo la metà del valore hash hai ridotto la complessità e quindi la sicurezza di l'algoritmo, a circa un quadrillionesimo della sicurezza che ha l'hash completo.
La tua domanda è un po 'vaga. Se stai chiedendo se è sicuro controllare parte del digest, allora no. Se l'hash del messaggio X è "abcdefg" e hash (Y) è "ppppefg", e si verifica solo una "parte" di esso (gli ultimi 3 caratteri, "efg"), allora si avrà lo stesso valore - e la tua funzionalità di hash fallisce.
Se intendi hash una parte del messaggio, puoi fornire solo l'integrità dei dati per quella parte, non l'intero messaggio. Potrebbe essere fatto per prestazioni forse, ma non è una buona pratica di sicurezza.
Leggi altre domande sui tag cryptography hash