The Blacksmith

Python is weird.

Introduction

This was one of the more interesting Web challenges from this CTF, because it taught me something new about Python and how it handles augmented assignment statements.

The challenge centered around a "market" API, where customers could buy "regular" and "exclusive" items.

SHOP = {
    "customers": [],
    "inventory": {
        "regular": (
            Weapon("brokensword", 5, 0),
            Weapon("woodensword", 5, 1),
            Weapon("stonesword", 10, 2),
            Weapon("ironsword", 50, 10),
            Weapon("goldsword", 100, 20),
            Weapon("diamondsword", 500, 100),
        ),
        "exclusive": (Weapon("flagsword", 5, 0),),
    },
}

The customer's eligibility to purchase exclusive items depends on the customer's tier, which checks if the customer's fame and the sum of their loyalty point_history exceeds 1337.

@dataclass
class Customer:
    id: str
    gold: int
    loyalty: Loyalty | RestrictedLoyalty

    @property
    def tier(self):
        if (self.loyalty.fame + sum(self.loyalty.point_history)) > 1337:
            return "exclusive"
        return "regular"

    @staticmethod
    def index_from_id(id):
        for idx, customer in enumerate(SHOP["customers"]):
            if customer.id == id:
                return idx
        return None

Exploring the API

The first bug that might have been immediately obvious when visiting the page is that the index page is unauthenticated. Although the customer_id parameter is checked, a HTTPException is called but not raised.

@app.get("/")
def index(customer_id=""):
    customer = Customer.index_from_id(customer_id)

    if customer is None:
        HTTPException(status_code=401)

    shop_items = [
        *SHOP["inventory"]["exclusive"],
        *SHOP["inventory"]["regular"],
    ]
    if LOYALTY_SYSTEM_ACTIVE:
        return shop_items

    return [item for item in shop_items if item.loyalty_points == 0]

This pattern does not repeat itself in any of the other API routes, though. We can see that we in fact need a valid customer_id to access the rest of the features.

if customer_idx is None:
    raise HTTPException(status_code=401)

Let's register a new user. Because LOYALTY_SYSTEM_ACTIVE is set to False, we are given a RestrictedLoyalty which is a namedtuple. This is an immutable data structure. We also start with 5 gold.

LOYALTY_SYSTEM_ACTIVE = False

...

RestrictedLoyalty = namedtuple("RestrictedLoyalty", ["fame", "point_history"])

...

@app.get("/customer/new")
def register():
    if LOYALTY_SYSTEM_ACTIVE:
        customer = Customer(id=uuid4().hex, gold=5, loyalty=Loyalty(1, []))
    else:
        # Ensure loyalty immutable
        customer = Customer(
            id=uuid4().hex, gold=5, loyalty=RestrictedLoyalty(1, [])
        )

    SHOP["customers"].append(customer)
    print(SHOP['customers'])

    return {"id": customer.id}

Visiting this endpoint provides us with a new customer ID.

HTTP/1.1 200 OK
date: Wed, 07 Dec 2022 08:28:52 GMT
server: uvicorn
content-length: 41
content-type: application/json
Connection: close

{"id":"710eab1db93e413192e908358c38c168"}

A /battle endpoint provides a potential way to increase our fame, but as we saw earlier, LOYALTY_SYSTEM_ACTIVE is False so this is not possible.

@app.get("/battle")
def battle(customer_id=""):
    customer_idx = Customer.index_from_id(customer_id)
    if customer_idx is None:
        raise HTTPException(status_code=401)

    is_victorious = choice([True, False])

    if is_victorious and LOYALTY_SYSTEM_ACTIVE:
        SHOP["customers"][customer_idx].loyalty.fame += 1

    message = "You won!" if is_victorious else "You lost!"

    return {"result": message}

Since our goal is to purchase the flagsword, we should take a look at the /buy endpoint. Since this function is rather long, I'll break it up into parts.

First, we have to provide our customer_id and a list of items that we want to buy.

def weapon_from_name(weapons, name):
    for weapon in weapons:
        if weapon.name == name:
            return weapon
    return None
    
...

@app.get("/buy")
def buy_item(customer_id="", items: list[str] | None = Query(default=[])):
    customer_idx = Customer.index_from_id(customer_id)

    if customer_idx is None:
        raise HTTPException(status_code=401)

    if items is None:
        return {"purchased": ""}

The weapons that we are eligible to purchase depends on our customer tier. Since we are a regular plebeian, we can only get to purchase regular weapons. Among the regular weapons, we only have enough gold to buy either a brokensword or a woodensword.

    match SHOP["customers"][customer_idx].tier:
        case "regular":
            get_weapon = partial(
                weapon_from_name, SHOP["inventory"]["regular"]
            )
        case "exclusive":
            get_weapon = partial(
                weapon_from_name,
                [
                    *SHOP["inventory"]["regular"],
                    *SHOP["inventory"]["exclusive"],
                ],
            )
        case _:
            raise HTTPException(status_code=500)
            
    cart = []
    for item in items:
        weapon = get_weapon(item)
        if weapon is None:
            raise HTTPException(status_code=404)
        cart.append(weapon)

If any of the items we are attempting to buy exceeds our available gold, a 403 Forbidden is returned. The total price of all items is summed up and the loyalty points of the items are stored in a point_history list.

    total_price = 0
    point_history = []
    for item in cart:
        if item.price > SHOP["customers"][customer_idx].gold:
            raise HTTPException(status_code=403)
        total_price += item.price
        if item.loyalty_points > 0:
            point_history += [item.loyalty_points]

If there are any loyalty points involved, the code attempts to add the point_history list to our customer point_history record, EAFP-style.

    try:
        if len(point_history) > 0:
            SHOP["customers"][
                customer_idx
            ].loyalty.point_history += point_history
        if SHOP["customers"][customer_idx].gold < total_price:
            raise HTTPException(status_code=403)
        SHOP["customers"][customer_idx].gold -= total_price
    except Exception as e:
        raise HTTPException(status_code=403)

Note that because our loyalty object is an immutable namedtuple, this will definitely raise an exception. In fact, attempting to set any attribute in the namedtuple will cause an AttributeError when performing the assignment.

>>> from collections import namedtuple
>>> RestrictedLoyalty = namedtuple("RestrictedLoyalty", ["fame", "point_history"])
>>> my_loyalty = RestrictedLoyalty(0, [])
>>> my_loyalty.fame = 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: can't set attribute

Finally, if we managed to purchase a flagsword, then we are presented with the flag.

    if "flagsword" in [weapon.name for weapon in cart]:
        return {"purchased": FLAG}

    return {"purchased": cart}

Immutability is Misleading

I didn't manage to spot this bug for quite a while, but luckily this challenge is one that can be solved by fuzzing and logging out as many things as possible.

If we just analyze the behaviour of the application when attempting to set the point_history, we would quickly find that something weird is going on.

try:
    if len(point_history) > 0:
        SHOP["customers"][
            customer_idx
        ].loyalty.point_history += point_history
    if SHOP["customers"][customer_idx].gold < total_price:
        raise HTTPException(status_code=403)
    SHOP["customers"][customer_idx].gold -= total_price
except Exception as e:
    print("Exception: ", e)
    print("Point history: ", SHOP["customers"][customer_idx].loyalty.point_history)
    raise HTTPException(status_code=403)

By sending a request to buy a woodensword (costing 5 gold and having 1 loyalty point) as follows

/buy?customer_id=96d04a31cdca47dba99e588f85d28b1b&items=woodensword

We see that the AttributeError is raised as expected, but somehow, our point history has actually been modified!

Exception:  can't set attribute
Point history:  [1]
INFO:     172.17.0.1:59960 - "GET /buy?customer_id=96d04a31cdca47dba99e588f85d28b1b&items=woodensword HTTP/1.1" 403 Forbidden

Wait... what??? I thought the namedtuple is immutable?

Digging Deeper

I wanted to dig a little deeper to investigate the root cause of this weird behaviour that challenged my Introduction to Programming Python knowledge.

Immutability in Python is tricky - while the tuple itself is immutable, if a tuple contains a mutable object, that object can still be modified in-place. For example, if we have a list within a tuple, that list can still be modified in-place using a method such as append.

>>> tup = (["hello"], )
>>> tup[0].append("world")
>>> tup
(['hello', 'world'],)

But wasn't the code performing assignment instead of an in-place operation? Didn't the exception get raised anyway?

Turns out, all the Introduction to Programming lessons that taught me x += y was the same as x = x + y were wrong. Taking a look at Python's documentation on statements, we would see that it is explained that these two statements are not quite the same.

An augmented assignment expression like x += 1 can be rewritten as x = x + 1 to achieve a similar, but not exactly equal effect. In the augmented version, x is only evaluated once. Also, when possible, the actual operation is performed in-place, meaning that rather than creating a new object and assigning that to the target, the old object is modified instead.

Hmm... ok, but if the operation is only performed in-place, why raise the error?

I then looked up Python's in-place operators, and found that the += operator is just syntactic sugar for the __iadd__ method. Basically, when doing x += y, we are really doing:

x = x.__iadd__(y)

and because some objects like tuples are immutable, it is not guaranteed that the operation would be in-place, so there is still an assignment step regardless of whether the operation was in-place or not.

For list objects, the __iadd__ method (implemented as list_inplace_concat in the CPython source) is just a wrapper for list_extend, an in-place method. We see that the original list object is still returned to make the assignment step work.

static PyObject *
list_inplace_concat(PyListObject *self, PyObject *other)
{
    PyObject *result;

    result = list_extend(self, other);
    if (result == NULL)
        return result;
    Py_DECREF(result);
    return Py_NewRef(self);
}

It is at the assignment step that an error is raised, because the immutable namedtuple does not support item assignments. But by the time this happens, the list has already been modified.

Back to the Challenge

In order to solve this challenge, we just have to buy the woodensword 1337 times. Note that because our gold amount is checked against total_price only after the point_history assignment is attempted, we can just add the woodensword to our cart 1337 times.

if len(point_history) > 0:
    SHOP["customers"][
        customer_idx
    ].loyalty.point_history += point_history
if SHOP["customers"][customer_idx].gold < total_price:
    raise HTTPException(status_code=403)
SHOP["customers"][customer_idx].gold -= total_price

First, we send a request to increase our loyalty point history 1337 times.

Then we could unlock and buy the flagsword!

/buy?customer_id=96d04a31cdca47dba99e588f85d28b1b&items=flagsword

HTTP/1.1 200 OK
date: Wed, 07 Dec 2022 09:35:01 GMT
server: uvicorn
content-length: 83
content-type: application/json
Connection: close

{"purchased":"STF22{this_is_a_dummy_flag_for_your_personal_testing_do_not_submit}"}