top of page
ドットの接続

第２８回

その暗号は
すでに解読されている！？

日本政府にCRYPTRECと称される暗号機関が存在することはご存じでしょうか。暗号機関と書くと諜報機関と混同してしまい、怪しげな組織のように思われますが、そうではなく、政府推奨暗号の安全性を評価・監視し、暗号技術の適切な実装法・運用法を調査・検討するプロジェクト機関です。2003年に、初めて日本国政府として推奨する暗号のリストが発表されました。その際には、10年はその安全性が保たれるであろうことを評価基準にして、各種暗号を評価し、その厳しい評価に合格した暗号だけがリストアップされたのです。しかしながら、その後、10年を待たず、解読技術を含めて、暗号技術が格段に発展したことから、幾度となく大きな見直しが求められました。特に2013年度版の暗号評価リスト案では大幅に改定され、10年前に比較して大きく変わっています。その後も評価が続けられ推奨暗号リストが更新されています。専門家による厳格な審査が行われ、このリストに採用されること自体が容易ではありません。そしてリストに載ったとしても、10年後にはリストから除外されることも少なくないのです。

数字

暗号の安全性とはどのように評価するのでしょうか。その説明は非常に難しいので、その評価の一つとしての「暗号解読」に的を絞りましょう。一般には暗号解読に成功する事は、その暗号に利用した鍵（パスワード）がわかる、あるいはどのような暗号文も平文に戻す事が可能となることだと理解されています。しかし、暗号の研究者、技術者にとって、解読に成功する事は与えられた仮定の下で当初保証した仕様（条件）を満足しないことを証明することです。典型的な条件の一つが鍵の全数探索安全性です。つまり、128ビットの鍵を使用したとすれば、十分な暗号文やそれに対する平文の情報があったとしても、鍵や平文を求めるには、鍵の全数探索より小さな計算量で求められないことです。少しでも小さな計算量で鍵や平文を求めることができるとすれば、その暗号は当初の安全性の仮定を満足しない事になり、解読されたと呼ばれるのです。10年も前の2011年8月、暗号に関する有名な国際会議であるCRYPTO2011（米国、サンタバーバラ）で、AESが解読されたという発表がなされました。しかし、現実的な意味で解かれたわけではなく、鍵の全数探索よりも小さい計算量、つまり128ビット鍵のAESであれば、2126.18の計算量で解けることが示されたのです。もちろん、この結果は理論的には素晴らしい結果ですが、現実的に意味は無いのでしょうか。いや、決してそうではなく、当初の仕様を満足出来なかったという意味で、AESにとっては大きな欠点であり、その傷口から、更に大きな欠点が生まれる可能性は否定出来ず、AESに関する信頼性は少なからず揺らいだものとなったと言わざるえません。その「解読された」AESは現在でも利用されています。

暗号の解読のための仮定（条件）ですが、様々な条件があります。アルゴリズム、つまりどのように暗号され、復号されるのかという方法、さらにその方法に至った経緯や根拠を公開するという条件の他に、細かなところでは、ハードウェアやソフトウェア化した際の電力やメモリの使い方まで様々です。昨今ではサイドチャネル攻撃といって、ハードウェアでの実現であれば電力の使用状況、ソフトウェアであればメモリやCPUの使用状況、場合によってはバッファメモリの痕跡を使っての攻撃も考えられており、それらに耐性を有するための条件も必要となって来ています。根本的な解読の条件としては以下に上げられます。

​

​

  1.  既知暗号文攻撃：　大量の暗号文のみから鍵や平文を推定する攻撃

  2.  既知平文攻撃：　大量の平文とそれに対応する暗号文から鍵や平文を推定する攻撃

  3.  選択平文攻撃：　希望する一部の平文に対して暗号文が得られる仮定のもとから鍵や平文を推定する攻撃

  4.  選択暗号文攻撃：　希望する一部の暗号文に関して平文が得られるという仮定のもとから鍵や平文を推定する攻撃

​
 

もはや、条件4は鍵はともかく、任意の暗号文を平文に戻す事ができるという条件なので、事実上、暗号が解けるに等しい厳しい条件と言えます。しかし、現在の暗号はこれらすべての仮定でも安全でなければならないのです。

新しいキー

暗号に対する攻撃方法でもっとも単純な攻撃法はブルートフォース攻撃と呼ばれる鍵や平文の全数探索法です。鍵が128ビットであれば、2128個の鍵をすべて検査すれば、正しい鍵を求める事が可能であり、解読が成功します。しかし、これは解読の条件ではなく、前提として、どのような攻撃方法も鍵の全数探索よりも小さな計算量で成功しないということであって、逆に鍵の全数探索で解読が成功したとしても問題にならないのです。また現実的に解かれないために鍵を128ビットにしているのです。実際、AES以前の事実上の米国標準暗号であったDESは鍵が56ビットであったため、その全数探索で解かれてしまいました。

鍵を全数探索する事無く、鍵の全数探索よりも計算量を少なくして攻撃する方法として、ショートカット攻撃法が存在します。これは具体的な攻撃手順を指すのではなく、暗号アルゴリズムの性質を用いて行う攻撃です。

​

​

​

このショートカット攻撃として、強力な攻撃方法として中間一致攻撃があります。一般にAESのような共通鍵暗号は、比較的単純な変換、つまり文字を置き換えるという換字変換、文字の順序を置き換えるという転置変換を複数回組み合わせて暗号化します。AESではこのような基本操作を10回繰り返しています。基本的に暗号を解く際は入力（平文）と出力（暗号文）との極めて微小な相関を利用して解くことを試みるのですが、設計上、そのような相関はない、正確には見つけるのが困難であるようにしています。1回だけの繰り返しであれば、そのような相関を見つける事が出来ても、10回繰り返す事によって不可能になっているのです。

 

しかし、5回の繰り返しであれば、見つけられるかも知れません。中間一致攻撃とは、繰り返しの半分のところでの相関を見つけることによって、入力側と出力側から一致する、すなわち平文と暗号文が結びつくようにする方法です。このときに重要な役割を演じるのが「誕生日の問題」なのです。バースデイパラドックスとも呼ばれます。誕生日の問題では高々40人の教室で同一の誕生日を持つ人が高い確率で存在するというものでした。365日もあるにも関わらず、40人いるだけで一致してしまうというものです。これと同じように、数多くある平文と暗号文が、繰り返しの途中で一致する確率が小さくないことを利用する方法です。一昨年のAESの解読もこの中間一致攻撃を応用した方法でした。ただ、小さくないといっても、2128が2126.18になるようなわずかな差なのですが。

3.png
bottom of page