GG18/GG20 프로토콜 보안 취약점 분석

저자: Max, Safeheron

배경

최근 Fireblocks 팀은 GG18, GG20, Lindel 17 MPC 프로토콜에서 0-day 취약점을 공개했습니다. 이 취약점은 공격자가 MPC 개인 키 조각 뒤에 있는 실제 키를 추출할 수 있게 합니다.

문제가 공개되기 전에 Fireblocks 팀은 Safeheron과 연락을 취하고 적극적인 소통을 진행했습니다. Safeheron이 오픈소스한 GG18/GG20 MPC 프로토콜은 논문 내용을 엄격히 따릅니다. 이 버전의 오픈소스 알고리즘을 사용할 경우 유사한 공격을 받을 수 있습니다. 취약점 공개 전에 Safeheron은 오픈소스 프로젝트에서 발견된 취약점을 이미 수정하였으며, Fireblocks 팀도 패치의 유효성을 확인하는 데 협력했습니다.

Fireblocks 팀은 Safeheron의 C++ 기반 오픈소스 GG18/GG20 프로토콜을 사용하여 POC를 구성하여 이 취약점을 시연하고 커뮤니티가 이해하는 데 도움을 주었습니다.

Safeheron 상용 서비스의 GG18/GG20 MPC 프로토콜은 CMP20/CGGMP21의 관련 제로 지식 증명을 추가로 도입하여 이 취약점의 영향을 받지 않습니다.

취약점 영향 범위

이 문서는 GG18 및 GG20에 대한 취약점의 영향을 중점적으로 다룹니다. GG18/GG20 프로토콜에 대해 공격자는 특수한 Paillier 키를 구성하여 MPC 서명 단계에서 공격을 완료할 수 있습니다. 제한된 서명을 통해 공격자는 다른 참여자의 개인 키 조각을 해독할 수 있습니다.

이번 취약점의 영향 범위는 상당히 넓습니다. MPC 프로토콜의 보안 가정을 영향을 미치기 때문에 거의 모든 주요 오픈소스 GG18/GG20 프로토콜 구현이 이 취약점의 영향을 받습니다.

취약점 원리

MPC 프로토콜을 어떻게 공격할 수 있을까요? 일반적인 MPC 프로토콜은 보안 가정 하에서 증명 가능한 안전성을 가지고 있습니다. 따라서 MPC 프로토콜에 대한 공격은 종종 프로토콜이 의존하는 보안 가정에 초점을 맞춥니다. 보안 가정은 MPC 프로토콜의 기초와 같으며, 보안 가정이 성립하지 않으면 전체 MPC 프로토콜이 영향을 받게 됩니다.

GG18/GG20을 예로 들면, 이 MPC 프로토콜은 Paillier 동형 암호화 알고리즘의 안전성에 의존합니다. Paillier 동형 암호화 알고리즘은 복합 나머지 클래스의 어려운 문제를 기반으로 설계된 널리 사용되는 덧셈 연산을 만족하는 동형 암호화 알고리즘입니다. 이번 취약점은 Paillier 동형 키의 구성을 타겟으로 하여 단계적으로 $$MtA$$ 프로토콜과 관련 제로 지식 증명 프로토콜을 공격하여 유효한 공격을 형성했습니다.

전체 공격의 핵심 논리는 다음과 같습니다:

(1) KeyGen 서브 프로토콜 단계에서 공격자는 안전하지 않은 동형 키를 구성합니다.
(2) Sign 서브 프로토콜 단계:
(a) 두 개의 $$MTA$$ 프로토콜이 실행되는 동안, 예를 들어 $$MtA(k,x)$$와 $$MtA(k,\gamma)$$ 프로토콜에서 공격자는 자신의 안전하지 않은 동형 키를 기반으로 불법적인 $$k$$ 값을 구성합니다;
(b) 안전하지 않은 동형 키의 특성을 이용하여 악의적인 제로 지식 증명을 구성하여 다른 참여자를 속이고 검증을 완료합니다;
(c) 공격자는 공격 대상과 서명을 완료하고 과정에서 $$\mu$$를 기록합니다.
(3) 여러 번 Sign 서브 프로토콜을 반복하여 중국 나머지 정리를 기반으로 상대방의 개인 키 조각을 계산합니다.

취약점 공격 방법

이번 섹션에서는 공격의 세부 사항을 자세히 설명합니다. 일반적인 MPC 임계 다중 서명 시나리오에는 여러 참여자가 존재하며, 이들 참여자는 서로 공격을 시작할 수 있으며 공격 방식은 완전히 동일합니다.

공격 방법을 소개하기 위해, MPC 지갑이 세 명의 당사자 A, B 및 C에 의해 공동으로 생성되고 사용된다고 가정해 보겠습니다. 각 당사자는 각각 자신의 개인 키 조각 $$xA$$, $$xB$$ 및 $$xC$$를 관리합니다. 이 취약점을 이용하여 당사자 A는 당사자 B와 C를 공격하여 상대방의 개인 키 조각을 얻을 수 있습니다. 이번 섹션에서는 "당사자 A가 당사자 B를 공격하려고 시도하는 경우"를 예로 들어 당사자 B의 개인 키 조각 $$xB$$를 추출하는 방법을 소개합니다. (당사자 A는 동일한 방식으로 당사자 C의 개인 키 조각 $$x_C$$를 추출할 수 있으며, 여기서는 생략하겠습니다.)

4.1 준비 단계------안전하지 않은 동형 키 구성

첫 번째 공격은 KeyGen 서브 프로토콜 실행 과정에서 발생하며, 이를 공격 준비 단계라고 부를 수 있습니다. 공격 준비 단계에서 공격자 당사자 A는 안전하지 않은 Paillier 동형 키를 성공적으로 구성했습니다.

정상적인 동형 키 구성 과정은 다음과 같습니다:

• 안전한 소수 $$p, q \in \{0,1\}\^{1024}$$를 무작위로 선택합니다.
• 계산합니다.
• $$ N_A = p * q$$
• $$\lambda_A = (p-1)*(q-1)$$

공격자 당사자 A가 동형 키를 구성하는 과정은 다음과 같습니다:

• 소수 $$(p1, p2, …, p{16}, q)$$를 무작위로 선택합니다. 여기서 $$pi$$는 서로 다른 작은 소수이고, $$q$$는 큰 소수입니다.
• 계산합니다.
• $$ NA = \Pii{pi} * q$$, $$NA$$의 길이는 2048 비트입니다.
• $$\lambdaA = \Pii(p_i-1)*(q-1)$$

우리는 공격자 당사자 A가 구성한 Paillier 공개 키 $$N_A$$가 많은 작은 인자를 포함하고 있음을 발견할 수 있습니다. 공격자 당사자 A가 구성한 불법적인 Paillier 키가 당사자 B를 속일 수 있을까요? 결국 여기서는 당사자 B가 검증할 제로 지식 증명을 구성해야 합니다.

위의 GG18/GG20의 $$KeyGen$$ 프로토콜을 자세히 살펴보면, 여기서는 $$Square-Free$$ 제로 지식 증명을 제공하기만 하면 됩니다. 공격자가 구성한 Paillier 동형 공개 키 $$N_A$$는 서로 다른 소인자만 포함하고 있으므로, 이 구성 방법은 분명히 $$Square-Free$$ 제로 지식 증명을 통과할 수 있습니다.

4.2 공격 단계: Sign 서브 프로토콜

주의: 공격은 16번의 Sign 서브 프로토콜을 성공적으로 실행해야 하며, 현재는 $i$번째 Sign 서브 프로토콜을 실행하고 있다고 가정합니다.
Sign 서브 프로토콜에서 처음 몇 라운드는 $$MtA$$ 프로토콜을 실행해야 하며, GG18 (https://eprint.iacr.org/2019/114.pdf) 4.2 절을 참조합니다.

• $$ MtA(kA, \gammaB) : \alphaA + \betaB \leftarrow kA * \gammaB$$
• $$ MtA(kA, xB) : \muA + \nuB \leftarrow kA * xB$$

정상적인 계산 과정은 다음과 같습니다:

• 무작위로 $$k_A \in Zq$$를 선택합니다.
• $$Enc(k_A)$$를 계산합니다.
• $$MtA$$ 프로토콜을 실행합니다.
• $$ MtA(kA, \gammaB) : \alphaA + \betaB \leftarrow kA * \gammaB$$
• $$ MtA(kA, xB) : \muA + \nuB \leftarrow kA * xB$$
• 무작위 수 $$kA$$에 대한 암호문 $$Enc(kA)$$의 제로 지식 증명을 생성합니다. GG18 (https://eprint.iacr.org/2019/114.pdf) A.1 절 Range Proof을 참조합니다.
• 이후 정상적으로 MPC Sign 서브 프로토콜을 완료합니다.

공격자의 계산 과정은 다음과 같습니다:

• 특수한 $$k_A$$ 값을 구성합니다.
• 특수하게 구성된 $$k_A$$ 값을 사용하여 정상적으로 $$MtA$$ 프로토콜을 실행합니다.
• 악의적인 제로 지식 증명을 구성하여 속임수를 시행합니다.
• 이후 정상적으로 MPC Sign 서브 프로토콜을 완료합니다.

이제 구체적인 작업 방식을 소개합니다.

특수한 $$k_A$$ 값 구성

공격자는 무작위 값을 사용하지 않고, $i$번째 MPC Sign 서브 프로토콜에서 다음과 같은 방식으로 $$kA$$를 구성합니다. $$ kA = NA / pi $$
주의: 이 특수하게 구성된 $$k_A \gg q\^3$$는 정상적인 경우 예상 제로 지식 증명을 통과할 수 없습니다. 여기서 $$q$$는 타원 곡선의 차수입니다.

제로 지식 증명 구성

GG18 프로토콜은 공격자가 $$MtA$$ 실행 단계에서 유효한 제로 지식 증명을 제공할 것을 요구합니다. GG18 (https://eprint.iacr.org/2019/114.pdf) A.1 절 Range Proof을 참조합니다. 이 제로 지식 증명은 다음을 증명할 수 있습니다:

• Witness: $kA' = 0 \ne kA$, 기타 무작위 수
• Statement: $Enc{NA}(kA)$는 $$kA'$$의 암호화된 암호문이며, $$k_A \in (-q\^3, q\^3) $$를 만족합니다.

주의: 위의 내용은 불법적인 Statement입니다. 왜냐하면:
-$$Enc{NA}(kA)$$는 $$kA'=0$$의 암호화된 암호문이 아니기 때문입니다.
-$$k_A \gg q\^3$$입니다.

정상적인 경우 GG18 프로토콜에서 이곳의 Range Proof는 완전히 유효하며, 공격자가 제로 지식 증명을 구성하여 이 Statement가 검증을 통과하도록 하는 것은 어렵습니다.

그렇다면 공격자 당사자 A는 어떻게 장애를 극복할까요? 이때 공격자 당사자 A가 KeyGen 프로토콜 단계에서 구성한 안전하지 않은 Paillier 키 $$N_A$$를 활용해야 합니다. 안전하지 않은 Paillier 키가 있기 때문에 악의적인 제로 지식 증명을 구성할 기회를 가질 수 있습니다.

GG18/GG20 프로토콜의 제로 지식 증명 프로토콜 설명은 다음과 같습니다:

Verifier의 검증 과정에서 가장 중요한 것은 암호문 제약의 등식(빨간 상자 부분)을 만족하는 것입니다:

$$ u = \Gamma\^s s\^N c\^{-e} \pmod {N\^2} $$
공격 기술은 합리적인 도전 값 $$e = Hash(…, w, )$$를 구성하여 다음을 만족하도록 합니다: $$e \pmod {pi} = 0$$ $$c = (1+NA)\^kA * \rho\^NA \mod (NA\^2)$$, $$kA = NA/pi$$
$$\begin{align*}
c\^e \&= ((1+NA)\^kA * \rho\^NA)\^e \&\mod (NA\^2) \\
\&= (1+NA)\^{ekA} * \rho\^{eNA} \&\mod (NA\^2) \\
\&= (1+NA)\^{bpi * NA/pi} * \rho\^{eNA} \&\mod (NA\^2) \\
\&= \rho\^{eAN} \&\mod (NA\^2) \\
\&= Enc{NA}(0)\^e \&\mod (N_A\^2) \\
\end{align*}$$

여기서 $$c$$를 $$k_A'=0$$의 암호문으로 "변환"하여 성공적으로 제로 지식 증명을 구성했습니다.

주의: 여기서는 구성 과정에서 $$\gamma$$를 폭력적으로 반복하여 1씩 증가시키고 $$w$$를 업데이트하여 $$e \pmod {pi} = 0$$을 만족시킬 수 있습니다. 모듈러 $$pi$$는 작은 소수이므로 폭력적으로 반복하여 성공할 수 있습니다.

당사자 B 개인 키 조각의 모 $$p_i$$ 나머지 계산

공격자는 공격 대상과 Sign 서브 프로토콜을 완료하고 추가로 $$MtA$$ 프로토콜에서 $$\muA$$ 값을 기록합니다. $$ \muA = kA * xB + \nuB \pmod {NA}$$
최신 GG18 논문을 고려할 때, $$\nuB \le q\^5$$이므로, $$ \muA = Dec{NA}(Enc{NA}(kA * xB + vB))$$ $$\begin{align*} \muA - (\muA \mod (NA/pi)) =\& Dec{NA}(Enc{NA}(kA * xB + \nuB)) - (Dec{NA}(Enc{NA}(kA * xB + \nuB)) \mod (NA/pi))\\ =\& (xB \mod pi) * (NA/pi) + \nuB - \nuB \\ =\& (xB \mod pi) * (NA/p_i)
\end{align*}$$

따라서:

$$xB \pmod {pi} = (\muA - (\muA \mod (NA/pi)))/(NA/pi) $$
$$ai = (\muA - (\muA \mod (NA/pi)))/(NA/p_i) $$

등식의 오른쪽은 모두 공격자가 알고 있는 매개변수이므로, 공격자는 $$ai$$를 계산할 수 있습니다. 따라서 $$xB = ai \pmod {pi}$$를 얻을 수 있습니다.

4.3 마무리 단계: 공격 대상의 개인 키 조각 계산

16번의 성공적인 MPC Sign 서브 프로토콜을 실행한 후, 다음을 얻습니다:

$$ xB = a1 \pmod {p1}$$ $$ xB = a2 \pmod {p2}$$
$$ … $$
$$ xB = a{16} \pmod {p_{16}}$$

$$p1 * p2 *… * p{16} > q$$이므로, 중국 나머지 정리에 따라 공격자 당사자 A는 당사자 B의 개인 키 조각 $$xB$$를 계산할 수 있습니다. 공격 성공.

4.4 공격 효과

GG18 논문에는 두 가지 구현 버전이 있으며, 수정된 버전과 구버전이 있습니다. 각 버전에 따라 공격 효과가 다릅니다.

• 수정된 논문에서 $$MtA$$ 프로토콜에서 사용하는 $$\betaB \< q\^5$$ (앞서 언급한 $$\nuB$$에 해당)인 경우, 위의 공격 방법을 사용하여 16번의 서명으로 공격자는 공격 대상의 개인 키 조각을 해독할 수 있습니다.
• 구버전 논문에서 $$MtA$$ 프로토콜에서 사용하는 $$\betaB \< NA$$ (앞서 언급한 $$\nuB$$에 해당)인 경우, 위의 공격 방법의 변형을 사용하여 공격을 수행해야 하며, 여기서는 추가 설명을 생략합니다. 많은 추측 실행이 필요하며, 최소한 10\^6 수준의 서명 시도가 필요합니다. 공격자는 공격 대상의 개인 키 조각을 해독할 수 있을 것입니다. 보다 정확하게 말하면, 확률 $$\tau\^l$$로 상대방의 개인 키 조각을 성공적으로 추출하기 위해 필요한 서명 횟수는: $$\sum{i=1}\^nf\tau(pi)$$입니다.

여기서 $$f_{\tau} (p) = log(1-\tau) / log(1-1/p\^2)$$입니다. Fireblocks의 논문에서 해당 공식에 오류가 있었으며, 이를 수정했습니다.

주의: GG18 수정된 논문에서 저자는 많은 보안 수정 제안을 제공하였으므로, 이 MPC 프로토콜을 구현할 때는 수정된 버전을 기반으로 구현해야 합니다.

실제 공격 시나리오 예시

위의 섹션에서는 이 취약점의 원리와 알고리즘 수준의 공격 방법을 설명했습니다. 그렇다면 실제 MPC 기반 자가 관리 지갑 애플리케이션 시나리오에서 사용되는 MPC 프로토콜에 이 취약점이 존재한다면, 공격을 어떻게 수행할 수 있을까요?

이 취약점은 t/n 임계값에 영향을 미치며, 이해를 돕기 위해 MPC 지갑의 참여자가 2명인 당사자 A와 당사자 B로 가정하고, 서명의 임계값을 2/2로 설정합니다. 여기서 당사자 A의 개인 키 조각은 사용자가 보유하고 있으며, 지갑 제공자가 제공하는 모바일 앱을 통해 관리 및 사용합니다. 당사자 B의 개인 키 조각은 지갑 제공자가 보유하고 있으며, 클라우드에 저장되고 사용됩니다.

공격을 수행하려면 공격자는 다음과 같은 능력을 갖추어야 합니다:

(1) 지갑 제공자가 지갑을 생성하고 거래를 시작하는 구현 논리 및 메커니즘을 이해하고 있어야 합니다.
(2) 지갑 제공자 앱을 모방하여 MPC 프로토콜을 사용하여 지갑을 생성하고 거래 서명을 완료할 수 있어야 합니다.

그렇다면 공격자는 공격을 시작할 수 있습니다:

(1) 앱을 모방하여 지갑을 생성하고, 지갑을 생성할 때(해당 KeyGen 서브 프로토콜에 해당) 로컬 당사자 A MPC 프로토콜에서 안전하지 않은 동형 키를 구성한 후, 해당 동형 키를 사용하여 지갑을 생성하고 로컬 당사자 A의 개인 키 조각 $$xA$$를 획득합니다. (2) 앱을 모방하여 해당 지갑을 사용하여 정상적으로 거래 서명을 16번 수행하고(해당 Sign 서브 프로토콜에 해당), 매번 MPC 프로토콜에서 악의적인 $$kA$$와 악의적인 제로 지식 증명을 구성하여 16번의 서명을 완료하고 각 서명에서 $$\mu$$를 수집합니다.

위의 작업을 완료한 후, 공격자는 생성된 지갑에 해당하는 클라우드의 당사자 B의 개인 키 조각 $$xB$$를 획득할 수 있습니다. 서명 임계값이 2/2이므로 공격자는 로컬에서 개인 키 조각 $$xA$$를 얻었고, 동시에 공격 프로토콜을 통해 클라우드 개인 키 조각 $$xB$$를 얻었으므로, 공격자는 $$xA$$와 $$x_B$$를 통해 지갑에 해당하는 실제 개인 키 $$x$$를 얻을 수 있습니다.

위의 공격 시나리오에서 이 지갑을 공격하려면 지갑 생성 시점부터 공격을 시작해야 하며, 해당 지갑을 사용하여 여러 번 서명하여 공격을 완료해야 최종적으로 해당 지갑의 개인 키를 얻을 수 있습니다.

취약점 수정

전체 공격 과정을 살펴보면, 모든 공격이 공격 준비 단계에서 시작되며, 이 단계에서 공격자 당사자 A는 안전하지 않은 동형 키 $$N_A$$를 구성했습니다. 이 키는 많은 작은 인자를 포함하고 있으며, 이는 후속 공격을 촉진했습니다.

취약점 수정을 위해 GG18/GG20 프로토콜에 추가적인 제로 지식 증명을 추가하여 동형 공개 키 $$N_A$$에서 작은 인자가 발생하지 않도록 하여 공격을 근본적으로 차단합니다. 전체 GG18/GG20 프로토콜에서 이 패치를 적용한 후, 보안 가정에 대한 문제가 없으므로 프로토콜은 여전히 안전합니다.

취약점을 수정하기 위해 두 개의 제로 지식 증명을 추가해야 합니다:

• 첫 번째 제로 지식 증명은 Paillier의 Blum 모듈 증명으로, 동형 공개 키 $$N_A$$가 최대 두 개의 소인자만 가지며, 각 소인자가 특정 특성을 만족하도록 보장합니다.
• 두 번째 제로 지식 증명은 작은 인자가 없음을 보장하여 동형 공개 키 $$N_A$$에 작은 소인자가 없도록 합니다.

이 두 개의 제로 지식 증명 구현은 CMP20 및 CGGMP21(6.3 절 및 C.5 절)을 참조할 수 있으며, 이 증명은 Paillier 공개 키 $$N$$에 $$2\^{256}$$보다 작은 인자가 존재하지 않도록 보장합니다.

Safeheron은 오픈소스 알고리즘에서 이 취약점을 수정했으며, 구체적인 수정 방법은 다음을 참조하십시오:

https://github.com/Safeheron/multi-party-ecdsa-cpp/pull/7/commits/ee78a86b53f341196623bd65a5ae1ee20bcc2853

https://github.com/Safeheron/multi-party-ecdsa-cpp/pull/10/commits/fbc3474f9b05b1a9e6cfd58647e6ebfc4d4fcbca

공격 탐지

MPC 프로토콜의 보안 업그레이드를 완료한 후, 안전을 위해 과거 데이터를 검증하여 해당 취약점에 대한 공격을 받았는지 확인할 수 있습니다. 이 취약점의 이용은 안전하지 않은 Paillier 키를 구성하는 데 의존하므로, 과거에 이러한 공격을 받았다면 공격자의 Paillier 공개 키 $$N$$에 반드시 작은 인자가 존재할 것입니다. 따라서 MPC 참여자의 Paillier 공개 키 $$N$$에 작은 인자가 존재하는지 분석하여 공격 여부를 탐지할 수 있습니다.

구체적인 탐지 방법은 성숙한 큰 정수 분해 알고리즘 도구를 이용하여 Paillier 모듈 $$N$$에 작은 인자가 존재하는지 확인하는 것입니다. 작은 인자가 존재한다면 공격의 가능성이 있으므로, 자산을 신속하게 이동하고 새로운 MPC 지갑을 생성할 것을 권장합니다.

Safeheron은 대수적 정수 분해 도구 (https://github.com/Safeheron/integer-factorization)를 제공하여 빠른 배치 검사를 수행할 수 있으며, 대수적 정수 분해 관련 알고리즘 원리는 대수적 정수 분해 알고리즘과 실천 (https://mp.weixin.qq.com/s/5FcA0qGXDKFeb_nMatFeWQ)을 참조할 수 있습니다.

요약

이 취약점의 원리와 공격 방법을 정리한 후, 이 취약점의 이용 장벽이 상대적으로 높지만, 보안 산업에 종사하는 우리는 항상 안전에 대한 경외심을 가져야 합니다.

Fireblocks 팀의 책임 있는 보안 공개는 "안전은 결코 혼자 싸우는 것이 아니다"라는 것을 보여주며, Safeheron 또한 오픈소스 투명성과 기술 중심을 고수하며 이번 보안 공개에 참여하게 되어 영광입니다. Safeheron은 앞으로 보안 파트너 SlowMist와 협력하여 업계의 다른 업체들이 이 취약점을 수정하도록 지원하여 사용자 자산의 안전을 보장할 것입니다.

업계의 안전을 실현하기 위해서는 모든 업체, 모든 보안 종사자, 모든 사용자의 관심과 노력이 필요합니다. 업계와 함께 노력하길 바랍니다.

참고 문헌
[1] Fireblocks: Practical Key-Extraction Attacks in Leading MPC Wallets (https://github.com/fireblocks-labs/mpc-ecdsa-attacks-23/blob/main/WhitePaper.pdf)
[2] GG18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup (https://eprint.iacr.org/2019/114.pdf)
[3] GG20: One Round Threshold ECDSA with Identifiable Abort (https://eprint.iacr.org/2020/540.pdf)
[4] CGGMP21: UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts (https://eprint.iacr.org/2021/060.pdf)