▲

Shamir의 비밀 공유 작동 방식

 (ente.com)
3P by GN⁺ | ★ favorite | 댓글 1개
  • Shamir 비밀 공유는 비밀을 여러 조각으로 나누고, 임계값 이상이 모일 때만 복구되며 그보다 적으면 아무 정보도 드러나지 않음
  • 회사 마스터 키, 가족 계정 복구, 팀 백업처럼 한 사람에게 전체 비밀을 맡기기 어렵고 일부 조각 손실에도 복구가 필요할 때 유용함
  • 핵심 모델은 비밀을 다항식의 0 지점 값으로 숨기고, 각 조각을 곡선 위의 점 하나로 나눠 주는 방식임
  • 임계값 k에는 차수 k - 1의 다항식을 쓰며, 두 조각은 직선, 세 조각은 포물선, 네 조각은 3차 곡선에 해당함
  • Ente Legacy Kit는 이 방식을 한 계층으로 사용해 카드가 영구 복구 키가 되지 않게 하고, 발급된 카드를 폐기 가능하게 만듦

비밀을 점과 다항식으로 나누는 방식

  • Adi Shamir가 1979년에 발표한 방식이며, 핵심은 단순히 “깨기 어렵다”가 아니라 필요한 조각 수가 부족하면 정보가 전혀 드러나지 않는다는 데 있음
  • 서로 다른 두 점은 정확히 하나의 직선을 결정하지만, 한 점만 있으면 그 점을 지나는 직선은 무한히 많고 각 직선은 세로축과 다른 위치에서 만남
  • 비밀이 숫자 7이라면, 직선이 세로축과 만나는 위치에 이 값을 숨길 수 있음
  • 기울기는 비밀 자체가 아니라 비밀을 숨기기 위한 무작위성 역할을 함
  • 각 사람에게 직선 위의 점 하나를 나눠주면, 한 사람의 점 하나만으로는 가능한 직선이 무한히 많아 서로 다른 비밀과 모두 호환됨
  • 두 점을 합치면 직선이 고정되고, 그 직선이 0에서 갖는 값을 읽어 비밀을 복구할 수 있음
  • 이 구조는 2-of-n 비밀 공유 방식이며, 점은 원하는 만큼 만들 수 있지만 임의의 두 점이면 직선을 복구할 수 있음
  • 임계값이 커지면 더 높은 차수의 곡선을 사용함
    • 포물선은 세 점이 있어야 결정되므로, 비밀을 포물선이 세로축과 만나는 위치에 숨기면 임의의 세 조각으로 복구 가능하고 두 조각으로는 복구할 수 없음
    • 일반적으로 임계값 k에는 차수 k - 1의 다항식을 사용함
    • 2개 조각은 직선, 3개 조각은 포물선, 4개 조각은 3차 곡선에 해당함
    • 실제 구현은 그래프 종이가 아니라 유한체 산술을 사용하지만, 비밀은 0에서의 값이고 무작위 계수들이 이를 숨기며 각 조각은 다항식 위의 한 점이라는 구조는 같음
    • 조각이 부족하면 비밀 계산이 어려운 정도가 아니라, 모든 가능한 비밀이 여전히 가능한 상태로 남는다는 점이 중요함

Ente Legacy Kit와 참고 자료

함께 보면 좋은 글 β

▲
GN⁺   [-]
Hacker News 의견들

  • 이 주제로 석사 논문을 썼음. Dropbox, Google Drive, OneDrive 같은 일반적인 저장소 제공자 여러 곳에 데이터를 나눠 저장하는 앱을 만들고, 암호화를 보조하기 위해 비밀 분산을 사용함
    장점은 제공자가 더 이상 데이터를 읽을 수 없고, 2곳만 살아 있어도 되므로 추가 중복성이 생기며, 마스터 비밀번호를 잊으면 끝나는 다른 보안 저장소 앱과 달리 기존 계정 복구 절차를 그대로 쓸 수 있다는 점이었음

    • 아이디어가 좋아 보이는데, 이후에 제품이나 오픈소스 앱으로 이어졌는지 궁금함

  • 여러 키/값 쌍을 단일 암호문으로 합치는 방법이 있는지 궁금함. 단순히 이어 붙이거나 결과 크기를 폭발시키지 않으면서, 이 방식에 정보를 넣는 모든 사람이 같은 암호화된 덩어리를 저장하되 각자의 키로는 서로 다른 값을 복호화하게 만드는 식임
    이렇게 되면 사람들이 서로의 백업 역할을 하면서도 무엇이 저장돼 있는지에 대해 그럴듯한 부인 가능성을 가질 수 있음

  • 석사 논문에서 Shamir 비밀 분산을 메시 네트워크에 적용했음. 메시의 노드 하나가 공격자에게 탈취되어 그 노드의 비밀이 회수되더라도 전체 암호화를 깨는 것은 불가능하게 만드는 방식이었음

  • 우리 팀은 보조 비밀 저장소의 암구호를 “민주적으로 안전한” 방식으로 배포하는 데 이 기법을 씀. 그 보조 저장소에는 기본 비밀 저장소에 접근하는 방법이 들어 있음
    https://packages.debian.org/trixie/ssss는 괜찮고 꽤 직관적인 구현임

  • Shamir 덕분에 한 번 크게 살았음. 거의 잊혀진 백업을 급히 복원해야 했는데, 그때 쓰인 임의 비밀번호를 재구성할 수 있었음
    “혹시 모르니” 가족에게 분산 조각을 나눠 둔 게 다행이었음

  • “유용한 점은 조각이 너무 적으면 비밀을 계산하기 어렵다는 데 있지 않다. 조각이 너무 적으면 비밀에 대한 정보가 전혀 없다는 데 있다. 조각 하나가 부족하면 가능한 모든 비밀이 여전히 가능하다”는 부분이 이차 체나 그 변형으로 수를 인수분해하는 과정을 떠올리게 함
    mod n 합동식 체계를 찾아 결국 소인수를 계산하게 되지만, 충분히 모이기 전에는 불가능함. 각 합동식도 어떤 정보는 담고 있을 텐데, 우리는 어떤 공간에서 자유도를 줄이고 있는 걸까 늘 궁금했음
    여기서도 각 조각은 다항식의 공간을 제한하지만, 키가 축과 만나는 지점을 알려줄 만큼 충분히 제한하지는 못함

  • 정말 멋진 기법이고, 컴퓨터 과학자가 다항식으로 할 수 있는 흥미로운 일로 중등학교에서도 가르칠 수 있을 정도임

    • 중등 수학 교사인데 실제로 학생들에게 이렇게 가르침
      일차함수 식을 되찾는 수업에서 Shamir를 소개하고, 학생들이 비밀 PIN을 기울기로 정한 뒤 두 점을 만들어 다른 두 학생에게 나눠 줌. 그 두 학생은 짝을 이뤄 PIN을 다시 찾아야 하고, 학생들이 항상 매우 몰입함

  • Bruce Schneier가 고전적인 책 Applied Cryptography에서 이 내용을 설명했고, HashiCorp Vault에도 Go 구현이 있었음. 실무적으로는 분산 조각이 몇 비트여야 하는지 늘 궁금했음
    뉴스그룹에서 들은 답은 “실제 키 길이보다 1비트 더”였음. 요즘은 양자 컴퓨팅 위협이 1) 조각 크기 선택과 2) 비밀 분산 전반의 장단점에 어떤 영향을 줄지 궁금함

    • 기본적인 Shamir 방식은 정보 이론적으로 안전하고, 양자 컴퓨터에도 완전히 영향을 받지 않음
      1바이트 비밀로 ‘10개 중 임계값’ Shamir 조각을 만들고 그중 9개의 1바이트 조각을 줘도, 우주의 어떤 컴퓨터도 비밀을 알아낼 수 없음. 실제 구현에서는 무결성 확인을 위해 메시지 인증 코드나 체크섬을 붙여야 하므로 몇 바이트 더 커짐
    • 보통 컴퓨터가 실수를 좋아하지 않기 때문에 유한체에서 비밀 분산을 함. 조각 크기는 점 (x, y)이고, x는 작을 수 있으며 보통 참여자가 n명일 때 log n 정도이고, y는 체 안의 임의 점임
      Shamir 비밀 분산은 정보 이론적으로 안전해서 k-out-of-n 비밀에서 k개 점을 모르면 무차별 대입을 해도 모든 비밀이 똑같이 그럴듯함. 그래서 체의 비트 크기는 원하는 대로 정할 수 있지만, 당연히 비밀의 비트 크기보다는 커야 함. 5개 원소뿐인 유한체에 100비트를 숨길 수는 없음
      보통 공격자가 비밀 자체를 무차별 대입하지 못하게 해야 함. 방식은 정보 이론적으로 안전해도 비밀 자체는 보통 그렇지 않기 때문임. 예를 들어 지갑의 시드가 그렇고, 그래서 비밀에 임의성을 더하고 체의 비트 크기를 충분히 크게 잡아 이런 공격을 막음
      공격 모델에 따라 80비트나 128비트 체면 충분히 안전하며, 조각 크기도 80비트나 128비트보다 약간 큰 정도가 됨. 양자 컴퓨터에 대해서는 이 방식이 정보 이론적으로 안전하므로 공격이 존재할 수 없음
    • HashiCorp는 Vault의 seal/unseal 과정용 구현을 아직 갖고 있는 것으로 알고 있음. 물론 뭔가 바뀌지 않았다면
    • Shamir 방식은 대수학의 기본정리에 기반함. n차 다항식을 유일하게 정의하려면 n+1개의 점이 필요하다는 내용임
      그래서 n-of-k 구성을 만들려면 n-1차 다항식 p(x)를 만들고, 그 다항식에서 k개의 임의 점을 뽑음. i번째 조각은 단순히 (xi, yi)이므로 비트 수는 다항식을 구성하는 체가 결정함
      체는 전체 비밀을 담을 만큼 넓어야 하고 (x, y) 두 값을 저장해야 하므로, 조각 크기는 최소한 비밀 크기의 두 배임. 다만 조각이 손상되지 않았는지 확인할 무결성 검사는 필요함
      양자 컴퓨팅은 여기서 아무것도 바꾸지 않는다고 이해하고 있음. 점 하나만 빠져도 마지막 점이 비밀을 무엇으로든 바꿀 수 있고, 이를 구별할 방법이 없음
    • 전체 비밀이 반드시 바탕 체의 원소 하나일 필요는 없음. 더 작은 체 원소들의 n-튜플이어도 됨
      터무니없이 많은 조각을 예상하지 않는다면 GF(2^8) 이 꽤 자연스러운 선택이고, 큰 정수 연산을 다룰 필요도 없음

  • Ente의 구현은 여기 있음: (https://2of3.ente.com/)

    • 지금까지 본 것 중 가장 마음에 들고, 매우 사용자 친화적임. 다만 조금 더 설정 가능했으면 좋겠음
      이상적으로는 3 of 4: A B C D 또는 2 of 3: E F G 그리고 1 of 1: H 같은 구성을 만들 수 있으면 좋겠음
      복구할 때 정확히 무엇이 필요한지 명확하도록 카드에 이름을 붙이는 방법도 있으면 좋겠음. 물론 현재 설계의 단순함도 나름 장점이 있음
    • 대부분의 Linux 배포판에 패키징된 구현도 있음: http://point-at-infinity.org/ssss
    • 브라우저 기반 버전이 여러 개 있고, 온라인으로 쓰거나 내려받아 오프라인에서 사용할 수 있음
      https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

  • 몇 년 전에 브라우저에서 Shamir 비밀 분산을 실행하는 작은 도구를 만들었음. 페이지를 내려받으면 완전히 오프라인으로도 쓸 수 있음
    https://simon-frey.com/s4/

    • 몇 년 전에 그 페이지를 내려받아 USB 디스크 몇 개에 저장했고, KeePass 데이터베이스와 비밀번호 조각도 함께 넣어 뒀음
      가족 몇 명에게 나눠 주고, 내가 죽으면 아내에게 전달하라고 알려 둠
답변달기