messages to break hash modulus 2^n Let $H_{2^n}(k,m)$ be a hash function where $k$ and $n$ are unknown and $m$ is a message in the format $(m[0], m[1], ..., m[s])$, with $m[i] &lt; 2^n$ for all $0 &lt; i \le s$. Define the hash as:

$H_{2^n}(k,m) = (k^s + m[1]k^{s -1}+\dots + m[s -1]k + m[s]) \;mod\;2^n$

The attacker sends a set $M = \{m_1, m_2, ..., m_a\}$ of messages and wins the game if $H_{2^n}(k,m_i) = H_{2^n}(k,m_j)$ for some $m_i,m_j \in M$ where $m_i \ne m_j$.

How can the attacker choose a set $M$ that will surely win the game?



I'm guessing there must be some trick with the last part of the message (i.e. $m[s]$), for example, if the attacker sends a set $M$ where $m_i = (0,0,\dots, 1 + 2^i)$, it's possible to ignore $k^s$ and if $M$ is big enough, than its elements will collide for sure, but I don't think this is the right way to use the argument.
If k is even


Choose a string m
Choose any block of m other than the last
Flip the most signficant bit of that block.


They collide because you effictively shift all bits of that block one place to the left. If $x \equiv y \mod 2^{n-1}$ then $2x \equiv 2y \mod 2^n$.

Additionally if $k$ is even all strings with their last $n$ blocks equal collide. This is because the previous blocks have a coefficient congruent to 0 mod $2^n$. (They're multiplied by a multiple of $2^n$.)