I recently had some time to think about the following cryptography problem:

I've written up a short example in Python3 to show this in action (in case you doubt me!)

For more information: Davies-Meyer.

Given two functions, and find
corresponding such that a collision between the functions occurs.
Logically this means you need to find the correct arguments such that .

apply definitions of

xor both sides by

apply AES decryption to both sides with key

Now we have solved for message 2; the other values we can simply choose at random.

apply definitions of

xor both sides by

apply AES decryption to both sides with key

Now we have solved for message 2; the other values we can simply choose at random.

I've written up a short example in Python3 to show this in action (in case you doubt me!)

```
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor as xor
from Crypto import Random
from binascii import hexlify as hexify
# find a, b, x, and y such that
# AES(y, x) XOR y == AES(b, a) XOR b
# Note that for clarity, these names are not used
# each variable is referred to as a m (message) or a k(key)
# and AES takes arguments (key, message)
def collision():
random = Random.new()
k1 = random.read(16)
m1 = random.read(16)
k2 = random.read(16)
key1 = AES.new(k1, AES.MODE_ECB)
key2 = AES.new(k2, AES.MODE_ECB)
m2 = key2.decrypt(xor(xor(key1.encrypt(m1), k1), k2))
xor1 = xor(key1.encrypt(m1), k1)
xor2 = xor(key2.encrypt(m2), k2)
print("key 1: %s\nkey 2: %s" %(hexify(k1), hexify(k2)))
print("msg 1: %s\nmsg 2: %s" %(hexify(m1), hexify(m2)))
print("AES(key1, msg1) xor key1: %s\nAES(key2, msg2) xor key2: %s" %(hexify(xor1), hexify(xor2)))
if __name__ == '__main__':
collision()
```

For more information: Davies-Meyer.

Cryptography

Python