sudo_u2.0 ·

Table of Contents

Author: pattu_sai

Same as last time, but but but but but but but but but but but but

We were given the ELF binary main.

Extracting the Source
#

I couldn’t really understand much from the static analysis to I tried running it

❯ file main
main: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=91f195f677bd49f09bf72523558d34197cff5dd9, for GNU/Linux 2.6.32, stripped
❯ ./main
Enter row 0 : 123
Enter row 1 : 123
Enter row 2 : 123
Enter row 3 : 123
Enter row 4 : 123
Enter row 5 : 123
Enter row 6 : 123
Enter row 7 : 123
Enter row 8 : 123
YWRkaXRpb25hbF9lbmNyeXB0aW9ueG9y
Traceback (most recent call last):
  File "main.py", line 27, in <module>
    7,
ValueError: chr() arg not in range(0x110000)
[8564] Failed to execute script 'main' due to unhandled exception!

file main.py 💀, interesting, i thought this was an ELF?

a little searching took me to this writeup that mentioned something called PyInstaller used to bundle python projects into a single executable

We can extract the original python source with PyInstXtractor to get individual compiled python files one of which is main.pyc and probably the only one of interest

We can then decompile the compiled python bytecode with any of decompyle3, uncompyle6, or pycdc I followed the writeup and used pycdc giving me main.py

main.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Source Generated with Decompyle++
# File: main.pyc (Python 3.10)

suduko = [
    [ 0, 2, 0, 0, 0, 9, 0, 0, 0],
    [ 0, 0, 8, 0, 3, 0, 0, 5, 0],
    [ 0, 7, 6, 0, 1, 0, 0, 0, 3],
    [ 0, 6, 0, 0, 0, 7, 0, 0, 1],
    [ 3, 0, 9, 0, 0, 0, 4, 0, 7],
    [ 7, 0, 0, 6, 0, 0, 0, 9, 0],
    [ 6, 0, 0, 0, 5, 0, 1, 4, 0],
    [ 0, 5, 0, 0, 6, 0, 3, 0, 0],
    [ 0, 0, 0, 9, 0, 0, 0, 7, 0]
]
enc = [ 495237299, 217684511, 386590850, 528415946, 731927833, 964744145, 679842775, 152369177, 843175228, 495237718, 217684823, 386591029, 528415747, 731927785, 964743470, 679841975, 152369411, 843175008, 495237388, 217684244, 386591311, 528416703, 731928018, 964743376, 679842422, 152369877, 843175846, 495237278, 217684511, 386590967, 528415916, 731927914, 964744137, 679842781, 152369179, 843175275, 495237633, 217684822, 386591028, 528415756, 731927790, 964743463, 679842019, 152369408, 843174965, 495237456, 217684293, 386591308, 528416698, 731928022, 964743391, 679842337, 152369874, 843175929, 495237327, 217684507, 386590969, 528415995, 731927913, 964744082, 679842696, 152369182, 843175228, 495237719, 217684740, 386591080, 528415834, 731927740, 964743458, 679842017, 152369486]
n = []

def pmitonsicnufsihtknihtuoyod(suduko, n):
    m = []
    for i in range(len(suduko)):
        m.append([
            n[i],
            suduko[i].count(0)])
    m.sort((lambda x: x[1]), **('key',))
    print(m)


def YWRkaXRpb25hbF9lbmNyeXB0aW9u(suduko_solution):
    a = (lambda .0: [ str(i) for i in .0 ])(suduko_solution)
    sc = [
        ''] * 9
    for i in range(len(suduko_solution)):
        for j in range(len(a)):
            sc[i] += a[j][i]
        sc[i] = int(sc[i])
    print(sc)

for i in range(9):
    print('Enter row', i, ': ', '', **('end',))
    m = int(input())
    n.append(m // 1000000)
    n.append(m // 1000 % 1000)
    n.append(m % 1000)
for i in range(len(enc)):
    print('YWRkaXRpb25hbF9lbmNyeXB0aW9ueG9y')
    print(chr(enc[i] ^ n[i % len(n)]), '', **('end',))

for a long time the given sudoku was just unsolvable 💀, the handout was fixed later

Analysis
#

Looking at the parts that actually run, first we can understand what input is expected. Each row expects a 9-digit number that it will then split into 3 3-digit numbers and populate the array n with them

Then it decrypts the encrypted flag by XORing each number in the enc array with numbers in n

But the numbers in enc are way larger than 3-digits! There’s no way XORing them with n is going to give you a printable character!

Let’s look at the other included functions

def YWRkaXRpb25hbF9lbmNyeXB0aW9u(suduko_solution):
    a = (lambda .0: [ str(i) for i in .0 ])(suduko_solution)
    sc = [''] * 9
    for i in range(len(suduko_solution)):
        for j in range(len(a)):
            sc[i] += a[j][i]
        sc[i] = int(sc[i])
    print(sc)

the function name translates to additional_encryption in b64, and looking carefully we can note that it creates an array of 9 integers that represent the transpose of the input sudoku matrix

def pmitonsicnufsihtknihtuoyod(suduko, n):
    m = []
    for i in range(len(suduko)):
        m.append([
            n[i],
            suduko[i].count(0)]
        )
    m.sort((lambda x: x[1]), **('key',))
    print(m)

the function name is the reversed string doyouthinkthisfuncisnotimp and what it seems to do is sort an array based on the number of zeroes in the rows of the incomplete sudoku

Working Towards A Solution
#

Eventually the author released an open hint

@everyone Open hint for sudo_u2.0 compare encrypted data with solved_sudoku, columnwise

My teammate had solved the sudoku already

So i tried out the suggested xor in the hint

❯ python solve.py
495237299 ^ 495237618 = 321
217684511 ^ 217684953 = 454
386590850 ^ 386591742 = 892
528415946 ^ 528416379 = 689
731927833 ^ 731928564 = 749
964744145 ^ 964753821 = 10828
679842775 ^ 679842135 = 640
152369177 ^ 152369487 = 342
843175228 ^ 843175296 = 188

and these numbers are a lot more workable with than earlier, also they can now be XORed with our n matrix of 3-digit numbers! (except that weird 10828 but nvm that for now)

I know n is 3-digits at a time row-wise of the solved sudoku, but the first row doesn’t give me printable characters :(

^ 423 = 230 = æ
^ 579 = 901 = ΅
^ 618 = 278 = Ė

So I tried another row till I got something printable, in this case namely the 4th row

^ 265 = 72 = H
^ 497 = 55 = 7
^ 831 = 67 = C

and wow, that’s starting to look like the flag format H7CTF

Continuing in this way I got to my final row order

mod_sudo = [
    [ 2, 6, 5, 4, 9, 7, 8, 3, 1],
    [ 7, 4, 1, 6, 8, 3, 2, 9, 5],
    [ 6, 9, 7, 3, 5, 8, 1, 4, 2],
    [ 9, 1, 8, 2, 3, 6, 7, 5, 4],
    [ 5, 7, 6, 8, 1, 4, 9, 2, 3],
    [ 3, 8, 9, 1, 2, 5, 4, 6, 7],
    [ 1, 5, 4, 7, 6, 2, 3, 8, 9],
    [ 4, 2, 3, 5, 7, 9, 6, 1, 8],
    [ 8, 3, 2, 9, 4, 1, 5, 7, 6],
]

Giving me the string

H7CTF⭫9022b983⬨e13d74ce⬧a7fe7625⭳32eec874⬡12f8f7fa⬨609438e6⬨f7231daf⬤3|

Cleaning this up and submitting did not in fact give me the flag so I raised a ticket and was told there was still another step related to the doyouthinkthisfuncisnotimp function. I tried rearranging the chunks based on the number of zeroes in their original row

For example 9022b983 came from XORing enc with rows 7 and 2 in the original sudoku which both had 6 zeroes in them originally.

Similarily e13d74c3 came from XORing enc with rows 3 and 5 which both had 5 zeroes initially

So I would rearrange my flag to something like H7CTF{e13d74c39022b983...

I am straight up ignoring the unprintable characters and assuming they are just delimiters because idk what else to do with them

I tried the flag that I got in this manner but that wasn’t correct either so I went back to the tickets to cry about it.

10 minutes later the challenge author told me try the cleaned up original flag I had gotten again and that was the flag, I’m guessing something went wrong with the intended 3rd stage of the challenge, 🤷

H7CTF{9022b983e13d74cea7fe762532eec87412f8f7fa609438e6f7231daf3}

solve.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
if __name__ == "__main__":
    # transposed solution in sc
    sc = addn_enc(suduko_solution)
    for i in range(9):
        # change order of submitted sudoku
        m = int(''.join(map(str, mod_sudo[i])))
        n.append(m // 1000000)
        n.append(m // 1000 % 1000)
        n.append(m % 1000)

    flag = []
    for j in range(0, len(enc), 3):
        for i in range(j, j + 3):
            if i >= len(enc):
                break
            # enc[i] XOR columnwise_transpose
            before_xor = enc[i] ^ sc[i%len(sc)]
            # result XOR n[i] coming from modified sudoku solution
            flag.append(chr(before_xor ^ n[i % len(n)]))
    print("".join(flag))