disclaimer: финальное обрамление и лингвистические корректировки для статейного тона делал с помощью ИИ, само же насыщение исследования производил самостоятельно
Зачем я вообще это пишу
Привет, кодебай! Я grizzzer, капитан команды VON (а с недавних пор и D15C0NN3CT). В финале StudentCTF 2025 мы заняли 9-е место. И вот уже несколько месяцев меня не отпускает один таск с тех квалов. Lucky Duck ******, категория crypto, по паре причин.Первая. Его на квалах не взяла ни одна команда. Ноль решений. Обычно это либо что то очень креативное, либо продуманное, в любом случае стоит себя.
Вторая. Когда я уже потом разобрал райтап до конца — поймал себя на мысли, что это вообще не олимпиадная штука. Слабый генератор случайных чисел плюс склейка остатков по разным модулям реальный класс уязвимостей. Как в 2013-м слили часть Bitcoin-кошельков на Android. Так же выкатывают JWT-секреты и токены сессий, когда разработчик ушёл за random не туда.
Поэтому если вы раньше не слышали про Китайскую теорему об остатках — или слышали, но решили, что это «про древнего китайца и его солдат», — попробую на живом таске показать, как штука работает и где ещё она прилетает на голову.
Оригинальные исходники таска и короткий разбор от организаторов лежат в их репозитории: studentCTF2025 на GitHub. Эта статья — расширенная версия поверх их writeup. Я постарался разжевать каждый кусок и добавить математическую интуицию, которой в коротком writeup'е не хватало.
Что нам выдают
Условие у задачи такое:Выходит как-то Месси расстроенным из казино, проиграв все деньги, а навстречу ему Берлекэмп, а он и говорит: «Пошли покажу, как это делается».
Из условия сразу проскальзывает, куда копать. Лионель Месси тут не случайно — это отсылка к его однофамильцу-математику, Джеймсу Мэсси. Тот самый Мэсси, который вместе с Элвином Берлекэмпом придумал алгоритм Берлекэмпа–Мэсси — этот алгоритм умеет ломать линейные генераторы псевдослучайных чисел. Здесь в идеале сразу поймать намек на стратегию: обыграем казино, научившись предсказывать его «случайности».
Сам сервис — веб-блэкджек. Регистрируешься, тебе выдают JWT-куку и 1000 условных рублей в банке. Цель — довести баланс до 1 000 000. Тогда ручка /api/flag возвращает флаг.
Ставки за один кон — от 50 до 7500. Простая прикидка: даже если каждый раз ставить по максимуму и выигрывать каждую партию подряд, до миллиона нужно сыграть больше сотни раундов. А честно выигрывать каждый раз в блэкджек никак не получится — у казино крошечный, но стабильный матперевес. Как всегда.
Под капотом — LFSR
Лезу в backend. Авторизация нормальная, JWT с секретом, которого у нас нет. Брать штурмом — мимо. Идём дальше: backend/challenge/lfsr.py.
Python:
class LFSR():
def __init__(self, taps: list[int], seed: int):
self.taps = taps
self.state = [int(i) for i in list("{:040b}".format(seed))]
def sum(self, m):
res = 0
for i in m:
res ^= i
return res
def clock(self):
x = self.state[0]
self.state = self.state[1:] + [self.sum([self.state[i] for i in self.taps])]
return x
def gen_number(self):
for _ in range(len(self.state)):
self.clock()
number = "".join(list(map(str, self.state)))
number = int(number, 2)
return number
Оригинальный фрагмент кода — тот самый LFSR.
Если LFSR — это для вас «что-то знакомое, но не помню что» — короткий ликбез. Linear Feedback Shift Register, регистр сдвига с линейной обратной связью. Название мощное. На самом деле — простая железяка из 60-х, придуманная для того, чтобы быстро и дёшево гнать «псевдослучайные» биты.
Схема Fibonacci LFSR: на каждом такте регистр сдвигается, новый бит = XOR выбранных tap-битов.
Принцип такой. У нас есть массив из N бит — это state. На каждом такте делаем три действия:
Выплёвываем самый левый бит наружу — он считается «случайным».
Сдвигаем остальные биты влево.
В освободившуюся справа позицию пишем XOR от нескольких заранее выбранных бит регистра.
Позиции бит, которые мы XOR-им, называются taps. При удачно подобранных taps регистр пробегает все 2^N − 1 ненулевых состояний, прежде чем зацикливается. Для 40-битного регистра — около триллиона разных состояний. На слух — «никогда не повторится».
Красиво. Но есть подвох. LFSR — конструкция полностью линейная. Слово «случайный» тут условное: стоит подсмотреть пару десятков подряд идущих выходных бит — и весь регистр восстанавливается. И taps, и текущее состояние. Поэтому в реальной криптографии чистый LFSR давно никто не использует. А авторы таска как раз на этом и ловят.
Теперь gen_number. На один «случайный» 40-битный state регистр прокручивается 40 раз. Получаем 40 свежих бит — из них собирается число. Каждый вызов gen_number — это просто 40 шагов LFSR друг за другом.
Идём дальше — что в этом регистре изначально и какие у него taps.
Что мы знаем и чего мы не знаем
Taps лежат в импорте из backend/secret.py:
Импорт taps. Самих значений нам, естественно, не дают.
А seed (начальное состояние) генерируется в момент регистрации в backend/auth.py:
bytes_to_long(os.urandom(5)) — наш стартовый state. 5 байт = 40 бит.
На регистрации каждому пользователю выпадает свой 40-битный seed — из криптостойкого os.urandom. Сам seed лежит у сервера в БД, нам его не показывают. Taps общие для всех пользователей, но и их мы тоже не видим. Итого: 40 неизвестных бит seed'а плюс маска taps на 40 бит сверху. Где-то на этом моменте большинство тех кто все же пытались решить, как я потом выяснил, сдавались.
Спойлер:
рано.
От 40 бит к конкретной карте
Логика выдачи карт в start.py:
get_cards: state обновляется раз в 2 игры, колода обновляется раз в 5 игр.
next_card: индекс карты = state mod длина_колоды, карта вынимается из колоды.
Python:
def next_card(state: int, deck: list, cards: list):
index_ = state % len(deck)
cards.append(deck[index_])
deck.pop(index_)
returnЗдесь три важные детали, которые в итоге и ломают всю «случайность».
Первая. Колода — это четыре стандартные колоды по 52 карты, склеенные вместе. Итого 208 карт (строчка main.py: deck = DECK * 4). Каждая карта встречается в этой большой колоде ровно четыре раза.
Вторая. state обновляется не на каждую карту, а раз в две игры. Полная колода пересоздаётся ещё реже — раз в пять игр. Всё, что между этими обновлениями, — одно и то же число state крутится по модулю текущей длины колоды и достаёт оттуда верхнюю карту.
Третья — и самая важная. После каждой выданной карты длина колоды уменьшается на единицу. Значит, модуль, по которому мы берём state, тоже не статичный: сначала 208, потом 207, потом 206, и так далее.
А вот тут — главное наблюдение всей атаки. Каждый раз, когда нам приходит карта, мы можем открыть исходную колоду из 208 карт и сказать: «вот эта карта живёт ровно на четырёх позициях». Позиции фиксированные, мы их знаем. Значит, state по модулю текущей длины колоды совпадает с одним из четырёх известных нам остатков.
Например, нам выпадает двойка червей:
Первая карта — 2-h.
Её четыре позиции в исходной колоде из 208 карт — это 0, 52, 104 и 156. Значит, state на момент выдачи первой карты сравним с одним из {0, 52, 104, 156} по модулю 208. Какой именно — не знаем. Но точно один из четырёх.
Дальше выпадает, скажем, пятёрка треф:
Вторая карта — 5-c.
Её четыре позиции — 29, 81, 133, 185 в исходной колоде. Но колода после выдачи первой карты уже короче на единицу: 207 карт. И значит, state теперь берём по модулю 207, а индексы корректируем с учётом того, какая карта и из какой позиции была изъята.
Из этого вырастает простое дерево: каждая новая карта умножает число возможных остатков на 4 — одну из четырёх копий взяли, но какую именно, неизвестно.
Дерево остатков: после двух карт — 16 веток, после семи — уже 16 384.
Семи карт хватает. 4^7 = 16 384, и при этом у нас в руках семь пар «остаток — модуль» для 40-битного state. На каждой из 16 384 веток пробуем восстановить state через Китайскую теорему об остатках. Дальше среди кандидатов оставляем только тех, кто согласуется со следующими 2–3 картами. Один кандидат выживет — это и есть наш state.
Прежде чем идти дальше — обещанный «крипто для чайников». Что такое Китайская теорема об остатках и почему семь остатков по разным модулям однозначно сходятся в одно число.
Китайская теорема об остатках — на пальцах и не только
Что такое «сравнение по модулю»
Если в памяти ещё жива школьная арифметика — это просто деление с остатком. 17 разделить на 5: в частном 3, в остатке 2. Математики записывают это короче: 17 ≡ 2 (mod 5). Читают «семнадцать сравнимо с двойкой по модулю пять». Удобная компактная запись для длинной фразы «остаток от деления 17 на 5 равен двойке».Самая бытовая модель — часы. На циферблате двенадцать делений. Если сейчас 10 часов, через 5 будет 3: 10 + 5 = 15, а 15 ≡ 3 (mod 12). Мы не говорим «сейчас пятнадцатый час» — говорим «три», и неявно работаем по модулю 12. То же самое с днями недели по модулю 7, месяцами по модулю 12 и так далее.
В программировании это знакомый оператор %. В Python a % b и есть «остаток от деления a на b».
Постановка задачи: одно число по нескольким остаткам
Допустим, у меня в голове есть какое-то число x. Я не скажу вам, какое. Но скажу вот что:- если поделить x на 3, в остатке будет 2;
- если поделить x на 5, в остатке будет 3;
- если поделить x на 7, в остатке будет 2.
На первый взгляд — нет. Таких чисел на бесконечной прямой бесконечно много. Но добавим маленькое условие: «x меньше 105». Ответ становится единственным. Это число 23. Проверим: 23 = 3·7 + 2 (даёт 2 по модулю 3), 23 = 5·4 + 3 (даёт 3 по модулю 5), 23 = 7·3 + 2 (даёт 2 по модулю 7). Сходится.
А почему «меньше 105»? Потому что 3·5·7 = 105. Основная мысль Китайской теоремы об остатках звучит так: если модули попарно взаимно просты, любому набору остатков соответствует ровно одно число в диапазоне от 0 до произведения этих модулей минус один. Ни больше, ни меньше — одно.
Три остатка по модулям 3, 5 и 7 однозначно склеиваются в одно число по модулю 105.
Чуть строже: формулировка теоремы
Пусть нам даны k попарно взаимно простых модулей n₁, n₂, …, nₖ (это значит, что НОД любой пары из них равен единице). И заданы k остатков a₁, a₂, …, aₖ, где 0 ≤ aᵢ < nᵢ. Тогда система сравненийx ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), …, x ≡ aₖ (mod nₖ)
имеет ровно одно решение x в диапазоне 0 ≤ x < N, где N = n₁·n₂·…·nₖ. И ещё одна приятная вещь — это решение можно посчитать за линейное от k время.
Как именно его считать — пошаговый рецепт
Возьмём наши x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) и пройдём руками. Идея — собрать ответ из трёх «кусочков». Каждый кусочек устроен хитро: даёт нужный остаток по своему модулю и ноль по всем остальным.Считаем общий модуль N и так называемые «дополнения» Nᵢ = N / nᵢ:
N = 3 * 5 * 7 = 105
N1 = 105 / 3 = 35 # делится на 5 и на 7, но не на 3
N2 = 105 / 5 = 21 # делится на 3 и на 7, но не на 5
N3 = 105 / 7 = 15 # делится на 3 и на 5, но не на 7
Теперь для каждого Nᵢ нужно найти его обратный по модулю nᵢ — такое число Mᵢ, что Nᵢ · Mᵢ ≡ 1 (mod nᵢ). Обратный точно найдётся, потому что Nᵢ и nᵢ взаимно просты (это сразу следует из попарной взаимной простоты всех модулей). А там, где числа взаимно просты, обратный находится через расширенный алгоритм Евклида — тоже школа.
35 mod 3 = 2 → ищем M1 такое, что 2*M1 ≡ 1 (mod 3) → M1 = 2
21 mod 5 = 1 → ищем M2 такое, что 1*M2 ≡ 1 (mod 5) → M2 = 1
15 mod 7 = 1 → ищем M3 такое, что 1*M3 ≡ 1 (mod 7) → M3 = 1
И финальная сборка:
x = (a1 * N1 * M1 + a2 * N2 * M2 + a3 * N3 * M3) mod N
= (2 * 35 * 2 + 3 * 21 * 1 + 2 * 15 * 1) mod 105
= (140 + 63 + 30) mod 105
= 233 mod 105
= 23
Те самые 23. Итого каждое слагаемое aᵢ · Nᵢ · Mᵢ даёт правильный остаток по своему модулю nᵢ (потому что Nᵢ · Mᵢ ≡ 1 mod nᵢ) и ноль по всем остальным (потому что Nᵢ делится на все nⱼ, кроме nᵢ). Сумма по модулю N это свойство сохраняет — и в итоге единственный ответ.
Почему такое решение единственно
Допустим, нашлось два разных решения x и y, оба в диапазоне [0, N). Тогда разность x − y сравнима с нулём по каждому модулю nᵢ — иначе говоря, делится на каждый nᵢ. А раз все nᵢ попарно взаимно просты, она делится и на их произведение N. Но при этом |x − y| < N. Делиться на N и быть меньше N по модулю одновременно — это возможно только при x − y = 0. Существование мы уже показали выше, конструкцией. Итого: теорема даёт строго одно решение.А если модули НЕ взаимно простые?
А это как раз про наш таск. Длины колоды — 208, 207, 206, 205 и так далее. Это идущие подряд натуральные числа, и среди них полно общих делителей: 208 и 206 оба делятся на 2, 207 и 204 оба делятся на 3, и так далее.В обобщённой версии теоремы условие «попарно взаимно просты» можно ослабить. Достаточно потребовать совместность системы: для любой пары (i, j) остатки aᵢ и aⱼ должны давать одно и то же значение по модулю НОД(nᵢ, nⱼ). Если хотя бы для одной пары это нарушается — система противоречива, решений просто нет.
Чтобы свести задачу с не взаимно простыми модулями к классической, в сплойте реализована простая вещь: каждый модуль делят на НОД с предыдущими модулями. На выходе — набор уже попарно взаимно простых модулей, на котором CRT работает в чистом виде. Вот этот фрагмент из скрипта:
Python:
def get_new_modules(m: list):
result = [0 for _ in range(len(m))]
for i in range(len(m)):
result[i] = m[i]
for i in range(len(result)):
for j in range(i + 1, len(result)):
gcd_ = GCD(result[i], result[j])
if gcd_ != 1:
result[j] = result[j] // gcd_
return resultПосле нормализации передаём остатки (тоже нормализованные) и модули в sage.all.CRT. На выходе — кандидат на state. Если он выдержит сверку с оставшимися 2–3 картами, это и есть честный state.
Сложность
По хорошему, CRT — очень дешёвый алгоритм. Для k модулей он считается за O(k) умножений и k вычислений обратного по модулю (последнее — расширенный Евклид, тоже линейный). Перебор 16 384 веток на CPython с CRT внутри Sage отрабатывает за секунды. Если бы нужно было масштабировать — например, делать 4^15 веток — переписали бы на C++ или распараллелили. Никаких принципиальных ограничений тут нет.Возвращаемся в казино: атака целиком
Теперь у нас в руках весь инвентарь. Соберём цепочку.Шаг 1. Накопить наблюдения
Регистрируемся, делаем минимальную ставку 50, играем несколько кругов. Аккуратно записываем каждую карту и длину колоды на момент её выдачи. На каждый раунд получаем 2 карты себе и 2 карты дилеру. Если жмём «ещё» — добираем себе. Если дилер «добирает до 16» — это тоже наблюдения, всё считается. После 3–4 коротких раундов у нас уже копится 15–20 пар «карта — длина колоды».Главное на этом этапе — не сбиться в порядке. Какая карта какой по счёту в общем потоке наблюдений, не путаться с тем, что state обновляется раз в 2 игры, а полная колода пересоздаётся раз в 5. Любая ошибка в порядке = ошибка во всей системе сравнений = ничего не сойдётся.
Шаг 2. Перебор веток и CRT
Берём первые 7 наблюдений, относящихся к одному и тому же state. Каждая карта даёт нам по 4 кандидата на остаток. Получаем 4⁷ = 16 384 веток. На каждой ветке нормализуем модули (get_new_modules выше) и зовём CRT. Лишние ветки CRT отсеет сам — если система остатков по модулям несовместна, он просто бросит исключение, мы его поймаем и пойдём дальше.
Python:
for k in range(0, 2**14):
try:
remainders = []
k = "{:014b}".format(k)
k = [int(k[l:l+2], 2) for l in range(0, len(k), 2)]
for j, numb in enumerate(k):
if len(remainders) == 0:
remainders.append(indexes_[j][numb])
else:
count = 0
for l in range(len(remainders)):
if remainders[l] < indexes_[j][numb]:
count += 1
remainders.append((indexes_[j][numb] - count))
except Exception:
continue
try:
supposed_states.append(CRT(remainders, new_modules))
except Exception:
continueДальше — отсев. Прогоняем каждого выжившего кандидата по оставшимся 2–3 картам и проверяем, что состояния согласуются. У правильного state все наблюдения сходятся в одну точку.
Повторяем процедуру на двух последовательных state. На выходе — два честных, идущих подряд 40-битных значения state. Это вход для следующего шага.
Шаг 3. Берлекэмп–Мэсси — добываем taps
У нас два state, каждый по 40 бит — 80 бит подряд из выхода LFSR. Для восстановления секретных taps в 40-битном LFSR этого с запасом: минимальный полином строится из ~2L бит, где L — длина регистра. У нас ровно 2·40 — впритык, но хватает.Алгоритм Берлекэмпа–Мэсси итеративно подбирает самый короткий LFSR, который выдаёт нашу битовую последовательность. На вход — биты, на выход — характеристический полином этого LFSR. На словах это магия, в Sage — буквально пять строк:
Код:
def crack_lfsr(states):
F = GF(2)
binary_stream = []
for i in states:
binary_stream.extend([F(int(k)) for k in "{:040b}".format(i)])
g = berlekamp_massey(binary_stream)
print(g)
taps = []
for i, degree in enumerate(g):
if i != 40 and degree == 1:
taps.append(i)
return tapsЧто мы получим на выходе:
x^40 + x^23 + x^21 + x^18 + x^16 + x^15 + x^13 + x^12 + x^8 + x^5 + x^3 + x + 1
А секретные taps — просто ненулевые коэффициенты (без x^40):
[0, 1, 3, 5, 8, 12, 13, 15, 16, 18, 21, 23]
Готово. С этой минуты у нас есть и taps, и текущий state, и формула LFSR. Дальше умеем считать любые будущие state и, как следствие, все будущие карты до конца игры.
Шаг 4. Дело техники — копим миллион
А вот эта часть как раз самая нудная. Зная все будущие карты, надо аккуратно вести игру в блэкджек так, чтобы баланс рос максимально быстро. Стратегия из сплойта примерно такая:- Симулируем партию у себя в голове (как в фильме «Револьвер») — карты, которые получим мы, карты дилера.
- Если у нас сразу 21 — ставим максимум (7500) и забираем 1.5× выигрыша.
- Если можно сделать «дабл» с гарантированным выигрышем — делаем дабл с максимумом.
- Если мы можем просто переиграть дилера обычным способом — обычная ставка 7500.
- Если ни одна стратегия не даёт уверенного выигрыша — делаем сорендо (потеря половины ставки) и идём дальше.
При ставке 7500 и средней выигрышности «знающего все карты» баланс растёт быстро. От 1 000 до 1 000 000 эксплойт прокручивается на нашей машине минут за 10–15.
Полный листинг эксплойта со всей этой стратегией лежит в репозитории организаторов (Lucky Duck ******/sploit/sploit.py). Я не буду тащить его сюда целиком — он на ~250 строк, и интересного в нём ровно то, что мы уже разобрали выше.
Флаг
stctf{blackjack_is_super_cool_game!}Заслуженно. И главное — оставляет приятное послевкусие.
Где ещё такая логика выстреливает в реальном мире
Можно отмахнуться: «это всё круто в CTF, а в проде никто LFSR на блэкджек не вешает». Отчасти правда. Но только отчасти. Сам шаблон — «предсказуемый генератор + видимые выходы → восстановили состояние → дальше делаем что хотим» — это не редкая экзотика, а класс реальных багов.1. Слабые ГПСЧ в проде — это до сих пор живёт
Самый известный кейс — Bitcoin-кошельки на Android в 2013 году. SecureRandom в Java на Android той эпохи имел дефект инициализации, и значительная часть приватных ключей генерировалась из малого пространства энтропии. Атакующие просто сканировали блокчейн на слабые ключи и подметали баланс с уязвимых кошельков. Прямого LFSR там не было, но механика та же: предсказуемый random = потерянные деньги.В вебе из той же оперы — древние, но не вымершие баги в PHP rand() / mt_rand(): если использовать их для генерации токенов сброса пароля или CSRF-токенов, Mersenne Twister восстанавливается из 624 последовательных 32-битных выходов. Существуют публичные тулзы вроде untwister от Bishop Fox, которые ровно на этом и работают.
Совсем громкая история: в 2010-м хакеры распаковали PlayStation 3 после того, как Sony забыла использовать случайное nonce в ECDSA-подписях прошивок (одно и то же значение во всех подписях). Один nonce на две подписи — приватный ключ вытаскивается алгоритмически. В нашем казино проблема не в одинаковом nonce, а в слабой периодической структуре. Но класс ошибки тот же.
2. CRT — рабочая лошадка боевой криптографии
В этой статье CRT работала как атакующий инструмент. Но в боевой крипте она чаще всего вообще не про атаку — а про скорость. Самый известный кейс — RSA-CRT: расшифровка и подписание в RSA ускоряются примерно в 4 раза, если считать их «по половинам» в Z/pZ и Z/qZ, а потом склеивать обратно через CRT. Этой оптимизацией пользуется чуть ли не каждая криптобиблиотека: OpenSSL, BoringSSL, libgcrypt, MbedTLS, Crypto++.У этого ускорения есть оборотная сторона — атака Боне–Демилло–Липтона. Представьте, что в момент CRT-вычисления RSA-подписи в железе случается сбой: лазером по чипу, плохая микросхема, что угодно. И одна из «половин» считается с ошибкой. По разности между корректной и ошибочной подписями можно вытащить простой множитель модуля и развалить весь RSA-ключ. Угроза реальная для смарт-карт и HSM, поэтому современные реализации всегда перепроверяют подпись, прежде чем отдать её наружу.
3. Пентест — где это пригодится напрямую
Если в ваших руках оказалось что-то, что генерирует «случайные» токены — JWT-секреты, ключи API, идентификаторы сессий, captcha, шестизначные коды подтверждения — первое, что стоит спросить: «откуда берётся эта случайность». Если ответ «from random import randint» или «Math.random()» — половина работы уже сделана. Дальше дело за наблюдением последовательных выходов и восстановлением состояния.Кстати, Berlekamp–Massey — не только про LFSR. Любой генератор, выход которого описывается линейной рекуррентой над конечным полем (Galois LFSR, NLFSR с линейным выходом, простые конструкции из обучающих материалов), берётся им же. Полезно держать в голове, если приходится реверсить проприетарные протоколы.
4. И что про это говорят у нас
В ру инфобезе про слабые генераторы говорят регулярно. Positive Technologies в отчётах PT ESC разбирают предсказуемость токенов и инкрементальных идентификаторов в чужих продуктах — стабильный класс находок при анализе банковских приложений. У Kaspersky в исследованиях GReAT периодически всплывают примеры из APT-таргетов, где атакующие эксплуатировали слабый ГПСЧ на заражённой стороне, чтобы предсказывать «случайные» имена файлов и доменов C2.Из защитной стороны — Яндекс и Сбер в публичных гайдах по разработке честно проговаривают: для всего, что хоть как-то связано с безопасностью, нужен криптостойкий генератор. В Python это secrets и secrets.token_urlsafe / token_bytes (а не random). В Node — crypto.randomBytes и crypto.randomUUID. В Go — crypto/rand вместо math/rand. В Java — java.security.SecureRandom с явной инициализацией от системного источника. В С/С++ на Linux — /dev/urandom через getrandom(2). Эти штуки в стандартной библиотеке вынесены отдельно специально — чтобы разработчик не уехал на math/random там, где от непредсказуемости зависит безопасность.
5. Что должны были сделать авторы Lucky Duck ******, чтобы атака не сработала
Полезный мысленный тренинг для любого CTF-разбора: на месте автора сервиса понять, что именно надо было сделать, чтобы атака не прошла. Здесь — два пункта:- Заменить LFSR на криптостойкий ГПСЧ. В Python — secrets.SystemRandom() или просто os.urandom для выбора карты. Никакой Berlekamp–Massey против них не работает.
- Не возвращать клиенту никаких карт, по которым можно реконструировать остатки. В реальном онлайн-казино «справедливость» обеспечивается не только секретностью генератора, но и provably-fair схемами (commit-reveal, server seed + client seed), которые позволяют игроку проверить раздачу post factum, не давая возможности её предсказать.
Если зашло — посмотрите ещё
Я недавно ковырял ещё один очень похожий по духу таск — он лежит на платформе Standoff Hackbase в разделе Standalone. Тоже казино, тоже блэкджек, тоже уязвимый алгоритм — но устроено всё по-другому. Без спойлеров, вот ссылка: Standoff Hackbase — таск про блэкджек. Если эта статья зашла — попробуйте, очень рекомендую.Заключение
Надеюсь, у вас после этой статьи примерно то же чувство: что вы теперь понимаете не только, что произошло в этой конкретной задаче, но и зачем эта тема вообще нужна и где она ещё может выстрелить.
Если знаете кого-то, кому интересна крипта, но кажется, что «это сложно и не для меня» — закиньте, лишним не будет. Я до этой задаче тоже не шарил в крипте, только после этого узнал что такое cryptohack.org и добрался до этой статьи. В последнее время в CTF ходит много слухов по поводу «теории мертвого CTF», поэтому чем больше людей научится делать таски подобного уровня по интересности и сложности задания - тем больше шанс сохранить интерес к будущим соревнованиям. А ещё — если увидели ошибку или хотите поспорить по математике или по стратегии в блэкджеке — велкам в комментарии.
