올해 초, 캐나다 암호화폐 거래소 QuadrigaCX CEO의 갑작스런 사망으로 CEO만이 알고 있던 거래소의 비밀키가 유실되었고, 거래소가 보유하고 있던 1억 5천만 달러 상당의 암호화폐를 영원히 복원할 수 없게 되는 사건이 있었다. 그리고 비슷한 시기에 한국에서도 암호화폐 거래소 코인빈도 비밀키를 유실하여 25억원 상당의 암호화폐를 유실했고, 두 거래소는 결국 파산했다. 만약 거래소의 비밀키가 백업되어있었거나, 복구할 수 있었다면 이런 참사는 막을 수 있었을 것이다.
디지털 정보 시대에서 패스워드나 비밀키와 같은 정보를 보호하는 것은 매우 중요한 일이다. 일반적으로 비밀키 유실을 막기 위해서는 다른 여러 곳에 백업을 해놓는 방법을 사용하였다. 하지만 이런 방법은 비밀키의 유출 가능성을 키우는 리스크를 가지고 있다. 많은 저장소 데이터를 백업할수록 또는 많은 사람들에게 비밀키를 알려줄 수록 비밀키를 유실할 가능성은 줄어들지만, 반대로 비밀키가 유출될 가능성 또한 늘어난다.
Photo by rawpixel.com from Pexels
위에서 언급된 리스크들을 해결하기 위해 아래의 조건을 만족시키는 secret sharing이 연구되고 있다.
1. 하나의 secret을 여러 조각으로 나누어 분산시켜 저장한다. (shares)
2. 원래의 secret을 복원하기 위해서는 반드시 일정한 수 이상의 share가 필요하다. (threshold)
단순히 secret을 일정한 길이로 잘라서 여러 사람에게 분산시키는 것 만으로도 위의 조건을 만족하는 secret sharing을 구현할 수 있다. 아래 그림의 예시처럼 네 사람이 네 개의 조각 중 세 개 씩 소유한다면 두 사람이 모이면 원래의 secret을 복구할 수 있다.
하지만 이런 방법으로는 사람의 수와 threshold값이 커질수록 필요한 조각의 수가 매우 커진다. 100명의 사람이 secret을 나누어 갖고, threshold를 50으로 설정하게 되면 secret은 1.009x10⊃2;⁹개가 필요하고, 각 사람은 5.04x10⊃2;⁸개의 조각을 가지고 있어야 한다.
따라서 더 효율적인 알고리즘을 필요로 했고, 대표적인 알고리즘으로 Shamir’s secret sharing과 Blakey’s secret sharing이 있다. Blakey’s secret sharing은 n차원 도형들의 교점을 이용하는 방법으로 아래 그림에서는 2차원 평면 3개가 모이면 점 하나를 결정한다.
3개의 평면으로 공간 위에 있는 하나의 점을 결정하는 Blakey’s secret sharing
Shamir’s secret sharing은 1979년에 발표된 알고리즘으로, x축 좌표값이 서로 다른 t개의 점을 지나는 x의 t-1차 다항식은 유일하게 결정된다는 사실을 이용한다. 예를 들어 2개의 점은 하나의 직선을 결정하고, 3개의 점은 하나의 포물선을 유일하게 결정할 수 있다. 아래 그림은 하나의 secret을 7개의 share로 나누고, threshold를 3으로 설정한 모습이다.
Shamir’s secret sharing
t개의 점들 중에서 하나만 부족하더라도 무수히 많은 t-1차 다항식이 후보로 존재하여 원래의 다항식을 추측할 수 없다. 따라서 t개보다 적은 비밀 조각이 모이더라도 원래 비밀값은 아예 노출되지 않는다.
Shamir’s secret sharing의 sharing 단계는 아래와 같다.
S는 비밀값이고, 비밀값을 복구하기 위해 모여야 하는 정보의 수 t 와 비밀을 나눠줄 사람 수 n을 정한다. (t<=n)
다항식 q(x)를 임의로 결정한다 (a_0=S)
3. 다항함수 y = q(x) 위에 존재하는 n개의 점 (1, q(1)), (2, q(2)), …, (n, q(n)) 들은 shared secret이 된다.
비밀 복구 과정은 다음의 과정을 통해 이루어진다.
다항함수 y= q(x) 위에 있는 T개의 점(shared secret)을 모은 뒤 위 polynomial interpolation을 통해 q(x)를 알아낸다.
q(0)은 원래 비밀값 S이다.
Polynomial interpolation은 주어진 점들을 모두 지나는 다항식을 찾는 것으로, 식으로 표현하면 아래와 같다.
Shamir’s secret sharing의 특징은 모든 구성원이 나눠갖는 비밀이 서로 유일(unique)하며 평등하다는 것이다. 또한 threshold 이상의 조각만 있으면 secret를 복구할 수 있기 때문에 일부 비밀 조각이 유실되더라도 안전하고, 소수의 배신자가 있더라도 secret을 복구할 수 없다.
이런 특징들은 한계점이 되기도 한다. 모든 shared secret이 동등하기 때문에 비밀을 나눌 때 보안 등급에 따라 나누기가 힘들고, 비밀 조각을 제공할 때 일부러 틀린 비밀 값을 주는 것을 방지할 수 없으며 비밀을 복구할 때도 누군가 오염된 값을 줘서 비밀이 제대로 복구되었는지 알 수 없다.
Shamir’s secret sharing의 단점들은 이후에 나온 여러 연구들에 의해 보강되었다. 1987년 Feldman과 Benaloh는 shared secret 소유지들이 자신의 share를 검증할 수 있는 verifiable secret sharing scheme을 각각 만들었다. 1996년 Stadler와 1999년 Schoenmakers, 2004년에는 Pederson이 자신의 share 뿐 아니라 다른 사람의 share도 검증 가능한 publicly verifiable secret sharing 알고리즘을 각각 만들었다.
디지털 재산을 보호하는데 있어서 secret sharing은 중요한 요소가 될수 있는 만큼, CodeChain에서는 codechain-keystore를 통해 secret sharing 을 제공할 예정이다. 그리고 CodeChain의 모든 비밀키를 분산하여 저장함으로써 해킹의 위협으로부터 보호하고, 유실을 방지하여 보다 신뢰도 높은 서비스를 제공할 것이다.
가입하기
