Quanto è grande il rischio di hash punti fissi / cicli?

Question

Quanto è grande il rischio di hash punti fissi / cicli?

#1 da (6 voti)

5

È stata stabilita la saggezza di password hash più volte con un salt per aumentare il tempo necessario per l'iterazione della forza bruta . Allo stesso tempo (a meno che l'algoritmo non garantisca diversamente) c'è una possibilità minuscola ma non nulla di finire con un punto fisso o ciclo , per cui (ad esempio)

hash(hash(hash_so_far + salt) + salt) = hash(hash_so_far + salt)

o

hash(hash(hash(hash_so_far + salt) + salt) + salt) = hash(hash_so_far + salt)

ecc.

Identità o cicli brevi * sarebbero buchi neri di sicurezza - più iterazioni non significherebbero più difficili da decifrare - e un algoritmo in cui tali cicli sono comuni sarebbe peggio che inutile, portando a un paio di domande ovvie:

Le lunghezze medie e medie del ciclo sono note per algoritmi comuni come MD * e SHA - *?
Esistono algoritmi utili * che garantiscono che il ciclo più piccolo sia l'intero spazio di output?

* AFAICT, qualsiasi algoritmo di hashing utile (output finito, deterministico) avrebbe almeno un ciclo "banale", quando lo spazio di output è stato esaurito.

theory risk hash

posta l0b0 27.12.2012 - 14:30

fonte

1 risposta

Leggi altre domande sui tag theory risk hash

Come implementare un Web of Trust? Un virus può infettare i file del codice sorgente con dati pericolosi?

score 6 · Accepted Answer

Supponiamo che tu abbia una funzione pseudocasuale con un output di n bit. Una buona funzione di hash con un determinato sale dovrebbe comportarsi come un PRF.

La struttura generale, media di un PRF, rispetto all'applicazione ripetuta, è quella di avere un grande "ciclo": se esegui ripetutamente l'hash e il rehash, ad un certo punto, inserirai un ciclo e otterrai un valore che tu già incontrato. La durata media del ciclo sarà circa 2 ^{n / 2} . Il numero di passaggi che dovrai eseguire prima di raggiungere il ciclo riguarderà anche 2 ^{n / 2} . Quasi tutti i valori iniziali ti porteranno, in definitiva, a questo ciclo interiore. Ci possono essere alcuni valori iniziali che non ti porteranno a questo ciclo; potrebbero esserci anche dei punti fissi (esiste una probabilità del 63,2% che esista almeno un punto fisso); ma il numero di tali potenzialmente i punti problematici non saranno più, in media, di 2 ^{n / 2} .

Per riassumere, se n è abbastanza grande che una probabilità di 2 ^{-n / 2} può essere trascurata, allora le cose vanno bene . In particolare, se n = 256 (stai utilizzando SHA-256), puoi smettere di preoccuparti. Anche con MD5 ( n = 128 ), i cicli brevi sono sufficientemente rari da non implicare alcun problema di sicurezza effettivo.

Un ciclo a spazio pieno significherebbe che la tua funzione di hash non è un PRF, ma una permutazione e una permutazione con un solo ciclo. Costruire una permutazione unidirezionale è possibile, ma molto più difficile di una funzione unidirezionale per la quale sembra che sia possibile riunire alcune operazioni e rotazioni bit a bit; per una permutazione, hai bisogno di matematica (ad esempio con l'esponenziazione modulo un numero intero non primo) e questo implicherà qualche problema in più (la permutazione sarà mediamente a senso unico, ma potrebbero esserci dei valori per i quali non sarà).