Shamirの秘密分散の仕組み
(ente.com)- Shamir秘密分散は秘密を複数の断片に分け、しきい値以上が集まったときにのみ復元でき、それより少なければ何の情報も明らかにならない
- 会社のマスターキー、家族アカウントの復旧、チームのバックアップのように、1人に秘密全体を任せにくく、かつ一部の断片が失われても復元が必要な場合に有用
- 中核となるモデルは、秘密を多項式の
0の位置の値として隠し、各断片を曲線上の点1つとして配る方式 - しきい値
kには次数k - 1の多項式を使い、2つの断片は直線、3つの断片は放物線、4つの断片は3次曲線に対応する - Ente Legacy Kitはこの方式を1つのレイヤーとして使い、カードが永続的な復旧キーにならないようにし、発行済みカードを無効化できるようにしている
秘密を点と多項式で分ける方法
- Adi Shamirが1979年に発表した方式で、核心は単に「破りにくい」ことではなく、必要な断片数に満たなければ情報がまったく漏れない点にある
- 異なる2点は正確に1本の直線を定めるが、1点だけではその点を通る直線は無数にあり、それぞれの直線は縦軸と異なる位置で交わる
- 秘密が数値
7なら、直線が縦軸と交わる位置にこの値を隠せる - 傾きは秘密そのものではなく、秘密を隠すためのランダム性として機能する
- 各人に直線上の点を1つずつ配れば、1人が持つ1点だけではあり得る直線が無数にあるため、異なる秘密のどれとも両立してしまう
- 2点を合わせると直線が確定し、その直線が
0で持つ値を読んで秘密を復元できる - この構造は2-of-nの秘密分散方式であり、点はいくつでも作れるが、任意の2点があれば直線を復元できる
- しきい値が大きくなるほど、より高次の曲線を使う
- 放物線は3点あって初めて定まるため、秘密を放物線が縦軸と交わる位置に隠せば、任意の3つの断片で復元でき、2つの断片では復元できない
- 一般にしきい値
kには次数k - 1の多項式を使う 2個の断片は直線、3個の断片は放物線、4個の断片は3次曲線に対応する- 実際の実装では方眼紙ではなく有限体演算を使うが、秘密は
0での値であり、ランダムな係数がそれを隠し、各断片は多項式上の1点だという構造は同じ - 断片が不足している場合、秘密の計算が難しいという程度ではなく、あり得るすべての秘密が依然として可能な状態のまま残る点が重要
Ente Legacy Kitと参考資料
- Enteはこのアイデアを Legacy Kit で使っている
- 必要な目標は、単に秘密を分けることではなく、分割された断片が永続的な復旧キーにならないようにしつつ復旧を可能にすること
- Legacy KitはShamir方式を、より大きなフローの中の1つのレイヤーとして使っている
- カードには復旧キー自体は入っておらず、別の秘密をローカルで再構成したうえで、サーバーが仲介する復旧に参加する
- この構造により、発行済みカードを無効化でき、紛失したカードが永続的な負債として残らない
- 参考資料
1件のコメント
Hacker News のコメント
このテーマで修士論文を書いた。Dropbox、Google Drive、OneDrive のような一般的なストレージプロバイダ複数にデータを分散保存するアプリを作り、暗号化を補助するために 秘密分散 を使った
利点は、プロバイダがもはやデータを読めなくなること、2か所さえ生きていればよいので 追加の冗長性 が得られること、そしてマスターパスワードを忘れると終わりになる他のセキュアストレージアプリと違って、既存のアカウント復旧手順をそのまま使えることだった
複数のキー/値ペアを単一の 暗号文 にまとめる方法があるのか気になる。単純に連結したり結果サイズを爆発させたりせず、この方式に情報を入れる全員が同じ暗号化された塊を保存しつつ、それぞれのキーでは互いに異なる値を復号できるようなものだ
こうすれば人々が互いのバックアップ役になりつつ、何が保存されているかについて もっともらしい否認可能性 を持てる
修士論文で Shamir の秘密分散 をメッシュネットワークに適用した。メッシュのノードの1つが攻撃者に奪取され、そのノードの秘密が回収されたとしても、全体の暗号を破ることはできないようにする仕組みだった
うちのチームは、補助秘密保管庫の合言葉を「民主的に安全な」方法で配布するためにこの手法を使っている。その補助保管庫にはメインの秘密保管庫へアクセスする方法が入っている
https://packages.debian.org/trixie/ssss は悪くなく、かなり直感的な実装だ
Shamir には一度かなり救われたことがある。ほとんど忘れ去られていたバックアップを急いで復元しなければならず、そのとき使われていたランダムなパスワードを再構成できた
「念のため」に家族へ 分散片 を分けておいて本当によかった
「有用なのは、断片が少なすぎると秘密を計算しにくいということではない。断片が少なすぎると、秘密についての情報がまったくないということだ。断片が1つ足りないだけで、あり得るすべての秘密が依然として可能なままだ」という部分は、二次体 やその変種で数を因数分解する過程を連想させる
mod n の合同式の体系を見つけて最終的に素因数を計算するが、十分に集まるまでは不可能だ。それぞれの合同式も何らかの情報は持っているはずで、我々はいったいどの空間で自由度を減らしているのだろうとずっと気になっていた
ここでも各断片は多項式の空間を制限するが、キーが軸と交わる点を教えられるほどには十分に制限しない
本当に素晴らしい手法で、コンピュータ科学者が多項式でできる面白いこととして 中等教育 でも教えられるレベルだ
一次関数の式を復元する授業で Shamir を紹介し、生徒が秘密の PIN を傾きとして決め、2つの点を作って別の2人の生徒に渡す。その2人はペアになって PIN を復元しなければならず、生徒たちはいつもとても熱中する
Bruce Schneier が古典的な書籍 Applied Cryptography でこれを説明しており、HashiCorp Vault にも Go 実装があった。実務的には、分散片は何ビットあるべきなのかいつも気になっていた
ニュースグループで聞いた答えは「実際の鍵長より 1 ビット長く」だった。最近では、量子コンピューティングの脅威が 1) 断片サイズの選択と 2) 秘密分散全般の長所短所にどんな影響を与えるのか気になっている
1バイトの秘密で「10個中しきい値」Shamir 断片を作り、そのうち 9 個の 1 バイト断片を渡しても、宇宙のどんなコンピュータでも秘密を知ることはできない。実際の実装では、完全性確認のためにメッセージ認証コードやチェックサムを付ける必要があるので数バイト大きくなる
Shamir 秘密分散は情報理論的に安全なので、k-out-of-n の秘密で k 個の点が集まらない限り、総当たりしてもすべての秘密が同じようにもっともらしい。したがって体のビット長は好きに決められるが、当然ながら秘密のビット長よりは大きくなければならない。5 個の要素しかない有限体に 100 ビットを隠すことはできない
通常は攻撃者が秘密そのものを総当たりできないようにする必要がある。この方式が情報理論的に安全でも、秘密そのものは普通そうではないからだ。たとえばウォレットのシードがそうで、だから秘密にランダム性を追加し、体のビット長も十分大きく取ってその種の攻撃を防ぐ
攻撃モデル次第では 80 ビットや 128 ビットの体で十分安全で、断片サイズも 80 ビットや 128 ビットより少し大きい程度になる。量子コンピュータについては、この方式は情報理論的に安全なので攻撃は存在しえない
したがって n-of-k 構成を作るには、n-1 次の多項式 p(x) を作り、その多項式上から k 個の任意の点を取る。i 番目の断片は単に (xi, yi) なので、ビット数は多項式を構成する体によって決まる
体は秘密全体を収められるだけ十分に大きくなければならず、(x, y) の2つの値を保存する必要があるので、断片サイズは少なくとも秘密サイズの 2 倍になる。ただし断片が壊れていないことを確認する完全性検査は必要だ
量子コンピューティングはここでは何も変えない、という理解でいる。点が 1 つ足りないだけで最後の点は秘密を何にでも変えられ、それを見分ける方法はない
とてつもなく多くの断片を想定しないなら、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のような構成を作れるとよい復旧時に正確に何が必要か明確になるよう、カードに名前を付ける方法もあるとよい。もちろん、今の設計のシンプルさ自体にも利点はある
https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/
数年前、ブラウザで Shamir 秘密分散を実行する小さなツールを作った。ページをダウンロードすれば完全に オフライン でも使える
https://simon-frey.com/s4/
家族の何人かに配って、自分が死んだら妻に渡すよう伝えてある