HOME >> 情報セキュリティ >> 記事

世界初！ストリーム暗号「Toyocrypt」の解読に成功
〜IPAはストリーム暗号の代数的性質を利用した世界最速の解読プログラムを開発〜

最終更新日：2005年9月27日

平成17年 9月26日

独立行政法人　情報処理推進機構

独立行政法人 情報処理推進機構（略称：IPA、理事長：藤原 武平太）は、2005年9月20日世界で初めてストリーム暗号(携帯情報機器の無線通信などに使用される暗号)「Toyocrypt」(以下、Toyocryptという。)の解読に成功しました。

　「Toyocrypt」は、2000年当時、実質的に永遠に解けない暗号として電子政府推奨暗号候補として提案されましたが採択にいたらなかったものです。近年、欧米亜の暗号に係る国際学術会議において、世界的な研究者間でこの暗号の解読可能性がひとつの主要な論点となっていました。新たに代数的攻撃手法を適用することで理論的に解読可能との研究結果が発表されるなど注目を浴びていますが、解読には高度なプログラミング能力と高速のコンピュータが必要なため、計算機を利用して実際に解読した実証例は皆無でした。
　IPAは、代数的攻撃手法に対する暗号の安全性評価手法を確立するために、IPAが認定したスーパークリエータらを起用し、暗号解読プロジェクトを立ち上げました。プロジェクトの活動の一環として、代数的攻撃に用いる、多次多変数連立方程式の解法 (グレブナー基底探索アルゴリズム)によるプログラム(「IPA-SMW」)を開発しました。これを、IPAが所有する暗号研究専用として使用する世界最高レベルの並列コンピュータ(グリッドコンピュータ)上で高速化および最適化を行った上で、Toyocryptの解読に適用し、世界で初めて、27分間という極めて短い時間での解読に成功しました。
　今後は、このIPA-SMWを用いて、継続的に電子政府推奨暗号等の安全性評価を行っていく予定です。

★世界で初めてストリーム暗号「Toyocrypt」の解読に成功

　2005年9月20日(火)、IPAセキュリティセンター暗号グループは、暗号の安全性解析を行うプロジェクトの一環として、世界最速の、ストリーム暗号※1の代数的性質を利用した鍵探索プログラムを開発し、世界で初めて「Toyocrypt」 (東洋通信機株式会社が発明したストリーム暗号)の解読に適用し、実際に解読可能である事を実証しました。

★「Toyocrypt」解読の背景：求められるストリーム暗号の安全性評価手法の確立

　近年Algebraic Attack（代数的攻撃）※2と呼ばれる解読法が提案され、この方法を用いたToyocryptや, E0(無線システムBluetooth ※3に用いられているストリーム暗号)などへの具体的な解読手法の理論が報告されています。このため、代数的攻撃によるストリーム暗号などに関する実質的な脅威を検証する必要が生じ、この安全性の評価手法の確立が電子政府推奨暗号の安全性確保のためにも強く求められていました。

★IPAで暗号解読プロジェクトを編成

　電子政府推奨暗号の安全性評価を行っているIPAでは、2004年にストリーム暗号の安全性の評価手法の開発を主たる目的とし、IPAの未踏ソフトウェア創造事業の中で「IPA認定スーパークリエータ(天才クリエータ)※4」に認定された世界最高レベルのプログラミング能力を誇る光成滋生氏(ユーテン・ネットワークス株式会社)※5、渡辺秀行氏(株式会社アイビス)※6、IPA研究員の杉田を起用した暗号解読プロジェクトを立ち上げました。
　本プロジェクトでは、代数的攻撃手法に対する安全性の評価手法を確立するにあたり、その攻撃に用いるグレブナー基底探索アルゴリズム※7の開発を行い、2004年下期に、グレブナー基底探索プログラム( IPA-SMW )を、IPAが所持する世界最高レベルの性能を持つとされる暗号研究専用に使用している並列コンピュータ (グリットコンピュータ)※８に実装しました。
IPA-SMWは、同機グレブナー基底探索プログラムとして従来の世界最高速をしのぐ高速化を達成したプログラムです。
本IPA-SMWのソースコードは、下記のサイトで公開しております。

URL：http://www.ipa.go.jp/security/fy16/development/crypt_stream/

　なお、IPA-SMWはIPAの立ち上げたプロジェクトで開発したプログラムで、開発者の杉田（Sugita）、光成（Mitsunari）、渡辺（Watanabe）の頭文字をとって名づけました。

★ストリーム暗号「Toyocrypt」の解読をめぐるこれまでの状況：現実に計算機を利用して解読した例は皆無

　Toyocryptとは、2000年に実質上永久に解けないストリーム暗号としてCRYPTREC(総務省および経産省の共同運営による暗号技術評価プロジェクト)※9が公募した電子政府推奨暗号に東洋通信機株式会社から提案された暗号アルゴリズムです。電子政府推奨暗号としては選抜されなかったものの、本アルゴリズムは、近年、欧米亜の暗号研究者が参加する暗号に係る国際学術会議で、安全性についての多数の研究結果の発表がなされており、理論的に解読可能であることが示されています。
　その解読時間は、2002年にCRYPTRECに報告されている攻撃手法を用いた場合、IPAが所有するグリッドコンピュータを用いて実装すると想定したとしても、100億年かかる( Toyocrypt の1ビット処理を1とした場合の計算量：296 )と見積もることが出来ますが、近年新たに提案された代数的性質を利用した攻撃手法を用いることにより、その解読時間を大幅に短縮することが可能であることが示されています。
しかし、解読のためのプログラム作成には高度なプログラミング能力とそれを実装できる十分な環境が必要であり、これまで現実にコンピュータを利用した解読に成功した例は皆無でした。

★Toyocryptを極めて短時間で解読

　IPAでは、2005年上期にIPA-SMWの更なる高速化および並列最適化を行い、プログラム処理の処理時間の短縮化を行った上で、Toyocryptの解読に適用し、Toyocryptの鍵探索プログラムを実装し、解読を試みた結果、極めて短時間で解読可能であることを実証しました。

(結果)　27分で解読に成功

221 ビットの平文と暗号文の対から、暗号化に用いられた鍵(128ビット)の算出に成功

★今後の活動方針は

　今後は、本プロジェクトにより開発したグレブナー基底探索プログラム（IPA-SMW）を、他の暗号アルゴリズムにも適用し、電子政府推奨暗号等の各種暗号アルゴリズムなどの安全性評価を行っていく予定です。

[用語集]

  • ※1 ストリーム暗号

    平文を 1 ビット、または数ビットごとに暗号化・復号を行う方法。そのアルゴリズムは、暗号鍵から鍵系列と呼ばれる擬似乱数を生成し、擬似乱数により平文を逐次暗号化していくものです。

  • ※2 Algebraic Attack （代数的攻撃)

    近年話題になった暗号の強力な解読法で、多次多変数の連立方程式を解くことにより鍵の推定をする方法。
    この方法は、ストリーム暗号や一部の公開鍵暗号に有効であるとされており、電子政府推奨暗号などの解読にも有効である可能性があるという報告さ近年発表されており、大きな話題となりました。

  • ※ 3 Bluetooth

    Ericsson 社、 IBM 社、 Intel Nokia社、東芝の 5 社が中心となって提唱している携帯情報機器向けの無線通信技術。 ノートパソコン や PDA 、 携帯電話 などでケーブルを使わずに接続し、音声やデータをやりとりすることができます。

  • ※4 IPA 認定スーパークリエータ

    IPA の未踏ソフトウェア創造事業において、個人または数名のグループを対象として、次世代の IT 市場創出を担う独創性と優れた能力を持つ研究者（スーパークリエーター）を積極的に発掘しています。渡辺秀行氏と光成滋生氏は 2003 年度のスーパークリエーターに選ばれました。

  • ※5 ユーテン・ネットワークス株式会社

    本社：〒152-0031 東京都目黒区中根 2丁目 20番 8号
    代表者：高島　研也
    設立： 2002 年 12 月
    資本金： 22,000 千円
    http://www.u10networks.com/index.html

  • ※6 株式会社アイビス

    本社：〒450-0002 名古屋市中村区名駅 3-18-11 新明ビル 4F
    代表者：神谷栄治
    設立： 2000/05/11 (平成12年)
    資本金： 1,850 万円
    http://www.ibis.ne.jp/index.html

  • ※7 グレブナー基底探索アルゴリズム

    多次多変数の連立方程式の解法であり、全ての連立方程式の解法が数学的に「グレブナー基底探索」に帰着されます。この探索の代表的なアルゴリズムとしてブッフベルガーアルゴリズム、 F4 アルゴリズム、 F5 アルゴリズムがあります。

  • ※8 暗号研究専用並列コンピュータ ( グリッドコンピュータ )

    IPA では、現在、世界最高レベルの性能を持つ暗号の研究専用の並列コンピュータを所有しており、このコンピュータの性能として、近年の 64 ビット CPU (2GHz) の高機能コンピュータの性能を1とした場合 128 倍 (128 台分の並列処理 ) の能力を持ちます。

  • ※9 CRYPTREC( Cryptography Research and Evaluation Committees)

    総務省および経済産業省が共同で開催している 暗号技術検討会 と、情報通信研究機構 (NICT) および情報処理推進機構 (IPA) が共同で開催する 暗号技術監視委員会 および 暗号モジュール委員会 によって構成される暗号技術評価プロジェクトです。

■本件に関するお問い合わせ先

独立行政法人 情報処理推進機構　セキュリティセンター・杉田／大久保
Tel:03-5978-7508 Fax:03-5978-7518 E-mail:電話番号:03-5978-7501までお問い合わせください。

■報道関係からのお問い合わせ先

独立行政法人 情報処理推進機構　戦略企画部広報グループ　高瀬／横山
Tel: 03-5978-7503 Fax:03-5978-7510 E-mail:電話番号:03-5978-7501までお問い合わせください。

ページトップへ