Hash a list of strings in a collision-resistant way

Question

I have a list of strings that I need to compute the hash of, but I can't figure out how to do it in a way that would be resistant to collision attacks.

For example, in this python code:

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

There is a collision between [b'foo', b'bar'] and [b'foobar'].

This can be reduced by inserting a separator between the strings:

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

However, you can still easily craft a collision by injecting separator characters in the string, e.g. [b'foo\0bar', b'baz'] and [b'foo', b'bar\0baz']. This could potentially be avoided by sanitizing the strings or otherwise escaping the separator character, but I'd rather having to do this if possible.

Another possibility is to hash each string separately, and then combine the hashes:

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

Note that I'm sill not sure if this actually solves the problem or just moves it a step back.

I'm not using the hash for a security-sensitive task, I'm just using it as a preliminary filter for some database queries, to reduce the performance hit from directly testing for equality every time. I'd prefer to use something that is resistant to this sort of attack (in theory an attacker could artificially induce extra load by submitting collisions or something like that) but the third version performs significantly worse when there are a lot of small strings, limiting the performance reasons for using a hash function in the first place.

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

How can I avoid this problem in computing the hash of a list of strings? Also, if there is an existing python tool I should be using for this instead, I'd be glad to know of it.

Answer 1

You can use the following canonical form of an array of strings:

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

Implementation:

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()

Answer 2

To avoid that kind of collision, you need indeed to encode the list of strings in a way which can, at least conceptually, be decoded unambiguously. As the "hash of hashes" case shows (and, cryptographically speaking, it's a fine method), the word "conceptually" is a bit subtle.

Anyway, I see two possible methods that should achieve reasonable performance:

1. Use the hash-of-hashes technique, with a secure hash function which is faster than SHA-1. I suggest trying BLAKE2 (not the "tree hashing" thing, just raw BLAKE2b or BLAKE2s).

2. Use a custom serialization. A simple method would be to add, as a prefix to each string, an encoding of its length; for instance, encode the length (in bytes) of the string over exactly, say, 4 bytes (I suppose here that no individual string is larger than 4 gigabytes). It's obvious that you could unambiguously decode such an encoded list. You don't have to actually implement the decoding; just that you could do it is enough to guarantee protection against collisions.

Of course, you could also do custom serialization and try to hash with BLAKE2.

Answer 3

You need to unambiguously encode the list of strings into a bytestring. By "unambiguous" I mean the encoding function needs to be injective; every distinct input needs to be mapped to a distinct output. One good sort of unit test case to write here is to write the encoding function as a separate, standalone function, write a function to decode it back to the original, and then a test case that verifies that encode-then-decode is a round trip.

This problem is similar to what programmers call serialization—converting between an in-memory object and a bytestring representation that can be later deserialized to reconstruct the original object. So serialization libraries might be of use here, as long as the serialized output is consistently determined by the input. Which is not always the case; for example, JSON serialization libraries can produce multiple valid outputs for the same input, depending e.g. on where they choose to insert whitespace or not.

A very simple sort of encoding that's often used in cryptographic systems is a length-prefixed encoding, where you output a list this way:

1. Output the length of the list, i.e., the number of elements, as a fixed-size field (e.g., a 32-bit integer in little-endian byte order);
2. For each string of the list:
   • Output the string's length, also as a fixed-size field;
   • Output the bytes in the string.