Using TEA to build a hash function

Question

Background:

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.

Answer 1

As you note in the comments, this would not be secure, because the block size is insufficient. A 64-bit hash is subject to extremely trivial collision attacks and feasible preimage attacks.

But TEA also suffers from related-key attacks, which is wholly unsurprising given the extremely simple key schedule. Even AES, which has a much more complex, but still relatively simple, key schedule suffers from related-key attacks, so I don't think it's likely that your proposal is going to help a lot.

In the real world, almost nobody uses related keys. WEP was a notable exception, and it used RC4, which is extremely vulnerable to them, and as a result was trivially insecure. In most modern protocols, we use some sort of key-derivation function, either from a key exchange or with a secret input and a salt, so we functionally never see related keys. This is why related-key attacks, while interesting, are often of limited practical use to attack real-world protocols and easy to defend against. However, with a hash function based on a block cipher, you absolutely must be resistant to related key attacks because the key (the message) is the part that the attacker controls in a Davies-Meyer construction.

If you picked a different block cipher that didn't have related keys attacks, then that would likely be a better candidate for a Davies-Meyer construction. It should be noted, however, that attacks on hash functions and general-purpose block ciphers tend to differ somewhat, so you can have some block ciphers that are secure when used in a hash algorithm and not elsewhere, and vice versa. Thus, at least some independent cryptanalysis is needed.