IoT時代に必要とされる軽量共通鍵暗号の安全性評価に貢献 ～国際暗号学会主催国際会議に採録された論文がTop3に選出される～

1．背景

暗号技術は、攻撃者が無限の計算能力をもったとしても安全である「情報理論的に安全」な方式と、攻撃者が、例えば地球上のコンピュータ全てを10年間利用したとしても解読できないといったように、一定の計算能力に制限された条件で安全である「計算量的に安全」な方式の2種類に分類できます。情報理論的に安全な方式はコンピュータの進歩に関わらず安全であるという利点があるものの、利用に当たっては秘密に保持すべき「鍵」と呼ばれるデータが、送信する平文と同じかそれ以上の長さが必要であるという問題があり、軍事や外交など究極の安全性が求められる場合を除き実用的ではありません。一方、計算量的に安全な方式は、鍵を128ビット程度に押えることが出来るという利点がある一方、安全だと証明された方式はありません。

計算量的に安全とされる暗号方式は、数学的に困難な問題や別の計算量的に安全とされる方式が本当に安全だという前提のもとに安全だと証明される縮約安全性を持つ方式と、暗号方式それ自身が安全だと期待される暗号プリミティブと呼ばれる方式の二種類に分類されます。縮約安全性を持つ方式は、仮定が成立し証明が誤っていない限り安全です。一方、暗号プリミティブは、方式を公開し、長年に亘り多数の暗号研究者の多数の解読を試みる公開の営みによっても解読されないということにより安全性の信頼度を増していきます。NTTが三菱電機と共同開発した共通鍵暗号Camelliaはこの暗号プリミティブに分類される方式であり15年以上に亘り誰も解読に成功しておらず安全性に対する信頼性が高い方式といえます。
大多数の暗号プリミティブは、実装効率化のため繰り返し構造をとっており、その繰り返し回数のことを段数と呼びます。たとえば、128ビット鍵のCamelliaの段数は18段であり、256ビット鍵のAESの段数は14段です。通常、段数を減ずれば減ずるほど暗号強度は低下します。暗号プリミティブに対する解読の試みは、多数の既知の解析手法に対して行なわれます。既知のそれぞれの解析手法に対し解読可能かどうかの試みは、段数をどこまで減じて解読可能かどうかを調べることにより行なわれます。例えば、AESは通常の差分解読法と呼ばれる解析手法に対し、4段を超えると解読困難であることが知られており、256ビット鍵のAESは、仕様通りでは14段であることから通常の差分解読法に対してはまず安全であろうということが分かります。
計算量的に安全な方式に対し鍵の全数探索攻撃は必ず成立する攻撃であることから、鍵の全数探索より少ない計算量で未知の平文や鍵が導出されれば学術的には「解読成功」となります。例えば、256ビット鍵長のAESは、攻撃者にとって都合のよい関係性を持った4つの異なる鍵を用いるという、現実的にはほぼ起こり得ない状況設定で、攻撃者が選んだ2^99.5ブロック（1ブロックは128ビット）の平文に対応する暗号文を入手し、AES-256の2^99.5回の暗号化時間に相当する計算量を用いることにより、ブーメラン攻撃と呼ばれる高度な解析手法を用いると鍵を回復できることが示されており、学術的には256ビット鍵長のAESは解読可能とされます。さらに、既知の解析手法に対し安全な方式に対しては、未知の方式を考案し、解読を試みます。このような差分解読法やブーメラン攻撃など数々の解析手法に対し、解読されない方式が安全であろう方式として信頼を勝ち得るのです。

2．技術のポイント

1993年に発表された線形解読法は、当時、事実上の標準方式であったDESに対し適用され、初の計算機実験による解読が示されました。以後、汎用的な解析手法として多数の暗号プリミティブに適用され、さらに線形解読法発表以降の新暗号に対しては、線形解読法が適用困難であるという証拠が開発者に求められるようになりました。線形解読法は暗号プリミティブに存在する非線形性を線形に近似することにより解読につなげます。これを線形、つまり1次、から非線形、つまり2次、また高次へと次数をあげて解読が実行可能であるかどうかは暗号研究者の長年の研究課題でした。例えば、1995年に発表された試みでは、暗号プリミティブの入出力部近傍に対しては非線形近似による解析が出来たものの、暗号プリミティブ全体に亘って非線形近似により解読につなげることには成功していませんでした。今回考案した非線形不変量攻撃は、この未解決問題を初めて解決したものです。

今回の論文における非線形不変量攻撃の適用対象は、改ざん検知暗号（改ざん検知機能付きの共通鍵暗号方式）の評価コンテストCAESARに応募された方式であるSCREAMおよびiSCREAM、そしてAsiacrypt 2015で発表された共通鍵暗号Midori64です。これらの方式において、sboxと呼ばれる非線形関数に対して2次の不変量を発見し、さらに線形変換部に二値直交行列が用いられていることから各段毎のsboxの出力を全て足し合わせることにより、不変量が保たれることを示し、解読へつなげました。その結果、SCREAMとiSCREAMにおいては、全鍵空間2^128個のうち2^96個の鍵に対して、33ブロック（1ブロックは128ビット）という短い暗号文のみから平文の32ビットが瞬時に復元されてしまうこと、またMidori64においては例えばCTRモードでの利用では、全鍵空間2^128個のうち2^64個の鍵に対して、33ブロック（1ブロックは64ビット）の暗号文から平文の32ビットが復元されてしまうことが分かりました。これまでの大多数の解析手法による安全性評価では、攻撃者が選んだ平文を暗号化してもらい出力された暗号文をテラバイト単位で用意するという、攻撃者にとって非現実的な環境を想定していました。これらの既存の解析手法と異なり、今回の解析手法では、平文を必要とせず暗号文からのみ解読すること、また、解読には1キロバイトにも満たない暗号文のみを必要とすることが画期的であると考えられます。

3．今後の予定

NTTセキュアプラットフォーム研究所は、今回、考案した非線形不変量攻撃を他の既存方式に適用し、解読可能かどうかの評価を行ないます。さらに、よりよい暗号技術の開発のため、今後も暗号安全性評価の技術の研究を推進してまいります。
なお、今回の成果の詳細は2016年12月4日から8日にベトナムのハノイで行なわれる国際暗号学会（IACR）主催の査読付最難関国際会議Asiacrypt 2016におけるTop3論文に相当する「Invited to Journal of Cryptology」に選ばれ、6日（火）に発表されます。

NTTの暗号プリミティブ研究の歴史

用語解説

Camellia ...

NTTと三菱電機が2000年に発表した方式。CRYPTREC暗号リスト中の電子政府推奨暗号に選ばれている他、ISO/IEC 18033-3やRFC 3713などの各種標準に記載されている。さらに、LinuxやFreeBSDまたOpenSSLなどのオープンソースでも利用可能である。

CTRモード ...

共通鍵ブロック暗号を用い、秘匿機能を実現するために用いられる暗号利用モードのひとつ。CRYPTREC暗号リストの電子政府推奨暗号リストや、米国技術標準院（NIST）のSP 800-38Aなどで採用され、広く使われている。

Journal of Cryptology招待 ...

国際暗号学会（IACR）が編集する暗号分野の専門論文誌Journal of Cryptologyに招待され、採録が確実な論文。Asiacrypt 2016では3論文がInvited to Journal of Cryptologyに選ばれた。