# Traverse | hardware, reverse, fpga, beginner

**Автор:** —

## Описание

> The next of algorithmic technology.
> Flag format: `ctfcup{[0-9a-f]+}`

## Деплой

Не требуется.

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

Только [public/traverse.zip](public/traverse.zip) (`traverse.bin` + `run.py`).

## Идея

Битстрим для Lattice iCE40 HX1K (распиновка iCEstick: clk 12 МГц на пине 21, rx на 9, tx на 8). Внутри: UART 115200 8N1, приёмник и передатчик, и автомат (DFA), у которого 8-битный регистр состояния. Каждый принятый байт двигает автомат по таблице переходов. По `\n` плата отвечает `s`, если автомат стоит в принимающем состоянии, иначе `f`, после чего автомат возвращается в стартовое состояние. `\r` игнорируется.

Автомат принимает ровно одну строку, флаг. Цепочка из 41 состояния читает флаг. От части её состояний отходят ложные ветки (97 состояний): короткие пути по символам из алфавита флага, которые всегда заканчиваются в мёртвом состоянии. Номера состояний случайные, переходы сгенерированы как `case` и после синтеза превращаются в ~700 LUT.

`run.py` запускает битстрим без железа: распаковывает его через icestorm (`iceunpack` + `icebox_vlog`) в gate-level Verilog и гоняет в Icarus Verilog с UART-тестбенчем. С флагом `--hw /dev/ttyUSBx` общается с настоящей платой.

Сборка только открытыми инструментами (yosys + nextpnr-ice40 + icestorm) в Docker: `src/build.sh`. `src/gen.py` генерирует `dfa.v` из флага, а `src/Makefile` собирает `traverse.bin`. Пересборка раздатки: [build_public.sh](build_public.sh) (с флагом `--rebuild` сначала перезапускает `src/build.sh`, иначе просто упаковывает текущие `public/traverse.bin` и `public/run.py` в zip).

## Решение

`iceunpack` + `icebox_vlog` дают нетлист из LUT и FF. Дальше можно разбираться статически: найти 8 FF регистра состояния и логику сравнения принятого байта с константами. Можно и динамически, используя симуляцию как оракул с доступом к внутренним регистрам.

[solve/solve.py](solve/solve.py) делает второе. После отправки строки снимается срез всех FF. Все строки, которые завели автомат в мёртвое состояние, дают одинаковый срез, если не считать регистров с последним принятым байтом; они вычисляются калибровкой на строках вида `~` + c. Остаётся BFS по префиксам: оставляем только те, чей срез отличается от мёртвого, и проверяем каждый кандидат отправкой `\n`. Ложные ветки отмирают за несколько шагов. Работает около 6–7 минут.

## Флаг

```
ctfcup{9f558d7345a6b6df34f6f142732bcc7a}
```