1
$\begingroup$

I'm working in Python, and my goal is to hash a list of strings with a cryptographic hash function such as sha256. It would need the property that a change in any string, or the order of the strings, will affect the outcome. For example, this would not be sufficient.

sha256(''.join(['string1', 'string2'])).digest()

because ['string1', 'string2'], ['string1str', 'ing2'], as well as ['string1string2'] will all result in the same hash.

One idea I've had for this is to hash repr(strings), but I'm concerned this may be inefficient, as unprintable characters are converted to the 4-byte form \xAB.

strings = ['string1', 'string2', '\x00', '\\x00']
tohash = repr(strings) # tohash == "['string1', 'string2', '\\x00', '\\\\x00']"
result = sha256(tohash).hexdigest() # 2da24fba01c065fe1f33cb937dec2c865de20ebdbd8f172d59d82cd920d3266d

This method works, but I haven't seen it used anywhere else, and it seems inefficient. Is there a standard way to hash multiple strings?

$\endgroup$
1
$\begingroup$

There are two ways of going about this:

  1. create a hash tree (or, as it is only one deep, a hash list);
  2. create a canonical representation of the strings;

For the first option you simply hash each string, and then hash all the resulting hashes. As the hashes should not have collisions, you can be certain that the resulting hash doesn't collide either.

In the other option you create a canonical hash. You've got three options:

  1. use escape characters or bytes;
  2. define the structure and size of the elements outside the strings;
  3. a combined approach of the above.

The first approach I won't explain much. It consists of appointing an escape character and use that for structural information. So e.g. a single 00 byte is used to indicate the end of a string and all the existing 00 in the string are doubled. Disadvantage of this approach is that your string may grow significantly.

As for the second approach: take a look at how ASN.1 would create structures using DER. You would use a "tag" to indicate a set, then the length of the set. Then you would put one or two strings in the set. Each string again has a tag and a length. This structure is completely canonical without requiring any escape characters (as DER is a binary encoding). This will only add a limited amount of overhead.

The combined approach is e.g. applied by Python: you can perfectly distinguish between ['string1', 'string2'], ['string1str', 'ing2'], as well as ['string1string2']. The language is already showing you how to encode lists of string!

| improve this answer | |
$\endgroup$
0
$\begingroup$

Yeah, the usual solution for this problem is to prepend the length of each string (in bytes) then concatenate them into one large array and hash the whole shebang. E.g., [john, smith] becomes the string "4john5smith".

| improve this answer | |
$\endgroup$
  • $\begingroup$ Good. Now do this for the string "4john"... $\endgroup$ – Maarten Bodewes Jan 31 '16 at 8:40
  • $\begingroup$ Assuming you're referring to djbs netstrings, you forgot the separator between the string and the number. Your example would be 4:john,5:smith, when using netstrings. $\endgroup$ – CodesInChaos Jan 31 '16 at 14:51
  • $\begingroup$ Do you actually need the separator? Can you give me an example of an attack that works without separators that is prevented by using them? $\endgroup$ – pg1989 Jan 31 '16 at 19:40
  • $\begingroup$ @pg1989 You need the first separator (the :) but not the ,. Owlstead already noted that the encoding becomes ambiguous without the : if the string starts with a number. $\endgroup$ – CodesInChaos Feb 8 '16 at 14:08
  • $\begingroup$ I don't think it does - the string '4john' just becomes '54john'... $\endgroup$ – pg1989 Feb 8 '16 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.