Internet Watch logo
記事検索
最新ニュース

IPAが暗号技術Toyocryptを世界で初めて解読、今後はAESやE0の安全性評価も


IPAのToyocrypt解読プログラム
 情報処理推進機構(IPA)は、9月20日付でストリーム暗号「Toyocrypt」の解読に成功したと発表した。暗号関連の国際会議などで理論的に解読できることが指摘されていたが、実際に解読したのは初めてだという。

 Toyocryptは、2000年に公募された電子政府推奨暗号に東洋通信機が提案したストリーム暗号のアルゴリズム。実際には電子政府推奨暗号に採用されることはなかったが、総当たり法と呼ばれる攻撃手法では解読に「100億年かかる」とされ、実質上永久に解けない暗号とされていたという。

 IPAが暗号の解読に採用したのは「代数的攻撃手法(Algebraic Attack)」だ。代数的攻撃手法とは、暗号のアルゴリズムから多次多変数の連立方程式を多数作成し、それらの方程式を解くことで暗号の秘密鍵を明らかにする手法。IPAでは2004年から暗号解読プロジェクトを立ち上げ、この代数的攻撃手法に用いる多次多変数連立方程式の解法「グレブナー基底探索アルゴリズム」によるプログラム「IPA-SMW」を開発していた。

 2005年上期にIPA-SMWをToyocryptに最適化。IPA-SMWの後処理で秘密鍵を算出できるようになった。開発には、xの2乗や3乗など高い次数が表われる連立方程式を設定する高い数学力のほか、高度なプログラム力が必要だったという。このためIPAでは「暗号学」「数学」「プログラミング」の3分野から、専門家を招集している。

 プログラムを担当したのは、未踏ソフトウェア創造事業で「スーパークリエータ」に認定された光成滋生氏(ユーテン・ネットワークス)と渡辺秀行氏(アイビス)。プロジェクトリーダーで連立方程式部分を担当したのは、IPAセキュリティセンター暗号グループの杉田誠研究員だ。なお、IPA-SMWには彼らの頭文字(杉田・光成・渡辺)を取った。


IPAセキュリティセンターの杉田研究員 スーパークリエータとして暗号解読に携わった渡辺氏。なお、光成氏は都合がつかず記者会見を欠席した

 今回の暗号解読では、IPAの所有するCPU(Opteron 2GHz)128個のグリッドコンピュータ上でIPA-SMWを実装し、2の21乗個の暗号文と平文の組み合わせから解読させたところ、9月20日に27分間で秘密鍵が判明し解読に成功した。杉田氏によれば、現在ではプログラムの最適化がより進み「20秒程度で解読できる」という。なお、電子政府推奨暗号に選ばれた「MUGI」「MULTI-S01」「128-bit RC4」といったストリーム暗号は「代数的攻撃手法では恐らく解けない」とコメントした。

 IPAの池田雄作理事によれば、今後はIPA-SMWを用いて、代数的攻撃手法で解読できるとの指摘がある米国政府の標準暗号化方式「AES」や、Bluetoothで利用されているストリーム暗号アルゴリズム「E0」などの安全性を評価する方針だ。


関連情報

URL
  IPAセキュリティセンターの「暗号技術」ページ
  http://www.ipa.go.jp/security/ipg/crypt.html

関連記事
国産暗号アルゴリズム「Camellia」がインターネットの標準暗号規格に採用(2005/07/20)
公開鍵暗号、ハッシュ関数の強度に疑問を投げかける研究報告(2005/05/13)
暗号通信などに用いられる「SHA-1」の攻撃を容易にする研究が公表(2005/02/22)


( 鷹木 創 )
2005/09/26 17:44

- ページの先頭へ-

INTERNET Watch ホームページ
Copyright (c) 2005 Impress Corporation, an Impress Group company. All rights reserved.