Qual è la probabilità che i primi 4 byte di hash MD5 calcolati dal contenuto del file si scontrino?

Question

Questa è una domanda combinatoria con una certa teoria negli algoritmi di hashing richiesti.

Diciamo che l'input può essere qualsiasi sequenza casuale di byte da 30 kb a 5 mb di dimensioni (immagino che faccia parecchi combinazioni di valori di input :))

Qual è la probabilità che i primi 4 byte (o primi n byte) di un hash MD5 calcolato dalla sequenza di byte saranno gli stessi per i file distinti?

Nel caso in cui ciò non possa essere calcolato specificamente per Hash MD5, allora qual è la probabilità che qualsiasi funzione hash che genera hash M-byte distribuito uniformemente calcolerà l'hash con collisione sul primo N byte per una data gamma di input?

Answer 1

In assenza di maggiori informazioni sulla probabilità dei valori del byte, sarei più di 1 su 2^32.

MODIFICARE. In effetti, 1 su 2^16 se stai prendendo i personaggi esadecimali anziché i byte puri.

MODIFICARE Basato sul commento:

MD5 può essere considerato uniforme che i valori calcolati siano assolutamente casuali?

L'algoritmo di hash MD5 è progettato in modo che un piccolo cambiamento nell'input si traduca in un hash completamente diverso, quindi direi che i byte hash MD5 sono distribuiti con uguale probabilità (non scommetterei comunque su nulla). Comunque puoi applicare un post-elaborazione al tuo hash (ad esempio puoi usare MD5 a chiave) per aumentare la sua casualità (e renderla più sicura, a proposito, da allora Gli hash MD5 semplici sono stati dimostrati insicuri).

Answer 2

Per una funzione di hash ideale, le uscite sono distribuite uniformemente, quindi le possibilità di due scontri sono una su 2^32. Il paradosso del compleanno, tuttavia, ci dice che se stiamo confrontando tutte le coppie di hash, dovremmo aspettarci di vedere una collisione una volta che abbiamo 2^16 hash, in media - quindi non fare affidamento su solo 4 byte sulla base "Ho molto meno di 4 miliardi di valori".

MD5 non è una funzione di hash ideale, come sappiamo, ma le debolezze sono in qualche modo accidentali qui: trovare una collisione su 4 bytes è nel regno di un ragionevole attacco a forza bruta, quindi non c'è bisogno di ricorrere alle debolezze crittografiche. Se sei preoccupato solo per i dati scelti in modo casuale, non vedrai una significativa deviazione statistica dalla casualità.

Answer 3

Se sei interessato alle probabilità che due input particolari abbiano lo stesso hash a 4 byte, allora è solo 1/2^32. Se sei interessato alle probabilità di due input da un set di X input totali con le stesse probabilità, questo rimane abbastanza basso fino a quando non inizi ad avvicinarti a 2^16 = 65536 input distinti nel set, dove raggiunge il 50% ( Questo fenomeno è noto come paradosso del compleanno).

In generale, uno dei criteri per una funzione hash per essere crittograficamente utile è l'uniformità in tutti i bit.

Answer 4

Le probabilità di una collisione in un hash a n-bit sono di circa 1 in 2^(n/2) a causa del Paradox di compleanno - Quindi circa 1 su 2^16 in questo caso. Se per qualche motivo ti riferissi a usare 32 bit della codifica esadecimale, ovviamente sarebbero solo i primi 16 bit effettivi, quindi le probabilità di una collisione sarebbero di circa 1 in 2^8.

Dato un file fisso specifico, le probabilità che qualsiasi altro file scelto a caso avrà lo stesso hash di quel file è di circa 2^n. In termini di hash crittografici, la differenza tra questi è la prima è una collisione, l'altra è una preimago.

A questa dimensione di hash, i punti deboli in MD5 sono piuttosto irrilevanti poiché gli attacchi più noti su MD5 prendono circa 2^32 calcoli, mentre si può generare una collisione anche in un hash a 32 bit ideale in circa 2^16 calcoli (da quando a distanza Scegliere semplicemente input casuali, hai 1 su 2^16 possibilità di collisione, quindi dopo circa 2^16 ipotesi casuali avrai probabilmente trovato una coppia di input in collisione).

Answer 5

Gli hash MD5 sono in genere esadecimali, quindi ci sono 16 possibili valori per ciascun byte. Pertanto per quattro byte ci sono 16*16*16*16 = 65536 possibili combinazioni, rendendo la probabilità di una collisione hash 1: 65536.

Answer 6

MD5 è esadecimale, quindi ogni personaggio può essere uno dei 16 alleli. Quindi questo farebbe 16^n

Per 4 caratteri, ciò rende 65536 diverse combinazioni possibili.