Consider a version of the division method in which \(h(k) = k\) mod \(m\), where \(m = 2^p - 1\) and \(k\) is a character string interpreted in radix \(2^p\). Show that if we can derive string \(x\) from string \(y\) by permuting its characters, then \(x\) and \(y\) hash to the same value. Give an example of an application in which this property would be undersirable in a hash function.

Suppose that string \(k\) is only a single character long. In this case, \(x\) = \(y\) and so we can both derive one string from the other and be certain that they hash to the same value since they are equivalent.

Let \(w\) be some positive number: \(w = w_1 w_2\) where \(\lvert w_1 \rvert \ge 1\) and \(\lvert w_2 \rvert = 1\). Suppose also that \(h(w_1) = k_1\). Then

\[\begin{align*} h(w) &= h(w_1) 2^p + h(w_2) \text{ mod } 2^p - 1 \\ &= h(w_1) + h(w_2) \text{ mod } 2^p - 1 \end{align*}\]

In this example, \(h(w_1)\) was the sum of all previous digits mod \(m\) and we are adding to this result the new digit mod \(m\). This proves our conclusion via induction.

This property would be undesirable for one of the primary uses of hash functions: storing passwords. If we can permute the password freely without impacting the outcome of a hash, then our system wouldn’t differentiate between passwords that use the same set of characters such as \(abc123\), \(123abc\), \(a2c3b1\), etc.