I'm doing a school problem where I'm supposed to find a colliding message in a hashing algorithm that is weak-collision resistant.

The hashing algorithm is AES with a key & message size of 128.

The problem

Given $m$ (message), $k$ (key), find some $m$' such that $$AES_{Decrypt}(k, m) = AES_{Decrypt}(k,m')$$

I've talked to my classmates about this and they tell me that it's really simple, basically a one-liner, if you understand encryption.

Clearly, there's something I'm missing.

  • Welcome to Cryptography. It is nice to you have said it is homework. Now, what are your thoughts? Note: I've edited your question, key is before the message. If anything is incorrect, please edit. – kelalaka Nov 10 at 14:48
  • 2
    Are you sure that this is the assignment? Keyed AES is a pseudo-random permutation or PRP. That means that - by definition - this cannot hold. Different ciphertext blocks always decrypt to different plaintext blocks... @kelalaka It says message size is 128 bits; so a single block. I infer direct use of the block cipher. – Maarten Bodewes Nov 10 at 16:21
  • 1
    Please do use the same account ... creating two separate accounts with the same name is not a good idea. Flag a moderator if you don't know how to do this. – Maarten Bodewes Nov 10 at 16:28
  • No! we don't have $E_k(a+b)=E_k(a)+E_k(b)$ for AES. This is a homomorphism – kelalaka Nov 10 at 17:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.