【コラム】順序保存暗号化(Order Preserving Encryption)は安全な暗号化か。
「順序保存暗号化(Order Preserving Encryption)は安全な暗号化か。」
一般の企業で会社の情報セキュリティを担当しているKさんは、このごろ悩み事が多い。個人情報保護法の遵守のため、個人情報が保存されている業務システムに暗号化製品を導入して適用しようとしている。暗号化製品を設置すれば、個人情報保護法の遵守は問題ないが、業務システムの性能が低下する可能性があり、心配が大きい。
その時、偶然「OPE」という技術を採用したという暗号化製品の広告を見ることになる。OPE技術がどのような技術かは分からないが、暗号化後にもDB検索の性能低下がないという説明が大きく伝わってくる。OPEという名前が「Order Preserving Encryption」だから、暗号化(Encryption)も性能低下も解決するということで自分の悩みを一回で解決してくれそうだ。
個人情報の保護のため、DB暗号化製品を導入するケースが増え、上記の話のようにOPEに対する関心が高まっている。
「OPE(Order Preserving Encryption)」は、どのような技術であり、どれほど安全なのか。個人情報保護の安全性と性能低下の克服の二兎を得る技術であるかを調べることにしよう。
手順を維持する暗号化は根本的に危険
DB暗号化は、個人情報保護のための必須技術と認識されている。DBサーバに暗号化を適用すると、DBサーバに保存されるデータを暗号化して保存し、データを照会する際には暗号化されたデータを復号した後に使用者に対して提供される。DBサーバは暗号化と復号のための処理演算を追加で遂行しなければならないため、速度低下が避けられない。暗号化の適用によるDBサーバの性能低下問題は、暗号化アルゴリズムの効率的な実現技術で解決できる。
DB暗号化でさらに重要な問題は、検索の索引を生成する問題である。検索の索引は、DBに保存されている膨大なデータの中から必要なデータを迅速に照会するために使用されるDB内部の追加情報である。暗号化されたデータから希望するデータを検索するには、暗号化になる前のオリジナルデータを知らなければならないため、暗号化されたデータを全部いちいち復号しなければならない。希望するデータを一つ照会するたびに、膨大なデータをすべて復号しなければならないため膨大な演算量の負担が発生するしかない。これを解決する方法のひとつが、「順序保存暗号化(Order Preserving Encryption、以下OPE)」だ。
OPEは、かなりずいぶん前から存在していた技術だ。OPEの歴史を遡ると、第一次世界大戦から使用された「One-Part Code」技術がOPEの始祖といえる。暗号化されたデータについても、DBの検索索引を容易に作れるという特長のために2000年代からDBMS業界で注目され始めた。2004年には、R.Agrawalを含め4人のIBM研究員たちが最初にOPEという用語を定義した。彼らはOPEの概念に対する数学的モデルと実現に対する方向性を提示したが、安全性に対する具体的な言及や証明をしなかった。
(参考文献:R.Agrawal、J.Kiernan、R.Srikant、and Y.Xu、「Order-preserving encryption for numeric data」、SIGMOD 2004、pp.563~574)
データを迅速に照会するためには、データを順に整列しておかなければならない。例えば、数百万人のマイナンバーの中から自分が探すマイナンバーが含まれているかどうかを容易に探す方法は、マイナンバーを13文字の自然数と見て大きさ順に整理しておくことだ。しかし、この方法は暗号化後には使用できない。暗号化は、オリジナルデータを予測できない任意の値に変換する過程なので、暗号化されたデータはオリジナルデータとは全く違う順番に整列されるしかない。暗号化を適用しても、暗号化したデータがオリジナルデータと同様の順番に整列されるようにしてくれる方法がOPEである。大きさが小さい順に整列された数字データ1234、3456、5678という三つの数字があると仮定する。一般的な暗号化を適用すれば、三つの暗号化された数字間の順序が巻き込まれる。OPEを適用すれば、1234の暗号が3456の暗号より前に整列されて、3456の暗号は5678の暗号よりもリードすることになる。
順序保存暗号化という名称のように、果たしてOPEは安全な暗号化だろうか。安全な暗号化は、暗号文からオリジナルデータに関するいかなる情報も得られないべきだ。OPEは、暗号文で「順序」という情報を得ることができ、これをもとに、平文を類推することができる。上記で説明した1234、3456、5678の例に戻ってみよう。1234の暗号文(A)と3456の暗号文(B)を知っていれば、暗号文Aと暗号文Bの間に整列される暗号文Cは1234と3456の間にある値から作られた暗号文であることが把握できる。この場合、暗号を解読しようとする攻撃者が1234と3456を知って、二つの数を暗号化した値(暗号文A、B)たちも知っているため、このような攻撃方法を「選択平文攻撃(Chosen Plaintext Attack;以下CPA)」という。
安全な暗号アルゴリズムは、CPA攻撃モデルを採用した攻撃者が暗号文Cがどんな数字を暗号化したかを区分できない「非区別性(Indistinguishability)」を満足しなければならないが、OPEはこれを満足しないために安全な暗号化とは言えないのだ。したがって、OPEはDES、AES、SEED、ARIAなどと同じ普通のブロック暗号化アルゴリズムと肩を並べそうな高いレベルの安全性を備えていない。世界の情報セキュリティ関連の標準でOPEを見られないことも、このような理由だ。
「順序保存を提供する安全な暗号化は不可能なのだろうか」
という問題を解決するために、米国のジョージア工科大学(Georgia Tech)のボルディレワ(Boldyreva)教授を含めた4人の研究者たちが2009年の研究結果を発表した。
(参考文献:A.Boldyreva、N.Chenette、Y.Lee、A.O’Neill、「Order-Preserving Symmetric Encryption」、EUROCRYPT 2009、pp.224~241.)
ボルディレワは、制限的な環境ではOPEの脆弱攻撃であるCPA攻撃をある程度のレベルまでは防御できると証明した。尚且つ、制限条件でOPEにCPA攻撃をブロック暗号化アルゴリズムと同等のレベルに防御することは現実的に不可能というのも明らかにした。つまり、単純アルゴリズムの改善だけではこれ以上の安全性を期待することは難しいということだ。
アルゴリズム自体だけではCPA攻撃から逃れることはできないので、「どう実現するのか」が業界の主要関心事として浮上している。現在、大半のセキュリティ会社がOPEの安全性を補完してくれる技術およびセキュリティデバイスをともに使用し、OPEの脆弱性を補完するために努力している。OPEと共に他の検証を受けた暗号化アルゴリズムを使用したり、順序情報のみをさらに暗号化することなどをその例に挙げられる。しかし、このような状況についてよく知らない一般人たちは、「順序の保存暗号化」という名称だけを信じてOPEを他の暗号化アルゴリズムのように安全性が高いと考えやすい。
実際、ある会社ではOPE技術の安全性を誇大に評価して業界の非難を買ったりした。したがって、OPE関連ソリューションを選択する時には、製品内にOPEの安全性を補完してくれるセキュリティデバイス及び技術があるかを調べた後製品を選択しなければならない。特に、CPA攻撃は攻撃者が暗号化システムに容易にアクセスできる時に主に発生するので、製品にこのような弱点はないかを確認しなければならない。
暗号化を必要とする応用は様々だ。安全度が高いレベルで要求される応用がいれば、安全度が高くなくても大丈夫な応用もあり得る。OPEの場合、安全性を一部犠牲にして性能を選んだ応用と見られる。コラムの冒頭に仮想シナリオの主人公だったKさんのように、個人情報保護を必要とする応用では、長期間検証され高い安全度を保障してくれることができる標準的な暗号化技術が必要である。OPEは、オリジナルデータの順序が暗号化後も維持されるというメリットがあるため、データ検索などでは有用な技術であることに違いないが、安全性には限界があるということを忘れてはならない。
したがって、セキュリティ業界はOPE技術を適用する場合、安定性が脆弱な部分と程度については、ユーザに正確に知らせなければならない。一方、使用者は従来のブロック暗号化アルゴリズムと同レベルの安全な暗号化を提供したりはしないということを理解して、安全度よりも性能が重要な応用に選択的に適用するようにする。それとともに、足りない安全度を補完してくれるセキュリティデバイス及び機能が製品内に搭載されているかを是非検討しなければならない。