Join Log in
Score:0
avatar Crypto

Using TEA to build a hash function

sa flag
Confused about Curves

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.

104
1 + 3
sa flag
Confused about Curves
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.
0
Reply
fgrieu avatar
ng flag
fgrieu
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]
0
Reply
sa flag
Confused about Curves
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.
0
Reply
Score:0
bk2204 avatar Crypto
fr flag
bk2204

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.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.