# Using TEA to build a hash function

TEA uses a 128 bit master key $$K_{0\ldots3}$$. All odd rounds use $$K_0$$, $$K_1$$ as the round subkey, and all even rounds use $$K_2$$, $$K_3$$. One cycle of TEA applied to the block $$A_i$$,$$B_i$$ is: $$A_{i+1} \leftarrow A_i + F_i(B_i, K_0, K_1) \hspace{0.5em};\hspace{0.5em} B_{i+1} \leftarrow B_i + F_i(A_i, K_2, K_3)$$. Where the round function $$F$$ is: $$F_i(b,k,k') = (\text{ShiftLeft}(b,4) + k) \oplus (b + \Delta_i) \oplus (\text{ShiftRight}(b,5) + k')$$

Consider complementing the most significant bits of $$K_0$$ and $$K_1$$. Note that flipping the most significant bit propagates through both the addition and XOR operations, and flipping it twice cancels the modification. Therefore, modifying the 128-bit master key in this way does not effect the encryption process. We can also complement the most significant bits of $$K_2$$,$$K_3$$ without any effect. This means that each TEA key has 3 other equivalent keys.

Question:

If we defined a new block cipher called TEA$$'$$ that was functionally identical to the original TEA, but with the following modification (see below), would we eliminate the equivalent key issue and be able to safely use TEA$$'$$ in a Davies-Meyer, Merkle-Damgard construction to build a hash function?

Modification:

TEA$$'$$ uses a 126 bit master key, $$M_{0 \ldots 125}$$. The 126 bit master key is mapped to the subkeys $$K_{0 \ldots 3}$$ in the following way: $$K_0$$'s most significant bit is 0, followed by the first 31 bits of the master key, $$M_{0 \ldots 30}$$. $$K_1$$ is composed of the next 32 bits of the master key, $$M_{31 \dots 62}$$. $$K_2$$'s most significant bit is 0, followed by the next 31 bits of the master key, $$M_{63 \ldots 93}$$. $$K_3$$ is composed of the final 32 bits from the master key, $$M_{94 \ldots 125}$$.

Essentially just use a 126 bit key, and keep the MSB of $$K_0$$ and $$K_2$$ set to 0.

• This is a question to help me learn. I am not interested in how to implement or build these constructs in production. I am just curious if there is some other related-key scenario I am not thinking of, etc. I also know that given TEA's 64-bit block size the hash isn't useful. The question is more about eliminating the equiv. key problem to make it safe for use, assuming the block size was sufficient. Nov 18, 2022 at 17:11
• Hint: if we use TEA' as the block cipher in a Davies-Meyer construction, what's the size of the hash? Is that enough to conclude? [apocryphal note: I wrote this comment before the above one became visible]
– fgrieu
Nov 18, 2022 at 17:26
• TEA' would have the same 64-bit block size as the original TEA, and thus a 64-bit hash. This is obviously too small when considering modern hardware. But as I mentioned in my comment, I am wondering if the modification fixes the equiv. key problem, and if we assumed the block size was sufficient, would we have something secure. Nov 18, 2022 at 17:28