Kyoto Cabinet-1.1.1に暗号化データベース機能を追加したという話。
背景
NTFSではファイルシステムの機能として特定のディレクトリを圧縮することができ、またその圧縮関数を暗号関数に置き換えることで、同じ枠組みで暗号化もサポートしている。ならば、圧縮をサポートしているKCでも、その圧縮関数を暗号関数に置き換えれば、圧縮データベースと同じ枠組みで暗号化データベースをサポートできるのではないか。つーことで、早速やってみた。
圧縮機能も暗号機能もユーザにとっては透過的に機能し、すなわちその機能を有効にするという以外はまったく同じ操作で生データベースも圧縮もしくは暗号化データベースも利用することができる。セキュリティに関わる機能を素人が実装するのは望ましいことではないが、カジュアルな用途では役に立つと思っている。とはいえ問題があれば指摘いただけると嬉しいので、ここに設計と実装を晒してみる。
枠組み
KCのファイルハッシュデータベース（HashDB）とファイルツリーデータベース（TreeDB）とディレクトリデータベース（DirDB）のいずれもが、tune_optionsというメソッドを持っており、それを用いてTCOMPRESSというフラグを立てると圧縮機能が有効になる。デフォルトではZlibの圧縮関数が呼ばれて、各レコードの値の部分が圧縮されて保存されることになる。
どの圧縮関数が適当かはアクセスパターンやデータパターンに左右されるのでプラガブルになっていることが望ましい。よって、従来から、tune_compressorというメソッドがサポートされていて、それに圧縮および伸長の関数を登録することで、ユーザがお好みの圧縮アルゴリズムを選択できるようになっている。ここに暗号および復号化の関数を登録すれば、既存の枠組みを一切変えることなく、暗号機能をサポートできる。
// 圧縮器の実装
class MyCompressor : kc::Compressor {
public:
char* compress(const void* buf, size_t size, size_t* sp) { ... }
char* decompress(const void* buf, size_t size, size_t* sp) { ... }
} mycompressor;
// データベースを圧縮モードで開く
kc::TreeDB db;
db.tune_options(kc::TreeDB::TCOMPRESS);
db.tune_compressor(mycompressor);
db.open(...);
暗号アルゴリズム
俺は暗号理論について全く詳しくないのだが、とりあえず実装が楽だし広く実用されているRC4（Arcfour）という暗号アルゴリズムを使うことにする。RC4は脆弱性を暴かれたWEPで使われているアルゴリズムなので脆弱だと思われがちだが、WEPの脆弱性はRC4の利用方法に問題があっただけで、RC4自体が解読可能になったわけではないらしい。今だったらおとなしくAESとか使うのがよさげな気もするが、そういう本気のユースケースでは既存のモジュールを使って上述のプラグインを実装することになるだろう。今回は、プラグインの一例としてのカジュアルな暗号機能を考え、できるだけ単純に実装できて簡単に利用できるものを目指す。
とりあえずはkcutil.hのユーティリティ関数群のひとつとして、arccipherという関数を追加してみた。ストリーム暗号は変換によってデータサイズが変わらないのと、暗号と復号が同じ関数でできるってのが楽でいいな。それはそれで問題なのだが、それは「利用モード」でカバーすべき話だろう。
/** * Cipher or decipher a serial object with the Arcfour stream cipher. * @param ptr the pointer to the region. * @param size the size of the region. * @param kbuf the pointer to the region of the cipher key. * @param ksiz the size of the region of the cipher key. * @param obuf the pointer to the region into which the result data is written. The size of the * buffer should be equal to or more than the input region. The region can be the same as the * source region. */ void arccipher(const void* ptr, size_t size, const void* kbuf, size_t ksiz, void* obuf);
ストリーム暗号では同じ鍵を2回使うことはできない。なぜなら、平文1と平文2をそれぞれ暗号化した暗号1と暗号2があるときに、暗号1と暗号2の各バイトのXORをとると、平文1と平文2のXORと同じバイト列が得られるからだ。平文のXORに文字の頻度分析とかすると元の文書のデータが結構予測できてしまうので、危険である。
std::string key = "1234";
std::string plain1 = "abcdefghij";
std::string plain2 = "0123456789";
unsigned char* cipher1 = new unsigned char[1024];
unsigned char* cipher2 = new unsigned char[1024];
kc::arccipher(plain1.data(), plain1.size(), key.data(), key.size(), cipher1);
kc::arccipher(plain2.data(), plain2.size(), key.data(), key.size(), cipher2);
// 平文1と平文2のXORがとれちゃう
for (size_t i = 0; i < plain1.size(); i++) {
uint32_t x = cipher1[i] ^ cipher2[i];
printf("%x: %c: %c\n", x, x ^ plain2[i], x ^ plain1[i]);
}
ということで、暗号関数を呼び出す毎に鍵を毎回変えなきゃならない。とはいえ毎回違う鍵の入力をユーザに求めるわけにはいかないので、ユーザから入力された鍵をちょっとずつ加工しながら使いまわすことにする。具体的には、直前に作った暗号のハッシュ値32ビットと、暗号関数が呼ばれた回数32ビットを連結したデータ（初期化ベクトル）を、ユーザが入力した鍵に接頭させたものを、個々のデータの暗号鍵にする。実際の実装は以下のようになる。
/**
* Compressor with the Arcfour cipher.
*/
class ArcfourCompressor : public Compressor {
public:
/**
* Constructor.
*/
ArcfourCompressor() : kbuf_(NULL), ksiz_(0), salt_(0), cycle_(false) {
_assert_(true);
kbuf_ = new char[0];
ksiz_ = 0;
}
/**
* Destructor.
*/
~ArcfourCompressor() {
_assert_(true);
delete[] kbuf_;
}
/**
* Set the cipher key.
* @param kbuf the pointer to the region of the cipher key.
* @param ksiz the size of the region of the cipher key.
*/
void set_key(const void* kbuf, size_t ksiz) {
_assert_(kbuf && ksiz <= MEMMAXSIZ);
delete[] kbuf_;
if (ksiz > NUMBUFSIZ) ksiz = NUMBUFSIZ;
kbuf_ = new char[ksiz];
std::memcpy(kbuf_, kbuf, ksiz);
ksiz_ = ksiz;
}
/**
* Begin the cycle of ciper salt.
* @param salt the additional cipher salt.
*/
void begin_cycle(int64_t salt = 0) {
salt_ = salt;
cycle_ = true;
}
private:
/**
* Compress a serial data.
*/
char* compress(const void* buf, size_t size, size_t* sp) {
_assert_(buf && size <= MEMMAXSIZ && sp);
uint64_t salt = cycle_ ? salt_.add(1) : 0;
char kbuf[NUMBUFSIZ*2];
writefixnum(kbuf, salt, sizeof(salt));
std::memcpy(kbuf + sizeof(salt), kbuf_, ksiz_);
char* zbuf = new char[NUMBUFSIZ+size];
char* wp = zbuf;
writefixnum(wp, salt, sizeof(salt));
wp += sizeof(salt);
arccipher(buf, size, kbuf, sizeof(salt) + ksiz_, wp);
if (cycle_) {
size_t range = size < sizeof(uint64_t) ? size : sizeof(uint64_t);
salt_.add(hashmurmur(wp, range) << 32);
}
*sp = sizeof(salt) + size;
return zbuf;
}
/**
* Decompress a serial data.
*/
char* decompress(const void* buf, size_t size, size_t* sp) {
_assert_(buf && size <= MEMMAXSIZ && sp);
if (size < sizeof(uint64_t)) return NULL;
char kbuf[NUMBUFSIZ*2];
std::memcpy(kbuf, buf, sizeof(uint64_t));
std::memcpy(kbuf + sizeof(uint64_t), kbuf_, ksiz_);
buf = (char*)buf + sizeof(uint64_t);
size -= sizeof(uint64_t);
char* zbuf = new char[size];
arccipher(buf, size, kbuf, sizeof(uint64_t) + ksiz_, zbuf);
*sp = size;
return zbuf;
}
/** The pointer to the key. */
char* kbuf_;
/** The size of the key. */
size_t ksiz_;
/** The cipher salt. */
AtomicInt64 salt_;
/** The flag of the salt cycle */
bool cycle_;
};
使い方は簡単で、set_key メソッドででユーザ入力の鍵を登録して、鍵の攪拌を始めたいタイミングで begin_cycle を呼べばよい。その際に64ビットのユニークなsaltを指定することが重要である。どうやってユニークにするかはアプリ側の責任だが、カジュアルにはミリ秒の時間とかでもいいかなーと（多分怒られる）。実際にはmacアドレスとinodeとタイムスタンプを組み合わせるとかするのかもしれない。
// RC4圧縮器（暗号器）を作る
kc::ArcfourCompressor comp;
comp.set_key("foobarbaz", 9);
// データベースを圧縮モードで開く
kc::TreeDB db;
db.tune_options(kc::TreeDB::TCOMPRESS);
db.tune_compressor(&comp);
// 鍵の攪拌を開始する
comp.begin_cycle(kc::time() * 1000);
もっとカジュアルに
上記のようないかにも裏方の知識を要するプログラミングをしたいユーザは少ないだろう。特にスクリプト言語バインディングからはC/C++のプログラミングなしで呼べるようにしないと使えない。ということで、多相データベース（PolyDB）の命名規則を拡張して、圧縮関数と暗号鍵を指定できるようにしてみた。
kc::PolyDB db;
db.open("casket.kct#zcomp=arc#zkey=foobarbaz");
うおおお。簡単！ たったこれだけで暗号化データベースが作れちゃう。鍵の管理はアプリケーションの責任になるが、中の暗号アルゴリズムがどうなっているかとかいうことを気にせずに気軽に暗号化ができるというのは嬉しいことだ。もちろんスクリプト言語バインディングからも同じように使える（KCを最新版にする必要はあるが）。
ただし、ファイルハッシュデータベースとディレクトリデータベースの圧縮関数はレコードの値部分にしか適用されないので、暗号関数を使った場合も同様で、キーは平文のままになることに注意すべきだ。ファイルツリーデータベースはページ単位で圧縮を行うので、キーも暗号化される。なので、キーの存在を知られたくない場合（大抵のユースケースではそうだと思うが）は、ファイルツリーデータベースを使うべきである。多相データベース経由の場合は、拡張子「.kct」かオプション「#type=kct」をつける。
あと、暗号関数自体をDB内に記憶することはできないので、暗号関数はDBを開く度に必ず指定する必要がある。DB内部には一定のデータに暗号関数をかけた時のチェックサムだけが保存されているので、指定する暗号関数が一貫していなかったりパスワードが間違っていたりした場合にはエラーを検出してopenに失敗するようになっている。
性能
100万レコードの読み書きにかかる時間とファイルサイズを平文データベースと暗号化データベースで比較してみた。
| set | get | remove | size | |
| HashDB (平文) | 0.786 | 0.784 | 0.693 | 38297720 |
| HashDB (暗号) | 4.456 | 4.306 | 4.240 | 46297720 |
| TreeDB (平文) | 0.713 | 0.801 | 0.741 | 19931904 |
| TreeDB (暗号) | 0.736 | 0.864 | 0.756 | 19931904 |
ファイルハッシュDBにおいては、暗号化による時間と空間のペナルティがかなり大きいことがわかる。時間効率が悪化する原因は、暗号化処理もしくは復号処理とそれに伴う初期化ベクトルの生成処理をレコード数と同じ頻度で行うことである。空間効率が悪化する原因は、各レコードにひもづけて初期化ベクトルを保存しなきゃならないからである。
一方で、ファイルツリーDBにおいては、時間も空間もほとんど変わらない。暗号化処理や復号処理はページ単位でしか行わず、ページ数はレコード数に比べるとかなり少ないので、結果的にオーバーヘッドが非常に小さくなるのだ。サイズが全く同じなのは、ページ毎に付加される初期化ベクトルがページ毎のアラインメントによるパディング領域に収まるからである。
まとめ
DBMにちょっと秘密のデータを格納したい時、KCの暗号化データベース機能を使うと便利である。暗号強度がどれほどのものなのかはよくわからないので、現状では実験的な位置づけにすぎないけども、今まで平文で保存していたブログのパスワードとかをこっちに載せ替えるのとかには役立つと思う。特にファイルツリーDBでは性能が全くと言っていいほど劣化しないので、本当に気軽に暗号化を施すことができる。