パスワードを忘れた? アカウント作成
10904 story

IPA、ストリーム暗号Toyocryptの解読に成功 43

ストーリー by Acanthopanax
矛と盾 部門より

maia 曰く、 "IPA(情報処理推進機構)が26日、ストリーム暗号Toyocryptの解読に成功したと発表した(プレスリリースCNET記事)。2000年に東洋通信機が開発したToyocryptは解読するのに100億年かかるといわれたが、2002年頃から代数的攻撃法による解読可能性が指摘され、2004年からIPAでは「IPA-SMW」というプログラムを開発し、解読に挑戦してきた。221の平文と暗号文の対から、暗号化に用いられた128ビット鍵の算出に成功し、20日には27分で解読に成功したが、26日には20秒台まで達しているという(解読に用いたグリッドコンピュータは2GHzのCPU128個で構成されている)。今後、Bluetoothに用いられているストリーム暗号や、電子政府推奨暗号AESに対しても、IPA- SMWで解読できるかどうか検証していく。"

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 光成氏って (スコア:5, 興味深い)

    by Anonymous Coward on 2005年09月27日 6時08分 (#805067)
    午後のこ~だの人ですね。約80倍の高速化はこの辺のパワーか(ぉ

    仮にAESが破られてしまうと多方面への影響は避けられませんね。MacOS X等の暗号化FSとかもAESだし。
    • by Anonymous Coward
      平文と暗号文が手に入らないといけないから、ただちに脅威ってことないかなぁ。

      AESやぶったらぜひPSP(ry
  • by RX-178 (2626) on 2005年09月27日 10時11分 (#805130)
    元の(解読に用いたグリッドコンピュータは2GHzのCPU128個で構成されている)
    の部分はどこかに出ていたのでしょうか。
    プレスリリースには
    >※ 8 暗号研究専用並列コンピュータ ( グリッドコンピュータ )
    >IPA では、現在、世界最高レベルの性能を持つ暗号の研究専用の並列
    >コンピュータを所有しており、このコンピュータの性能として、近年
    >の 64 ビット CPU (2GHz)の高機能コンピュータの性能を 1 と
    >した場合 128 倍 (128 台分の並列処理 ) の能力を持ちます。
    とありますが、これは能力比較であって2GHzを128個ではないですよね
    • C NET Japan の記事では

      | プロジェクトでは暗号解読のための「IPA-SMW」というプログラ
      | ムを開発し、IPAが運用する暗号研究専用のグリッドコンピュー
      | タに実装し、Toyocryptの解読に挑戦してきた。なお、暗号解読
      | に用いたグリッドコンピュータは、周波数2GHzのCPU128個で構
      | 成されている。

      となっている。
      • なんか、CNet Japanの方が間違っている予感...。
      • impressでは

        >今回の暗号解読では、IPAの所有するCPU(Opteron 2GHz)128個のグリッドコンピュータ上でIPA-SMWを実装し、2の21乗個の暗号文と平文の組み合わせから解読させたところ、

        http://internet.watch.impress.co.jp/cda/news/2005/09/26/9245.html

        という記事がでていますね。
  • 暗号解読って、trivial independent な問題なんですか?
    だから並列化しまくれるって言うことかな?
    --
    屍体メモ [windy.cx]
  • 「誰でもグリッドが容易に使える時代」

    というのは

    「誰でもプログラムさえあれば暗号が容易に解けるようになる時代」

    ってことになりますな。
    犯罪者にとっても、普通の人にとっても。

    これを「グリッドの普及による暗号クライシス」と呼ばずしてなんと言おうか?
    • Re:ということは、だよ (スコア:2, すばらしい洞察)

      by Vorspiel (2391) on 2005年09月27日 20時20分 (#805425) ホームページ
      例えば,1人の使える計算機リソースが「たかだか」100万(≒2^20)倍になったところで,強い(brute-forceでしか破れないような)アルゴリズムにはぜーんぜん影響ないかと.
      #鍵長を20bit伸ばせば同じ強度
      親コメント
      • by Vorspiel (2391) on 2005年09月27日 20時38分 (#805441) ホームページ
        ついでだからこんなページ [burtleburtle.net]を見つけてみました.
        面白そうなところだと:
        • 2^129: 1立方メートルにぎっしりナノコンピュータ(直径10^-8m)を詰め込んで作ったマシンのinstruction per second
        • 2^268: 上記のサイズのナノコンピュータを太陽のサイズに詰め込んだマシンのinstruction per 100万年
        結論: 計算量が2^256のオーダーならbrute-forceじゃまず永久に解けないから安心すれ.
        親コメント
        • by Anonymous Coward
          遠い未来を考えるのであれば、量子コンピューターが実用化されて「重ねあわせ」による並列演算が使えるようになった時代に一瞬で今までの暗号は解読されると思うのですが、どうなんでしょうか。
           まあ、我々が生きている間に量子コンピューターが実用化されることはないと思いますが。
          • 量子コンピュータ・量子暗号についてはあんまり詳しくないですが、
            >量子コンピューターが実用化されて「重ねあわせ」による並列演算が使えるようになった時代に一瞬で今までの暗号は解読されると思うのですが
            というのは私の知る限りでは真だったと思います。
            #現在の計算量的安全性に頼った暗号はすべからくアウトなんでしたっけ?
            で、それに対抗するには量子力学的に安全な量子暗号を使うしかない、ってことだった…よね?
            親コメント
            • by Anonymous Coward
              >#現在の計算量的安全性に頼った暗号はすべからくアウトなんでしたっけ?

              その「すべからく」は誤用です。はてなダイアリー - すべからくとは [hatena.ne.jp]

              #「暗号は須らくアウトになるべし」?
            • by Anonymous Coward
              >>量子コンピューターが実用化されて「重ねあわせ」による並列演算が使えるようになった時代に一瞬で今までの暗号は解読されると思うのですが
              >というのは私の知る限りでは真だったと思います。

              それは流石に言いすぎです。
              # あなたが知っている暗号という限定ならいいんですけど
  • 20min. vs 20sec. (スコア:1, すばらしい洞察)

    by Anonymous Coward on 2005年09月27日 21時11分 (#805463)
    cnetの記事によれば [cnet.com]
    > 「9月26日現在、約20秒台で解読できるようになっている」という。

    @ITの記事によれば
    [atmarkit.co.jp]
    > 現在では20秒程度にまで解読速度が短縮されている。

    ITProの記事によれば
    [nikkeibp.co.jp]
    > 現在では20秒で解読できるという。]

    対して

    ITmediaの記事によれば
    [itmedia.co.jp]
    > 現在では20分程度にまで解読速度が短縮されている。

    どっちが正しいの?
    • by Anonymous Coward on 2005年09月28日 3時08分 (#805659)
      IPAのプレスリリース [ipa.go.jp]によると27分とは書いているが,
      20秒という記述はどこにもないから,20分程度というのが有力.

      因みに,それぞれの記事にはこうも書いてある.

      cnetの記事によれば [cnet.com]
      > 9月20日にToyocryptを27分間で解読することに成功した。

      @ITの記事によれば [atmarkit.co.jp]
      > 27分で算出することに成功。

      ITProの記事によれば [nikkeibp.co.jp]
      > 27分で解読した。

      ITmediaの記事によれば [itmedia.co.jp]
      > 27分で算出することに成功。


      可能性としては,
      1. 20日には27分かかったものが,26日には20秒台になった.
      2. 杉田誠氏がインタビューでうっかり20秒と言ってしまった.
      3. 同氏のインタビューで記者が20分を20秒と(聞き|書き)間違えた.
      1はほとんど有り得ないだろうから,2か3だろうな. てか,単純に2じゃないかと.
      親コメント
  • by hidemaro (28645) on 2005年09月28日 1時36分 (#805634) 日記
    今秋の情試は暗号化について重点的に勉強すれば受かりますか・・・?

    --
    ---- I don't Know What You Say !!
          (意味わかんねぇ!!)
  • by Anonymous Coward on 2005年09月27日 6時43分 (#805072)
    221? 2^21? どっち?
    暗号には詳しくないのですが、2^21も実例があるからこそ秘密鍵が推測できるって事ですかね?

    参考:@ITの記事 [atmarkit.co.jp]
  • by Anonymous Coward on 2005年09月27日 7時32分 (#805078)
    でもIPAとしては暗号技術をつぶしていくことにどういう意味があるの?
    • Re:すごい! (スコア:3, すばらしい洞察)

      by kusigahama (7719) on 2005年09月27日 13時23分 (#805236) ホームページ 日記
      安全でない暗号を、安全だと思い込んで使い続けるのは危険だから、ですね。
      解読したのが悪意ある人だった場合を考えてみてください。
      親コメント
    • Re:すごい! (スコア:2, すばらしい洞察)

      by Anonymous Coward on 2005年09月27日 7時34分 (#805079)
      雑な暗号(と呼ばれる類似品)は潰すほうが安全な世界に近づけます。

      生き残ったものだけがあればいい。
      親コメント
      • 生き残ったものが極端に少ない場合,それが破られたときのリスクが高いと思います.

        一概に安全になるとは言えないんじゃないかなぁ.
        --
        旅に出ます.(バグを)探さないで下さい.
        親コメント
        • Re:すごい! (スコア:2, すばらしい洞察)

          by Anonymous Coward on 2005年09月27日 11時37分 (#805172)
          たとえ生き残りが全滅してしまったとしても、
          危険なものを安全であると信じてる状態よりは、
          ましだと思います。

          まあ、そんな状況が起こったら、暗号研究者たちにとっては
          極めて恥ずかしい状況でしょうが。

          親コメント
          • Re:すごい! (スコア:2, すばらしい洞察)

            by Anonymous Coward on 2005年09月27日 15時09分 (#805272)
            > まあ、そんな状況が起こったら、暗号研究者たちにとっては
            > 極めて恥ずかしい状況でしょうが。

            いや、そんな状況がおこったら、多くの計算が効率的にできるってことに
            なるから、今の大方の予想 P \neq NP を覆すような極めてワクワクな
            状況だと思います。暗号研究者の恥じどころか、世の中ひっくりかえす
            大革命の口火を切ったってことで、永く尊敬されると思う。
            親コメント
      • >雑な暗号(と呼ばれる類似品)は潰すほうが安全な世界に近づけます。
        全く以って真なのですが「ハードウェアで暗号化よって高速」
        な製品は破られるたんびに買い換えるような時代が来るんです
        かね。
        それともせっかく買ったの
        • >全く以って真なのですが「ハードウェアで暗号化よって高速」
          >な製品は破られるたんびに買い換えるような時代が来るんです
          >かね。
          再プログラム可能素子で暗号化素子を組めばよいのではなかろうか。
          速度が出ないかな。
          • 通信機器の内部ではFPGAによって作られる回路は多々あります。
            そう言った箇所で使われるFPGAの多くは外部からMPUを用いて
            (ファームウェアのように)書き換えることが可能であり、
            また実際にFPGAで動いている機器が多いわけですから、速度が
            ネックになることは少ないと思われます。
            (ネックになるくらいならベンダーは採用していません)
    • Re:すごい! (スコア:2, 興味深い)

      by Anonymous Coward on 2005年09月27日 8時24分 (#805091)
      暗号技術と暗号解読技術は表裏一体です。
      優れた暗号解読技術なしには良い暗号は作れません。

      #暗号を作ったときは、自らその破り方も考えておくものなのだ。
      親コメント
    • Re:すごい! (スコア:2, 参考になる)

      by Anonymous Coward on 2005年09月27日 9時00分 (#805102)
      http://h2np.net/docs/crypto2004.html

      特にToyocryptは、簡単に解読できるので「新しい解読法では、以前よりこれだけ改善された」という、とても判りやすい改良指標として使われているようです。
      親コメント
      • by Vorspiel (2391) on 2005年09月27日 9時20分 (#805111) ホームページ
        3年間で計算量が2^96→2^29→2^21(&計算機で実証)てのはすごいですなー.
        AESにも適用してみるって話ですが(理論的には弱点がどのぐらい見つかってるんでしょうか?),万が一現実的な時間で破れることが分かったりしたら一大事だなぁ.
        親コメント
        • by Anonymous Coward
          CPUパワーが余って困っていたんですよ
          これからは暗号と複合に力を割り振りましょうってことで
          • by Vorspiel (2391) on 2005年09月27日 10時42分 (#805148) ホームページ
            計算量(not処理時間)の激減は暗号解析理論の進化によるものであってCPUパワーの話とは別でしょ?
            それとも,CPUパワーが増大してるんだからもっと(鍵長が長くて|アルゴリズムが複雑で)計算に時間が掛かる代わりに安全な暗号を使おうよ,って話?
            親コメント
        • by Anonymous Coward
          現実的にはラウンド数や鍵長を減らしたAESのサブセットを解読してみる事になるでしょう。 フルセットのAESには歯が立ちませんから。
      • by Anonymous Coward
        http://h2np.net/docs/crypto2003.html

        この論文の爼上にあげられたのはE0 (Bluetooth の仕様に入っている)、LILI-128、Toyocryptでした。この3 つの安全性の低さは、どれもドングリの背比べで、はっきりいってぜんぜんダメです。

    • by clubx (27914) on 2005年09月27日 7時48分 (#805084)
      商品テスト
      親コメント
  • by Anonymous Coward on 2005年09月27日 11時02分 (#805156)
    ストリーム暗号「Toyocrypt」の解読をめぐるこれまでの状況:現実に計算機を利用して解読した例は皆無...

    なんかイタイなぁ、このプレスリリース

    • by Anonymous Coward on 2005年09月27日 15時58分 (#805284)
      確かに微妙にイタイなあ。「世界最高レベル」って、カカクメソッド?(w
      表現がちょっとトンデモ系っぽい。添削してみる。
      「Toyocrypt」は、2000年当時、実質的に永遠に解けない暗号として電子政府推奨暗号候補として提案されましたが採択にいたらなかったものです。
      「Toyocrypt」は、2000年に「実質的に永遠に解けない」と主張 して電子政府推奨暗号の公募に提案された暗号で、○○との理由で推奨暗号には採択されなかったものですが、
      近年、欧米亜の暗号に係る国際学術会議において、世界的な研究者間でこの暗号の解読可能性がひとつの主要な論点となっていました。
      暗号学研究の国際学術会議において、Toyocryptの効率的な解読手法の追求がひとつの主要な研究トピックとなっています。
      新たに代数的攻撃手法を適用することで理論的に解読可能との研究結果が発表されるなど注目を浴びていますが、解読には高度なプログラミング能力と高速のコンピュータが必要なため、計算機を利用して実際に解読した実証例は皆無でした。
      近年、新たに代数的攻撃手法を適用することでより効率的な解読が可能であるとの理論的研究が発表されているところですが、実際に解読した実証例はありませんでした。
      IPAは、代数的攻撃手法に対する暗号の安全性評価手法を確立するために、IPAが認定したスーパークリエータらを起用し、暗号解読プロジェクトを立ち上げました。
      IPAは、代数的攻撃手法による実質的な攻撃容易性を評価するため、解読プログラムの開発にIPAが認定したスーパークリエータらを起用し、高速暗号解読プロジェクトを立ち上げました。
      プロジェクトの活動の一環として、代数的攻撃に用いる、多次多変数連立方程式の解法 (グレブナー基底探索アルゴリズム)によるプログラム(「IPA-SMW」)を開発しました。これを、IPAが所有する暗号研究専用として使用する世界最高レベルの並列コンピュータ(グリッドコンピュータ)上で高速化および最適化を行った上で、Toyocryptの解読に適用し、世界で初めて、27分間という極めて短い時間での解読に成功しました。
      プロジェクトの活動の一環として、代数的攻撃に用いる、多次多変数連立方程式の解法 (グレブナー基底探索アルゴリズム)によるプログラム(「IPA-SMW」)を開発しました。これを、IPAが所有する暗号研究専用としては世界最高レベルの演算性能を誇る並列コンピュータ(クラスタコンピュータ)上で、プログラムの高速化および最適化を行った上で、Toyocryptの解読に適用し、世界で初めて、27分間という極めて短い時間での解読に成功しました。
      今後は、このIPA-SMWを用いて、継続的に電子政府推奨暗号等の安全性評価を行っていく予定です。
      今後は、このIPA-SMWを用いて、継続的に電子政府推奨暗号等の安全性評価を行っていく計画です。
      親コメント
    • *実証例*の部分を抜かしてますが。意図的?
  • by Anonymous Coward on 2005年09月29日 7時12分 (#806072)
    Toy Of Cryptを縮めたものだったのか!
typodupeerror

物事のやり方は一つではない -- Perlな人

読み込み中...