Per quanto riguarda il tuo aggiornamento, le tue funzioni hash crittografiche standard (MD5, SHA-1, famiglia SHA-2, SHA-3) tentano di approssimare oracoli casuali (e non tentare di essere iniettivi). Cioè tentano di mappare qualsiasi input su un'uscita scelta uniformemente a caso nello spazio di output (e di fare questa mappatura in modo coerente). Con probabilità schiacciante, gli oracoli casuali non saranno iniettabili quando il numero di possibili input è significativamente più grande della radice quadrata del numero di output possibili, a causa del compleanno paradosso .

Ad esempio, se si dispone di un output hash a 128 bit (un hash di 16 byte con 2 ¹²⁸ output possibili) e si utilizza un oracle casuale per hash significativamente più di sqrt (2 ¹²⁸ ) = 2 ⁶⁴ input, inizia a diventare in modo schiacciante probabile che ci saranno collisioni. D'altra parte, se hai hash significativamente meno di 2 ⁶⁴ input, sarà molto improbabile avere una collisione se hai iniziato con un oracolo casuale ideale. (Se hai hash circa 2 ⁶⁴ input rispetto alla possibilità di essere iniettivo è approssimativamente 1/2; ci può essere una collisione o meno).

Come esempio specifico, se hai tutti i 2 ⁷² possibili input da 9 byte la probabilità che un oracolo casuale sia iniettato su uno spazio di 16 byte è circa exp (-n ^{2 / 2m} ) ≈ 10 ^-14231 , dove n = 2 ⁷² ≈ 4.7 x 10 ²¹ e m = 2 ¹²⁸ ≈ 3.4 x 10 ³⁸ . Questo è incredibilmente improbabile; più o meno equivalente a giocare a powerball (probabilità di vincere 1 su 292 milioni) due volte a settimana per 16 anni e vincere il jackpot ogni volta senza perdere biglietti. E ancora, questo è solo per un input da 9 byte; con un input di 15 byte la probabilità di essere iniettiva è di circa 10 ^{-1127492937032632506267955467381579} !

Nel frattempo, se hai tutti i possibili input a 7 byte, ce ne sono solo 2 ⁵⁶ quindi con una grande probabilità non ci saranno collisioni (cioè sarà iniettabile). Poiché questo è significativamente meno di sqrt (2 ¹²⁸ ), un oracolo casuale non sarebbe iniettabile con probabilità con probabilità di 0,0000076 (circa 1 su 130 000 volte non sarebbe iniettivo e il resto del tempo sarebbe iniettivo).

Vedi la tabella delle probabilità su wikipedia per ulteriori informazioni.

È garantito che questa non è una prova per una specifica funzione di hash; per dimostrarlo dovremmo generare una collisione specifica all'interno dello spazio di input che in generale sarebbe difficile da mostrare.

Ora se hai bisogno di una funzione iniettiva che agisce in modo simile a un hash, questo è abbastanza semplice da ottenere usando un codice a blocchi (formalmente conosciuto come permutazione pseudocasuale ) come AES e scegliere una chiave casuale per crittografarlo con. I cifrari a blocchi sono necessariamente sia iniettivi che suriettivi. Se un codice a blocchi non era iniettivo, allora una persona con la chiave e la funzione di decrittografia e un blocco di testo cifrato da decifrare con non potevano forse recuperare il blocco originale.

Lo svantaggio dell'uso di un codice a blocchi invece di una funzione di hash è che il codice a blocchi richiede l'input di una sola lunghezza fissa e lo trasforma in output della stessa lunghezza fissa. Ad esempio, AES può solo prendere un input a 128 bit e trasformarlo in un output a 128 bit. (Sì, è possibile utilizzare le modalità di cifratura a blocchi per trasformare input più grandi, ma purché sia di uno a uno, la dimensione dell'output sarà della stessa lunghezza dell'input). Il fatto che una funzione hash possa prendere input di dimensioni variabili e generare un hash di dimensioni fisse lo rende ideale per molti scopi. Il fatto che questo requisito di hash per mappare input di dimensioni variabili presi da uno spazio di input molto grande in uno spazio di output più piccolo significa che non sarà un iniettore secondo il principio del pigeonhole, di solito non è un problema nella pratica.

Aggiornamento:

Ancora no. Anche se si limita lo spazio di input per avere le stesse dimensioni dello spazio di output (o inferiore), non c'è alcuna garanzia o prova formale che una determinata funzione di hash sarà collisione -free (almeno, nessuna prova che io sappia)

Parte del motivo per cui ci piacciono le funzioni hash crittografiche è che, per quanto ne sappiamo, non hanno pattern distinguibili. Questa è un'arma a doppio taglio che rende quasi impossibile effettuarne un'analisi matematica (e se potessimo, li dichiareremo deboli e passeremo a qualcosa di più complesso).

Potresti, suppongo, scrivere un programma per controllare tutti gli 2 ¹²⁸ input per MD5 e vedere da solo se ci sono delle collisioni, ma avresti bisogno di circa 10 ²⁷ 1 terabyte di dischi rigidi solo per memorizzare la tabella di ricerca per sapere quando si verifica una collisione.

Risposta precedente

In generale, nessuna funzione hash non è iniettiva; non forniscono garanzie sul fatto di essere privi di collisione .

Tutte le funzioni di hash standard (incluse quelle che hai citato) prendono un input di lunghezza arbitraria e producono un output a lunghezza fissa. Prendiamo ad esempio SHA-256 con un'uscita a 256-bit, potrei mappare i primi 2 ²⁵⁶ ingressi a uscite univoche, ma per quanto riguarda il 2 ²⁵⁶ + 1 th inupt? ha per entrare in collisione con qualcosa che è già stato mappato - questo è noto come Principio Pigeonhole .

Più formalmente, qualsiasi funzione il cui dominio (spazio di input) è più grande del suo intervallo (spazio di output) non può essere iniettabile.

Per quanto ne so, il motivo principale per cui MD5 è stato deprecato per uso crittografico è che conosciamo diverse coppie di stringhe brevi (a 128 bit) che producono collisioni sotto MD5. Vedi Demo di collisione MD5 .

Per quanto ne so, non ci sono collisioni note per alcun hash nella famiglia SHA (anche se teoricamente sappiamo che devono esistere secondo il principio del piccione).

A parte: questo è al di fuori della portata della tua domanda, per interesse ti accennerò che è su un problema aperto se gli hash nella famiglia SHA sono suriettivi (cioè se ogni possibile output è effettivamente mappato a, o se ci sono lacune).

Le funzioni di hash vengono generalmente utilizzate per verificare l'integrità dei dati. Consentono a un utente di verificare che alcuni dati di input corrispondano a un determinato valore hash, ma se i dati di input sono sconosciuti, è impossibile ricostruirli conoscendo il valore hash memorizzato. In poche parole posso generare una stringa che identifica un certo tipo di dati con una funzione hash. È possibile generare due hash uguali da due ingressi diversi? La risposta è sì, ma è così rara. Questa situazione è chiamata collisione. Le collisioni si verificano quando membri di un set molto grande (come tutti i possibili file del computer) vengono mappati su una stringa di bit relativamente breve. Matematicamente, un attacco di collisione trova due messaggi diversi m1 e m2, come hash (m1) = hash (m2). Questo è una dimostrazione di attacco collisione MD5 in cui lo stesso hash viene generato da due file eseguibili diversi. Un altro esempio è la funzione di hash SHA1 che è stata sostituita con SHA-2 che ha meno probabilità di essere sfruttata con un attacco di collisione.