Rehasher (450)

Challenge description: I wrote a new asymmetric encryption algorithm, and it is truly unbreakable!
Points: 450
Contents: rehasher.zip (containing message.txt and smoothiecrypt.py)

message.txt

I wrote a new asymmetric encryption algorithm, and it is truly unbreakable!

Don't believe me? What if I told you I repeatedly hashed the input using SHA-256?

See you in fifty million years or so when you finally bruteforced my private key! >:)

Cipher text: 15e1c8c4bd2fcb12838d3f48e8fc567adf4fac1c36648eb270ad899a717dfadfccd9b49fc32a726711dd1d7faab7ed81
Public key: 537472347762337272795f536d303074686933535f42337374

We are given some ciphertext, a "public key" and a python program. Let's go through the program step-by-step.

    p = bytes.fromhex(sys.argv[1])
    k = bytes.fromhex(sys.argv[2])

    encrypted = encrypt(p, k)
    print(encrypted.hex())

To start, the python script parses its commandline arguments into bytes objects. To my knowledge, these are equivalent to byte[] in c# and other related languages.

def encrypt(plain_text, key):
    result = bytearray()

    padding_size = math.ceil(len(plain_text) / BLOCK_SIZE) * BLOCK_SIZE
    plain_text = plain_text.ljust(padding_size, b'\0')

    for i in range(0, len(plain_text), BLOCK_SIZE):
        result.extend(encrypt_block(plain_text[i:i+BLOCK_SIZE], key))

    return result

The program will pad the plaintext with 00 bytes until it is a multiple of 16 bytes (the block size). Then, it will loop over each block, encrypt it with the public key, and write it to a result bytes object which is later returned. This looks an awful lot like ECB (Electronic codebook) encryption. In this encryption mode, each block is encrypted on its own, without being influenced by surrounding blocks. This means that, if we wanted to crack this encryption, we only would have to do it 1 block at a time. Additionally, since the last block is padded with zeroes, it may be an easy block to crack since its actual size may be anywhere from 1 to 16 bytes.

def encrypt_block(block, key):
    a = block[0:BLOCK_SIZE // 2]
    b = block[BLOCK_SIZE // 2:BLOCK_SIZE]

    for k in key:
        c = hashlib.sha256(b + bytes([k])).digest()[0:BLOCK_SIZE // 2]
        a, b = b, bytes(x ^ y for x, y in zip(c, a))

    return b + a

The encrypt_block function takes a block and the key, and does some funny stuff to it. Because this code was somewhat hard to understand at first, I decided to rewrite it and sprinkle in some print statements to print the intermediary state.

def encrypt_block(block, key):
    print(f"encrypt_block {block.hex()}")
    a = block[0:BLOCK_SIZE // 2]
    b = block[BLOCK_SIZE // 2:BLOCK_SIZE]

    for k in key:
        print("\tk[i]")

        # take quarter of hash!
        c = hashlib.sha256(b + bytes([k])).digest()[0:BLOCK_SIZE // 2]

        print(f"\t\tc = {c.hex()} sha256(prev_b + key[i]) -> sha256({b.hex()} + {bytes([k]).hex()})")

        # a ^= sha256(b+key[i])
        a = bytes(x ^ y for x, y in zip(c, a))

        # swap(a, b)
        b, a = a, b

        print(f"\t\ta = {a.hex()} (prev_b)")
        print(f"\t\tb = {b.hex()} (c ^ prev_a)")

    return b + a

That looks a lot better! It seems the program will take your block, split it into 2, and iterate over the key to do a series of operations on the half-blocks. These operations seem to be hashing the second half with a character of the key as seed, taking a section of that hash and xoring the first block with it, then swapping the 2 blocks and continuing with the next character in the key. In pseudocode, it would look like this:

for k in key:
    c = hash(b + k)
    a = a ^ c
    a, b = b, a

At this point, I thought I completely understood the algorithm and figured that, since it uses a SHA256 hash, my only option was to create some brute-force cracker. So I looked at my options:

SHA-256 is part of the SHA-2 family, with a blocksize of 32bit words (4 bytes). In our algorithm, we only use 1/4th of the output it produces, which means we could make a slightly optimized brute-force algorithm. However, in the end the gains would be minimal, so I assumed I would have a rate of about 25MH/s (or 25 000 000 tries per second), which is what my GTX 1660 Super gets with Hashcat.
I could look into cracking the last block, since its length could be anything between 1 and 16 bytes in size. Additionally, since I knew that the input blocks would have to be valid ASCII (as they contain the flag) and had to end with } (as that is the end of a valid flag), I could optimize my brute-force cracker to only check those. I ended up trying up to length 5 on my CPU, but to no avail. In the end, this would not have been useful anyway, since the middle block is 16 bytes in size with no known parts.
Looking at the algorithm, I noticed I could just crack the 8-byte half-blocks and work my way backwards through the algorithm. This would mean cracking ~300 values where we have 64 unknown bits in each input. This also went nowhere, because even with the optimistic 25MH/s, it would still require 300 * 2^64 / 2 checks, which would take 110680464442257 seconds, or about 200 times the time since "the last glacial maximum" according to Wolfram Alpha (3.5 million years in total, if you're less historically inclined).

So brute-forcing wouldn't get me anywhere. I decided to let this challenge rest for a bit and to come back to it later.

You may remember that I put some comments in my refactored sourcecode. Assuming some simple input (0000000000000000FFFFFFFFFFFFFFFF) for plaintext, 000102 for public key, we get the following output:

encrypt_block 0000000000000000ffffffffffffffff
        k[i]
                c = ba67e86d827ab4c9 sha256(prev_b + key[i]) -> sha256(ffffffffffffffff + 00)
                a = ffffffffffffffff (prev_b)
                b = ba67e86d827ab4c9 (c ^ prev_a)
        k[i]
                c = 7958108e887d823f sha256(prev_b + key[i]) -> sha256(ba67e86d827ab4c9 + 01)
                a = ba67e86d827ab4c9 (prev_b)
                b = 86a7ef7177827dc0 (c ^ prev_a)
        k[i]
                c = bdd1d6913fe75782 sha256(prev_b + key[i]) -> sha256(86a7ef7177827dc0 + 02)
                a = 86a7ef7177827dc0 (prev_b)
                b = 07b63efcbd9de34b (c ^ prev_a)
07b63efcbd9de34b86a7ef7177827dc0

I ended up staring at this for a bit and finally noticed something odd: the value a after a round is the same value that was passed into the hash function! This allows us to completely reverse the algorithm by doing the following steps:

take the final output (07b63efcbd9de34b86a7ef7177827dc0) and split it up into block b (07b63efcbd9de34b) and a (86a7ef7177827dc0)
calculate c by appending the last character of the key 02 to a, which was b in the previous round. This gives us bdd1d6913fe75782
calculate the a value of the previous round by xoring b with c. this gives us ba67e86d827ab4c9
repeat for every character in the reversed key

I have implemented this algorithm in a C# project and then used it to decrypt each block. The code looks like this:

        private static readonly byte[] PublicKey = "537472347762337272795f536d303074686933535f42337374".FromHexString();

        private static readonly string[] CipherText = {
            "15e1c8c4bd2fcb12838d3f48e8fc567a",
            "df4fac1c36648eb270ad899a717dfadf",
            "ccd9b49fc32a726711dd1d7faab7ed81",
        };

        private static void Main(string[] args)
        {
            Console.WriteLine("Hello, world!");
            Console.Write(Encoding.ASCII.GetString(Decrypt(CipherText[0].FromHexString())));
            Console.Write(Encoding.ASCII.GetString(Decrypt(CipherText[1].FromHexString())));
            Console.Write(Encoding.ASCII.GetString(Decrypt(CipherText[2].FromHexString())));
            Console.WriteLine();
        }

        private static byte[] Decrypt(byte[] full)
        {
            var arr1 = new byte[8];
            var arr2 = new byte[8];
            Array.Copy(full, 0, arr1, 0, 8);
            Array.Copy(full, 8, arr2, 0, 8);
            return Decrypt(arr1, arr2);
        }

        private static byte[] Decrypt(byte[] b, byte[] a)
        {
            foreach (byte k in PublicKey.Reverse())
            {
                var c = a.CrippledHash(k);
                byte[] prev_b = a.ToArray();
                b.XorWith(c);
                a = b;
                b = prev_b;
            }

            var newArr = new byte[16];
            a.CopyTo(newArr, 0);
            b.CopyTo(newArr, 8);
            return newArr;
        }

If we run this, this prints out the following flag RTN{3ncrypt_b3c0m3s_D3crypT_1f_K3y_is_R3v3rs3d}.

After solving this challenge, the challenge author told me that it essentially implements a Feistel cipher, which "makes irreversible operations reversible". So in the end, this encryption wasn't really symmetric and our "public key" was just an encryption key!

The full C# sourcecode can be downloaded here, while the refactored python code (with comments and notes) can be downloaded here.

CTF Writeups

Rehasher (450)