1
$\begingroup$

I know that DES has 56 independent key bits, and that 3DES has 168 independent key bits by using 3 separate 56-bit DES keys. 3DES also has a block size of 64 bits.

If I use 3DES as the underlying block cipher to construct a Davies-Meyer compression function, what would be the input/output size of this compression function?

enter image description here

Wikipedia states the following about Davies-Meyer compression functions:

If the block cipher uses for instance 256-bit keys then each message block Mi is a 256-bit chunk of the message. If the same block cipher uses a block size of 128 bits then the input and output hash values in each round is 128 bits.

Does this mean that if 3DES is used as the block cipher, the compression functions has message blocks of 168 bits? And input/output hash values of 64 bits?

Also, what would be the total input size-->output size mapping for the compression function?

Improve this question
$\endgroup$
6
  • $\begingroup$ If this is homework, you did it fine IMHO. The answer to the question in the last paragraph immediately follows from that of the questions in the butlast paragraph (which I find reasonable), and settling if "total input" includes $H_{i-1}$ (if we consider that it does and the academic context permits, we should tell we did; in an MCQ, I would probably opt for that, and mentally lament at ambiguity in MCQ). Suggestion: next time, resize down the image. $\endgroup$ Commented Dec 1, 2023 at 4:45
  • $\begingroup$ Follow-up questions: How could collision-resistance of this function be broken with a PC considering output size alone? What if we consider that DES has an 8-byte key? A hard one: we use this compression function in a toy Merkle-Damgård hash (with the 168-bit block size in the question). Does DES's complementation property or/and it's weak keys allow to break collision resistance without a computer? $\endgroup$ Commented Dec 1, 2023 at 5:26
  • $\begingroup$ @fgrieu thanks for the response. For my question about the total mapping size, I’ve understood this to mean that the mapping for the Davies-Meyer compression function would be 168+64=232 bits of input to —> 64 bits of output? Or should I not include the 168 key bits as part of the input size since that’s not actually the message being encoded? Your follow up questions are interesting, I'll think them over and get back to you if I have any solid answers, thanks! $\endgroup$ Commented Dec 1, 2023 at 14:01
  • $\begingroup$ If only one input is accounted for, it must be the 168-bit one, because in Merkle-Damgård using the Davies-Meyer construction, this input is freely chosen by adversaries. But I believe your 168+64=232 is fine because 1) If "total" has a meaning, it must be that we account for the two inputs of the Davies-Meyer compression function. 2) Commonly, proof of security of Merkle-Damgård using the Davies-Meyer compression function assumes that DM is collision-resistant for adversaries in control of both inputs, even though they have only partial control on the chaining input (here the 64-bit one). $\endgroup$ Commented Dec 1, 2023 at 18:43
  • $\begingroup$ @fgrieu If I were to express this compression function in terms of mathematical notation, could I say f: {0,1}^168 x {0,1}^64 -> {0,1}^64 ? Rather than arguing with language that there is a total input of 232 bits. I appreciate your help. In relation to your follow-up questions, the 64-bit block size could leave it vulnerable to a birthday attack, could this endageer the collision resistance of a Merkle-Damgard hash that is constructed using this compression function? $\endgroup$ Commented Dec 1, 2023 at 23:45

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.