On the insecurity of ROS
논문은 https://eprint.iacr.org/2020/945.pdf 입니다.
이번 논문을 읽기 위해서는 사전지식이 거의 필요하지 않습니다.
What is ROS?
ROS란, 다음의 약자를 따서 만든 이름입니다.
- Random inhomogeneities in a
- Overdetermined
- Solvable system of linear equations
ROS는 다음과 같이 정의되는 문제입니다.
소수 $p$와 임의의 input을 $\mathbb{F_p}$로 보내는 random oracle $H_{ros}$가 있다고 합시다.
이때, dimension $l$의 ROS 문제는 서로 다른 $\hat{\rho}_i \in \mathbb{F}_p^l$을 각 $1 \le i \le l+1$에 대하여 찾되, $c \in \mathbb{F}_p^l$이 존재하여
\[H_{ros}(\hat{\rho}_i) = \langle \hat{\rho}_i, c \rangle\]이 각 $1 \le i \le l+1$에 대해 성립하게 하는 문제입니다. Random Oracle 위에서 일종의 선형종속성을 찾는 문제라고 볼 수 있으며, 이 문제를 푸는 것으로 reduce 되는 다양한 암호 체계가 있습니다.
Attempt 1: Naive Attack
가장 단순한 생각은 $\hat{\rho}_i = e_i$로 설정하는 것입니다. 이러면
\[c_i = H_{ros}(e_i)\]가 성립하게 되며, 이제
\[H_{ros}(v) = \sum H_{ros}(e_i) v_i\]가 성립하는 $v$를 찾는 것이 문제가 됩니다. $H_{ros}$가 random oracle이므로, 이 식에 대한 어떤 기대도 할 수 없고, 그러니 이 문제를 해결하기 상당히 어렵습니다. 다른 접근이 필요합니다.
Attempt 2: Wagner’s Generalized Birthday Problem
이제부터
\[\rho' = \rho_0 + \sum_{i=1}^l \rho_i x_i \in \mathbb{F}_p [x_1, \cdots, x_l]\]을 linear multivariate polynomial로 생각하고, 이에 대응하는 vector
\[\hat{\rho'} = (\rho_1, \rho_2, \cdots, \rho_l)\]을 생각하겠습니다. 또한,
\[\rho'_i(x_1, \cdots, x_l) = x_i\]를 정의하면 $\hat{\rho’}_i = e_i$가 성립합니다.
이번에는
\[\hat{\rho}_{l+1} = (1, 1, \cdots, 1)\]로 고정하고, 각 $i$에 대해서 random한 $\rho_{i, i} \in \mathbb{F}_p^\times$를 충분히 선택한 다음
\[c_i = \rho_{i, i}^{-1} H_{ros}(\rho_{i, i} e_i)\]를 생각합시다. $\hat{\rho_i} = \rho_{i, i} e_i$라면
\[\langle \hat{\rho}_i, c \rangle = \langle \rho_{i, i} e_i, \rho_{i, i}^{-1} H_{ros}(\hat{\rho}_i) e_i \rangle = H_{ros}(\hat{\rho}_i)\]가 $1 \le i \le l$에서 성립하고, 이제 목표는
\[H_{ros}((1, 1, \cdots , 1)) = H_{ros}(\hat{\rho}_{l+1}) = \langle \hat{\rho}_{l+1}, c \rangle = \sum_{i=1}^l c_i\]입니다. 좌변이 고정이고, 각 $c_i$에 대한 후보는 충분히 많이 뽑을 수 있습니다.
결국, 우리는 list $X_1, X_2, \cdots, X_l$ 각각에서 하나의 원소를 뽑아서, 그 합이 원하는 값이 되도록 하는 것을 목표로 합니다. 이는 Generalized Birthday Problem으로 환원되며, 이에 대한 설명은 바킹독님의 글에 나와있습니다.
Attempt 3: Subset Sum over Powers of 2
Case 1 : $l \ge \lambda = \lceil \log p \rceil$
앞서 우리는 문제를 일종의 subset sum 문제로 변환시켰습니다. 그런데 우리는 값들이 2의 거듭제곱인 경우에는 subset sum 문제를 쉽게 풀 수 있습니다. 그러면 ROS도 이러한 형태의 subset sum 문제로 바꿀 수는 없을까요?
이를 위해서,
\[\rho_{i}'^0 = x_i, \quad \rho_{i}'^1 = 2x_i\]라 하고, 이에 대응하여
\[c_i^0 = H_{ros}(e_i) = H_{ros}(\hat{\rho}_i'^0), \quad c_i^1 = \frac{1}{2} H_{ros}(2e_i) = \frac{1}{2} H_{ros}(\hat{\rho}_i'^1)\]라 합시다. 만약 $c_i^0 = c_i^1$인 $i$가 있다면,
\[\hat{\rho}_i = e_i, \quad \hat{\rho}_{l+1} = 2e_i\]로 두면 바로 ROS가 풀림을 알 수 있습니다.
이제
\[f_i(x_i) = \frac{x_i - c_i^0}{c_i^1 - c_i^0}\]이라고 하면, $f_i(c_i^b) = b$가 $b \in {0, 1}$에서 성립합니다.
이제
\[\rho_{l+1}'(x_1, \cdots, x_l) = \sum_{i=1}^l 2^{i-1} f_i = \rho_{l+1, 0} + \sum_{i=1}^l \rho_{l+1, i} x_i\]라고 합시다. 이제
\[y = H_{ros}(\hat{\rho}_{l+1}') + \rho_{l+1, 0}\]이라 하고 이를 binary로
\[y = \sum_{i=1}^{l} 2^{i-1} b_i\]인 $b_i \in {0, 1}$을 잡읍시다. 이제
\[\hat{\rho}_i = \hat{\rho}_i'^{b_i}, \quad \hat{\rho}_{l+1} = \hat{\rho}_{l+1}', \quad c = (c_1^{b_1}, \cdots , c_l^{b_l})\]이라 합시다. 그러면 각 $1 \le i \le l$에 대해서는
\[\langle \hat{\rho}_i, c \rangle = 2^{b_i} \cdot 2^{-b_i} H_{ros}(\hat{\rho}_i) = H_{ros}(\hat{\rho}_i)\]가 성립하며, $i = l+1$인 경우에는
\[\langle \hat{\rho}_{l+1}, c \rangle = \rho_{l+1}(c_1^{b_1}, c_2^{b_2}, \cdots, c_l^{b_l}) - \rho_{l+1, 0} = \sum_{i=1}^l 2^{i-1} b_i - \rho_{l+1, 0} = H_{ros}(\hat{\rho}_{l+1})\]가 되어 ROS 조건이 만족함을 확인할 수 있습니다.
Case 2 : $l < \lambda = \lceil \log p \rceil$
이제 문제는 $l$ bit로 $\mathbb{F}_p$를 전부 다룰 수 없다는 것입니다. 이를 해결하기 위해서, $l$ bit로 subset sum을 할 수 있을 정도로 값을 Generalized Birthday Problem을 이용해 줄이고 시작합니다.
$L, w \ge 0$이 있고,
\[l \ge \max(2^w - 1, \lceil 2^w - 1 + \lambda - (w+1)L \rceil)\]이면 dimesion $l$ ROS 문제를 $\mathcal{O}(2^{w+L})$ 시간에 풀 수 있습니다.
이를 증명하기 위해,
\[k_1 = 2^w - 1, \quad k_2 = \max(0, \lceil \lambda - (w+1) L \rceil)\]라고 합시다. $1 \le i \le k_2$에 대해서는 Case 1과 동일하게
\[\rho_{i}'^0, \rho_{i}'^1, c_i^0, c_i^1\]를 정의할 수 있고, $f_i$ 역시 정의할 수 있습니다. 이제
\[\rho_{l+1}'(x_1, \cdots , x_l) = \sum_{i=1}^{k_2} 2^{i-1} f_i - \left\lfloor \frac{p-1}{2^{(w+1)L + 1}} \right\rfloor - \sum_{i=k_2+1}^l x_i = \rho_{l+1, 0} + \sum_{i=1}^l \rho_{l+1,i}x_i\]를 정의합니다. 이제 각 $k_2+1 \le i \le k_1+k_2$에 대하여 다음을 정의합니다.
\[H_i(\alpha) = \begin{cases} k_2 + 1 \le i \le l & \alpha^{-1} H_{ros}(\alpha e_i) \\ i = l+1 & \alpha^{-1}H_{ros}(\alpha \hat{\rho}'_{l+1}) + \rho_{l+1, 0} \end{cases}\]이제 Wagner’s Generalized Birthday Problem의 접근 방식으로, 적당한 $\rho_i^\star$가 있어 $y_i^\star = H_i(\rho_i^\star)$라 하면
\[s = \sum_{i=k_2+1}^{l+1} y_i^* \in \left[ - \left \lfloor \frac{p-1}{2^{(w+1)L+1}} \right \rfloor, \left \lfloor \frac{p-1}{2^{(w+1)L+1}} \right \rfloor \right]\]이도록 할 수 있습니다. 이게 $\mathcal{O}(2^{w+L})$이 소요되는 단계입니다.
이제
\[s + \left\lfloor \frac{p-1}{2^{(w+1)L+1}} \right\rfloor = \sum_{i=1}^{k_2} 2^{i-1}b_i\]인 $b_i \in {0, 1}$을 잡을 수 있습니다. 이제
\[\hat{\rho}_i = \begin{cases} 1 \le i \le k_2 & \hat{\rho}_i'^{b_i}\\ k_2 \le i \le l+1 & \rho_i^* e_i\end{cases}\] \[c_i = \begin{cases} 1 \le i \le k_2 & c_i^{b_i} \\ k_2+1 \le i \le l & y_i^* \end{cases}\]라고 하면 끝납니다. 확인을 해보면, $1 \le i \le k_2$에서는
\[\langle \hat{\rho}_i, c \rangle = 2^{b_i} \cdot 2^{-b_i} H_{ros}(\hat{\rho}_i) = H_{ros}(\hat{\rho}_i)\]이며, $k_2 \le i \le l$에 대해서는
\[\langle \hat{\rho}_i, c \rangle =\rho_i^* y_i^* = \rho_i^* H_i(\rho_i^*) = H_{ros}(\rho_i^* e_i) = H_{ros}(\hat{\rho}_i)\]이며, $i = l+1$에 대해서는
\[\langle \hat{\rho}_{l+1}, c \rangle = \rho_{l+1}^* \left( \rho_{l+1}'(c_1, c_2, \cdots, c_l) - \rho_{l+1, 0}\right)\] \[= \rho_{l+1}^* \left( \sum_{i=1}^{k_2} 2^{i-1} b_i - \left \lfloor \frac{p-1}{2^{(w+1)L+1}} \right\rfloor - \sum_{i=k_2+1}^l y_i^* - \rho_{l+1, 0} \right)\] \[= \rho_{l+1}^* \left(s - \sum_{i=k_2+1}^l y_i^* - \rho_{l+1, 0} \right)\] \[= \rho_{l+1}^* \left( y_{l+1}^* - \rho_{l+1, 0} \right) = H_{ros}(\hat{\rho}_{l+1})\]이 되어 증명이 끝납니다.
Results & Conclusion
기본적으로 바킹독님의 글에서 나온 결과가 훨씬 더 강화되었습니다.
저자들은 다음 scheme을 이 공격으로 깼습니다.
- Schnorr Blind Signature
- Okamoto-Schnorr Blind Signature
- CoSi multi-signature scheme
- Two-Round MuSig scheme
- GJKR07 Threshold Signature Scheme
- FROST Scheme, before fix
- Abe-Okamoto Partially Blind Signature
- Brands’ Signature Scheme, U-Prove
자세한 내용은 원 논문을 참고하세요. 핵심 아이디어는 이 글에 설명되어 있습니다.
지금까지 ROS의 공격을 다룬 논문을 알아보았습니다. 사전지식이 많이 필요한 아이디어/논문은 아니었지만, 떠올리기는 매우 어려운 아이디어인 것 같습니다. 이런 논문이 흥미가 많이 갑니다. 글 읽어주셔서 감사합니다.