おしぼりの日常

低レイヤが好きです.

論文紹介：Building Enclave-Native Storage Engines for Practical Encrypted Databases （1）

はじめに

興味のある分野の論文をたまに紹介するやつを定期的にできたらなあと思ってます．全く続かない気もしますが、とりあえずは第一段です．僕自身読み飛ばしたり理解できていない部分があるため、間違いがある場合は指摘してください．書いている途中であまりにも長くなりそうだったため、記事を分割することにしました．本稿では前提知識、この研究のモチベーション、この研究の着眼点あたりを説明します．以降の記事では提案手法を説明します（もし続けば ... ）．

論文の リンク

Trusted Execution Environment (TEE) とは何か 

TEE はハードウェアレベルで安全な隔離実行環境です．ハードウェアレベル、というのは root of trust がハードウェアであることを意味しており、 TEE は CPU が root of trust になります．昨今では様々なデータを扱うプログラム（プロセス）が存在しますが、それらを強力な権限を持つ攻撃者から守る手段が乏しく、より改竄されにくいハードウェアがプロセスに強力な保護を提供しようというものです．技術的には、MMU / TLB などのアドレス変換周りの技術を用いた特別なアドレス空間の作成 とメモリ暗号化技術により、通常のプロセスや特権的なソフトウェア（e.g. OS、ハイパーバイザー) からの攻撃にも耐性を持つ環境でプロセスを実行できます．Intel Software Guard Extension (SGX) は Intel 製の CPU における TEE であり、ring 3 のプロセスを安全に実行できるものです．SGX の概要は aos さんの記事 が詳しいです．TEE はチップベンダごとに Arm TrustZone や RISC-V KeyStone 、AMD SEV-SNP 等が存在しますが、今回は割愛します．TEEはいわゆる秘密計算技術のうちの一つですが、完全準同型暗号や秘密分散を用いた手法よりもオーバーヘッドが小さく、より実用的であるという特徴があります．近年では、機密データを扱うソフトウェアとして誰もが納得するであろう Database Management System (DBMS) を TEE を用いて保護する研究が増えています．従来のリレーショナルな RDBMS をはじめ、KVS を TEE で保護する研究もあります．今回紹介する論文は古典的な RDBMS におけるストレージエンジン（明確な定義はともかく、メモリ及びストレージ上のデータ操作を行う DBMS の心臓のようなもの) を TEE を用いて保護する研究になります．

この研究のモチベーションは？

以下、論文からの引用です．

Though some enclave-based encrypted databases emerge recently, there remains a large unexplored area in between about how confdentiality can be achieved in diferent ways and what infuences are implied by them.

enclave というのは TEE における安全なメモリ領域のことです．ここに書かれている通り、Enclage のモチベーションは Intel SGX を用いた encrypted database における設計上の選択肢を明らかにし、それらのトレードオフを分析する ことにあります．実際に論文内では様々な観点から複数の選択肢を示しており、それらのトレードオフを定性的（一部は定量的）に分析しています．そして、それらのトレードオフを考慮したときに最も実用的と考えられる "バランスの良い" ストレージエンジンを提案してみたよ、というのが基本的な内容になります．

DBMS with SGX は何が辛いのか？

モチベーションが理解できたところで、SGX と DBMS を組み合わせる上で主要な課題について説明します．後述のトレードオフを理解するためにはこの課題を理解しておく必要があります（どれも直感的なので安心してください）．論文では以下の 3 点を SGX の課題としています．

  1. enclave サイズの制限
  2. enclave 内外の関数呼び出しコスト
  3. Trusted Computing Base (TCB) の最小化

1. enclave のサイズ制限

1 について、まずプロセスを安全に実行可能なメモリ領域である enclave のサイズは制限されています．古めの SGX なら 128 ~ 256 MiB 、Xeon の第三世代以降のスケーラブルプロセッサなら 512 GiB （1ソケットあたり) に制限されています．512 GiB 使える環境は非常に限定的であり、Azure の Confidential VM でもだいたいメモリ全体の 50% ~ 75% くらいが enclave に割り当てられています．具体的に必要な enclave サイズは扱うデータサイズに依存するので一旦議論しないとして、とにかくメモリ全体を使えるわけではない、という点が重要です．DBMS はストレージ上のファイルをメモリに展開しながら動作するため、このメモリサイズの制限は特に致命的です．最近のインメモリ技術なんかも考慮するとまあ辛そうなのは明らかです．

2. enclave 内外の関数呼び出しコスト

SGX が提供する保護モデル

また、Intel SGX は 1 つのプロセス内で一部のコードのみを enclave 内で動かす、という上記のような保護モデルを提供しています（画像は ここ から引用）．図の左側が通常のメモリ領域であり、右側が enclave です．通常のメモリ領域に配置されたコードは Intel SGX SDK が提供する Ocall / Ecall というラッパー関数を用いて Enclave 内外の関数呼び出しを行います．図における Call Trusted Func が enclave 内の関数を呼び出す Ecall であり、図には書かれていませんがその逆が Ocall です．Ecall はともかく、なぜ Ocall などという以下にも攻撃対象になりそうな機構があるのでしょうか？答えとしては、enclave 内でできないことがあまりにも多すぎるからです．上記で触れた aos さんの記事などにも書かれていますが、enclave 内ではシステムコールを利用できません．そのため、システムコールを必要とする処理（I/O など）は全て一旦 enclave 外に出て行う必要があります．例えば、printf を用いて Hello World したい場合、

  1. ocall_printf のような Ocall を定義する
  2. ocall_printf 内部で printf を行うコードを書く
  3. enclave 内から ocall_printf を呼び出す

みたいな流れが必要になります．気になる方は aos さんの実践編の記事を読んでみてください．詳細はともかく、この Ocall / Ecall の呼び出しのオーバーヘッドが非常に大きい、というのが 2 つ目の課題です．全てのデータを enclave 内に展開してしまえばこの問題も少しは緩和されるのですが、実際にはそれは無理で、一部のデータのみを enclave 内に置きます．enclave 外へのデータアクセスは Ocall / Ecall を必要とするので、じゃあ何をどこに置くべきなの？という問題が出てきます．また、既存の DBMS もストレージアクセスを最小化する方針で基本的には動いていますが、SGX を使う場合は普通のディスクアクセス + Ocall / Ecall のオーバーヘッドがあるため、I/O のコストは相対的に通常の DBMS よりも大きくなります．

3. TCB の最小化

最後に、TCB （参考：Wikipedia) の最小化です．TCB は適当に言えば「そのシステムにおいて安全であると信頼されるべき部分であり、ここが侵害されると全てが崩れるような大事な部分」です．Intel SGX などの TEE を用いる場合は enclave 内で実行するコードを指して TCB と言います．直感的に分かる通り、ここが大きければ大きいほど脆弱性を生みやすいです．逆にここが小さければ小さいほど、システム全体の安全性を担保しやすいです．大規模なシステムよりも小規模なシステムの方がセキュリティを担保しやすい、という当たり前の話です．

SGX の実用が難しいのは、上記の 3 つの課題が密接に関連しているからです．例えば、TCB を小さく enclave のメモリ使用量を抑えようとすると、必然的に enclave 外のコードが増えます．そうすると、（処理の内容にもよりますが）Ocall / Ecall の回数は増えます．イメージとしては、モノリシックとマイクロサービスのトレードオフに似ていて、マイクロサービスにすると通信コストが増えるのと同様に Ocall / Ecall が増える感じです．この論文のモチベーションはこのようなトレードオフ自体は明らかであるものの、じゃあ実際にどうするのが正解なの？という問いに答えることにあります．

ストレージエンジンの構造

以降の説明に備え、Enclage が想定する基本的なストレージエンジンの構造を説明します．Enclage は B+ tree ベースのインデックスとヒープファイルベースのデータストア（データのキャッシュ）を持つストレージエンジンを想定しています．後者はいわゆる Buffer Pool というやつです．ストレージエンジンはデータへのアクセスが発生すると、インデックスが貼られている場合はまずインデックスを探し、無ければ Buffer Pool にアクセスします．それでもなければストレージから Buffer Pool にデータを読み込みます．イメージは以下の画像のようになります．Buffer Pool について詳しく書かれた資料はあまり無い気がしますが、The internals of PostgreSQL は詳しめに書かれています．

ストレージエンジンの構造

設計上の選択肢とトレードオフ

論文の流れのままに説明したいと思います．まず、 B+ を素朴に enclave 外に配置した場合の利点と欠点について説明します．少しいきなりに感じるかもしれませんが、この例は後述のいくつかのトレードオフを論じる前のクッションとして非常に有用です．

最も簡単な暗号化 B+ tree の実装と問題点

以下の画像は論文から引用したもので、enclave 外 に配置可能かつ最も簡単な暗号化 B+ tree の実装です．この実装は探索処理においてキーの比較処理以外を全て enclave 外で実行できるため実装が非常に容易な一方で、以下のような問題があります．

  1. Ecall の頻発による性能低下
  2. 暗号化処理との相性の悪さ
  3. キーの順序関係・親子関係の漏洩

1 はキーの比較のたびに Ecall が呼ばれるからです．2 は暗号化において細かいデータを暗号化すると初期化コストが増えがち + メタデータのサイズが増加（所謂 ciphertext amplificaion）してしまうからです．この問題は（実は？）SGX 特有ではなく、何かのデータを暗号化する場合のかなり一般的な問題です．3 はキーの比較処理の過程で漏洩するからです．3 において順序関係が漏洩した場合、セキュリティ的な強度は順序保存暗号程度にまで落ちます．論文ではこのように素朴な実装はシンプルであるため実装が容易な一方で、性能上・セキュリティ上の問題点を生じさせると述べています．論文の構成的には、「なので、しっかりとトレードオフを考えることが大事だよ」という話です．

最も簡単な暗号化 B+ tree の実装

設計ポイント

上記の B+ tree の例から、なんとなく SGX 特有の課題に対処するための工夫が必要そうなことが分かりました．以降では論文の流れに沿って、いくつかの実装上の重要なポイントと選択肢を見ていきます．論文で述べられている実装上のポイントは以下の 5 つです．

  1. 暗号化の粒度
  2. enclave で実行するロジックの選定
  3. メモリアクセスの粒度
  4. enclave メモリの利用方法
  5. レコード ID の保護方法

暗号化の粒度

論文では Encryption Granularity と書かれている部分です．暗号化の粒度は上述した B+ tree の例のような item （e.g. インデックスのキー、カラム）レベルのものと、page レベルのものがあります．この page は Buffer Pool に格納されるヒープページのことを指しています．item レベルの暗号化は B+ tree の例のように既存の操作（B+ tree なら node の split など) への影響がないために実装が容易である点で優れています．一方で、保護対象のデータ構造の "構造" （頭痛が痛いみたいですが）は維持されてしまうため、その構造から分かる順序関係などの情報などは漏洩してしまいます．また、暗号化処理回数の増加による性能低下や ciphertext amplification , Ecall の頻発（ほとんど上述した B+ tree の例と同様）も発生します．

enclave で実行するロジックの選定

最小限のロジックだけを enclave で実行する（つまり TCB 最小化を主眼とする）場合、インデックスを走査するときのキーの比較処理のみを enclave 内で実行し、B+ tree と Buffer Pool の全てのデータ構造を enclave 内に配置できます．ただし、この設計では Ecall が頻発しますし、キーの順序関係の漏洩が生じます．逆に全てのデータ構造を enclave 内に配置した場合、Ecall はほとんど発生せず、かつ漏洩する情報も最小限になります．

メモリアクセスの粒度

これは少し表現がわかりづらいのですが、アクセスパターンの漏洩が焦点です．例えば、暗号化の粒度で item レベルの暗号化を選択した場合、レコードへのアクセスパターンが漏洩します．僕はあまり詳しくありませんが、このようなアクセスパターンの漏洩も攻撃に利用されうるため、対策が必要らしいです．逆に page レベルの暗号化を選択した場合、特定の 1 item にアクセスするだけでも page 全体を enclave にロードする必要がありますが、page 内のどのレコードにアクセスしたかのパターン情報は漏洩しません．

enclave メモリの利用方法

どのデータを enclave に常駐させるか？という話です．論文内では頻繁にアクセスされるデータを配置するといいのでは？みたいなことを言っています．無限の enclave があれば全て解決しますが、実際はそうはいかないという．

レコード ID の保護

ちょっとここは自分も理解できていないのですが、レコードの識別子である rid をどう保護すべきか？という話をしています．理解できたら追記します．

おわりに

だいぶ勢いで書きました．続きも書けたらいいなと思います．