Tengo una lista de cadenas de las que necesito calcular el hash, pero no puedo averiguar cómo hacerlo de una manera que sea resistente a los ataques de colisión.
Por ejemplo, en este código de python:
def list_digest_1(strings):
import hashlib
hash = hashlib.sha1()
for s in strings:
hash.update(s)
return hash.hexdigest()
Hay una colisión entre [b'foo', b'bar'] y [b'foobar'] .
Esto se puede reducir insertando un separador entre las cadenas:
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()
Sin embargo, aún puedes crear fácilmente una colisión inyectando caracteres separadores en la cadena, por ejemplo. [b'foo y %code% . Esto podría evitarse potencialmente eliminando las cadenas o escapando al carácter separador, pero preferiría hacerlo si es posible. [b'foo', b'bar%code%baz']bar', b'baz']
Otra posibilidad es agrupar cada cadena por separado y luego combinar los hashes:
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
Tenga en cuenta que todavía no estoy seguro de si esto realmente resuelve el problema o simplemente lo mueve un paso atrás.
No estoy usando el hash para una tarea sensible a la seguridad, solo lo uso como un filtro preliminar para algunas consultas de la base de datos, para reducir el impacto en el rendimiento de las pruebas directas de igualdad en todo momento. Preferiría usar algo que sea resistente a este tipo de ataque (en teoría, un atacante podría inducir artificialmente una carga adicional al enviar colisiones o algo así), pero la tercera versión es significativamente peor cuando hay muchas cadenas pequeñas, lo que limita las razones de rendimiento para usar una función hash en primer lugar.
def list_digest_1(strings):
import hashlib
hash = hashlib.sha1()
for s in strings:
hash.update(s)
return hash.hexdigest()
¿Cómo puedo evitar este problema al calcular el hash de una lista de cadenas? Además, si hay una herramienta Python existente que debería usar para esto, me encantaría saberlo.