비밀 분할 문제

존속해야 하고 비상시에 접근할 수 있지만 한 사람이 절대 손상시킬 수 없는 마스터 키가 있다고 가정해 보십시오. 이 키를 어떻게 저장해야 할까요? 여러 사람에게 전체 키를 제공하면 그중 누구라도 악용할 수 있습니다. 사본 하나만 보관하면 단일 장애 지점이 생깁니다.

128비트 키를 64비트 절반 두 개로 나누어 두 사람에게 각각 제공하는 방법은 영리해 보이지만 안전하지 않습니다. 무차별 대입 비용이 2^128에서 2^64로 줄어들기 때문입니다. 공격자가 한 사람의 키 조각을 손에 넣으면 64비트만큼 유리한 출발점을 확보하게 됩니다.

적절한 비밀 공유 방식은 다음 조건을 충족해야 합니다. (1) 임계값: k-of-n 공유 조각 중 어느 k개라도 비밀을 복원할 수 있어야 합니다. (2) 보안: k-1개의 공유 조각은 비밀에 대한 정보를 전혀 드러내지 않아야 합니다. (3) 완벽성: 계산적 가정이 필요하지 않아야 합니다.

비트코인 지갑, HSM 마스터 키, 인증 기관 개인 키, 핵 발사 코드, 암호화폐 거래소의 콜드 월릿은 모두 임계값 접근이 필요합니다. 단일 키를 잃으면 치명적이고, 한 내부자가 키를 손상시켜도 역시 치명적입니다.

두 당사자 사이에 비밀 S를 공유하려면 무작위 R을 생성합니다. 당사자 1에게 share1=R을 주고, 당사자 2에게 share2=S XOR R을 줍니다. 복원할 때는 share1 XOR share2 = R XOR (S XOR R) = S가 됩니다. 어느 공유 조각 하나만으로도 완전히 무작위이므로 S에 대한 정보가 전혀 드러나지 않습니다.

XOR 공유는 완벽한 2-of-2 방식이지만 k-of-n 임계값 방식으로 일반화할 수 없습니다. 공유 조각 3개 중 어느 3개라도 비밀을 복원하면서 2개로는 아무것도 알아낼 수 없는 3-of-5 방식을 만들 수는 없습니다. 이 문제는 다항식 보간으로 해결됩니다.

완벽한 비밀성이란 k개보다 적은 공유 조각이 비밀에 대해 상호 정보를 전혀 포함하지 않는다는 뜻입니다. 이는 계산적 보안보다 강력합니다. 계산 능력이 무한한 공격자라도 k-1개의 공유 조각으로는 아무것도 알아낼 수 없습니다.

AWS CloudHSM은 M-of-N 쿼럼 인증을 사용합니다. PGP 키 에스크로는 마스터 키를 분할합니다. 암호화폐 수탁 제공업체(Fireblocks, BitGo)는 핫 월릿 키에 MPC 또는 Shamir 공유를 사용합니다. 인증 기관의 오프라인 키에는 5-of-7 절차가 사용됩니다.

키 절차는 마스터 키를 생성하고 분할하는 공식적이고 감사 가능한 과정입니다. 예를 들어 7명의 키 보유자가 보안실에 모이고, 각자 하나의 공유 조각이 담긴 하드웨어 토큰을 받습니다. 전 과정을 영상으로 기록하고, 두 명의 감사자를 배석시키며, 각 단계를 문서화합니다.

비밀 공유는 전체 비밀을 복원합니다(복원 시점에 단일 장애 지점이 생길 위험이 있습니다). 다중 서명은 각 당사자가 독립적으로 서명하고 서명을 결합하여 서명을 분산합니다. 임계값 서명(TSS)은 서명 작업 자체에 비밀 공유를 적용한 것입니다.

보안 다자간 계산(MPC)은 복원 단계를 완전히 없앱니다. 당사자들은 비밀을 공개하지 않고 공유 조각을 사용해 공동으로 계산합니다. 임계값 ECDSA와 임계값 BLS는 운영 중인 수탁 시스템에 배포되어 있습니다.

단순한 키 분할은 안전하지 않습니다. 적절한 비밀 공유에는 완벽한 비밀성을 보장하는 임계값 접근이 필요합니다. XOR는 2-of-2를 처리하고, 다항식 보간은 k-of-n을 처리합니다. 다음 주제: Shamir 비밀 공유 수학입니다.