# compuuuter | web, beginner

**Автор:** —

## Описание

> I build a new scratch competitor

## Деплой

Per-instance: [deploy/](deploy/).

## Выдать участникам

Только [public/compuuuter.zip](public/compuuuter.zip) (исходники сервиса, whitebox).

## Идея

Scratch-подобный «граф-компьютер»: участник собирает блоки с числовыми
операциями, загружает граф в виде JSON, вычисляет его и читает результат
каждой ноды. Нода выглядит так:

```json
{ "id": 1, "type": 2, "args": [10, 11] }
```

`type` выбирает операцию (`const`, `add`, `sub`, `mul`, `xor`, `and`, `or`,
`shl`, `shr`, `mod`), `args` — это id нод, чьи результаты читаются. Граф можно
загрузить, пропатчить, вычислить и прочитать результаты.

Есть скрытый опкод **`type 1337`**, который выдаёт байты флага как
little-endian целое. Использовать его «нельзя»: `compute` начинается с проверки,
которая отклоняет любую ноду с `type == 1337`, а вот `patch` такой проверки
**не делает** — это «просто правка».

**Уязвимость — TOCTOU между проверкой и вычислением** (`deploy/app.py`).
`compute` сначала прогоняет guard («нет ноды с типом 1337»), *потом* строит
таблицу нод и вычисляет. `patch` меняет ноду на месте (тот же объект, на который
ссылается таблица) из другого запроса. Если переключить `type` выходной ноды на
`1337` *после* прохождения guard, но *до* того как вычисление дойдёт до неё —
guard её не увидел, а вычисление спокойно выполнит опкод флага.

**Как выиграть гонку — hash flooding.** У нормального графа окно между проверкой
и использованием — микросекунды, его надо растянуть. Индекс нод — обычный `dict`
по id. Хеши целых в CPython не рандомизируются: на 64-битном CPython для
неотрицательного `n` верно `hash(n) == n % (2**61 - 1)`. Значит все id вида
`BASE + k*(2**61-1)` имеют одинаковый хеш и схлопываются в одну цепочку коллизий,
вставка и поиск `n` таких ключей — O(n²). Несколько тысяч ключей-наполнителей
растягивают вычисление до нескольких секунд — этого хватает, чтобы успеть послать
`PATCH`.

Пересборка раздатки: [build_public.sh](build_public.sh) (упаковывает дерево
`deploy/` в `public/compuuuter.zip`).

## Решение

1. Загружаем граф: `N` нод-наполнителей `const` с id `7 + k*(2**61-1)`
   (`k = 0..N-1`) — «секундомер» — плюс безобидная выходная нода `id=1`,
   последней, чтобы она считалась после всего наполнителя.
2. В одном потоке шлём `POST /compute`. Guard проходит (на 1337 никто не
   ссылается), начинается медленная O(n²) сборка/вычисление.
3. Через ~0.3 с (guard давно завершён, сборка молотит) шлём
   `PATCH {"id":1,"type":1337,"args":[]}`.
4. Когда вычисление дойдёт до ноды 1, оно прочитает `type == 1337`, выполнит
   опкод флага, и результат ноды 1 — это целое с байтами флага. Переводим обратно
   в little-endian байты.

```
$ python3 solve.py http://<host> 6000
ctfcup{...}
```

Если `compute` успел завершиться до патча — повторить (или увеличить `N`).

Разбор: [solve/WRITEUP.md](solve/WRITEUP.md). Эксплоит: [solve/solve.py](solve/solve.py).

## Флаг

```
ctfcup{9cd591ac67dd2dc2b6f439b2c88617be_%s}
```