# Can one build a one-way function from AES?

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.)

-

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? – mikeazo♦ Dec 18 '12 at 15:31
you may assume that it is a multiple of 1408 – fshtea Dec 18 '12 at 15:37
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). – Paŭlo Ebermann♦ Dec 22 '12 at 21:42
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. – D.W. Dec 23 '12 at 7:46

## 2 Answers

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?

-

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.893135130405426, "perplexity_flag": "middle"}