HMAC にオートコンプリートを食われた:暗号化したメールアドレスで入力補完検索を実現する
私たちはユーザーの PII をテナントごとの鍵で保存時に暗号化しており、データベースのダンプが漏洩しても役に立つ情報は何も出てきません。メールアドレスの列は暗号文です。電話番号、氏名、カスタム属性も暗号文です。私たちはこれを誇りにしています。セールスポイントでもあります。
そしてそれを本番に出した日、管理画面の検索ボックスがひっそりとオートコンプリートしなくなりました。
エラーはありません。ログも出ません。ユーザー検索に ali と入力すると、以前なら 3 文字打った時点で [email protected] が表示されていたテナント管理者に、何も表示されなくなりました。メールアドレスを最後まで正確に打てば別ですが。検索は壊れたわけではありません。「前方一致」から「完全一致」へと黙って劣化しており、システムの誰もそれを報告に値するとは考えなかったのです。
これは、平文では保存しないと決めたデータに対して入力補完を取り戻すまでの話と、その途中で踏んだ 3 つの落とし穴の話です。暗号そのものは簡単な部分でした。
暗号化がオートコンプリートを食べる理由
平文であれば、前方一致検索はまさにデータベースの本分です。メールアドレス順のインデックスを持っておけば、starts with "ali" は範囲スキャンです。>= "ali" かつ < "alj" となるすべてです。安く、自明で、それで終わりです。
列を暗号化すると、順序付きのインデックスはなくなります。代わりとして定番なのがブラインドインデックスです。暗号文と並べて値の鍵付き HMAC を保存し、検索語の HMAC を計算し直してユーザーを引きます。HMAC(key, "[email protected]") は決定的なので、完全一致の検索は完璧に動きます。しかもインデックスからは読める情報が何も漏れません。テナントごとの鍵がなければ、比較対象となるダイジェストを計算できないからです。
しかし HMAC が何のためにあるのかに注目してください。その設計目標はただ 1 つ、似た入力から無関係な出力を生み出すことです。1 ビット反転させれば、まったく別のダイジェストになります。HMAC("ali") と HMAC("alistair") には何の関係もありません。ブラインドインデックスを漏洩しても安全にしている性質こそが、「前方一致」に答えられなくしている性質そのものです。順序はそれ自体が漏洩です。ブラインドインデックスはうっかり前方一致検索を壊すのではありません。原理的に壊すのです。
だから検索ボックスは黙って完全一致に劣化しました。インデックスがまだ答えられる問いは完全一致だけだったからです。
設計:すべてのプレフィックスをそれぞれ独立した値としてインデックスする
インデックスが「等しい」にしか答えられないなら、「前方一致」を「等しい」に変えてしまえばいい。
正規化したメールアドレスのローカル部(@ より前の部分)のすべてのプレフィックスに、それぞれ専用のブラインドインデックス行を持たせます。[email protected] なら、al、ali、alis、alist と続く行です。PartitionKey が HMAC(prefix)、RowKey がユーザー ID です。これで「ali で始まる」は HMAC("ali") に対する完全一致の検索になります。ポイントクエリ 1 回で、順序は不要です。氏名検索は同じ理由で既にこの方式で動いていたので、メールアドレスがそこに加わっただけです。
2 つの定数で破綻しないようにしています。プレフィックスは 2 文字から始め(1 文字での検索が役に立ったことはなく、行数が倍になります)、16 文字で打ち切ります(メールアドレス 1 件あたりのファンアウトに上限を設けるためです。それより長いクエリは先頭 16 文字で一致させ、数件の候補を復号後に絞り込みます)。つまりメールアドレス 1 件あたりのコストは最大でインデックス 15 行で、作成時に書き込み、メールアドレス変更時に移し、削除時に取り除きます。
トレードオフを一文で言えばこうです。漏らすことを拒んだ順序性を買い戻し、その代金を書き込みのファンアウトで払う。 ストレージと書き込みは安く、漏洩した構造は安くありません。いい取引です。
変更時の移動処理には、コード内に専用のコメントを書くに値する微妙な点が 1 つありました。プレフィックス行はローカル部をキーにしているので、ドメインとは無関係に、ローカル部が変わったときに書き換えを行わなければなりません。[email protected] から [email protected] への同一ドメイン内のリネームは、ドメインインデックスを念頭に書かれたガードからは「ドメインは変わっていないのでインデックス処理はスキップ」に見えます。そうなると古いプレフィックス行が、リネームされたユーザーを永遠に指し続けることになります。
そして、作ったものについて正直に言っておきます。このインデックスは意図的にプレフィックスの一致を漏らします。テーブルを手に入れた攻撃者は、2 人のユーザーのメールアドレスが先頭 3 文字を共有していることはわかります。それが何かはわかりませんが。検索可能暗号が漏洩をゼロにすることはありません。クエリの形ごとに、どの漏洩を許すかを意識的に選べるようにするだけです。等価性とプレフィックスの等価性が、私たちの選んだ漏洩です。漏洩を選び、その周りのすべてを設計する。この考え方こそが規律のすべてです。
設計はうまくいきました。そこからシステムの問題が始まりました。
落とし穴その 1:作成できない鍵
ブラインドインデックスにはテナントごとの HMAC 鍵が必要で、暗号化鍵と同じく Vault の Transit エンジンでプロビジョニングします。鍵を作成しようとすると 500 が返ってきました。invalid key size for HMAC key。
Vault は hmac タイプの鍵には明示的な key_size(32 から 512 バイト)を要求し、固定長のタイプ(aes256-gcm96、ecdsa-p256)では逆にそれを禁止しています。私たちの鍵作成呼び出しは {"type":"hmac"} しか送っていませんでした。フィールドが 1 つ足りなかっただけです。
これがバグ報告ではなく落とし穴だった理由はこうです。トークン化の操作がすべて例外を投げました。そしてログインの経路もトークン化を行います。サインイン時にメールアドレスでユーザーを探す処理は、管理画面の検索と同じブラインドインデックスを通るからです。暗号化を有効にして壊れたのは検索ではありませんでした。ログインが壊れたのです。「ユーザーがより安全になります」を売り文句にした機能が、開発環境で最初に有効にした瞬間にサインインを止めました。修正は、hmac 鍵には key_size=32(HMAC-SHA256)を指定し、固定長のタイプでは省略することです。そして恒久的なルールとして、どこであれ暗号化を有効にする前に、本物の Vault に対してトークン化の経路をスモークテストすること。モックは鍵作成のペイロードを検証してくれません。
落とし穴その 2:ユーザーを置き去りにしかねない更新
メールアドレスを変更すると、インデックスのメンテナンスが必要になります。古い行を消し、新しい行を書く。最初の実装はこの順序、つまり削除してから書き込みでした。自然で、すっきりしていて、間違っています。
新しい行の書き込みには、今や毎回 Vault が関わります(HMAC の PartitionKey を計算するためです)。古い行を先に削除すると、書き込み中に Vault が一瞬でも不調になれば、ユーザーには古い検索用の行も新しい行もどちらも残りません。ユーザーは暗号化された状態でテーブルに存在しているのに、何からも見つけられません。ログインからもです。これは検索の劣化ではありません。将来どこかで再インデックスが走るまで、ユーザーが締め出されるということです。
修正はエラーハンドリングではなく順序です。インデックスをメンテナンスするすべての箇所で、削除の前に書き込む。2 つのステップの間でクラッシュしても、残るのは余分な古い行(無害で、遅延的に掃除されます)であって、欠けた行ではありません。障害モードが「ユーザーに到達できない」から「冗長な行が 1 つ」に変わり、そのコストはゼロです。書き込み経路にリモートの依存先が含まれるなら、途中で止まった状態に耐えられるほうのステップ順を選んでください。
落とし穴その 3:インポートを飲み込んだパーティション
ドメインのブラインドインデックス(HMAC(domain) からメンバーへ)も持っていて、「acme.com の全員」が 1 回の検索で済むようにしています。決定的なハッシュには、インポートするまで誰も勘定に入れていない帰結があります。あるドメインのユーザー全員が1 つのパーティションに入るのです。Azure Table のパーティションが捌けるのは毎秒およそ 2,000 オペレーションです。Auth0 からの単一ドメイン 5 万ユーザーのインポートで、ドメインインデックスへの書き込みがすべてまさにそのボトルネックに流れ込みました。
修正はバケット化です。メンバーをユーザー ID のハッシュで 16 のパーティションに分散させ、ドメインでの読み取りはバケット全体にファンアウトします。上限があり、頻度も低いので問題になりません。教訓を担ったのは 2 つの細部でした。バケットのハッシュは手書きの FNV-1a です。.NET の string.GetHashCode はプロセス間で意図的に不安定にされているので、それでバケットを決めると、翌日のプロセスは同じユーザーに対して別のバケットを計算し、削除すべき行を見つけられなくなります。そして読み取り経路は従来のバケットなしのパーティションも引き続き走査するので、既存の行は強制的なバックフィルなしで見つけられるままでした。新しい書き込みはすぐに分散し、古い行はそのユーザーが次に更新されたときに移行します。
教訓
この話に新しい暗号技術は何もありません。HMAC は何十年も前からありますし、「値をハッシュし、ハッシュをインデックスする」は一文で収まります。実際にコストがかかったのはすべてシステムの仕事でした。プロダクトが本当に必要とするクエリの形はどれか(等価、プレフィックス、ドメイン。ブラインドインデックスはちょうど 1 つの問いにしか答えないので、それぞれに専用のインデックスを用意しました)。鍵がどうプロビジョニングされ、それが失敗したときにログインの経路で何が起きるか。リモートの KMS が間に挟まるとき、インデックスの書き込みをどの順序で行うか。そして平文では起きなかった負荷の集中を、決定的なハッシュがどこで引き起こすか。
検索可能暗号は暗号の機能として売られています。作ってみれば、それが暗号の衣装をまとった分散システムの機能だとわかるでしょう。検索ボックスは再びオートコンプリートするようになり、ali と 3 文字打てば Alistair が見つかります。そして同じテーブルを盗んだダンプには、16 のバケットに散らばった HMAC ダイジェストが並んでいるだけです。つまり、何もありません。その両方を同時に実現することが、最初から目的でした。
すべてのユーザーの PII を保存時に暗号化しながら管理画面の検索ボックスを瞬時に保つ。Authagonal で認証を運用すれば、まさにこういうものを自分で作らずに済みます。3 つの落とし穴の代償は、私たちがもう払っておきました。