Twin Keys

In the two keys that we have to "insert", one has to start with the prefix of "CryptoHack Secure Safe", and the other must not have this prefix. The two keys have to pass this check:

xxxxxxxxxx
h1 = hashes[0]
h2 = hashes[1]
for i in range(2, 2**(random.randint(2, 10))):
    h1 = xor(self.magic1, xor(h2, xor(xor(h2, xor(h1, h2)), h2)))
    h2 = xor(xor(xor(h1, xor(xor(h2, h1), h1)), h1), self.magic2)
...
if h1 == h2:
    return {"msg": f"The safe clicks and the door opens. Amongst its secrets you find a flag: {FLAG}"}

The xor is flushed out as the number of iterations is a even number, and note that in the calculation of h2, it reuses the value from h1 in the previous line. We can easily verify this by replacing the initial value of h2 to be h1 also.

Therefore, the task is to find two keys, given the prefix constraint, such that they have the same MD5 hash. We can use hashclash to help us in this challenge. Specifically, we will use the Unicoll implementation in hashclash. After building the source code following the instruction, we will run the poc_no.sh script.

Reading the details on Unicoll, we will run the script by specifying a prefix file with the content of "CryptoHack Secure Safelmao", where the "lmao" part is there as the script will remove the last three bytes in the prefix portion. The commands that we have to run are the following (given that you work in the folder of ipc_workdir, following the instructions to run poc_no.sh from hashclash)

xxxxxxxxxx
echo "CryptoHack Secure Safelmao" > prefix
../scripts/poc_no.sh prefix

Wait for a while, then the two files with the same MD5 hash will be generated, with the file name of collision1.bin and collision2.bin. Sending the hex representation of the two files to the server will return the flag.

Python Implementation:

xxxxxxxxxx
from pwn import *
import json 

# From hashclash poc_no.sh script, prefix is "CryptoHack Secure Safelmao" 
# (the last 4 bytes are arbitrary as the script eats up some 2 bytes at the end of the prefix)
m1 = "43727970746f4861636b2053656375726520536166656c6d522ca4e4ddf8f3410c0299c31b78267cf3dd0a8f200786f6b6aa217215d8759644c28255eafe784d54028d9321aa4fce949d8777176439a7c344b270c286c1730d36e98096cbc127e791e3d96f2c7380107c00117cf9cab68df29d2a856a082ae03df9262e07ff29"
m2 = "43727970746f4861636c2053656375726520536166656c6d522ca4e4ddf8f3410c0299c31b78267cf3dd0a8f200786f6b6aa217215d8759644c28255eafe784d54028d9321aa4fce949c8777176439a7c344b270c286c1730d36e98096cbc127e791e3d96f2c7380107c00117cf9cab68df29d2a856a082ae03df9262e07ff29"

io = remote('socket.cryptohack.org', 13397)
io.recvline()

to_send = {'option': 'insert_key', 'key': m1}
io.sendline(json.dumps(to_send).encode())
print(io.recvline())

to_send = {'option': 'insert_key', 'key': m2}
io.sendline(json.dumps(to_send).encode())
print(io.recvline())

to_send = {'option': 'unlock'}
io.sendline(json.dumps(to_send).encode())
io.interactive()

My initial approach is to use the other script in hashclash, the cpc.sh script, which allows chosen prefix collision. This is used in generating hashquines. I refer to this article detailing how you can generate two images with the same MD5 hash using the cpc.sh script from hashclash.

It takes roughly 10 hours for the script to generate a collision between two files with the prefixes of CryptoHack Secure Safe and W (yes the letter W because why not). I have to run this on a Macbook using M1 chip as my laptop cannot handle the heavy computation needed for this task. Also, there are a lot of things to be tweaked for the script to run correctly on Mac, refer to this PR for more details on fixing the Bash script. Also, there is a warning of Warning: no OS randomness!, which is due to the fact that in lib/hashclash/rng.cpp, the following check does not work:

xxxxxxxxxx
#if defined(__linux__) || defined (__FreeBSD__) // fails
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>  
#include <unistd.h>   
namespace hashclash {
    void getosrnd(uint32 buf[256])
    {
        int fd;
        if ((fd = open("/dev/urandom", O_RDONLY)) < 0) return;
        read(fd, reinterpret_cast<char*>(buf), 256*4);
        close(fd);
    }
}
// some other checks for Windows, not applicable
#else // so it leads to this branch
namespace hashclash {
    void getosrnd(uint32 buf[256])
    {
        std::cout << "Warning: no OS randomness!" << std::endl;
        // without OS randomness
        // use fact that buf is uninitialized
    }
}
#endif

The fixed script is in this link, which basically removes the checks for Linux/Windows OS, as we know /dev/urandom exists on MacOS. Build the source code after modifying the rng.cpp file.

After 10 hours, the following two files (represented by the two hex strings) has the same hash, with one starting with CryptoHack Secure Safe, and the other with the letter W. Unfortunately these hex strings are too big to send (CryptoHack has a 1024 byte limit). However I do learn a lot about how we can generate programs/images/GIFs with the same MD5 hash, using this approach.

xxxxxxxxxx
43727970746f6861636b2053656375726520536166650a3d6284110175d34deb8093de31c1d93045fbbe1e71f00a6375a830aa980000000027191473dd8289bd1f5a8153e6e1d8d3a1be6f2f150f69325761ff562563c1965f86739c45f59e062bdddd998663dde7c358541716bad6a93d0c2e0c16775695f81a19b43bae97f754f09e096e1b86e9a84a4aa39b5cbbf82785346ff631d288895a2c18b0cf0f4473ee293ca6bb1bb1a6bba4a5fba17f983b3b4410d3a2e215e658759648610130c3f328de30d940bf52bfbf0fb0504e3632b99df5f043e6004a05c3e38d419d899dbb03c39d0236c23afe881f64dbc2a9f4df54c30ef0642a75f5120d4231a27f56f7b5a54291c995ba412f7401250729f0c356f0535f8610e14597b4f09e84cf1c6a57e7326948eca5ab32a5b09319782c4e89eadc33f1db0bf902c6622c2a47f5a9d2e7110cb13c876f56138c159c6446eb1eb32809a02ecccd8932b1e067db3347e185a986f187f9a52c3ccefff26c6501d8402cc81f5f99d1fd68af7062d23dfae20f248eb02003ae912334de09ea90855d5a71e6dc2e5f089d97239a366a99b2a307fa4b58ab6dd8bac91cdd5c60f787a637e8b9432c265d79c0f00af50ee415f765db0d6d72f758a238893319a40f8a36522341e368a80ffd0aaec3632f942375c8fd5b49e69a3a76a5e5200d9a75bef039541e66dfbce6a9fae817c32be44b1efcc513e5926d33666dae76658e4366e483fa5dbd23f5778a7799a320d60c4da1ff0356cd18a6b140c4bd1814747b944aacc838c5d58c629a56acfab0d4120ad72fbfb0fc21b2b418b200c758ee99944738d0d51d2d3a810db2f52c14d9d2a0d3afa024912f1c031c3781e13b399943384097d2743af8b48eacdc2cabca

570a6796489725a6fb17281ad35262cbc755d7cd86e55fd083019b4d550661ab88118afa4d34b37559465697ef6c4a0790ccfe1900000000ca244adff67d041d1f5a8153e6e1d8d3a1be6f2f150f69325761ff562563c1965f86739c45f59e062bdddd998663dde7c3585417f6b9d6a93d0c2e0c16775695f81a19b43bae97f754f09e096e1b86e9a84a4aa39b5cbbf82785346ff631d288895a2c18b0cf0f4473ee293ca6bb1bb1a6bba4a5f9a17f983b3b4410d3a2e215e658759648610130c3f328de30d940bf52bfbf0fb0504e3632b99df5f043e6004a05c3e38d419d899dbb03c39d0236c23afe881f64fbc2a9f4df54c30ef0642a75f5120d4231a27f56f7b5a54291c995ba412f7401250729f0c356f0535f8610e14597b4f09e84cf1c6a57e7326948eca5ab32a5309319782c4e89eadc33f1db0bf902c6622c2a47f5a9d2e7110cb13c876f56138c159c6446eb1eb32809a02ecccd8932b1e067db3347e185a986f187f9a52c3ccefdf26c6501d8402cc81f5f99d1fd68af7062d23dfae20f248eb02003ae912334de09ea90855d5a71e6dc2e5f089d97239a366a99b2a307fa4b58ab6dd8bac91cd55c60f787a637e8b9432c265d79c0f00af50ee415f765db0d6d72f758a238893319a40f8a36522341e368a80ffd0aaec3632f942375c8fd5b49e69a3a76a5e5208d9975bef039541e66dfbce6a9fae817c32be44b1efcc513e5926d33666dae76658e4366e483fa5dbd23f5778a7799a320d60c4da1ff0356cd18a6b140c4bd1816747b944aacc838c5d58c629a56acfab0d4120ad72fbfb0fc21b2b418b200c758ee99944738d0d51d2d3a810db2f52c14d9d2a0d3afa024912f1c031c3781e13b599943384097d2743af8b48eacdc2cabca