2
$\begingroup$

We change the AES block cipher encryption:

  • we delete the key schedule algorithm
  • the user now provides a string of 1408 bits
  • we divide the string to 11 sub keys, and use them directly in the encryption part of AES as the round keys.

We call the resulting function $AES' : \mathbb Z_2^{1408} \times \mathbb Z_2^{128} \to \mathbb Z_2^{128}$.

Then we use this function $AES'$ as cryptographic compression function in the following way:

Given text $M$, we divide it to blocks $M_1, \dots M_n$ of size 1408 bits each. Then define $g_i \in \mathbb Z_2^{128}$ as

  1. $g_0=0$
  2. $g_i = AES'(M_i,g_{i-1})\quad$ (Each $M_i$ is used as the round keys in one AES encryption.)

Then the hash function $h : \mathbb Z_2^{n·1408} \to \mathbb Z_2^{128}$ is defined as follows : $h(M)=g_n$

Is $h$ a one way function? If not, how could an attack reveal $M$, given $h(M)$?

(I don't want you to solve, I just want some hints to solve this problem.)

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you only interested in one-wayness or also collision resistance? What do you do if $M$ is not a multiple of 1408 bits long? $\endgroup$ – mikeazo Dec 18 '12 at 15:31
  • $\begingroup$ you may assume that it is a multiple of 1408 $\endgroup$ – fshtea Dec 18 '12 at 15:37
  • $\begingroup$ I edited your question, since this is not about "changing AES encryption", but building an one-way function from parts of AES (quite a different task). $\endgroup$ – Paŭlo Ebermann Dec 22 '12 at 21:42
  • $\begingroup$ Where did you run into this problem? Is this a homework problem, or did you run into it in some practical setting? That may help us give you a more useful answer. $\endgroup$ – D.W. Dec 23 '12 at 7:46
  • $\begingroup$ The security of AES does not only stem from the round function, but also from the key schedule. If you delete this part, you remove any security properties from AES. This leaves... no convincing arguement that this function could be one-way. Hint: even worse, look at the last round of AES more closely. $\endgroup$ – tylo Oct 14 '13 at 13:53
4
$\begingroup$

As Mike asked, it's not clear if you're asking about onewayness, or collision resistance (as you call the function a 'cryptographic compression function').

Assuming you're asking about onewayness, well, given a single 128 bit value $h(M)$, we obviously cannot uniquely deduce the 1408 bit value $M$. However (hint), let us assume that we can ask for the value $h(M \oplus \Delta)$, for 1408 bit values $\Delta$ that we pick; how can we use that to recover $M$? How can we extend this observation to cases where the length of $M$ is a multiple of 1408 bits?

Assuming you're asking about collision resistance, well, how can we pick a value $M$ so that $h(M)$ is a predetermined value? Hint: look at how the AES uses the last round subkeys.

Improve this answer
$\endgroup$
3
$\begingroup$

Restrict to $n=1$. Let $M$ and $M'$ be two 1408-bit messages differing in the last 128 bits. What's $h(M)\oplus h(M')$? Can a function $h$ with this property be one-way?

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This is a nice attack, basically allowing an attacker to find a preimage for any hash value. $\endgroup$ – tylo Oct 14 '13 at 13:40
1
$\begingroup$

Using the key as the message produces a one-way response. Then if you break the message into 128-bit chunks $m_1$, $m_2$, ... you can use:

$k_1 = m_1; r_1 = E(k_1,k_1);$

$k_2 = r_1 \oplus m_2; r_2 = E(k_2,k_2);$

$k_3 = r_2 \oplus m_3; r_3 = E(k_3,k_3);$

...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.