Атаки на основе решения задачи ROS / Хабр

В данной статье речь пойдёт о протоколах выработки ЭЦП на базе схемы Шнорра и их безопасности. Так что если какие-то из этих слов звучат для вас скорее как ругательства, то лучше предварительно ознакомиться с данными понятиями. Также следует морально подготовиться к обилию математических выкладок. Если же вы готовы, приятного чтения.

Долгое время, схемы выработки ЭЦП, для которых была доказана безопасность в схеме ROM, считались надёжными, однако всё изменилось после публикации атаки на основе решения задачи ROS. В основе этой атаки лежит принцип параллельного выполнения, при котором противник может получить преимущество в подделке подписи, открывая множество сеансов параллельно.
Но сперва про задачу ROS.

Постановка задачи ROS

По заданным простому числу и параметру стойкости требуется найти $\vec{c} \in \mathbb{F}_p^\ell \text{ и } \vec{p}_0, \dots, \vec{p}_\ell \in \mathbb{F}_p^\ell$ такие, что: $h(\vec{p}_j) = \langle \vec{p}_j, \vec{c} \rangle, \forall j=\overline{1, l+1}$ , где $h(\cdot)$ – некоторая хэш-функция, $\langle \cdot \rangle$ – скалярное произведение векторов. Также задачу можно переформулировать в матричном виде

$\begin{pmatrix} h(\vec{p}_0) \\ h(\vec{p}_2) \\ \vdots \\ h(\vec{p}_l) \end{pmatrix} = \begin{pmatrix} p_{0,0} & p_{0,1} & \cdots & p_{0,l-1} \\ p_{1,0} & p_{1,1} & \cdots & p_{1,l-1} \\ \vdots & \vdots & \ddots & \vdots \\ p_{l,0} & p_{l,1} & \cdots & p_{l,l-1} \end{pmatrix} \cdot \begin{pmatrix} c_0 \\ c_2 \\ \vdots \\ c_{l-1} \end{pmatrix}$

Редукция ROS к обобщённой атаке дней рождений

Для начала заметим, что для любого выполняется:

$\begin{pmatrix} h(i00\ldots0) \\ h(0i0\ldots0) \\ \vdots \\ h(000\ldots i) \\h(?) \end{pmatrix} = \begin{pmatrix} i & 0 & \cdots & 0 \\ 0 & i & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & i \\ ? & ? & \cdots & ? \end{pmatrix} \cdot \begin{pmatrix} \frac{1}{i}h(i00\ldots0) \\ \frac{1}{i}h(0i0\ldots0) \\ \vdots \\ \frac{1}{i}h(000\ldots i) \end{pmatrix}$

После такой подстановки вся сложность решения задачи ROS будет заключаться в поиске нетривиальной линейной комбинации, лежащей в прообразе функции хэширования $h(\cdot)$ . Нетрудно заметить, что эта задача напоминает известную атаку дней рождений Вагнера.

Обобщённая атака дней рождений работает следующим образом. Пусть имеется списков $L_0, L_1, \ldots , L_{l-1}$ , заполненных случайными значениями нормализованной функции хэширования $h(\cdot)$ . Тогда алгоритм Вагнера позволяет за субэкспоненциальное время найти такие $\frac{1}{\alpha_i}h(x_{\alpha_i}) \in L_i$ , что

$\frac{1}{\alpha_0}h(x_{\alpha_0}) + \frac{1}{\alpha_1}h(x_{\alpha_1}) + \ldots \frac{1}{\alpha_{l-1}}h(x_{\alpha_{l-1}}) - h(1\ldots1) \equiv 0 \text{ mod .}$

Применительно к нашей задаче, будем заполнять значениями $\frac{1}{\alpha_i}h(x_{\alpha_i \beta_i})$ , где $x_{\alpha_i \beta_i} = 00 \ldots \alpha_i \ldots 0$ (на месте с номером $\beta_i$ стоит $\alpha_i$ ). Тогда решением задачи будет

$\begin{pmatrix} h(x_{\alpha_0 \beta_0}) \\ h(x_{\alpha_1 \beta_1}) \\ \vdots \\ h(x_{\alpha_{l-1} \beta_{l-1}}) \\ h(11\ldots 1) \end{pmatrix} = \begin{pmatrix} \alpha_0 & 0 & \cdots & 0 \\ 0 & \alpha_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \alpha_{l-1} \\ 1 & 1 & \cdots & 1 \end{pmatrix} \cdot \begin{pmatrix} \frac{1}{\alpha_0}h(x_{\alpha_0 \beta_0}) \\ \frac{1}{\alpha_1}h(x_{\alpha_1 \beta_1}) \\ \vdots \\ \frac{1}{\alpha_{l-1}}h(x_{\alpha_{l-1} \beta_{l-1}}) \end{pmatrix}$

Решение за полиномиальное время

Теорема 1. Если размер задачи $\ell > \lceil$ log $p \rceil$ , то существует полиномиальный алгоритм решения задачи ROS.

Доказательство. Введём следующее обозначение: для многочлена $\rho = \rho_0 + \rho_1 x_1 + \rho_2 x_2 + \ldots + \rho_\ell x_\ell \in \mathbb{Z}p[x_1, \ldots, x_\ell]$ обозначим $\hat{\rho}$ вектор, содержащий на -ой позиции коэффициент при , то есть $\hat{\rho} = (\rho_1, \rho_2, \ldots, \rho_\ell).$ Заметим, что свободный член не включен.

Наша цель найти $(\hat{\rho}_i)_{i \in \{ 1, \ldots, \ell+1 \} }$ и $c = (c_1, \ldots, c_\ell$ ) такие, что $h(\hat{\rho}_i) = \langle \hat{\rho}_i, c \rangle \quad \text{для } i = 1, \ldots, \ell + 1$ , а $h(\cdot)$ - некоторая функция хеширования.

Определим

$\rho_i^0 := x_i, i = \overline{1, \ell}, \text{ т.е. $\hat\rho_1^0 := (1,0\ldots ,0)$, $\hat\rho_2^0 := (0,1\ldots ,0)$, $\ldots$ , $\hat\rho_{\ell}^0 := (0,0\ldots ,1)$}$ $\rho_i^1 := 2x_i, i = \overline{1, \ell}, \text{ т.е. $\hat\rho_1^1 := (2,0\ldots ,0)$, $\hat\rho_2^1 := (0,2\ldots ,0)$, $\ldots$ , $\hat\rho_{\ell}^1 := (0,0\ldots ,2)$}$

Тогда положим $c_i^b := 2^{-b} h(\hat{\rho}_i^b)$ , для и . Если существует $i^* \in {1, \ldots , \ell }$ такое, что $c_i^0 = c_{i}^1$ , то мы нашли решение ROS $(\hat{\rho}_1^0, \ldots, \hat{\rho}_\ell^0, \hat{\rho}_{i^*}^1)$ и $(c_1^0, \ldots, c_\ell^0)$ . И правда

$\begin{pmatrix} h(1,0,\ldots,0) \\ h(0,1,\ldots,0) \\ \vdots \\ h(0,0,\ldots,1) \\ h(0, \ldots, 0,2,0, \ldots, 0) \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & \cdots & 2 & \cdots & 0 \end{pmatrix} \cdot \begin{pmatrix} h(1,0,\ldots,0) \\ \vdots \\ \frac{1}{2}h(0, \ldots , 1, \ldots, 0) \\ \vdots \\ h(0,0,\ldots,1) \end{pmatrix}$

Теперь предположим, что $\forall i \in {1, \ldots \ell}$ $c_{i}^0 \neq c_{i}^1$ , тогда можем построить следующий многочлен

$f_i(x_i) := \frac{x_i - c^0_i}{c^1_i - c^0_i}$

Этот многочлен неспроста напоминает интерполяционный, можно заметить, что , а .

Построим ещё один многочлен

$\rho_{\ell+1}(x) := \sum_{i=1}^{\ell} 2^{i-1}f_i(x_i) = \sum_{i=1}^{\ell} 2^{i-1} \frac{1}{c^1_i - c^0_i} x_i - \sum_{i=1}^{\ell} 2^{i-1} \frac{c_i^0}{c^1_i - c^0_i} = \alpha_0 + \alpha_1 x_1 + \ldots \alpha_{\ell} x_\ell$

Любой элемент поля $\mathbb{F}_p$ можно представить в бинарном виде: $n = \sum_i^{\ell} 2^{i-1} b_i$ , используя введённые ранее обозначения продолжим равенство

$n = \sum_i^{\ell} 2^{i-1} b_i = \sum_i^{\ell} 2^{i-1} f_i(c^{b_i}_i) = \rho_{\ell + 1}(c_1^{b_1}, \ldots, c_{\ell}^{b_{\ell}}) = \langle \hat{\rho}_{\ell+1}, c \rangle + \alpha_0$

В качестве можно взять любой элемент поля $\mathbb{F}_p$ , а значит и $n = h(\alpha_0, \ldots , \alpha_{\ell}) + \alpha_0$ , тогда $h(\alpha_1, \ldots , \alpha_{\ell}) + \alpha_0 = \langle \hat{\rho}_{\ell + 1}, c \rangle + \alpha_0 \Rightarrow h( \alpha_1, \ldots , \alpha{\ell}) = \langle \hat{\rho}_{\ell + 1}, c \rangle$

Таким образом решением задачи ROS будут векторы $(\hat\rho^{b_1}_1, \ldots , \hat\rho_{\ell}^{b_{\ell}}, \hat\rho_{\ell + 1})$ и $c = (c^{b_1}_1, \ldots , c_{\ell}^{b_{\ell}})$ .

Замечание. Стоит заметить, что данное доказательство является конструктивным, т.е. является описанием алгоритма построения задачи ROS.

Пример

Пусть , $h(\cdot)$ = sha256. Найденное решение

$\begin{pmatrix} 85 \\ 77 \\ 15 0\\ 56 \\ 225 \\ 41 \\ 86 \\ 210 \\ 119 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 220 & 16 & 163 & 109 & 151 & 51 & 128 & 135 \end{pmatrix} \cdot \begin{pmatrix} 85 \\ 164 \\ 75 \\ 56 \\ 225 \\ 41 \\ 86 \\ 210 \end{pmatrix}$

Если у кого-то есть желание поэкспериментировать, то вот мой код. В целом, он просто повторяет описанный в теореме алгоритм.

import hashlib

p = 251  
l = 8    

def hash_vector(vec):
    s = ','.join(str(x) for x in vec)
    h = hashlib.sha256(s.encode()).digest()
    val = int.from_bytes(h, 'big') % p
    return val

rho0 = []  
rho1 = []  
for i in range(l):
    vec0 = [0]*l
    vec0[i] = 1
    rho0.append(vec0)
    vec1 = [0]*l
    vec1[i] = 2
    rho1.append(vec1)

h0 = [hash_vector(v) for v in rho0]
h1 = [hash_vector(v) for v in rho1]

inv2 = pow(2, -1, p)
c0 = h0[:]                     
c1 = [(h1[i] * inv2) % p for i in range(l)]  

solution_found = False
for i in range(l):
    if c0[i] == c1[i]:
        for j in range(l):
            print(rho0[j])
        print(rho1[i])
        print("c =", c0)
        solution_found = True
        break

if not solution_found:
    diff = [(c1[i] - c0[i]) % p for i in range(l)]
    alpha = [0]*l
    alpha0 = 0
    pow2 = 1
    for i in range(l):
        factor = (pow2 * pow(diff[i], -1, p)) % p
        alpha[i] = factor
        alpha0 = (alpha0 - pow2 * c0[i] * pow(diff[i], -1, p)) % p
        pow2 = (pow2 * 2) % p

    h_alpha = hash_vector(alpha)
    n = (h_alpha + alpha0) % p
    bits = []
    temp = n
    for _ in range(l):
        bits.append(temp & 1)
        temp >>= 1

    rho_solution = []
    c_solution = []
    for i in range(l):
        if bits[i] == 0:
            rho_solution.append(rho0[i])
            c_solution.append(c0[i])
        else:
            rho_solution.append(rho1[i])
            c_solution.append(c1[i])
    rho_solution.append(alpha)   

    for idx, vec in enumerate(rho_solution[:-1]):
        print(vec)
    print(alpha)
    print("c =", c_solution)

Последние модификации

Чем меньше знаков в двоичном представлении , тем быстрее будет решаться задача ROS, но противник не может повлиять на выбор , так что в статье 2025 года было предложено для уменьшения числа знаков в ходе атаки рассмотреть вместо бинарного представления числа тернарное, более того, оказывается, эту идею можно адаптировать для системы с произвольным основанием. Но метод решения уже становиться итерационным и вероятностным, а мы переносимся из конечных полей на решётки. Выкладки становятся ещё более пугающими, чем раньше, так что останавливаться на них не будем кого заинтересовало, читайте Baccarini A. Revisiting the ROS Problem: Improved Attacks and New Trade-offs / A. Baccarini, G. Malavolta, R. Parisella // Cryptology ePrint Archive, Report 2025/306. — 2025.

Атака на слепую подпись Шнорра

Сценарий атаки

Противник открывает $\ell >$ log параллельных сессий.
Сервер возвращает $\ell$ точек $R'_i, \ i =\overline{1, \ell}$ .
Для $i \in [\ell]$ , противник случайным образом выбирает $(\alpha_{i,0}, \alpha_{i,1}, \beta_i) \stackrel{\$}{\leftarrow} \mathbb{Z}_p^3$ , и определяет $R_{i,b} := \bar{R}_i + \alpha_{i,b}G + \beta_i X$ (для $b \in \{0,1\}$ ). Пусть $c_i^b := H(R_{i,b}, m_i)$ для $i \in [\ell]$ и $b \in \{0,1\}$ .
Предположим, что $c_i^0 \neq c_i^1$ , иначе решение найдено, см. доказательство теоремы 1. Определим многочлен $\rho \in \mathbb{Z}_p[x_1, \ldots, x_\ell]$ :

$\rho(x_1, \ldots, x_\ell) := \sum_{i=1}^\ell 2^{i-1} \cdot \frac{x_i - c_i^0}{c_i^1 - c_i^0} = \sum_{i=1}^\ell \rho_i x_i + \rho_0$

Напомним, что из теоремы 1 следует, что вышеуказанный многочлен таков, что для любого $(b_1, \ldots, b_\ell) \in \{0,1\}^\ell$ , $\rho(c_1^{b_1}, \ldots, c_\ell^{b_\ell}) = \sum_{i=1}^\ell 2^{i-1} b_i$ (5).
Пусть $R_{\ell+1} := \langle \bar{\rho}, \bar{\mathbf{R}} \rangle = \sum_{i=1}^\ell \rho_i \bar{R}_i$ (постоянный член $\rho_0$ не включен).
Определим $c_{\ell+1} := H(R_{\ell+1}, m_{\ell+1})$ и рассмотрим бинарное разложение
$c_{\ell+1} - \sum_{i=1}^\ell \rho_i \beta_i + \rho_0$ : $c_{\ell+1} - \sum_{i=1}^\ell \rho_i \beta_i + \rho_0 = \sum_{i=1}^\ell 2^{i-1} b_i$
Пусть $\bar{c} = (c_1^{b_1} + \beta_1, \ldots, c_\ell^{b_\ell} + \beta_\ell)$ . Завершим открытые сессии $\ell$ с помощью $\bar{c}$ : ответим на -ю открытую сессию с помощью $\bar{c}_i$ , для $i \in [\ell]$ .
Противник получает ответы $\bar{s} := (\bar{s}_1, \ldots, \bar{s}_\ell) \in \mathbb{Z}_p^\ell$ и определяет $s_{\ell+1} := \langle \bar{\rho}, \bar{s} \rangle = \sum_{i=1}^\ell \rho_i \bar{s}_i$
Противник приступает к раскрытию подлинных подписей $\ell$ путем вычисления: $\mathbf{s} := (\bar{s}_1 + \alpha_{1,b_1}, \ldots, \bar{s}_\ell + \alpha_{\ell,b_\ell})$ .
Противник выдает $\ell + 1$ подделок $\bigl(m_i, (R_i, s_i)\bigr)_{i \in [\ell+1]}$ , определяемых как:

$(R_i, s_i) = \begin{cases} \bigl(\bar{R}_i + \alpha_{i,b_i}G + \beta_i X,\; \bar{s}_i + \alpha_{i,b_i}\bigr) & \text{для } i = 1, \dots, \ell, \\[4pt] \displaystyle \bigl(\sum_{i=1}^\ell \rho_i \bar{R}_i,\; \sum_{i=1}^\ell \rho_i \bar{s}_i\bigr) & \text{для } i = \ell + 1. \end{cases}$

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

Надеюсь вышеизложенный материал был кому-то полезен, а вот и список литературы.

Литература

Wagner D. A Generalized Birthday Problem / D. Wagner // Advances in Cryptology – CRYPTO 2002 (LNCS 2442). — 2002. — P. 288–304.
Benhamouda F. The ROS Problem Revisited: Improved Attacks and Consequences / F. Benhamouda, T. Lepoint, J. Loss, M. Orr`u, M. Raykova // Cryptology ePrint Archive, Report 2020/945. — 2020.
Baccarini A. Revisiting the ROS Problem: Improved Attacks and New Trade-offs / A. Baccarini, G. Malavolta, R. Parisella // Cryptology ePrint Archive, Report 2025/306. — 2025.
Schnorr C.-P. Security of Blind Discrete Log Signatures Against Interactive Attacks / C.-P. Schnorr // Information and Communications Security (ICICS 2001) (LNCS 2229). — 2001. — P. 1–12.
Komlo C. FROST: Flexible Round-Optimized Schnorr Threshold Signatures / C. Komlo, I. Goldberg // Cryptology ePrint Archive, Report 2020/852. — 2020.