3.9 KiB
Кристалл
Перед нами реализация какого-то постквантового протокола и файл output.json. На первый взгляд это что-то в духе Kyber/ML-KEM: публичная матрица G, секретный вектор k, маленький шум delta и публичный ответ:
\mathrm{response} = G \cdot k + \delta \pmod{q}
Флаг зашифрован AES-GCM, ключ AES получается из самого k, так что вся задача сводится к восстановлению секрета. Ищем и смотрим за что можно зацепиться:
| Параметр | Значение |
|---|---|
n (длина секрета) |
90 |
m (число уравнений) |
180 |
q (модуль) |
3329 |
шум delta |
[-3, 3] |
секрет k |
тернарный: -1, 0, 1 |
Для настоящего Kyber это слишком маленькие значения, высокая размерность делает LWE стойким, а здесь её банально не хватает. Значит, решение — решёточная редукция.
Решение
В output.json лежат параметры протокола, матрица G размера 180 × 90, вектор response и артефакты AES-GCM (nonce, sealed_data, integrity). Секрет, понятно, в явном виде не выдан, но он связан с публичными данными системой уравнений с маленькой ошибкой.
Обращаемся к Kannan's embedding. Берём первые m' = n = 90 уравнений и строим решётку размерности d = m' + n + 1 = 181 с базисом:
B = \begin{bmatrix}
q \cdot I & 0 & 0 \\
G^{\top} & I & 0 \\
\mathrm{response} & 0 & 1
\end{bmatrix}
Идея Kannan's embedding простая: добавить к базису строку с публичным
\mathrm{response}и единицей в нижнем углу — тогда вектор(\delta,\, -k,\, 1)автоматически оказывается в решётке, и он короткий именно потому, что\deltaиkмалы. Подробнее: Galbraith, §18.2.
Внутри решётки сидит очень короткий вектор (\delta,\, -k,\, 1): \delta маленький, k состоит только из \{-1, 0, 1\}, так что он заметно короче случайных векторов базиса. После LLL/BKZ он всплывает в редуцированном базисе. Остаётся пройтись по строкам, у которых последний элемент равен \pm 1, и достать кандидата:
k[j] = -sign * row[m_prime + j]
Проверим результат. Кандидат должен быть тернарным, плюс разница (\mathrm{response}_i - G_i \cdot k) \bmod q на всех 180 уравнениях обязана укладываться в [-3, 3]. Когда правильный k найден, AES-ключ считается точно так же, как в chall.py:
aes_key = sha256(json.dumps(k, sort_keys=True).encode()).digest()[:16]
Обычный AES.MODE_GCM с сохранённым nonce отдаёт флаг.
Флаг
caplag{DOVY5xkLn1zcGGYGe1gW4OnXYg1AQsLs}