[Knight Frontier] BoB 프로젝트 탐구 - 양자내성암호를 결합한 블록체인 플랫폼 개발 및 연구

주제 선정 이유

Google의 Sycamore, IBM의 Osprey... 양자 컴퓨터가 이론적 가능성에서 실제 하드웨어로 빠르게 구현되고 있다. 2019년 Google이 "양자 우월성(Quantum Supremacy)"을 달성했다고 발표한 이후, 업계의 발전 속도는 가속화되고 있다. 문제는 충분히 강력한 양자 컴퓨터가 등장하면 현재 사용되는 암호 시스템의 대부분이 무용지물이 된다는 것이다.

 

블록체인의 보안 근간인 ECDSA(Elliptic Curve Digital Signature Algorithm) 같은 공개키 암호는 Shor's algorithm에 의해 다항 시간(polynomial time)에 깨진다. 더 심각한 건 블록체인의 불변성이다. 일반적인 중앙화 시스템은 양자 위협이 현실화되면 암호 시스템을 업그레이드하면 되지만, 블록체인은 과거의 모든 트랜잭션과 블록이 영원히 보존되고, 그들은 과거에 '안전했던' 알고리즘으로 보호되고 있다. 양자 컴퓨터가 등장하면 과거의 모든 서명이 위조 가능해지고, 과거 블록의 무결성이 의심받을 수 있다.

 

"Store now, decrypt later" 공격도 현실적인 위협이다. 공격자가 지금은 해독할 수 없지만 미래의 양자 컴퓨터로 해독할 목적으로 암호화된 통신을 수집하는 것이다. 국가 기밀이나 개인 건강 기록처럼 장기간 민감한 데이터는 특히 위험하다. 블록체인의 거래 내역도 수십 년 후에도 가치가 있을 수 있어 표적이 된다.

 

전공 수업에서 암호학을 배우면서 양자 컴퓨팅 부분이 가장 이해하기 어려웠다. 양자 중첩, 얽힘 같은 개념들이 직관에 반하고, 수학적으로도 복잡했다. 하지만 그만큼 흥미로웠고, 이번 기회에 제대로 이해하고 싶다는 동기가 생겼다. 특히 이론적인 위협이 실제 시스템 설계에 어떤 영향을 미치는지 탐구하고 싶다.

 

주제 관련 기반 지식

1. 양자 컴퓨터의 원리와 암호학적 위협

양자 컴퓨터는 양자역학의 원리, 특히 중첩(superposition)과 얽힘(entanglement)을 이용해 계산을 수행하는 기계다. 고전 컴퓨터의 비트는 0 또는 1 중 하나의 값을 가지지만, 양자 컴퓨터의 큐비트(qubit)는 0과 1의 중첩 상태로 존재할 수 있다. 측정하는 순간 하나의 값으로 붕괴하지만, 측정 전까지는 여러 가능성을 동시에 표현한다.

 

이 특성 덕분에 n개의 큐비트는 2^n개의 상태를 동시에 표현할 수 있다. 50큐비트면 약 1000조(10^15)개의 상태다. 물론 측정하면 하나의 결과만 얻지만, 양자 알고리즘은 이 병렬성을 교묘하게 활용해 특정 문제를 극적으로 빠르게 푼다.

 

가. Shor의 알고리즘 - 공개키 암호의 종말

1994년 Peter Shor가 발표한 이 알고리즘은 양자 컴퓨터로 큰 수의 소인수분해와 이산로그 문제를 다항 시간에 풀 수 있음을 보였다. 이는 RSA와 ECDSA 같은 공개키 암호의 보안 기반을 무너뜨린다.

• 소인수분해: RSA는 큰 수(예: 2048비트)를 두 소수의 곱으로 분해하기 어렵다는 가정에 기반한다. 고전 컴퓨터로는 수십억 년 걸리지만, 충분히 큰 양자 컴퓨터는 몇 시간 안에 풀 수 있다.
• 이산로그: ECDSA는 타원곡선에서 이산로그 문제의 어려움에 의존한다. 양자 컴퓨터는 이것도 다항 시간에 해결한다.
• 필요한 큐비트 수: 2048비트 RSA를 깨려면 약 4000 큐비트의 논리적 큐비트(오류 정정된)가 필요하다. 현재 최고 수준이 1000 물리 큐비트 수준이고 오류율이 높아, 실용적 공격까지는 아직 시간이 있다. 하지만 전문가들은 10-15년 내 가능할 것으로 본다.

나. Grover의 알고리즘 - 대칭키 암호 약화

1996년 Lov Grover가 발표한 알고리즘은 정렬되지 않은 데이터베이스에서 특정 항목을 찾는 문제를 제곱근 시간에 해결한다. 암호학적으로는 brute-force 공격을 제곱근만큼 가속화한다는 의미다.

• 보안 강도 절반: 128비트 대칭키는 2^128번의 시도가 필요하지만, Grover's algorithm으로는 2^64번이면 충분하다. 즉 128비트 보안이 64비트 보안으로 감소한다.
• 해시 함수 영향: SHA-256은 256비트 출력이지만 충돌 저항성은 128비트 보안 수준이다. 양자 컴퓨터로는 64비트로 감소한다.
• 실용적 방어: 키 크기를 두 배로 늘리면 된다. AES-256을 쓰면 양자 컴퓨터로도 128비트 보안을 유지한다. 따라서 대칭키 암호는 상대적으로 덜 위협받는다.

다. CRQC (Cryptographically Relevant Quantum Computer)

모든 양자 컴퓨터가 암호를 깰 수 있는 건 아니다. 현재 수준의 양자 컴퓨터는 큐비트 수도 적고 오류율도 높아 실용적 암호 해독은 불가능하다. CRQC는 실제로 현재 암호 시스템을 위협할 만큼 강력한 양자 컴퓨터를 의미한다.

• 요구 사양: RSA-2048을 깨려면 수천 개의 논리적 큐비트, 수백만 개의 물리적 큐비트(오류 정정 고려), 낮은 오류율(0.001% 이하), 긴 coherence time이 필요하다.
• 도달 시점 예측: 보수적 예측은 20-30년, 낙관적 예측은 10-15년이다. 2022년 미중 양자 기술 경쟁이 격화되면서 일부는 더 빨라질 수 있다고 본다.
• 대비의 시급성: 블록체인 프로젝트는 커뮤니티 합의가 필요하고 마이그레이션에 시간이 걸려, 지금부터 준비해야 CRQC 등장 시점에 대응할 수 있다.

 

2. NIST Post-Quantum Cryptography 표준화

NIST(미국 국립표준기술연구소)는 2016년 PQC 표준화 프로세스를 시작해 전 세계 암호학자들로부터 제안을 받았다. 82개 후보가 제출되었고, 여러 라운드의 분석과 공격 시도를 거쳐 2024년 최종 표준이 발표되었다. 이 표준들은 양자 컴퓨터로도 깨기 어려운 수학적 난제에 기반한다.

 

가. CRYSTALS-Dilithium - 격자 기반 디지털 서명

Dilithium은 Module Learning With Errors(Module-LWE) 문제에 기반한 디지털 서명 알고리즘이다. 격자(lattice)는 다차원 공간의 점들이 규칙적으로 배열된 구조로, 격자 위에서 가장 가까운 벡터를 찾는 문제(SVP)나 짧은 벡터를 찾는 문제(CVP)는 양자 컴퓨터로도 어렵다고 알려졌다.

• 세 가지 보안 레벨:
  • Dilithium2: 128비트 보안 (AES-128 수준)
  • Dilithium3: 192비트 보안 (AES-192 수준)
  • Dilithium5: 256비트 보안 (AES-256 수준)
• 키와 서명 크기: 공개키는 약 1312-2592바이트, 서명은 2420-4595바이트다. ECDSA의 32바이트 공개키, 64바이트 서명과 비교하면 40-70배 크다.
• 성능: 서명 생성은 비교적 빠르지만(수 밀리초), 서명 검증은 매우 빠르다. 블록체인에서는 검증이 더 자주 일어나므로 (모든 노드가 검증) 이는 좋은 특성이다.
• 표준화 상태: 2024년 NIST가 공식 표준으로 채택. FIPS 204로 지정되었다.

나. SPHINCS+ - 해시 기반 서명

SPHINCS+는 해시 함수만을 사용하는 디지털 서명으로, 가장 보수적인 보안 가정을 갖는다. 격자나 코드 기반 암호가 깨지더라도, 해시 함수(SHA-256 등)가 안전하면 SPHINCS+도 안전하다.

• Stateless의 장점: 과거 해시 기반 서명(XMSS, LMS)은 상태를 유지해야 했다. 같은 키로 두 번 서명하면 안 되는데, 이는 관리가 복잡하다. SPHINCS+는 상태가 없어 사용이 편리하다.
• 큰 서명 크기: 서명이 수십 KB에 달한다(SPHINCS+-128f는 약 17KB). 이는 블록체인에 치명적일 수 있다. 매 블록마다 수백 개의 서명이 있다면 블록 크기가 기가바이트 단위로 증가할 수 있다.
• 느린 서명 생성: 수백 밀리초에서 초 단위 시간이 걸린다. 하지만 검증은 빠르다.
• 활용 시나리오: 장기 보관이 필요한 중요 서명(루트 인증서, 정부 문서)에 적합하다. 빈번한 서명이 필요한 곳에는 부적합하다.

다. Falcon - NTRU 격자 기반 서명

Falcon은 NTRU라는 특수한 격자 구조를 사용한다. 가장 큰 장점은 작은 서명 크기다.

• 작은 서명: Falcon-512는 약 666바이트, Falcon-1024는 약 1280바이트다. Dilithium보다 2-3배 작고 SPHINCS+보다 훨씬 작다.
• 복잡한 구현: 부동소수점 연산을 사용해 구현이 까다롭다. 부채널 공격(타이밍 공격, 전력 분석)에 취약할 수 있어 constant-time 구현이 어렵다.
• 성능: 서명 생성과 검증 모두 빠르다. 하지만 구현 복잡도와 부채널 리스크로 Dilithium보다 덜 선호된다.
• 표준화 상태: NIST의 두 번째 우선 선택(Alternative)으로 지정되었다.

라. CRYSTALS-Kyber - 키 교환 메커니즘

블록체인에서는 디지털 서명이 더 중요하지만, 키 교환도 필요하다(특히 P2P 통신 암호화). Kyber는 격자 기반 키 캡슐화 메커니즘(KEM)이다.

• 작동 방식: 한쪽이 공개키를 생성하면, 다른 쪽이 그 공개키로 공유 비밀을 캡슐화한다. 개인키 소유자만 캡슐에서 비밀을 추출할 수 있다.
• 세 가지 레벨: Kyber512(128비트 보안), Kyber768(192비트), Kyber1024(256비트)
• 성능: 매우 빠르다. 키 생성, 캡슐화, 역캡슐화 모두 밀리초 미만이다.
• 표준: FIPS 203으로 채택되었다.

 

3. 하이브리드 암호 시스템

양자 위협의 시기가 불확실한 현재 상황에서, 가장 실용적인 접근은 기존 암호와 PQC를 동시에 사용하는 하이브리드 방식이다. 둘 중 하나만 안전해도 전체 시스템이 안전하다는 원리다.

 

가. 하이브리드 서명 구조

트랜잭션에 ECDSA 서명과 Dilithium 서명을 모두 포함한다. 검증자는 둘 다 유효한지 확인한다. 만약 양자 컴퓨터가 등장해 ECDSA가 깨지더라도 Dilithium이 보호하고, 반대로 격자 암호에 예상치 못한 취약점이 발견되어도 ECDSA가 보호한다.

• 서명 크기 문제: 두 서명을 모두 포함하면 크기가 크게 증가한다(64바이트 + 2420바이트 = 2484바이트). 하지만 안전한 전환 경로를 제공한다는 장점이 크다.
• 점진적 전환: 초기에는 하이브리드로 시작해 커뮤니티가 PQC에 신뢰를 쌓으면, 거버넌스 투표로 ECDSA를 제거할 수 있다.
• 실제 사례: Google은 Chrome에서 TLS에 하이브리드 키 교환(X25519 + Kyber)을 실험 중이다. Signal 메신저도 비슷한 접근을 한다.

나. Address Agility - 다중 알고리즘 지원

블록체인 주소 체계를 확장해 여러 암호 알고리즘을 동시에 지원한다. 주소에 알고리즘 식별자를 포함시켜, 사용자가 원하는 알고리즘을 선택할 수 있게 한다.

• Bitcoin의 예: SegWit은 다양한 스크립트 버전을 지원한다. 미래에 새로운 서명 알고리즘이 나오면 새 버전을 추가하면 된다.
• Ethereum의 Account Abstraction: EIP-4337은 계정 로직을 유연하게 만들어, 서명 검증 방식을 사용자가 정의할 수 있게 한다. PQC 서명도 스마트 컨트랙트로 검증 가능하다.
• 장점: 기존 사용자는 영향받지 않고, 새로운 사용자만 PQC를 사용할 수 있다. 점진적 마이그레이션이 가능하다.

 

4. 블록체인 구성 요소의 양자 안전성

블록체인은 여러 암호 기법을 조합해 작동한다. 각 요소가 양자 위협에 어떻게 영향받는지 이해해야 한다.

가. 해시 함수 - 상대적으로 안전

SHA-256, Keccak-256 같은 해시 함수는 Grover's algorithm의 영향을 받지만, 보안 강도가 절반으로 줄어들 뿐 완전히 깨지지 않는다. 출력 크기를 늘리면 충분히 대응할 수 있다.

• Proof of Work 영향: Bitcoin의 채굴은 SHA-256 해시의 선행 0 찾기다. 양자 컴퓨터로 제곱근만큼 빠르게 찾을 수 있지만, 이는 더 빠른 ASIC이 나온 것과 비슷하다. 난이도 조정으로 해결된다.
• Merkle Tree: 블록의 트랜잭션을 Merkle Tree로 요약한다. 해시 함수가 안전하면 Merkle Tree도 안전하다.
• 대응 방안: SHA-512 같은 더 긴 출력을 사용하거나, SHA-3(Keccak) 계열로 전환한다.

나. 디지털 서명 - 심각한 위협

블록체인에서 트랜잭션 인증, 블록 서명, 투표 등 모든 곳에 디지털 서명이 사용된다. ECDSA가 깨지면 전체 시스템이 무너진다.

• 과거 트랜잭션 위험: 이미 블록체인에 기록된 과거의 모든 트랜잭션도 위험하다. 공격자가 과거 트랜잭션의 서명을 위조해 "실은 내가 그 거래를 했다"고 주장할 수 있다.
• 주소 재사용 문제: Bitcoin은 주소를 한 번만 사용하고 버리는 걸 권장한다. 주소에서 아직 출금하지 않았다면 공개키가 노출되지 않아 안전하다. 하지만 한 번 사용하면 공개키가 블록체인에 기록되어 양자 공격에 노출된다.
• PQC로 교체 필수: 디지털 서명을 PQC로 바꾸는 것이 양자 안전 블록체인의 핵심이다.

다. Proof of Stake 합의 - 서명 의존도 높음

PoS는 검증자들이 블록에 서명하고, 다른 검증자들이 그 서명을 검증한다. ECDSA가 깨지면 공격자가 다른 검증자의 서명을 위조해 이중 서명을 만들 수 있다.

• Slashing 회피: PoS는 악의적 행동(이중 서명 등)을 하면 예치금을 잃는다(slashing). 하지만 서명 위조가 가능하면 다른 검증자의 이중 서명을 만들어 그를 slashing 시킬 수 있다.
• BLS 서명: Ethereum 2.0은 BLS 서명을 사용해 여러 서명을 하나로 aggregation한다. BLS도 pairing 기반이라 양자 공격에 취약하다. PQC에는 효율적인 aggregation 기법이 아직 부족하다.
• 대응: PQC 서명으로 교체하되, aggregation이 안 되면 블록 크기가 크게 증가하는 트레이드오프를 감수해야 한다.

 

프로젝트 진행 과정 예상

이 프로젝트를 진행한다면 먼저 NIST 표준 문서들을 꼼꼼히 읽으며 각 알고리즘의 수학적 기반을 이해하는 것부터 시작할 것이다. 단순히 라이브러리를 갖다 쓰는 게 아니라, 왜 이 알고리즘이 양자 공격에 안전한지, 어떤 가정에 의존하는지를 이해해야 한다. 격자 문제, 해시 함수 보안성, NTRU 구조 등을 공부한다.

 

다음으로 기존 블록체인 구현을 분석한다. Bitcoin Core나 go-ethereum 코드를 읽으며 디지털 서명이 어디에 어떻게 사용되는지 파악한다. ECDSA를 PQC로 교체하려면 정확히 어떤 함수들을 수정해야 하는지 리스트업한다.

 

프로토타입 구현은 Substrate를 사용할 것이다. Substrate는 Rust로 작성된 모듈식 블록체인 프레임워크로, pallet이라는 모듈을 교체해 기능을 변경할 수 있다. pallet-balances, pallet-session 같은 기본 팔렛들을 살펴보고, 서명 검증 로직이 어디 있는지 찾는다.

 

liboqs라는 PQC 라이브러리를 Substrate에 통합한다. liboqs는 C로 작성되어 있고 Rust 바인딩이 있다. Dilithium3을 선택해 키 생성, 서명, 검증 함수를 구현한다. 트랜잭션 구조를 수정해 서명 필드를 64바이트에서 2420바이트로 확장한다.

 

하이브리드 모드도 구현한다. 트랜잭션에 ECDSA 서명과 Dilithium 서명을 모두 포함하도록 구조를 수정하고, 검증 로직에서 둘 다 체크하도록 한다. 이를 통해 안전한 전환 경로를 보여준다.

 

성능 벤치마킹이 중요한 부분이다. 다음 지표들을 측정하고 기존 ECDSA 블록체인과 비교한다:

• 키 생성 시간: 새 계정을 만드는 데 걸리는 시간
• 서명 생성 시간: 트랜잭션에 서명하는 시간
• 서명 검증 시간: 한 서명을 검증하는 시간 (블록체인에서 가장 빈번한 연산)
• 블록 크기: 100개 트랜잭션이 포함된 블록의 크기
• TPS (Transactions Per Second): 1초에 처리 가능한 트랜잭션 수
• 네트워크 대역폭: 블록 전파에 필요한 대역폭

여러 시나리오를 테스트한다. 단순 송금만 있는 블록, 스마트 컨트랙트 호출이 많은 블록, 검증자 수를 10개, 100개, 1000개로 변경하며 확장성을 확인한다.

 

마지막으로 마이그레이션 전략을 연구한다. 기존의 대형 블록체인 네트워크(Bitcoin, Ethereum)가 어떻게 PQC로 전환할 수 있을지 시나리오를 작성한다. 하드 포크가 필요한가? 기존 사용자들은 어떻게 새 주소로 자산을 옮기나? 과거 블록의 보안은 어떻게 보장하나?

 

예상 시행착오

가장 큰 도전은 성능과 블록 크기의 폭증이다. Dilithium3 서명은 ECDSA보다 40배 크다. 블록당 1000개 트랜잭션이 있다면, 서명만으로 2.4MB를 차지한다(ECDSA는 64KB). 10분마다 2.4MB 블록이 생성되면 하루 346MB, 1년 126GB다. Bitcoin은 14년간 500GB인데, PQC로 전환하면 몇 년 만에 그걸 넘을 수 있다.

 

이는 탈중앙화를 위협한다. 풀 노드를 운영하려면 테라바이트급 스토리지와 고속 네트워크가 필요하다면, 일반 사용자는 포기하고 소수의 강력한 노드만 남게 된다. 라이트 노드를 사용하면 블록 헤더만 검증할 수 있지만, 이는 보안이 약하다.

 

서명 검증 시간도 문제다. Dilithium 검증은 ECDSA보다 느리다. 블록당 1000개 서명을 검증하는 시간이 크게 증가하면 블록 생성 시간을 늘려야 하고, 이는 사용자 경험을 해친다. 병렬 검증(여러 코어로 동시에 검증)이나 GPU 가속을 고려해야 한다.

 

PQC 알고리즘의 구현 복잡도도 만만찮다. Constant-time 구현을 보장하기 어렵고, 특히 Falcon 같은 경우 부동소수점 연산 때문에 타이밍 공격에 취약하다. 보안 감사를 철저히 해야 한다.

 

마지막으로 커뮤니티 합의를 이끌어내는 것도 큰 도전이다. Bitcoin 커뮤니티는 매우 보수적이고 큰 변경에 저항한다. "양자 컴퓨터는 아직 멀었다"는 주장과 "지금 준비해야 한다"는 주장이 충돌할 것이다. 기술적 해결책뿐 아니라 거버넌스 전략도 필요하다.

 

주제 조사 후 느낀 점

이 주제를 파고들면서 양자 위협이 생각보다 훨씬 가깝게 느껴졌다. 10-15년이면 내가 현업에서 활발히 일하고 있을 시기다. 이론적 가능성이 아니라 실제로 대응해야 할 현실적 위협이다. 특히 "Store now, decrypt later"는 지금 당장 데이터가 수집되고 있을 수 있다는 점에서 소름 끼쳤다.

 

동시에 기술적 복잡도와 실용성의 긴장을 실감했다. 암호학자들은 수학적으로 완벽한 보안을 추구하지만, 엔지니어는 실제로 돌아가는 시스템을 만들어야 한다. PQC 서명의 큰 크기는 블록체인의 근본 가치인 탈중앙화를 위협할 수 있다. 보안을 위해 탈중앙화를 희생하는 건 본말전도다.

 

Address Agility 개념이 특히 인상 깊었다. 시스템을 설계할 때부터 미래의 변화를 고려하는 것. 단일 알고리즘에 의존하지 않고, 새로운 알고리즘이 등장해도 유연하게 대응할 수 있는 구조. 이는 암호학뿐 아니라 모든 시스템 설계의 원칙이라고 생각한다.

 

양자역학의 기초 원리(중첩, 얽힘)를 이해하려고 노력하면서, 내 직관이 얼마나 고전적인지 깨달았다. "큐비트가 0과 1을 동시에 표현한다"는 게 처음엔 말이 안 되는 것 같았지만, 이는 내가 거시 세계의 경험에만 의존하기 때문이다. 양자 세계는 다른 규칙을 따르고, 그걸 받아들이고 이해하는 것이 양자 암호학의 출발점이다.

 

https://csrc.nist.gov/news/2024/postquantum-cryptography-fips-approved

Post-Quantum Cryptography FIPS Approved | CSRC

 

https://pq-crystals.org/index.shtml

CRYSTALS