Hash un elenco di stringhe in un modo resistente alle collisioni

Question

Hash un elenco di stringhe in un modo resistente alle collisioni

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

1

Ho una lista di stringhe di cui ho bisogno per calcolare l'hash di, ma non riesco a capire come farlo in un modo che sarebbe resistente agli attacchi di collisione.

Ad esempio, in questo codice python:

def list_digest_1(strings):
    import hashlib
    hash = hashlib.sha1()
    for s in strings:
        hash.update(s)
    return hash.hexdigest()

C'è una collisione tra [b'foo', b'bar'] e [b'foobar'] .

Questo può essere ridotto inserendo un separatore tra le stringhe:

def list_digest_2(strings):
    import hashlib
    hash = hashlib.sha1()
    for s in strings:
        hash.update(s)
        hash.update(b'def list_digest_3(strings):
    import hashlib
    hash = hashlib.sha1()
    for s in strings:
        hash.update(
            hashlib.sha1(s).digest()
        )
    return hash.hexdigest()
')
    return hash.hexdigest()

Tuttavia, è ancora possibile creare facilmente una collisione iniettando i caratteri separatori nella stringa, ad es. [b'foo[b'foo', b'bar%code%baz']bar', b'baz'] e %code% . Questo potrebbe potenzialmente essere evitato sanitizzando le stringhe o altrimenti sfuggendo al carattere separatore, ma preferirei farlo se possibile.

Un'altra possibilità è quella di separare ciascuna stringa separatamente, quindi combinare gli hash:

def rand_str(length):
    return ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(length)).encode('utf-8')

def rand_list(length, str_length):
    return [rand_str(length=str_length) for _ in range(length)]

import tqdm
str_list = [rand_list(length=10000, str_length=2) for _ in tqdm.tqdm(range(1000))]

for hash_fun in list_digest_1, list_digest_2, list_digest_3:
    t = timeit.Timer(lambda: [hash_fun(s) for s in str_list])
    print('{}: {}'.format(hash_fun.__name__, t.timeit(number=1)))

# list_digest_1: 1.318927247000829
# list_digest_2: 2.4033974090016272
# list_digest_3: 7.667939508999552

Tieni presente che non sono sicuro che questo risolva il problema o lo faccia un passo indietro.

Non sto utilizzando l'hash per un'attività sensibile alla sicurezza, lo sto solo utilizzando come filtro preliminare per alcune query del database, per ridurre il risultato in termini di prestazioni direttamente dal test di uguaglianza ogni volta. Preferirei usare qualcosa che sia resistente a questo tipo di attacco (in teoria un attaccante potrebbe indurre artificialmente un carico extra presentando collisioni o qualcosa del genere) ma la terza versione peggiora significativamente quando ci sono un sacco di piccole stringhe, limitando i motivi di prestazioni per l'utilizzo di una funzione di hash in primo luogo.

def list_digest_1(strings):
    import hashlib
    hash = hashlib.sha1()
    for s in strings:
        hash.update(s)
    return hash.hexdigest()

Come posso evitare questo problema nel calcolo dell'hash di un elenco di stringhe? Inoltre, se ci fosse uno strumento Python che dovrei usare per questo, sarei felice di saperlo.

performance python hash

posta AJMansfield 07.07.2017 - 20:31

fonte

3 risposte

Leggi altre domande sui tag performance python hash

diceware, perché ci sono parole così brutte? [duplicare] URL sospetto in valore chiave redis

score 2 · Answer 1

È possibile utilizzare la seguente forma canonica di una matrice di stringhe:

<fixedLen1>string1><fixedLen2><string2>...

Implementazione:

def list_digest(strings):
    import hashlib, struct
    hash = hashlib.sha1()
    for s in strings:
        hash.update(struct.pack("I", len(s)))
        hash.update(s)
    return hash.hexdigest()

score 2 · Answer 2

Per evitare questo tipo di collisione, è necessario effettivamente codificare l'elenco di stringhe in un modo che possa, almeno concettualmente, essere decodificato in modo non ambiguo. Come mostra il caso "hash of hashes" (e, crittograficamente parlando, è un buon metodo), la parola "concettualmente" è un po 'sottile.

Ad ogni modo, vedo due possibili metodi che dovrebbero raggiungere prestazioni ragionevoli:

Usa la tecnica hash-of-hashes, con una funzione hash sicura che è più veloce di SHA-1. Suggerisco di provare BLAKE2 (non la cosa di "tree hashing", solo BLAKE2b o BLAKE2s grezzi).
Utilizza una serializzazione personalizzata. Un metodo semplice sarebbe quello di aggiungere, come prefisso ad ogni stringa, una codifica della sua lunghezza; per esempio, codifica la lunghezza (in byte) della stringa su esattamente, per esempio, 4 byte (suppongo qui che nessuna stringa singola sia più grande di 4 gigabyte). È ovvio che potresti decodificare univocamente tale elenco codificato. Non è necessario implementare effettivamente la decodifica; solo che potresti fare è sufficiente per garantire protezione contro le collisioni.

Naturalmente, potresti anche eseguire la serializzazione personalizzata e provare ad eseguire l'hash con BLAKE2.

score 1 · Answer 3

Devi codificare in modo univoco l'elenco di stringhe in un bytestring. Con "non ambiguo" intendo che la funzione di codifica deve essere injective ; ogni input distinto deve essere mappato su un output distinto. Un buon tipo di caso di test unitario da scrivere qui è quello di scrivere la funzione di codifica come una funzione separata, autonoma, scrivere una funzione per decodificarla all'originale, e quindi un test case che verifica che la codifica-decodifica sia un round viaggio.

Questo problema è simile a quello che i programmatori chiamano serializzazione - convertendo tra un oggetto in memoria e una rappresentazione di test che può essere successivamente deserializzata per ricostruire l'oggetto originale. Pertanto le librerie di serializzazione potrebbero essere utilizzate qui, a condizione che l'output serializzato sia costantemente determinato dall'input. Quale non è sempre il caso; ad esempio, le librerie di serializzazione JSON possono produrre più uscite valide per lo stesso input, a seconda, ad es. su dove scelgono di inserire spazi bianchi o meno.

Un tipo molto semplice di codifica che viene spesso utilizzato nei sistemi crittografici è una codifica con prefisso di lunghezza, in cui viene generato un elenco in questo modo:

Emette la lunghezza della lista, cioè il numero di elementi, come un campo a dimensione fissa (ad es. un numero intero a 32 bit in ordine byte little-endian);
Per ogni stringa dell'elenco:
- Emette la lunghezza della stringa, anche come campo a dimensione fissa;
- Emetti i byte nella stringa.