データベースライブラリTkrzwに暗号化データベースの機能をつけた。AESとRC4をサポートしている。圧縮データベースの機能を流用し、データを暗号化しつつも、全体を復号することなく、特定のレコードの検索や更新ができるようになる。もちろん一定の性能低下はあるが、以下に示すように許容範囲だろう。
機密情報を扱うアプリケーションでは、ファイルシステムに保存するデータは暗号化したい。それは商社の顧客情報かもしれないし、警察の捜査履歴かもしれないし、地図アプリの行動履歴かもしれない。ノートPCやタブレットなど、外に持ち出して使う場合、筐体を落としたり盗まれたり押収されたりすれば、そのストレージは第三者に覗かれる可能性がある。たとえデータセンターに置いたマシンでも、レイオフされてやけっぱちになった現地管理者がストレージデバイスを抜き取って持ち去るリスクがある。そのような事態に備えるには、ファイルシステムごと暗号化しておくのが無難だ。しかし、性能やその他の都合でそれができない場合や、付加的にさらにセキュリティを高めたい場合には、データベースファイルを暗号化するのが有効だ。
もっと卑近な例がある。マッチングアプリをスマホに入れていたとしよう。不倫中の奥様が、旦那の目を盗んではそのアプリで間男と連絡を取り合うとする。旦那にパスワードが盗み見されたり、寝ている間に指紋認証を使われると、OSのロックは突破されるリスクがあるため、使い終わったらかならずアプリからはログアウトしている。アプリの認証情報がばれなければ、アプリの情報は見られないに違いないと考えて。しかし、そのアプリのユーザ情報や履歴が暗号化せずに保存されていたならどうか。OSのロックが突破されているなら、その場で、もしくはファイルを転送してから、データファイルの中身を見られてしまう。実際のところ、lessコマンドで開くだけの簡単なお仕事なのだ。
不倫の調査でそこまでやるかはともかく、秘密のデータをローカルに保存するならば、暗号化しておくことは重要だ。しかし、暗号の実装は、既存のライブラリを使っても非常に面倒だし、間違った使い方をすると簡単に解読されてしまうし、そもそもアプリ開発者が自分でやろうとすること自体がセキュリティ上のリスクだ。なので、暗号化をストレージ層に任せられるなら、是非ともそうしたいところだ。そういうわけで、データベースライブラリに暗号化機能を実装した。
使い方は簡単だ。圧縮データベースと同様に、データベースファイルを開く時にオプションフラグを指定するだけでよい。Pythonだとこんな感じだ。
import tkrzw
# B+木データベースを開き、圧縮モードをAESにし、暗号キー「foo」を指定。
dbm = tkrzw.DBM()
dbm.Open("chatlog.tkt", True, record_comp_mode="aes", cipher_key="foo")
# レコードを格納する。ページは勝手に暗号化される。
dbm.Set("00000001", '{user: "join", text: "今日旦那は？"}')
dbm.Set("00000002", '{user: "nancy", text: "出張って言ってた。"}')
dbm.Set("00000003", '{user: "join", text: "じゃあ家でどう？"}')
# レコードを検索する。暗号化されていたページは勝手に復号される。
print(dbm.GetStr("00000001"))
print(dbm.GetStr("00000003"))
# データベースを閉じる。
dbm.Close()これだけなのだ。アプリ開発者は特に暗号について勉強しなくても、ファイルを開く際にフラグを追加するだけで、データを暗号化できる。暗号化しても、使い方は全く変わらない。時間効率と空間効率が若干悪化するが、それがボトルネックになることはない。後述するが、AES-256/CBC/PKCS#7を実装しているので、妥当な暗号キーを設定しさえすれば、どこぞの国家機関が頑張っても解読は困難だ。
利用上の注意点がある。暗号化したデータベースは自身が暗号化されていることはメタデータとして持っているが、当然ながら暗号キーは記録されていない。よって、暗号化したデータベースを開く際には、常に同じ暗号キーを指定する必要がある。暗号キーを渡さなかった場合は空のバイト列が渡されたとみなされる。誤った暗号キーを渡すと誤った値が読み出される。
以下、実装のうんちく。TkrzwのHashDBMクラスは、キーに対応する値を保存する単純な実装だが、値を書き込む前に任意のエンコーダで加工することができる。また値を読み出した後に任意のデコーダで復元することができる。そこに圧縮コーデックを注入すれば圧縮データベースになるし、暗号化コーデックを注入すれば暗号化データベースになるわけだ。従来は圧縮コーデックだけを同梱していたが、最新版からはAESとRC4の暗号化コーデックも同梱される。
HashDBMでは値だけがエンコードされるので、キーは平文のままである。またエンコードが個々のレコードの単位で行われるので、圧縮においても暗号化においても理想的とはいえない。一方、HashDBMの上に構築されるTreeDBMでは、キーと値のリストからなる論理ページをHashDBMの値として管理する。つまり、複数のレコードのキーと値をまとめて圧縮または暗号化してくれる。よって、圧縮率の観点でも暗号強度の観点でも有利だ。圧縮や暗号化を行う際には、基本的にはTreeDBMを使うと良い。一方、キーが平文のままでも問題なく、値のデータ量が大きいという場合にはHashDBMを使っても良い。
暗号化のコーデックはAESとRC4から選べる。AES（Rijndael）はブロック暗号であり、16バイトずつのブロックで暗号化と復号を行う。最後のブロックにパディングを入れて、サイズが必ず16の倍数になるようにする。そうすると実質の長さがわからなくなるので、パディングに入れるバイトには元の長さを16で割った余りを値とするバイト列で表現する。また、暗号に使う初期化ベクトル16バイトを先頭に付ける。元々のサイズが16の倍数であっても、ダミーのパディングブロックが最後につけられる。
[初期化ベクトル{16}][ペイロード][パディング]つまり、HashDBMでは、レコード毎に16バイト初期化ベクトルと、平均8バイトのパディングが付くので、平均24バイトほどフットプリントが増大する。TreeDBMでは平均6000バイトのページ毎に暗号化するので、例えばページ内に100個のレコードが入るなら、レコード毎のフットプリントの増大は0.24バイトに過ぎない。お得だ。
ところで、AESはブロックを暗号化するためのアルゴリズムだが、ブロック単体をいかに堅牢に暗号化したとしても、同じ暗号キーと同じデータの組は常に同じパターンに暗号化されるという宿命がある。これによって、復号しないでも中身が予想できたり、それがヒントになって解読が簡単になるという問題が発生する。それを防ぐのが利用モードとか運用モードとか呼ばれるもので、暗号アルゴリズムと組み合わせて使う。今回は最も典型的なCBCモードというのを実装している。16バイトの各ブロックの各々のバイトで、前のブロックのバイトとのXORを取ったものを保存すれば、同じデータを保存することにはならないという作戦だ。最初のブロックには前のブロックが存在しないので、16バイトのランダムな初期化データを先頭につける。これが初期化ベクトルだ。初期化ベクトルは乱数によって毎回異なる値が生成されるため、同じ暗号データが生成される確率はほぼゼロだ。
AESはキーの長さによって挙動が変わる。16バイト以下のキーを与えると、16バイトになるようにパディングを入れた上で、AES-128関数として動作する。その場合、10ラウンドの撹拌を行う。それを超えて24バイト以下だと、24バイトになるようにパディングを入れた上で、AES-192関数として動作する。その場合、12ラウンドの撹拌を行う。それを超えて32バイト以下だと、32バイトになるようにパディングを入れた上で、AES-256関数として動作する。その場合、14ラウンドの撹拌を行う。それを超える長さだと、32バイトになるようにキーのXOR折返しを行った上で、AES-256関数を使う。当然、速度と暗号強度にはトレードオフの関係があるので、それを踏まえて鍵長を設定することになる。ユーザアカウントと紐づけてストレージを管理するのであれば、ユーザIDとパスワードを連結した文字列をSHA-256にかけて生成した32バイトのバイナリを指定するのが無難だろう。
次に、RC4（ArcFour）について考える。これはストリーム暗号であり、1バイト毎に暗号化を行う。暗号キーを種にした疑似乱数列を生成して、入力の各バイトにおいて前のバイトと乱数と自身のXORを取るという単純な実装だ。ストリーム暗号においても、同じ暗号キーと同じデータの組は同じパターンに暗号化される問題がある。よって、初期化ベクトルとキーを連結したデータをキーにして暗号化を行う。初期化ベクトル自体は暗号化されずに出力の先頭につけられる。ストリーム暗号では初期化ベクトルの長さを任意に設定できるが、今回は6バイト（48ビット）固定にした。
[初期化ベクトル{6}][ペイロード]かつてWi-fiの暗号化に使われていたWEPという暗号化方式は、脆弱性が発見されて利用停止に追い込まれている。WEPは暗号関数にRC4を採用していたが、それが問題ではないらしい。暗号キーが104ビットで初期化ベクトルも24ビットと短いのが主な原因だそうな。今回はそれを踏まえて任意の長さの暗号キーを許し、48ビットの初期化ベクトルを利用する。それでもAESに比べて暗号強度が劣ることは明白だ。ではなぜわざわざRC4をサポートしたかというと、空間効率が良いからだ。フットプリントの増加はHashDBMのレコードあたりで6バイト、TreeDBMのレコードあたりで0.06バイトで済む。また、実装が単純な分、AESよりも時間効率が高いことが期待される。最低限のセキュリティは欲しいが、データ量の増大は抑えたいという場合には、RC4の出番だ。
平文とRC4暗号化とAES化とLZ4圧縮とZSTD圧縮との性能比較を行う。「00000001」「00000002」…「10000000」といった8バイト文字列をキーと値に持つレコードをTreeDBMに1000万個格納し（Set）、その各々を検索する（Get）処理にかかる時間を計測し、また生成されたデータベースファイルのサイズを比較する。
| class | Set | Get | Size |
| Raw | 1,922,421 | 1,884,234 | 182,267,058 |
| RC4 | 1,793,944 | 1,723,193 | 182,534,622 |
| AES | 1,761,819 | 1,662,892 | 183,028,638 |
| LZ4 | 1,828,816 | 1,826,283 | 92,860,130 |
| ZSTD | 1,611,288 | 1,785,054 | 61,037,993 |
この実験は、B+木のデータベースにシーケンシャルアクセスをかけているということに留意されたい。B+木のデータベースでは順序が近隣のレコードはページ単位でまとめられて、そして最近使ったページはメモリ上にキャッシュされる。圧縮や暗号化はページがファイルに書き込まれる際にだけ行われ、毎回のレコード操作で行われるわけではない。シーケンシャルアクセスの場合、キャッシュヒット率は100%に近づき、レコード操作の回数の1/50くらいの頻度でしか圧縮や暗号化は行われないことになる。このアクセスパターンでは、平文では1秒に190万回ものレコード操作ができる。そして、暗号化による性能低下が非常に小さいというのがこの実験の肝だ。RC4でもAESでも170万QPS以上出せる。これは圧縮操作のZSTDよりも早く、LZ4には負けるというくらいだ。いずれにせよ、暗号化や圧縮が原因でボトルネックになることはそうそうあるまい。暗号化に伴う空間効率の悪化も平文に比べて無視できるほどで、データサイズは0.5%も増えない。時間コストと空間コストがここまで小さいなら、暗号化による利点がたとえ大きくないにしても、費用対効果としては十分と言えるだろう。
RC4とAESを比べると、空間効率でも時間効率でもRC4の方が良いという結果になった。そうでなくてはRC4の意味がない。とはいえ、この実験での性能は大差ないとも言える。RC4が思ったより遅く、AESが思ったより早かった。RC4は個々のレコードのエンコードやデコードをする度に元来のキーと初期化ベクトルを連結した新しいキーを生成する必要があり、その処理は鍵長に関わらず必ず256バイトの乱数テーブルを二つ作る処理を伴うために遅い。初期化ベクトルを使わないECBモードなら乱数テーブルを使い回すことでRC4は爆速にできるのだが、ECBモードで複数のデータを処理すると脆弱性が露呈するので、現実的ではない。一方、AESは鍵長で決まる10から14のラウンド数に比例する時間がかかるが、その実装はひたすらアンロールなどの最適化がされているので、複雑な割には高速だ。
RC4は初期化は遅いが対象データの長さあたりの処理は効率的だ。だいたい3000バイトより長いデータでは、RC4の方がAESより早くなる。つまり、HashDBMに3000バイト未満のレコードを格納する場合には、AESの方が早い。TreeDBMの圧縮や暗号化はページ単位で行われるが、デフォルトでは8192バイトでページ分割するので、4096バイトくらいのデータを対象に圧縮や暗号化が行われる。この単位をもっと大きくして、65536バイト分割くらいになると、平文で198万QPS、RC4で188万QPS、AESで177万QPSとなり、RC4の速度が光るようになる。とはいえ、総じてAESの利点の方が大きいので、基本的にはAESを使うべきだろう。HashDBMのレコード単位で暗号化をする際に、時間効率は悪くとも空間効率を少しでも上げたいならば、RC4を使ってもよい。
以上の考察を裏付けるべく、値が100バイトのレコードをHashDBMとTreeDBMのそれぞれに入れる実験もしてみた。
| class | Hash-Set | Hash-Get | Hash Size | Tree-Set | Tree-Get | Tree Size |
| Raw | 1,515,645 QPS | 1,950,478 QPS | 114.63 MB | 1,399,361 QPS | 1,658,892 QPS | 106.49 MB |
| RC4 | 342,577 QPS | 2,041,478 QPS | 120.35 MB | 1,100,026 QPS | 1,187,321 QPS | 106.65 MB |
| AES | 915,297 QPS | 2,055,004 QPS | 143.24 MB | 1,001,877 QPS | 1,045,518 QPS | 107.29 MB |
HashDBMでは暗号化と復号をレコード単位で行うので、当然回数が増えて、スループットも劇的に落ちる。また、処理対象が100バイトと短い場合には、鍵の初期化にかかる時間の割合が増えるので、AESよりもRC4の方が遅くなる。一方でTreeDBMでは暗号化と復号の回数が少なく処理対象も大きくなるので、スループットの低下は小さい。予想通りの結果だ。そして、空間効率の悪化は特にHashDBMとAESの組み合わせで大きくなる。これも予想通りの結果だ。
データベースの話は抜きにして、エンコーダ/デコーダとしての純粋な性能も知りたくなったので、計測してみた。malloc+memcpyでただコピーするだけの実装と、LZ4での圧縮・伸長、ZSTDでの圧縮・伸長、ZLIBでの圧縮・伸長、RC4での圧縮・伸長、RC4での暗号化・復号、AESでの暗号化・復号にかかる時間を比較する。ランダムに選択した英字からなる10000バイトの文字列を処理するのを100000回繰り返した。
| class | compression | decompression |
| memcpy | 0.089472 | 0.079636 |
| LZ4 | 2.389348 | 0.426064 |
| ZSTD | 9.401033 | 1.86894 |
| ZLIB | 31.539818 | 4.940597 |
| RC4 | 1.927086 | 1.742706 |
| AES | 2.947371 | 3.056584 |
てことで、対象データが十分に大きい場合、RC4はAESよりも明確に早い。とはいえAESもそれなりに早く、LZ4よりは遅いがZSTDよりは早いという位置に居る。圧縮アルゴリズムと暗号アルゴリズムの速度比較をするのも変な話だけれども。
まとめ。データベースライブラリTkrzwに暗号化機能をつけた。性能も利便性も損なうことなく、データを暗号化して保護できる。実際のところ、暗号化したからってユーザの利便性が上がるわけではないのだが、売り文句にはなるだろう。「暗号化データベースにより大切なお客様のデータを保護いたします」的な文言を手に入れることができる。既存のコードをたった数行変えるだけ暗号化できるので、その意味でのコスパもかなり良いだろう。
製品紹介のスライドに圧縮と暗号化の話も載せておいたので、興味があればご覧頂きたい。
docs.google.com
