# How to hash a list of multiple items?

In some protocols, a key is derived from a hash of many parameters (K=H(param1,param2,param3))

Is there a hash function that takes many parameters as input ?

Or we can simply use a function like SHA-1 by concatenating these parameters as input ?

-

As tylo correctly notes, when we hash multiple values, the important feature that any method we choose should have is that it should be unambiguous: there should not be any way to construct two valid sets of values that produce the same hash value — or at least it should not be any easier than breaking the collision resistance of the underlying hash function by constructing two strings with the same hash value.

In practice, there are many ways to do this. Some are only valid for ceratin kinds of inputs:

• Plain concatenation of the input values before hashing them can be problematic, since, as tylo notes, e.g. "12" || "3" = "1" || "23". However, in some special cases it can be safe, e.g. when all the inputs (or all but one of them) are known to have a fixed length, or when there some other way to always tell where one input value ends and the next begins.

• Using a separator string works well, if we can guarantee that the separator will never occur in any of the input strings (or at most, that it can only occur in one of them and that the number and order of the inputs is fixed). When hashing ASCII or UTF-8 text, null bytes are popular separators.

Other methods are more general, and can be used for (almost) any input tuples:

• Prepending the length of each input string to it before concatenating them, as suggested by fgrieu in the comments, makes the encoding unambiguous. One potential issue is that, if a fixed-size length field is used, this limits the length of the allowed input strings. This can be avoided if a variable-size encoding is used for the length; perhaps the simplest way to do that is to just write the length out as sequence of decimal (or hexadecimal) digits, followed by some non-digit separator.

• There are also several existing data serialization formats that have already solved the problem of uniquely encoding arbitrary data structures into strings. Perhaps the best known example in cryptography is ASN.1 DER, but there are several other alternatives such as csexps. One advantage of using such a format is that they typically support more complex data structures than just tuples of strings; another is that you can find pre-made encoders instead of having to code your own.

• Finally, instead of just encoding the inputs into a single string and hashing it, it's also possible to modify the hashing method to directly support multiple inputs. One general way to do that is to use a hash list, in which every input value is first hashed separately, and the resulting hashes (which have a fixed length, and can thus be safely concatenated) are then concatenated and hashed together.

-

In short: almost. Simple concatenation or arbitrary parameters might cause problems with the cryptographic properties. If you consider fixed domains for your parameters and pad the input with $0$s, you should be fine.

Example: If you have 2 parameters, and you apply a cryptographic hash function to the input (1,23) you end up with the same hash as (12,3). This would not be considered collision resistant any more. However, if you say that the input is a 2-digit decimal number, hashing "0123" and "1203" will not end up in the same hash value.

More formally, your concatenation has to be an injective function, where different inputs always result in different outputs. Other ways to achieve this is by separating the parameters by a special symbol.

-
Indeed, the mapping of parameters to hash input must be reversible. A usual solution is $H(\operatorname{len}(param1)||param1|| \operatorname{len}(param2)||param2|| \operatorname{len}(param3)||param3)$ where $\operatorname{len}$ produce an output of either fixed size, or is otherwise reversible. Also there's ASN.1 –  fgrieu Aug 29 '13 at 17:02
@fgrieu Recommending ASN.1 is kind of a trap :) I would certainly recommend ASN.1/DER if you have to go that way. For simple structures a simple fixed size length followed by value is certainly better. –  owlstead Aug 29 '13 at 22:10
@owlstead: far from me the idea of recommending anything ASN.1 –  fgrieu Aug 30 '13 at 6:15