Domanda:
Puoi scoprire quanto sono grandi i cambiamenti confrontando due hash?
Maria Ahmed
2020-02-19 16:45:39 UTC
view on stackexchange narkive permalink

Mi rendo conto che una funzione hash è una funzione unidirezionale e che le modifiche nell'hash dovrebbero dirci che i dati originali sono cambiati (che l'intero hash cambia anche alle più piccole modifiche ai dati).

Ma c'è un modo per scoprire in che misura sono cambiati i dati originali quando due hash sono diversi?

Le risposte che otterrai qui si applicano alle funzioni hash crittografiche.Tieni presente che esistono altri tipi di funzioni hash con proprietà diverse, come l'hashing percettivo per le immagini.
La definizione di un "digest differenziabili" non è banale e specifica dell'applicazione: in pratica stai chiedendo un algoritmo di compressione ultra-lossy.Un esempio è un programma che scatta una foto o un'immagine e sostanzialmente la riduce a (ad esempio) 64x64px (dando una "dimensione hash" di 12 KiB).Quindi, un'immagine diversa, ma visivamente simile, con lo stesso trattamento avrà quindi una rappresentazione molto simile di 64x64px e sarà quindi possibile derivare una misura di "differenza" (ad esempio confrontando gli istogrammi dei pixel).Questo è un esempio elementare però.Vedi anche https://stackoverflow.com/q/6499491/159145
Soprattutto quando viene utilizzato il sale, non c'è possibilità di trovare la differenza.
[w-shingling] (https://en.wikipedia.org/wiki/W-shingling).MinHash e SimHash sono applicazioni pratiche.
Tutti gli aspetti negativi qui sono nel contesto di una funzione hash sicura;essendo questo un sito di domande e risposte di InfoSec, ha senso.Tuttavia, il tipo di costruzione che stai chiedendo esiste in diverse forme e ha molte applicazioni utili.Ad esempio, [hashing sensibile alla località] (https://en.wikipedia.org/wiki/Locality-sensitive_hashing) può essere utilizzato per determinare probabilisticamente quanto siano simili due input.
Forse gli hash non sono il modo per scoprire la differenza.Se è quello che stai cercando, controlla https://en.wikipedia.org/wiki/Levenshtein_distance
@Mark +1 si prega di elaborare una risposta?
Otto risposte:
#1
+93
MechMK1
2020-02-19 17:10:24 UTC
view on stackexchange narkive permalink

No, almeno con una buona funzione hash.

Puoi testarlo tu stesso creando un hash su un set di dati specifico, quindi un hash modificato su un set di dati diverso. Vedrai che ogni bit della funzione hash risultante ha circa il 50% di possibilità di capovolgimento.

Lo dimostrerò creando l'hash SHA-256 della stringa MechMK1 :

  $ echo -n "MechMK1" | sha256sum2c31be311a0deeab37245d9a98219521fb36edd8bcd305e9de8b31da76e1ddd9  

Quando si converte questo in binario, si ottiene il seguente risultato:

  00101100 00110001 10111110 00110001 00011010 00001101 11101110 1010101100110111 00100100 01011101 10011010 10011000 00100001 10010101 0010000111111011 00110110 11101101 11011000 10111100 11010011 00000101 1110100111011110 10001011 00110001 11011010 01110110 11100001 11011101 11011001  

Ora calcolo l'hash SHA-256 della stringa MechMK3 , che cambia un bit del input:

  $ echo -n "MechMK3" | sha256sum3797dec3453ee07e60f8cf343edb7643cecffcf0af847a73ff2a1912535433cd  

Quando convertito in binario nuovo, si ottiene il seguente risultato:

  00110111 10010111 11011110 11000011 01000101 00111110 11100000 0111111001100000 11111000 11001111 00110100 00111110 11011011 01110110 0100001111001110 11001111 11111100 11110000 10101111 10000100 01111010 0111001111111111 00101010 00011001 00010010 01010011 01010100 00110011 11001101  

Ho confrontato entrambi i risultati e controllato quanto spesso un bit differiva da entrambi gli hash e esattamente 128 o il 50% di tutti i bit differivano . Se vuoi giocare tu stesso con questo e vedere che tipo di risultati ottieni, ho creato un semplice programma in C che fa esattamente questo.

Il mio pensiero leggendo la domanda era "Caspita, spero proprio di no"
Tecnicamente, questo dimostra solo metà della domanda.Se il capovolgimento di un bit causa il ribaltamento del 50% di tutti i bit, ma il capovolgimento di due bit provoca il capovolgimento del 75% (50% + .5 * 50%), puoi rilevare la differenza in base al fatto che differenze maggiori causano più cambiamenti.So che in realtà non è così, ma penso che varrebbe la pena menzionarlo in questa risposta altrimenti eccellente.
-1
Mi è stato insegnato che il termine tecnico è [diffusione] (https://en.wikipedia.org/wiki/Confusion_and_diffusion).
@Bobson ha sbagliato a pensare lì - immagina 100 bit tutti 0.Capovolgi metà dei bit a caso.Ora abbiamo metà e metà, 50 0 e 50 1.Ora capovolgi di nuovo metà di tutti i bit a caso: metà (in media) di ciò che capovolgiamo sarà 0-> 1 e l'altra metà è già stata capovolta, quindi otteniamo 1-> 0.Rimaniamo ancora a ~ 50% 0 e 1, cambia solo la distribuzione dei bit con un valore 1.
@Baldrickk - Ecco perché ho detto che sapevo che non era il caso.Il mio punto era che la risposta non si espandeva da un bit a più bit, quindi non escludeva un algoritmo in cui le modifiche da capovolgimenti di bit erano effettivamente correlate.Probabilmente, però, ero eccessivamente pedante.
@Bobson Ho aggiornato la mia [risposta] (https://security.stackexchange.com/a/226118/86735) per più modifiche di bit.La matematica è facile con il modello Oracle casuale.
#2
+37
kelalaka
2020-02-19 19:01:17 UTC
view on stackexchange narkive permalink

TL: DR; Nelle funzioni hash crittografiche; gli hash di due messaggi distinti dovrebbero apparire statisticamente indipendenti. $


Mi rendo conto che l'hash è una funzione unidirezionale e che il si suppone che le modifiche all'hash ci dicano che i dati originali sono cambiati (che l'intero hash cambia anche con le più piccole modifiche ai dati).

Criteri valanghe , oltre ad essere unidirezionale, è anche ciò che vogliamo da buone funzioni hash crittografiche;

  • un singolo bit di cambiamento in l'input si traduce in modifiche in ciascuno dei bit di output con una probabilità del 50%.

  • modifiche di più bit : questo è un po 'complicato, se noi considera gli archivi delle funzioni hash per modellare una funzione pseudocasuale secondo il modello di oracolo casuale, quindi possiamo considerare ogni cambio di bit di input, in media, con il 50%, e non importa quanto bit viene cambiato .

    Si può vedere questo considerando un bit e lanciando una moneta se Head viene capovolto e se arriva coda non capovolgere il 50% del capovolgimento. Ora lancia un'altra moneta e fai lo stesso. Il risultato è lo stesso (matematica semplice).

    Ovviamente non possiamo ottenere il modello dell'oracolo casuale. Pertanto, i bit di uscita non sono indipendenti l'uno dall'altro. Sembrano essere lunghi quanto si riesce a trovare un elemento di distinzione e questo costituirebbe un attacco crittoanalitico contro la funzione hash. Una volta trovata una buona funzione hash crittografica, la vedrai nelle notizie.

Dimostrare che una funzione hash ha i criteri di valanga è un processo statistico che devi testare molti valori di input casuali. Non tutti gli ingressi e i complementi di bit comportano la metà del bit modificato e questo non è il comportamento previsto . Devi anche dimostrare che i bit di output vengono modificati in modo casuale.

Se non è soddisfatta, questa funzione hash può non riuscire a soddisfare la resistenza pre-immagine, la seconda resistenza prima dell'immagine e la resistenza alle collisioni * .

  • preimage-resistance - essenzialmente per tutti gli output pre-specificati, è computazionalmente impossibile trovare qualsiasi input che abbia hash su quell'output, cioè trovare qualsiasi preimage x ' in modo tale che h (x') = y quando viene fornito un valore y per il quale non è noto un input corrispondente.
  • 2nd-preimage resistenza, collisione debole : dal punto di vista computazionale non è possibile trovare un secondo input che abbia lo stesso output di qualsiasi input specificato, ad esempio, dato x , per trovare una seconda immagine precedente x '! = x tale che h (x) = h (x') .
  • resistenza alle collisioni, forte collisione - è computazionalmente impossibile trovare due input distinti x , x ' che hanno lo stesso output, cioè tali che h (x) = h (x ') .

Il fallimento di ciascuno può causare attacchi e, se ha successo, può essere devastante. Un esempio; considera che qualcuno trova un secondo messaggio al tuo messaggio originale che ha lo stesso valore (o l'hash dell'ISO del CD di Linux);

  Questo è un messaggio firmato che rappresenta il pagamento è $ 1,00, avere un buona giornata Ti pagherò $ 1.000.000,00 buona giornata  

Si spera che anche SHA-1 e MD5 stiano resistendo a questo attacco. Pertanto si può presumere che vi sia una modifica nei dati se il valore hash cambia. La probabilità che un testo casuale abbia lo stesso hash con il tuo valore sarà trascurabile.

Ma c'è un modo per scoprire in che misura sono cambiati i dati originali quando due hash sono diversi?

Si spera di no . Se esiste un unico pregiudizio che fornisce informazioni sulle modifiche che possono essere utilizzate da aggressori intelligenti.


* Queste sono definizioni formali e tratte dal seminal paper di Rogaway e Shrimpton Cryptographic Hash-Function Basics: ...

$ Grazie a FutureSecurity per la semplificazione

La "resistenza alle collisioni" è implicita nella "seconda resistenza prima dell'immagine" o ho capito male?
@Daniel Queste definizioni sono tratte da Rogaway e Shrimpton seminal paper [Cryptographic Hash-Function Basics] (https://web.cs.ucdavis.edu/~rogaway/papers/relates.pdf).A pagina 4, c'è un semplice grafico delle relazioni.La resistenza alle collisioni implica una seconda resistenza prima dell'immagine.Se non è resistente alla seconda immagine preliminare, un utente malintenzionato sceglie un m1 arbitrario e calcola una seconda prima immagine m2 per ottenere una collisione.Nota che 2 => 1 richiede [cura] speciale (https://crypto.stackexchange.com/q/10602/18298)
#3
+30
Ilmari Karonen
2020-02-20 04:54:25 UTC
view on stackexchange narkive permalink

Come le altre risposte hanno già notato, la risposta è "no" per funzioni hash crittografiche. Questi sono generalmente progettati per comportarsi il più possibile come una funzione perfettamente casuale e qualsiasi somiglianza rilevabile negli output hash generati per input simili consentirebbe anche di distinguere l'hash da una funzione casuale. *

Tuttavia , ci sono altri tipi di funzioni hash, come hash sensibili alla località, per le quali la risposta può essere almeno "sì, a volte".

In particolare, gli hash sensibili alla località presentano tipicamente proprietà come "due input che differiscono al massimo δ secondo alcune metriche di somiglianza, con probabilità p > 0, avranno hash che differiscono al massimo ε ( δ ) da qualche altra metrica di somiglianza (forse la stessa). " In genere, la metrica della distanza per gli hash può essere qualcosa come distanza di Hamming, mentre la metrica corrispondente per gli input potrebbe essere ad es. modifica distanza. La scelta di una funzione hash sensibile alla località dipende principalmente dalla particolare metrica della distanza che ti interessa.


*) Tecnicamente, la definizione classica di hash crittografico sicuro richiede solo resistenza alle collisioni e una prima e una seconda resistenza all'immagine. Non vedo alcun modo ovvio per dimostrare che una funzione hash non può avere queste proprietà pur essendo in qualche modo sensibile alla località, sebbene impongano alcuni vincoli piuttosto significativi. In particolare, il numero di output hash entro una distanza di ε ( δ ) da un dato output hash H ( x ) dovrebbe crescere più velocemente del numero di altri input entro la distanza δ dell'input corrispondente x per qualsiasi valore ragionevole di δ , altrimenti semplicemente testare un gruppo di input simili molto probabilmente produrrebbe una collisione. In ogni caso, non sono a conoscenza di alcuna funzione hash sensibile alla località che soddisferebbe anche questa definizione più debole di sicurezza crittografica e non ho idea di come potrebbe apparire un tale hash se esistesse.

#4
+17
schroeder
2020-02-19 16:54:26 UTC
view on stackexchange narkive permalink

Sono sicuro che esista un tipo di hash in cui ciò potrebbe essere possibile, ma lo scopo di un hash crittograficamente sicuro è assicurarsi che ciò non accada. Non si dovrebbe essere in grado di fare ipotesi o deduzioni sulle modifiche al messaggio in base alle modifiche all'output dell'hash.

Gli analisti crittografici misurano questo valore in base all ' effetto valanga. Gli hash forti dovrebbero apportare grandi modifiche all'output anche quando vengono apportate piccole modifiche all'input.

"Sono sicuro che esiste un tipo di hash in cui questo potrebbe essere possibile".Di sicuro!Questo banalmente esiste.`base64 (input) .substring (0,10)` è tecnicamente una funzione hash.
@Cruncher Diamine, c'è stato un tempo in cui le funzioni hash predefinite (per cose come le tabelle hash) per `string` facevano cose come" prendere i primi quattro byte della rappresentazione in byte della stringa e convertirli in int ".È abbastanza veloce, almeno: P
@Cruncher tecnicamente `rot13 ()` è una funzione hash.Stavo concedendo all'OP il beneficio del dubbio.
@schroeder Poiché rot13 è reversibile, non sono sicuro che la considererei una funzione hash.In genere pensiamo che un hash abbia la stessa dimensione per ogni input, motivo per cui non ho detto solo base64 senza la sottostringa.Ma comunque, è semantica
@Cruncher secondo la definizione tecnica, gli hash non devono essere unidirezionali.Gli hash unidirezionali devono essere unidirezionali
@schroeder `Una funzione hash è qualsiasi funzione che può essere utilizzata per mappare dati di dimensioni arbitrarie a valori di dimensioni fisse. Questa è la prima riga dell'articolo di wikipedia per la funzione hash.La mappatura di dati di dimensioni arbitrarie a valori di dimensioni fisse sarà * sempre * unidirezionale (principale di casella)
@Cruncher e questa è un'eccessiva generalizzazione degli hash crittografici.Esistono hash che forniscono lunghezze variabili e arbitrarie.Gli output di lunghezza fissa non sono un requisito per un hash.Gli hash crittografici più accettati sono di lunghezza fissa.
@Cruncher [Fips 202] (https://dx.doi.org/10.6028/NIST.FIPS.202): * la funzione di output estendibile SHAKE256 è una funzione che associa una stringa di bit di lunghezza arbitraria a una stringa di infinitamente molti bit *.Si può ancora considerare che sono fissi nel senso che il primo output e gli output successivi sono di dimensioni fisse se consideriamo SHAKE.La necessità è RSA-PSS e ciò richiede una funzione hash non standard.Se gli XOF fossero disponibili in fase di progettazione, la prova di sicurezza di RSA-PSS sarebbe molto più semplice.
#5
+10
solumnant
2020-02-20 22:48:32 UTC
view on stackexchange narkive permalink

Sì, ma solo per hash fuzzy come ssdeep https://ssdeep-project.github.io/ssdeep/index.html che sono specificamente progettati per misurare la somiglianza tra file e hash che copre solo alcune parti del file che non includono modifiche, come imphash https://www.fireeye.com/blog/threat-research/2014/01/tracking-malware-import-hashing.html. Ci sono altri tipi di hash che sono stati menzionati nei commenti alla domanda, ma poiché non ho familiarità con loro, le loro proprietà e l'utilizzo non li approfondirò qui. Sentiti libero di aggiungere a questa risposta se hai altri tipi di hash che non ho appena trattato.

Al di fuori degli hash specializzati che sono progettati per tracciare la somiglianza o che non coprono l'intero input , la risposta sarebbe no secondo le risposte di kelalaka o MechMK1 a questo post. È possibile che le mie funzioni descritte non siano vere funzioni hash, ma sono denominate come funzioni hash all'interno della mia comunità.

#6
+4
James Kirkby
2020-02-20 15:34:14 UTC
view on stackexchange narkive permalink

Una forte funzione hash dovrebbe, con una piccola modifica, produrre una grande differenza nell'hash di output, ovvero se vuoi controllare la differenza tra due valori, puoi utilizzare un algoritmo di distanza di hamming

https://en.wikipedia.org/wiki/Hamming_distance

#7
+1
Graham
2020-02-21 17:16:55 UTC
view on stackexchange narkive permalink

Puoi, ma non è puramente una funzione hash.

I codici di correzione degli errori sono un tipo di funzione hash che non solo consente alcune modifiche a un messaggio essere rilevato, ma consentire anche la correzione di tali modifiche. Le modifiche possono essere corrette solo per un certo grado di errore, ovviamente. Generalmente più grande è il codice di correzione degli errori relativo al messaggio, più modifiche possono essere rilevate e corrette.

I codici di correzione degli errori sono ottimizzati per questa capacità di correggere le modifiche. Ciò significa tuttavia che potrebbero non essere ottimali per rilevare le modifiche a un messaggio in cui la modifica non può essere corretta. Sono principalmente intesi come hash per i messaggi in cui la ritrasmissione non è facilmente possibile e quindi il recupero del messaggio originale è la priorità. Presumono inoltre che non si verifichino attacchi intenzionali al messaggio.

Gli hash crittografici, o anche gli hash meno sicuri come CRC, tendono a funzionare in modo diverso. Generalmente vengono utilizzati in situazioni in cui è possibile richiedere la ritrasmissione di un messaggio errato o in cui sussiste il rischio di attacchi intenzionali e i messaggi difettosi devono essere rilevati e rifiutati in modo affidabile. Queste sono sempre funzioni unidirezionali e il grado in cui sono "unidirezionali" indica quanto siano robuste. Come hanno già detto le risposte precedenti, un buon hash crittografico non ti fornirà alcuna informazione sul messaggio originale.

"o anche hash meno sicuri come CRC tendono a funzionare in modo diverso (da ECC)" - no.Un CRC ha la stessa struttura di un codice di correzione degli errori.In genere non identifica l'errore in modo univoco anche sotto una restrizione come "errori di bit singolo", ma si presta molto bene a eseguire * una * "correzione" e trovare un messaggio coerente con il CRC.
#8
  0
cmm
2020-02-22 21:03:11 UTC
view on stackexchange narkive permalink

Hash non sempre significa Hash crittografico

Potresti costruire una funzione hash specifica per lo scopo.

Considera l'idea di fare un confronto byte per byte dei file e di incrementare l'hash per ogni differenza. Aggiungi la differenza di lunghezze. È una funzione hash che fornisce un calcolo unidirezionale che si riferisce direttamente al grado di differenza.

Se vuoi una funzione hash più intelligente, prova "diff file1 file2 | wc -l".



Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 4.0 con cui è distribuito.
Loading...