CryptoFox

№ задачи	Название задачи
1	Матрешка (специальный приз «Вычислительные решения»)
2	Смарт-контракта для EVM (специальный приз «Вычислительные решения»)
3	Усложнение линейной рекурренты
4	Решетка с дополнительной структурой
5	Масленица, блинчики и троян-вымогатель (специальный приз Dr Web)
6	Запутанный белый ящик (специальный приз РеКрипт)
7	Внеклассное чтение: Прогрев журналов событий Windows (специальный
	приз «Positive Technologies»)
8	Алгоритм шифрования Незнайки
9	Доверенные токены
10	Схема цифровой подписи семейства Эль-Гамаля
11	Орбиты VULPIS

01

Đề bài

Старый мастер-кукольник славился своими матрёшками. Каждая кукла скрывала внутри себя другую, поменьше, а та — ещё одну. Говорят, в самой маленькой он прятал записку с секретом.

Однажды мастер решил идти в ногу со временем и вырезал свою матрёшку не из липы, а из байтов. Внутри — слой за слоем, загадка за загадкой. Тот, кто доберётся до самой сердцевины, найдёт его секрет.

Вам достался файл Matryoshka.exe. Программа просит ввести пароль. Найдите его.

Описать полностью ход решения. Приложить код программ, написанных для решения задачи.

Подсказка мастер не любил, когда за ним подглядывали.

02

Đề bài

Неумелый пользователь создавал очередную версию своего смарт-контракта для EVM (Etherium virtual machine) и случайно загрузил в мэйннет. К тому же при размещении он отправил туда почти все средства со своего личного аккаунта. Байт код смарт-контракта приведен ниже:

36600080373660006000F0600080808080945AF1600014601B57FD5B3360004780808080945AF100

Придумайте способ, как вернуть свои Ether. Ответ должен содержать значение поля call data спасительной транзакции, а также код вспомогательного смарт-контракта если он необходим.

03

Đề bài

Пусть \(P = \mathrm{GF}(2^n)\) — поле из \(2^n\) элементов, \(u = (u(i))_{i=0}^{\infty}\) — линейная рекуррентная последовательность над полем \(P\) порядка \(m\) максимального периода \(T(u) = 2^{nm} - 1\), \(f : P \to \{ 0, 1 \}\) — сбалансированное отображение, т. е. \(\left| \{ x : f(x) = 1 \}\right| = 2^{n-1}\) и двоичная последовательность \(v\) построена по правилу \(v(i) = f(u(i))\) для всех \(i \geqslant 0\).

1. Докажите, что \(T(v) = T(u)\).

2. Покажите, что для всех \(t\), которые не делятся на число \(\dfrac{2^{nm}-1}{2^n-1}\), расстояние Хэмминга \(\rho_t\) между векторами \((v(0), \ldots , v(T(u) - 1))\) и \((v(t), \ldots , v(t + T(u) - 1))\) равно \(2^{nm-1}\).

3. Опишите все функции \(f\), для которых \(\rho_t = 2^{nm-1}\) при всех \(t = 1, 2, \ldots , T(u) - 1\).

04

Đề bài

В настоящее время криптография на решетках по целому ряду причин является одним из наиболее перспективных направлений в постквантовой криптографии. Пусть задано Евклидово пространство \(\RR^n\) и \(m \leqslant n\) линейно независимых векторов \(\bm{b}_0\), \(\bm{b}_1\), … , \(\bm{b}_{m - 1} \in \RR^n\). Тогда решеткой \(\Lambda\) с базисом \(\bm{b}_0\), \(\bm{b}_1\), … , \(\bm{b}_{m-1}\) будем называть множество

\[\Lambda = \left\{ \sum_{i=0}^{m-1} x_i \cdot \bm{b}_i : x_i \in \ZZ \right\} \in \RR^n.\]

Базис решетки \(\Lambda\) принято записывать в виде матрицы \(\bm{B} \in \RR^{n \times m}\), столбцами которой являются базисные векторы bi. При этом число базисных векторов \(m\) называется рангом решетки \(\Lambda\). Кроме того, если \(m = n\), то решетка называется полной. У одной и той же решетки ранга \(m > 1\) бесконечно много различных базисов. Определителем полной решетки \(\Lambda\) называется абсолютное значение определителя любой ее базисной матрицы: \(\left| \det \bm{B} \right|\). Определитель решетки является ее инвариантом, то есть не зависит от выбранного базиса.

Длиной вектора \(\bm{v} \in \Lambda\) будем называть его евклидову норму \(\lVert \bm{v} \rVert_2\). Стойкость постквантовых криптосистем на решетках основывается на вычислительной сложности некоторых геометрических задач на решетках. Для решения таких задач, как правило, достаточно найти несколько «коротких» векторов решетки. Однако наилучшие современные алгоритмы справляются с таким поиском за экспоненциальное от ранга решетки время (в худшем случае). Более того, в общем случае неизвестны эффективные алгоритмы, позволяющие оценить длину кратчайшего ненулевого вектора решетки. Пусть \(\Lambda\) — полная решетка в пространстве \(\RR^n\), ее \(i\)-ым последовательным минимумом \(\lambda_i(\Lambda)\) называется минимальное число, при котором в \(\Lambda\) можно найти \(i\) линейно независимых векторов, длина которых не превосходит это число. Величину \(\lambda_i(\Lambda)\) можно также интерпретировать как минимальный радиус \(r\), при котором шар с радиусом \(r\) и с центром в нуле содержит \(i\) линейно независимых векторов \(\Lambda\). Например, \(\lambda_1(\Lambda)\) равен длине кратчайшего ненулевого вектора \(\Lambda\).

В общем случае неизвестны эффективные алгоритмы, позволяющие определить точное значение любого из последовательных минимумов решетки. Однако в криптографии часто прибегают к использованию решеток, обладающих некоторой дополнительной структурой. Введение дополнительной структуры позволяет улучшить эксплуатационные характеристики криптосистемы, но в то же время может упростить задачи, на сложности которых основывается стойкость этой криптосистемы. В приведенной ниже задаче предлагается изучить одну решетку, обладающую дополнительной структурой.

Пусть задано кольцо \(R = \ZZ[x] / (x^n + 1)\), где \(n = 1024\), и отображение \(\sigma: R \to \RR^n\), ставящее в соответствие многочлену \(a(x) = \sum_{k=0}^{n-1} a_k x^k \in R\) вектор \(\bm{a} = (_a0, a_1, \ldots , a_{n-1})\) Евклидова пространства \(\RR^n\). Пусть также \(g(x) = 1 + x + x^2 + \cdots + x^{n-1} \in R\). Рассмотрим главный идеал \(\mathcal{I} = (g) \subset R\), порожденный многочленом \(g(x)\).

1. Докажите, что множество \(\Lambda = \sigma(\mathcal{I})\) является полной решеткой в \(\RR^n\).

2. Найдите определитель решетки \(\Lambda\).

3. Найдите (или приведите оценки) последовательные минимумы \(\lambda_1(\Lambda)\) и \(\lambda_n(\Lambda)\) решетки \(\Lambda\).

05

Đề bài

В первый же день масленицы один из серверов в ЦОДе пострадал от атаки хакеров. Админ во второй половине дня так увлекся уничтожением блинчиков, что пропустил запуск трояна-вымогателя. Все данные оказались зашифрованы, а backup’ов нет. Помогите системному администратору не потерять работу: расшифруйте самый важный файл.

Описать полностью ход решения. Приложить код программ, написанных для решения задачи.

06

Đề bài

Любитель линейности, матриц и подстановок положил письмо с текстом в запутанный белый ящик.

Достань его, прочитай текст и получи приз!

Дано 3 файла:

• encr.py: код шифрования

• encr.evh: открытый ключ

• encrypted.bin: шифртекст

Сам алгоритм шифрования заключается в следующем. Каждые 4 бита входной последовательности преобразуются с помощью сгенерированной генератором песевдослучайных чисел (ГПСЧ) подстановки ( S-бокса). Для каждых 4-х бит входной последовательности генерируется свой S-бокс, преобразующая 4 бита входной последовательности в 4 бита выходной последовательности. Таким образом входная последовательность, состоящая из 32-х байт (или 64-х 4-битовых последовательностей), преобразуется с помощью 64-х различных S-боксов (каждые 4 бита обрабатываюются своим S-боксом). Полученная в результате последовательнось из 32-х байт дополняется двумя нулевыми байтами (в итоге получается 34 байта). Эти 34 байта могут быть представлены как 272-битовый вектор-столбец. На этот вектор-столбец умножается сгенерированная с помощью ГПСЧ несингулярная матрица размером 272x272 бит. Результат содержится в файле encrypted.bin. 32-х битная реализация AES подсказывает нам, что преобразование с помощью S-боксов и умножение на матрицу можно объединить, получив в результате набор таблично заданных преобразований - T-боксов. Такие T-боксы представлены в файле encr.evh. Следует обратить внимание, что эти T-боксы принимают на вход 8 бит, а не 4.

Задача: Имея на руках файлы encr.py, encr.evh, encrypted.bin, необходимо из шифртекста восстановить исходный текст (MSG в encr.py).

Описать полностью ход решения. Приложить код программ, написанных для решения задачи.

Giải

Xét ánh xạ affine

\[\begin{split}\begin{array}{ccc} T: & \FF_{2}^8 & \to & \FF_{2}^8 \\ & \bm{x} & \mapsto & \bm{x} \cdot \bm{A} \oplus \bm{b}, \end{array}\end{split}\]

trong đó \(\bm{A}\) là ma trận khả nghịch trên \(\FF_2\) cỡ \(8 \times 8\) và \(\bm{b}\) là vector độ dài \(8\) trên \(\FF_2\).

Ta xem vector \(\bm{x} = (x_0, x_1, \ldots, x_7)\) tương ứng với số nguyên \(x = x_0 + 2 x_1 + \cdots + 2^7 x_7\), do đó ta viết

\[\begin{split}T(x) & = T(x_0, x_1, \ldots, x_7) = (x_0, x_1, \ldots, x_7) \cdot \bm{A} \oplus \bm{b} \\ & = [x_0 \cdot (1, 0, \ldots, 0) \oplus x_1 \cdot (0, 1, \ldots, 0) \oplus \cdots \oplus x_7 \cdot (0, 0, \ldots, 1)] \cdot \bm{A} \oplus \bm{b} \\ & = x_0 \cdot (1, 0, \ldots, 0) \cdot \bm{A} \oplus x_1 \cdot (0, 1, \ldots, 0) \cdot \bm{A} \oplus \cdots \oplus x_7 \cdot (0, 0, \ldots, 1) \cdot \bm{A} \oplus \bm{b}.\end{split}\]

Để ý rằng \(T(0) = \bm{b}\), và

\[\begin{split}T(2^k) & = \underbrace{(0, \ldots, 1, \ldots, 0)}_{\text{vị trí thứ} \ k} \cdot \bm{A} \oplus \bm{b} \\ & = (0, \ldots, 1, \ldots, 0) \cdot \bm{A} \oplus T(0),\end{split}\]

tương đương với

\[x_k \cdot (0, \ldots, 1, \ldots, 0) \cdot \bm{A} = x_k \cdot \left(T(2^k) \oplus T(0)\right).\]

Thay vào \(T(x)\) bên trên ta có

\[T(x) = \left[\bigoplus_{k=0}^7 x_k \cdot \left(T(2^k) \oplus T(0)\right)\right] \oplus T(0).\]

Quá trình mã hóa có thể được viết dưới dạng

\[y_j = \bigoplus_{i=0}^{31} T[i, m_i, j], \quad j = 0, 1, \ldots, 31,\]

với:

• \(T\) là khóa công khai cho bởi đề bài, là một mảng 3D;

• \(m_i\) là thông điệp cần phục hồi;

• \(y_j\) là bản mã được cho.

Giả sử mỗi bảng \(T[\cdot, \cdot, \cdot]\) là một biến đổi affine. Nếu \(x = x_0 + 2 x_1 + \cdots 2^7 x_7\), như ta đã chứng minh trên thì

\[T[i, x, j] = \left(\bigoplus_{k=0}^{7} x_k \cdot T[i, 2^k, j] \oplus T[i, 0, j]\right) \oplus T[i, 0, j].\]

Đặt hằng số

\[C_j = \bigoplus_{i=0}^{31} T[i, 0, j],\]

và đặt

\[\begin{split}y'_j & = y_j \oplus C_j \\ & = \left(\bigoplus_{i=0}^{31} T[i, m_i, j]\right) \oplus \left(\bigoplus_{i=0}^{31} T[i, 0, j]\right) \\ & = \left(\bigoplus_{i=0}^{31}\left(\bigoplus_{k=0}^7 x_{i, k} \cdot \left(T[i, 2^k, j] \oplus T[i, 0, j]\right)\right) \oplus \cancel{T[i, 0, j]}\right) \oplus \left(\bigoplus_{i=0}^{31} \cancel{T[i, 0, j]}\right) \\ & = \bigoplus_{i=0}^{31} \bigoplus_{k=0}^{7} \left(x_{i, k} \cdot \left(T[i, 2^k, j] \oplus T[i, 0, j]\right)\right),\end{split}\]

trong đó \(m_i = x_{i, 0} + 2 x_{i, 1} + \cdots + 2^7 x_{i, 7}\), \(x_{i, k} \in \{ 0, 1 \}\).

Cuối cùng, ta phân tích byte thành bit. Với mỗi vị trị \(j\), mỗi vị trí bit \(b\), \(0 \leqslant b \leqslant 7\), được tính bởi

\[a_{ijk}^{(b)} = \left[\left(T[i, 2^k, j] \oplus T[i, 0, j]\right) \gg b\right] \bmod 2.\]

Lúc này ta chỉ việc giải hệ phương trình tuyến tính trên \(\FF_2\)

\[\bigoplus_{i=0}^{31} \bigoplus_{k=0}^7 a_{ijk}^{(b)} \cdot x_{i, k} = (y'_j \gg b) \bmod 2,\]

với \(j = \overline{0, 33}\) và \(b = \overline{0, 7}\).

Ta có \(34 \cdot 8 = 272\) phương trình và \(32 \cdot 8 = 256\) biến \(x_{i, k}\) nên phương trình có nghiệm duy nhất. Giải phương trình ta được kết quả.

07

Đề bài

Шифр задания: «Внеклассное чтение»: Прогрев журналов событий Windows.

Контекст операции:

Агент под прикрытием Алиса Акулова («Отличница») получает спецсообщение из Центра: немедленно вылететь в Вашингтон для выполнения нового задания. По легенде она — международный независимый журналист и фотограф с многолетним стажем работы на Ближнем Востоке и в Азии. Её реальная миссия — секретная разведывательная операция.

Проблема:

После недавнего крупного шпионского скандала в США службы безопасности ужесточили досмотр техники на границе: сотрудники Таможенно‑пограничной службы тщательно просматривают содержимое устройств и, среди прочего, проверяют журналы событий Windows (Event Viewer). Алиса успела «прогреть» телефон — наполнила его старыми чатовыми переписками и фотографиями, создающими правдоподобную историю поездок. Но с ноутбуком всё сложнее: его удалось купить только сегодня, и свежая установка новой Windows 11 никак не соответствует легенде о многолетней активной работе. Пустые и краткие журналы вызовут подозрения, что недопустимо.

По данным агентурной разведки, пограничные эксперты обращают обращают особое внимание на историю в системных журналах, особенно за последние 2–3 года:

• Event ID 6005, 6006, 6008 — события загрузки и выключения ОС.

• Event ID 4624 — успешный вход пользователя в систему.

Маскировка через перехват API не подходит — эксперты копируют и анализируют сами файлы .evtx в изолированной среде. Изменять системное время тоже неприемлимо: такие действия оставляют собственные следы в журналах, которые легко обнаружить. Скрипт должен быть написан на языке PowerShell, поскольку передача исполнимого кода или запароленного архива может вызвать подозрения у местных органов контрразведки.

Ваша миссия:

Вы — сотрудник российской оперативно-технической службы, сегодня на дежурстве. Вам поручено создать и протестировать инструмент для Алисы.

Цель: Разработать скрипт на PowerShell, который модифицирует непосредственно файлы журналов событий (EVTX), создавая в них правдоподобную историю использования ноутбука за последние 3 года. Скрипт должен быть самодостаточным, не требовать установки дополнительного ПО и оставлять минимум собственных следов.

Ожидаемые результаты:

• исходный листинг на PowerShell для запуска на Windows 11.

• скриншоты экрана с демонстрацией результата до и после запуска инструмента.

Время на выполнение ограничено. Удачи, оперативник. От вашего кода зависит успех миссии!

08

Đề bài

Незнайка решил создать свой алгоритм шифрования (файлы cipher.c, reg.c, reg.h). Он зашифровал очень для себя важный файл (open.txt), убедился, что получил зашифрованный файл (out.txt), и удалил изначальный файл. Потом при попытке восстановить изначальный файл он обнаружил, что забыл записать ключ, и теперь не знает как файл восстановить. Но Незнайка сохранил имотозащиту ключа (keymac.txt) для того, чтобы дать ее Знайке на проверку статистическим свойствам, чтобы убедиться что алгоритм хороший. Сможете ли вы восстановить изначальный файл (или его часть), и найти недочет в алгоритме Незнайки? Или алгоритм Незнайки достаточно хороший, чтобы стать стандартом шифрования Цветочного города?

09

Đề bài

Описать полностью ход решения. Приложить код программ, нВам доверили в использование систему, которая, для проверки прав пользователя, вызывает подпрограмму, принимающую на вход его токен, и возвращающую список его ролей в квадратных скобках, например [user,moderator] значит, что у пользователя есть права user и moderator. В случае неуспеха программа возвращает строку [].

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

Единственное, что доступно — это ранее выгруженные сегменты программы (директория ./app-bin): их состав полон (их конкатенация составляет рабочую программу), однако взаимный порядок неизвестен.

Требуется определить, как сформировать токен, который будет принят программой, то есть такой, для которого она выведет значение желаемых владельцем токена ролей.

В решении необходимо:

1. Привести ход действий, по которому осуществлялся разбор программы.

2. Пример токена, успешно предоставляющего роли user и admin.

3. Общий алгоритм генерации токена для произвольных ролей (на языке программирования).

Дополнительные баллы можно получить за:

• Обеспечение поддержки произвольных дополнительных данных в токене.

• Автоматизацию процесса запуска и тестирования программы локально.

• Приведение архитектурных проблем в программе написанных для решения задачи.

10

Đề bài

Алиса реализовала схему цифровой подписи из семейства подписей Эль-Гамаля. Программная реализация находится в файле sig.py.

Алиса подписывала сообщения из массива messages. Некоторые сообщения она подписывала с помощью своего секретного ключа d (некоторая осмысленное сообщение в виде массива байт), а для некоторых сообщений она имитировала подпись случайной генерацией значения подписи. Результаты работы программы расположены в файле out.txt.

Определите какие именно сообщения из массива messages были подписаны Алисой с помощью своего секретного ключа? Определите значение секретного ключа Алисы.

11

Đề bài

Игорь уже продолжительное время исследует криптографические свойства преобразования шифрмашины VULPIS. Суть преобразований состоит в разбиении открытого текста \(\alpha = (\alpha_1, \ldots , \alpha_{n / 2}, \alpha_{n/2+1}, \ldots, \alpha_n) \in V_n(2^m)\) на два полублока равной длины, которые подаются на вход 1 и 2 цепочки преобразований в соответствии со схемой

В рамках указанной схемы операция «+» определяется соответствующей операцией в аддитивной группе векторного пространства \(V_{n/2}(2)\), а преобразование \(: V_{n/2}(2^m) \to V_{n/2}(2^m)\), \(s(\alpha) = (s'(\alpha_1), \ldots, s'(\alpha_{n/2}))\), \(\alpha = (\alpha_1, \ldots, \alpha_{n/2}) \in V_{n/2}(2^m)\) задается ключевым параметром \(s' \in S(\mathbb{F}_{2^m})\).

В настоящий момент Игоря интересует ответ на вопрос: «существуют ли пары открытый текст-шифртекст, которые нельзя получить, используя преобразование шифрмашины VULPIS» для произвольного значения ключа \(s'\) и четного \(n \in \NN\).

Помогите Игорю ответить на интересующей его вопрос! В случае положительного ответа, также приведите пример хотя бы одной такой пары.

Giải

Gọi \(\alpha = (\alpha_1, \ldots, \alpha_{n/2}, \alpha_{n/2+1}, \ldots, \alpha_n)\) là bản rõ đầu vào, \(\beta = (\beta_1, \ldots, \beta_{n/2}, \beta_{n/2+1}, \ldots, \beta_n)\) là bản mã đầu ra.

Khi đó ta có

\[\begin{split}(\beta_1, \ldots, \beta_{n/2}) & = (s'(\alpha_1 \oplus s'(\alpha_{n/2+1})), \ldots, s'(\alpha_{n/2} \oplus s'(\alpha_n))), \\ (\beta_{n/2+1}, \ldots, \beta_n) & = (s'(\alpha_{n/2+1} \oplus s'(\alpha_1 \oplus s'(\alpha_{n/2+1}))), \ldots, s'(\alpha_n \oplus s'(\alpha_{n/2} \oplus s'(\alpha_n)))).\end{split}\]

Như vậy công thức chung là với mọi \(i\) sao cho \(1 \leqslant i \leqslant n/2\) thì

\[\begin{split}\beta_i & = s'(\alpha_i \oplus s'(\alpha_{n/2+i})), \\ \beta_{n/2+i} & = s'(\alpha_{n/2+i} \oplus s'(\alpha_i \oplus s'(\alpha_{n/2+i}))) = s'(\alpha_{n/2+i} \oplus \beta_i).\end{split}\]

Ta sẽ chứng minh tồn tại các phần tử \(\alpha_i\), \(\alpha_{n/2+i}\), \(\beta_i\) và \(\beta_{n/2+i}\) sao cho không thỏa hai đẳng thức trên với mọi hoán vị \(s'\).

Ta chọn \(\alpha_i = 1\), \(\alpha_{n/2+1} = 0\), \(\beta = 0\), \(\beta_{n/2+1} = 1\) và thay vào hai đẳng thức trên được

\[0 = s'(1 \oplus s'(0)), \quad 1 = s'(0 \oplus 0) = s'(0),\]

thay \(s'(0) = 1\) vào biểu thức phía trước \(0 = s'(1 \oplus 1) = s'(0)\). Điều này là vô lý vì \(s'(0)\) không thể cùng lúc nhận hai giá trị \(0\) và \(1\).

Như vậy với mọi vị trí \(i\), \(1 \leqslant i \leqslant n/2\), chọn \(\alpha_i = 1\), \(\alpha_{n/2+1} = 0\), \(\beta = 0\), \(\beta_{n/2+1} = 1\) sẽ cho ta cặp bản rõ và bản mã không thỏa mãn mô hình mã hóa với mọi hoán vị \(s' \in S(\mathbb{F}_{2^m})\).