E 'noto a quali dimensioni dei messaggi sono injective le funzioni standard di hash?

Question

E 'noto a quali dimensioni dei messaggi sono injective le funzioni standard di hash?

#1 da (3 voti)
#2 da (2 voti)

1

Questo semplice script Python verifica che tutti i messaggi di lunghezza 1 abbiano hash SHA-1 diversi:

import hashlib
s = set()
for i in range(256):
    s.add(hashlib.sha1(chr(i)).hexdigest())
print len(s)

È noto fino a che dimensioni dei messaggi sono funzioni hash crittografiche come SHA-1, SHA-2 o MD5 iniettive? In altre parole (per ogni funzione di hash):

Quali sono i due messaggi più brevi con lo stesso hash?
Qual è il più piccolo n tale che esistano due messaggi di lunghezza n con lo stesso hash?

hash md5 sha

posta Petr Pudlák 31.03.2015 - 10:16

fonte

2 risposte

Leggi altre domande sui tag hash md5 sha

Distinzione tra token e PAN effettivi per token basati su funzioni di crittografia reversibili autenticazione a due fattori senza TLS / SSL

score 3 · Answer 1

Secondo Wikipedia (barra di sintesi sul RHS), "Non sono state ancora prodotte collisioni effettive" per SHA-1. Il meglio che abbiamo fatto è trovare algoritmi che "dovrebbero" trovare le collisioni alla fine.

Dato che il punto di una funzione hash è che qualsiasi modifica (anche un singolo bit) dovrebbe cambiare l'intero risultato in un modo sostanzialmente pseudocasuale, stai essenzialmente guardando problema di compleanno .

La tabella su questa pagina di Wikipedia elenca il compromesso tra il numero di input che hai e quanto dovresti preoccuparti su una collisione. Questa altra tabella qui elenca la "sicurezza" di ciascun hash (in bit).

Un calcolo di esempio: per SHA-512 , con 256 bit di sicurezza, devi cercare 10 ^ 32 prima di iniziare a ottenere problemi. log2(10^32) è di circa 106 bit, il che significa che dovresti iniziare a preoccuparti delle collisioni dopo circa 13 byte . Tuttavia, potresti avere altri problemi a quel punto, come la bolletta della luce e la morte del Sole.

score 2 · Answer 2

Questo è qualcosa che ho passato un po 'di tempo a cercare di capire anche io. La risposta è molto più difficile di quanto sembri, ma sembra abbastanza coerente "Non ne abbiamo idea".

Questo potrebbe sembrare strano ma in realtà è abbastanza ragionevole se si considera ciò che si sta cercando. In sostanza stai chiedendo a qualcuno di trovare una collisione in una funzione hash. Questo dovrebbe essere MOLTO difficile. Sia SHA-1 che SHA-2 e in misura minore MD-5 (che è rotto) sono stati progettati non solo per trovare pre-immagini e collisioni che sarebbero state difficili, ma anche di più. Una buona funzione di hash dovrebbe essere indistinguibile da un oracolo casuale.

Se fossimo in grado di capire cose come quelle che stai chiedendo, sapremmo molto di più sulle funzioni, quindi cosa dovremmo essere in grado di dire.

Ovviamente puoi essere sicuro che ci sono due messaggi di lunghezza < = n + 1 che collidono, dove n è la lunghezza del blocco della funzione di hash. Mi aspetterei che la lunghezza delle collisioni più piccole sia vicina al massimo, ma ad essere sincero non posso davvero sostenere con la matematica.