# Сплетники - WriteUp

Задача находится в категории Blackbox (реверс без бинарника) и предполагает наблюдение за работой неизвестного протокола. Уже из вывода эндпоинтов `feed`, `status` и `settings` можно получить базовую картину:

- Есть одна сущность, которая задаёт вопросы, и две сущности, которые отвечают.
- Вопросы имеют жёсткую форму: вопросительное слово, существительное, прилагательное и обстоятельство (ровно 4 слова + `?`).
- Ответы всегда длиной 12 "слов" (фрагментов между пробелами) и выглядят как непрерывная последовательность из "Трёх мушкетёров".
- Сообщения валидируются системным участником `SYSTEM`.
- Общение идёт в рамках "эпох".
- Перед концом эпохи запускается выбор нового лидера: все участники задают вопросы и отвечают, а победитель выбирается по числу правильных ответов и средней задержке.

#### По обращению в эндпоинт `status` можно понять следующее:
```json
{
  "epoch": 12841, - номер эпохи
  "mode": "CHAT/ELECTION/PAUSE", - режим фида
  "leader_kid": "d997ba98d4de71fb", - id задающего в эпохе
  "election_duration_sec": 7.0, - длительность элекции
  "post_election_pause_sec": 2.0, - длительность паузы
  "pause_remaining_sec": 0.0,
  "answer_algo": "rsa_vdf_v1", - понимаем, что ответ детерминирован по RSA VDF
  "question_algo": "xs64_v1", - понимаем, что вопросы генерируются xorshift64
  "vdf_N_hex": "a0ede10c4195e4334e0622f66d94977f3d95ed014847af5c908adfd0d016eac45f8feca1edacd09393e8182039ec9fc0a1521a2d29cc7822084cb8bbe1e2e319e8db7243984c632cf87832d0147291f825a0be20c969bbcbfc0dd8c34a2230382584ffcb066aafa48c98ed5596b6f663dcd29a4fd39a5f7ce31177077e19112093595a68af689da8db66dcc68ff85e1b686621a1777ff2d964a6500550ebdf5de1526ec6135e7147f2afae2ddb975899c891e63cd7a534e461b7b7499a62bd55014d6212584a6feac79b51d438165f4ca890982975e7cc4325932a44fed1d0a305c19a80889be8f9e22cfa074dd325e2eda8bd344a280c36c75f3594c41b498f", - параметр N функции получения ответа
  "vdf_T": 10000000, - параметр T функции получения ответа
}
```

#### А если зайдём в `settings`, то увидим:
```json
{
  "vdf_keygen": "det_rsa_xs64_v1", - понимаем, что модуль RSA детерминированно генерируется из xorshift64
  "vdf_prime_bits": 1024,
  "miller_rabin_rounds": 32,
  "kid_algo": "sha256:8bytes:hex_lower",
  "answer_space": 131072, - пространство возможных ответов (dict_size для hint.py)
  "question_vocab": "16x16x16x16", - размерность словаря вопросов
  "book_encoding": "koi8_r",
  "book_sha256_src": "1babc9e9994556119ea941d0de6d867ce15640d55a2ee3801f577cf86633ea00", - помощь для нахождения книги
  "question_xs64_v1": {
    "u64_per_question": 4, - 4 генерации на построение вопроса
    "index_mask_bits": 4 - утекают 4 бита
  },
  "master_seed64_sha256_le64_prefix": "...", - жирный намёк, что есть общая часть сида (64-бит)
  "epoch_seed64_sha256_le64_prefix": "...", - и тут понимаем, что сид зависит от эпохи
}
```

### На этом этапе делаем выводы
- Книгу можно найти из открытых источников по хешу или по характерным фрагментам ответов.
- Ответ детерминирован и зависит от вопроса, эпохи и конкретного отвечающего.
- Для расчёта ответа используется RSA VDF.
- Свои сообщения можно отправлять в фид, если соблюдён формат и подпись.
- Вопросы в `CHAT` генерируются от `epoch_seed64`.
- Генерация RSA-ключа сидится от `master_seed64` (иначе `N` менялся бы по эпохам).

### Эксперименты с сообщениями
Подбор канона подписи показывает, что `sig` считается по всем полям, кроме самого `sig`. Попытка отправить `QUESTION` в обычной фазе не даёт результата, если мы не лидер, а попытка отправить `ELECTION_QUESTION` в `CHAT` сразу возвращает `400`.

При ответах на вопросы получаем либо "самозванец" (неверный ответ), либо просто не успеваем в тайм-окно. Отсюда основной вывод: алгоритм вычисления ответа нужно радикально ускорять.

Тут и начинается ключевая сложность задачи.

### Путь решения (обязательный)
Нужен бот для работы в реальном времени. Он должен уметь генерировать `kid` (как в `hint.py`), корректно подписывать сообщения и отслеживать смену эпох и режимов.

Минимальный функционал бота:

- опрашивать `/status` и понимать текущие `mode` (`CHAT/ELECTION/PAUSE`), `epoch`, `leader_kid`, `vdf_N_hex`, `vdf_T`;
- читать `/feed`, парсить события и хранить локальный лог по эпохам;
- отправлять `POST /feed` только в допустимом режиме (в `PAUSE` будет `409`);
- корректно выставлять `epoch` и подбирать `qid`, чтобы не конфликтовать с уже существующими сообщениями.

После этого восстанавливаем словарь вопросов, а затем `epoch_seed64` по вопросам лидера. В `CHAT` используется `xorshift64`, на вопрос тратится 4 значения `u64`, а в текст попадают только младшие 4 бита каждого значения. Это сводится к линейной системе GF(2), которая решается обычным гауссом.

Зная `epoch_seed64`, получаем `master_seed64 = epoch_seed64 ^ epoch` и проверяем себя по `master_seed64_sha256_le64_prefix` из `settings`. Далее берём `master_seed32 = master_seed64 & 0xFFFFFFFF`.

### Дальнейший путь
Есть два рабочих направления.

#### 1) "В лоб"
Можно писать максимально быструю реализацию VDF (параллель, низкоуровневый язык) и делать предвычисления для заранее выбранной эпохи.

Ключевой шаг - реверс формулы election-сида (из наблюдений видно, что `election`-вопросы зависят от `epoch` и `kid`):
```
seed = master_seed32 ^ epoch ^ kid16
```

Этот сид прогоняется через **xorshift32** (не `xorshift64`) для генерации `election`-вопросов. После предсказания трёх `ELECTION_QUESTION` на нужную эпоху можно выигрывать выборы и получать флаг как лидер.

#### 2) "Каноническое"
Из `settings` видно `vdf_keygen: det_rsa_xs64_v1`, то есть модуль `N` детерминированно генерируется из `xorshift64` на `master_seed64`. Поскольку `vdf_N_hex` стабилен между эпохами, это и есть нужный корневой сид.

Далее воспроизводим генерацию RSA-ключей, получаем `p` и `q`, проверяем `p*q == vdf_N_hex`, а затем считаем VDF-ответы на `ELECTION_QUESTION` через CRT и сокращение итераций до одной модэкспоненты. Это позволяет обогнать боссов, выиграть выборы и получить флаг.

### Хвосты
Эти факты неочевидны, но сильно упрощают решение:

- Ответ с высокой вероятностью можно однозначно преобразовать в вопрос (последовательности из 12 слов в книге почти всегда уникальны).
- Полезно логировать и `feed`, и `status`: между перезапусками задания RSA-ключи не меняются, так что накопленный датасет пригодится позже.
- В фазе элекции игрок даёт не 2 ответа, а 3, поэтому даже относительно медленная реализация может победить в рамках окна.