2023-06-28
6401
양자컴퓨터 시대에도 비트코인은 안전할까요?
이 질문은, '유의미한 시간 안에 임의의 SHA256 충돌을 일으킬 수 있는가?'와 관련됩니다.(참조: 해시함수란 무엇인가요?)
SHA256은 임의의 입력값을 받아 고정된 256비트의 숫자로 출력해주는 해시함수이며, 보통 출력값은 16진수 64자리로 표현합니다. SHA256은 기본적으로 충돌이 없다고 가정하지만, 디지털 데이터의 종류는 무한한 반면 SHA256 출력은 256비트로 제한되어 있기 때문에, 서로 다른 2^256개의 입력을 초과하는 또 다른 입력이 주어지면 비둘기집의 원리에 의해 반드시 충돌이 발생합니다. 다시 말해서, 빠르게 2^256번의 연산을 할 수 있는 엄청난 성능의 컴퓨터가 존재한다면, 임의의 SHA256 해시값의 충돌을 쉽게 찾을 수 있다는 것입니다. 그렇다면 2^256은 얼마나 큰 수일까요? 편의를 위해 2^256 = 10^77정도로 근사해 계산해보겠습니다.
현재 비트코인 네트워크의 해시레이트는 평균 350 EH/s 입니다. 이는 초당 3.5 * 10^20번, 연간 10^28번의 SHA256 연산을 수행한다는 의미입니다. 이 속도라면, 비트코인 네트워크는 향후 10^49년 안에는 반드시 SHA256 해시충돌을 찾게 됩니다. 그러면 10^49년은 얼마나 긴 시간입니까? 우주의 나이가 '겨우' 1.38 * 10^10년 정도로 추산된다는 점을 생각하면, 현재의 컴퓨팅 기술로는 SHA256 충돌을 찾는 것이 사실상 불가능합니다.
그렇다면 양자컴퓨터의 경우는 어떠합니까?
보통 사람들이 양자컴퓨터에 대해 갖는 이미지는 '엄청나게 빠른 컴퓨터'입니다. 그러나 이는 정확한 이해가 아닙니다. 양자컴퓨터는 다항 시간안에 소인수 분해를 할 수 있는 쇼어 알고리즘과 같이, 특수한 양자 알고리즘을 적용하여 효율적으로 풀 수 있는 일부 문제들에 강한 특수한 컴퓨터입니다. 그런 문제들 중에는, 소인수분해를 사용하는 공개 키 암호체계인 RSA나, 비트코인이 공개키 <-> 개인키를 구현하는데 사용하는 ECDSA(타원곡선암호)의 해독과 같은 것들이 있습니다. 그러나 여전히 양자컴퓨터로 임의의 SHA256 해시충돌을 찾는 효율적인 방법은 알려져 있지 않습니다. 그로버 알고리즘 등이 존재하지만, 이는 단순히 사용된 암호체계의 자릿수를 늘리는 것만으로도 간단하게 대처가 가능합니다.
뿐만 아니라, 비트코인의 주소가 도출되는 과정을 살펴보면 단순히 개인키에 ECDSA를 적용해 도출한 공개키 자체가 비트코인 주소가 되는 것이 아니라, 그 이후에도 SHA256과 RIPEMD160을 통해 두 차례 더 해시를 합니다. 따라서, SHA256과 RIPEMD160의 해시충돌을 임의로 빠르게 찾을 수 있는 방법이 없다면 비트코인의 공개주소를 보고 개인키를 알아내는 것은 불가능합니다. 게다가 설령 그런 방법이 있다고 하더라도, 임의충돌을 일으키기 위해 찾아낸 입력값이 해당 주소의 공개키일 확률은 극히 희박합니다.
결론적으로, 빠르게 양자컴퓨터가 발전하여 가시적으로 위협이 될 수준이 된다면 이는 RSA, ECDSA 등을 광범위하게 사용중인 전세계 군사/경제/금융계에는 큰 피해를 끼칠 것이나 여전히 비트코인은 가장 빠르게 대처하고 나쁜 사태를 예방할 것입니다.
비트코인 커뮤니티에서는 이미 양자내성 서명을 따르는 새로운 서명방식을 적용하는 것에 대한 연구가 진행중입니다. 이 구현 역시 세그윗 및 탭루트와 마찬가지로 비트코인을 잠그고 사용하는 새로운 스크립트를 구현하는 것(새로운 주소체계)이므로 소프트포크로 가능할 것으로 생각됩니다.
다만, 이 경우에도 아주 오래된 초창기 사토시 시대의 코인들처럼 '주소 자체가 공개키'인 P2PK 스크립트를 사용하는 주소들의 경우 주소로부터 개인키를 알아낼 수 있게 되기 때문에, 이 코인들이 시장에 풀려나올 가능성은 생기게 됩니다.
또한, 멤풀에서 대기중인 트랜잭션들에는 공개키가 포함되어 있기 때문에, 이 공개키로 개인키를 빠르게 역산할 수 있는 공격자가 존재한다면 그가 해당 주소의 코인을 이중지불하여 다른 곳으로 빼돌릴 수 있게 됩니다.
만약 SHA256과 RIPEMD160의 임의충돌을 찾을 수 있게 된다면 어떻게 될까요?
1. 이 경우에도 여전히 임의의 비트코인 주소를 보고 개인키를 알아내기는 거의 불가능에 가깝습니다. 이 주소들을 생성하는데 사용된 공개키와 동일한 해시값을 내는 인풋을 찾는다 하더라도, 그것이 해당 주소의 공개키일 확률은 극히 희박하기 때문입니다.
2. 대신 채굴이 매우 쉬워지는데, 그에 맞게 네트워크 난이도가 조절되어 다시 10분당 1개의 블록이 생성되도록 안정화 될 것입니다. 이 시기에는 이 용도의 양자컴퓨터를 사용한 채굴기가 아니라면 경쟁력이 없을 것입니다.
그러나 서두에서 언급했듯이, SHA256의 붕괴는 가능성이 매우 희박하기 때문에, 현실적으로 문제가 될 가능성이 존재하는 ECDSA의 취약점 노출과 달리 실질적으로 걱정할 문제라고 보기는 어렵습니다.
요약하면:
- SHA256은 매우 뛰어난 성능의 양자컴퓨터가 나온다고 해도 안전할 것이다. 난이도는 그에 맞춰 더 상승할 뿐이며, 해시레이트가 올라가 네트워크의 보안성이 증가한다.
- ECDSA는 양자컴퓨터가 충분히 강해진다면 위험해질 수 있다. 그러나 비트코인의 주소는 ECDSA 적용 이후에도 SHA256 / RIPEMD160 을 통한 두 번의 해시함수를 더 적용해 도출되므로, SHA256의 임의충돌을 만들어낼 수 있는 방법이 발견되기 전까지는 안전할 것이다. 설령 그런 방법이 발견되더라도, 임의충돌을 일으킨 인풋이 해당 주소의 공개키일 확률은 극히 희박하다.
- 충분히 빠른 시간 내 개인키를 역산할 수 있는 상황이 된다면, 공개키가 노출된 멤풀 내의 대기중인 트랜잭션들에 대한 이중지불 공격이 가능해진다.
- 양자내성을 갖는 새로운 비트코인 스크립트에 대한 연구들이 진행중이며, 소프트포크 업데이트로 구현이 가능할 것이다.
참고:
1. Will quantum computing break SHA-256 encryption?
2. Quantum Computers Break Encryption in China But Far From Cracking Bitcoin
3. 사토시가 사라지기 전, 그가 남긴 기록들 - 1분 비트코인
4. SHA-256 충돌은 왜 발견되지 않았을까?
5. @atomicBTC - 양자컴퓨터가 나오면 비트코인은 끝일까?
6. 양자 내성에 대한 커밋, 더 나은 방어: 빠른 양자 컴퓨팅 공격에 대한 비트코인의 속도와 위험을 구성할 수 있는 방어
2024-12-11 추가
7. BIP-P2QRH(Pay to Quantum Resistant Hash)
보통 사람들이 양자컴퓨터에 대해 갖는 이미지는 '엄청나게 빠른 컴퓨터'입니다. 그러나 이는 정확한 이해가 아닙니다. 양자컴퓨터는 다항 시간안에 소인수 분해를 할 수 있는 쇼어 알고리즘과 같이, 특수한 양자 알고리즘을 적용하여 효율적으로 풀 수 있는 일부 문제들에 강한 특수한 컴퓨터입니다. 그런 문제들 중에는, 소인수분해를 사용하는 공개 키 암호체계인 RSA나, 비트코인이 공개키 <-> 개인키를 구현하는데 사용하는 ECDSA(타원곡선암호)의 해독과 같은 것들이 있습니다. 그러나 여전히 양자컴퓨터로 임의의 SHA256 해시충돌을 찾는 효율적인 방법은 알려져 있지 않습니다. 그로버 알고리즘 등이 존재하지만, 이는 단순히 사용된 암호체계의 자릿수를 늘리는 것만으로도 간단하게 대처가 가능합니다.
뿐만 아니라, 비트코인의 주소가 도출되는 과정을 살펴보면 단순히 개인키에 ECDSA를 적용해 도출한 공개키 자체가 비트코인 주소가 되는 것이 아니라, 그 이후에도 SHA256과 RIPEMD160을 통해 두 차례 더 해시를 합니다. 따라서, SHA256과 RIPEMD160의 해시충돌을 임의로 빠르게 찾을 수 있는 방법이 없다면 비트코인의 공개주소를 보고 개인키를 알아내는 것은 불가능합니다. 게다가 설령 그런 방법이 있다고 하더라도, 임의충돌을 일으키기 위해 찾아낸 입력값이 해당 주소의 공개키일 확률은 극히 희박합니다.
결론적으로, 빠르게 양자컴퓨터가 발전하여 가시적으로 위협이 될 수준이 된다면 이는 RSA, ECDSA 등을 광범위하게 사용중인 전세계 군사/경제/금융계에는 큰 피해를 끼칠 것이나 여전히 비트코인은 가장 빠르게 대처하고 나쁜 사태를 예방할 것입니다.
비트코인 커뮤니티에서는 이미 양자내성 서명을 따르는 새로운 서명방식을 적용하는 것에 대한 연구가 진행중입니다. 이 구현 역시 세그윗 및 탭루트와 마찬가지로 비트코인을 잠그고 사용하는 새로운 스크립트를 구현하는 것(새로운 주소체계)이므로 소프트포크로 가능할 것으로 생각됩니다.
다만, 이 경우에도 아주 오래된 초창기 사토시 시대의 코인들처럼 '주소 자체가 공개키'인 P2PK 스크립트를 사용하는 주소들의 경우 주소로부터 개인키를 알아낼 수 있게 되기 때문에, 이 코인들이 시장에 풀려나올 가능성은 생기게 됩니다.
또한, 멤풀에서 대기중인 트랜잭션들에는 공개키가 포함되어 있기 때문에, 이 공개키로 개인키를 빠르게 역산할 수 있는 공격자가 존재한다면 그가 해당 주소의 코인을 이중지불하여 다른 곳으로 빼돌릴 수 있게 됩니다.
만약 SHA256과 RIPEMD160의 임의충돌을 찾을 수 있게 된다면 어떻게 될까요?
1. 이 경우에도 여전히 임의의 비트코인 주소를 보고 개인키를 알아내기는 거의 불가능에 가깝습니다. 이 주소들을 생성하는데 사용된 공개키와 동일한 해시값을 내는 인풋을 찾는다 하더라도, 그것이 해당 주소의 공개키일 확률은 극히 희박하기 때문입니다.
2. 대신 채굴이 매우 쉬워지는데, 그에 맞게 네트워크 난이도가 조절되어 다시 10분당 1개의 블록이 생성되도록 안정화 될 것입니다. 이 시기에는 이 용도의 양자컴퓨터를 사용한 채굴기가 아니라면 경쟁력이 없을 것입니다.
그러나 서두에서 언급했듯이, SHA256의 붕괴는 가능성이 매우 희박하기 때문에, 현실적으로 문제가 될 가능성이 존재하는 ECDSA의 취약점 노출과 달리 실질적으로 걱정할 문제라고 보기는 어렵습니다.
요약하면:
- SHA256은 매우 뛰어난 성능의 양자컴퓨터가 나온다고 해도 안전할 것이다. 난이도는 그에 맞춰 더 상승할 뿐이며, 해시레이트가 올라가 네트워크의 보안성이 증가한다.
- ECDSA는 양자컴퓨터가 충분히 강해진다면 위험해질 수 있다. 그러나 비트코인의 주소는 ECDSA 적용 이후에도 SHA256 / RIPEMD160 을 통한 두 번의 해시함수를 더 적용해 도출되므로, SHA256의 임의충돌을 만들어낼 수 있는 방법이 발견되기 전까지는 안전할 것이다. 설령 그런 방법이 발견되더라도, 임의충돌을 일으킨 인풋이 해당 주소의 공개키일 확률은 극히 희박하다.
- 충분히 빠른 시간 내 개인키를 역산할 수 있는 상황이 된다면, 공개키가 노출된 멤풀 내의 대기중인 트랜잭션들에 대한 이중지불 공격이 가능해진다.
- 양자내성을 갖는 새로운 비트코인 스크립트에 대한 연구들이 진행중이며, 소프트포크 업데이트로 구현이 가능할 것이다.
참고:
1. Will quantum computing break SHA-256 encryption?
2. Quantum Computers Break Encryption in China But Far From Cracking Bitcoin
3. 사토시가 사라지기 전, 그가 남긴 기록들 - 1분 비트코인
4. SHA-256 충돌은 왜 발견되지 않았을까?
5. @atomicBTC - 양자컴퓨터가 나오면 비트코인은 끝일까?
6. 양자 내성에 대한 커밋, 더 나은 방어: 빠른 양자 컴퓨팅 공격에 대한 비트코인의 속도와 위험을 구성할 수 있는 방어
2024-12-11 추가
7. BIP-P2QRH(Pay to Quantum Resistant Hash)
7
