2.9 KiB
ShardSlope
В escrow_export.json лежат две группы долей секрета по схеме Шамира с порогом threshold = 2. У калибровочной группы есть две доли, у карантинной — только одна. Для карантинного секрета одной доли обычно недостаточно. Но в экспорте обе группы имеют одинаковый rng_cache_id — проверяем, не переиспользован ли случайный коэффициент.
Решение
При пороге два доли — точки на прямой над конечным полем:
y = s + ax \pmod p,
где s — секрет, а a — случайный коэффициент наклона. Для каждого секрета коэффициент должен выбираться заново. Общий rng_cache_id позволяет предположить, что worker мог переиспользовать его между calibration_batch и quarantine_batch. Вычисляем коэффициент по калибровочной группе и проверяем, даст ли он осмысленный второй секрет.
В раздатке есть recover.py, который восстанавливает калибровочный секрет из двух точек. По этим же точкам вычисляем наклон.
a = (y_2-y_1)(x_2-x_1)^{-1} \pmod p.
Когда a известен, одной карантинной доли (x,y) уже хватает для расчёта s = y-ax \pmod p. Повторяем расчёт на Python:
from pathlib import Path
import json
data = json.loads(Path("public/escrow_export.json").read_text())
p = int(data["field_prime"])
first, second = data["calibration_batch"]["shares"][:2]
x1, y1 = int(first["x"]), int(first["y"])
x2, y2 = int(second["x"]), int(second["y"])
slope = (y2 - y1) * pow(x2 - x1, -1, p) % p
share = data["quarantine_batch"]["shares"][0]
secret = (int(share["y"]) - slope * int(share["x"])) % p
Остаётся перевести число в байты в big-endian:
raw = secret.to_bytes(max(1, (secret.bit_length() + 7) // 8), "big")
print(raw.decode())
Получаем строку флага. Коэффициент, вычисленный по калибровочной группе, позволил восстановить карантинный секрет по одной доле.
Флаг
caplag{slope_reuse_breaks_2of3_escrow}