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, 興味深い)
仮にAESが破られてしまうと多方面への影響は避けられませんね。MacOS X等の暗号化FSとかもAESだし。
Re:光成氏って (スコア:0)
AESやぶったらぜひPSP(ry
グリッドコンピューター (スコア:2, すばらしい洞察)
の部分はどこかに出ていたのでしょうか。
プレスリリースには
>※ 8 暗号研究専用並列コンピュータ ( グリッドコンピュータ )
>IPA では、現在、世界最高レベルの性能を持つ暗号の研究専用の並列
>コンピュータを所有しており、このコンピュータの性能として、近年
>の 64 ビット CPU (2GHz)の高機能コンピュータの性能を 1 と
>した場合 128 倍 (128 台分の並列処理 ) の能力を持ちます。
とありますが、これは能力比較であって2GHzを128個ではないですよね
Re:グリッドコンピューター (スコア:0)
| プロジェクトでは暗号解読のための「IPA-SMW」というプログラ
| ムを開発し、IPAが運用する暗号研究専用のグリッドコンピュー
| タに実装し、Toyocryptの解読に挑戦してきた。なお、暗号解読
| に用いたグリッドコンピュータは、周波数2GHzのCPU128個で構
| 成されている。
となっている。
Re:グリッドコンピューター (スコア:0)
Re:グリッドコンピューター (スコア:0)
って日本独自記事か
Re:グリッドコンピューター (スコア:0)
>今回の暗号解読では、IPAの所有するCPU(Opteron 2GHz)128個のグリッドコンピュータ上でIPA-SMWを実装し、2の21乗個の暗号文と平文の組み合わせから解読させたところ、
http://internet.watch.impress.co.jp/cda/news/2005/09/26/9245.html
という記事がでていますね。
trivial independent ? (スコア:1)
だから並列化しまくれるって言うことかな?
屍体メモ [windy.cx]
Re:trivial independent ? (スコア:0)
ということは、だよ (スコア:1)
というのは
「誰でもプログラムさえあれば暗号が容易に解けるようになる時代」
ってことになりますな。
犯罪者にとっても、普通の人にとっても。
これを「グリッドの普及による暗号クライシス」と呼ばずしてなんと言おうか?
Re:ということは、だよ (スコア:2, すばらしい洞察)
#鍵長を20bit伸ばせば同じ強度
2^nのデカさ (スコア:1)
面白そうなところだと:
Re:2^nのデカさ (スコア:0)
まあ、我々が生きている間に量子コンピューターが実用化されることはないと思いますが。
Re:2^nのデカさ (スコア:1)
>量子コンピューターが実用化されて「重ねあわせ」による並列演算が使えるようになった時代に一瞬で今までの暗号は解読されると思うのですが
というのは私の知る限りでは真だったと思います。
#現在の計算量的安全性に頼った暗号はすべからくアウトなんでしたっけ?
で、それに対抗するには量子力学的に安全な量子暗号を使うしかない、ってことだった…よね?
Re:2^nのデカさ (スコア:0)
その「すべからく」は誤用です。はてなダイアリー - すべからくとは [hatena.ne.jp]
#「暗号は須らくアウトになるべし」?
Re:2^nのデカさ (スコア:0)
>というのは私の知る限りでは真だったと思います。
それは流石に言いすぎです。
# あなたが知っている暗号という限定ならいいんですけど
20min. vs 20sec. (スコア:1, すばらしい洞察)
> 「9月26日現在、約20秒台で解読できるようになっている」という。
@ITの記事によれば [atmarkit.co.jp]
> 現在では20秒程度にまで解読速度が短縮されている。
ITProの記事によれば [nikkeibp.co.jp]
> 現在では20秒で解読できるという。]
対して
ITmediaの記事によれば [itmedia.co.jp]
> 現在では20分程度にまで解読速度が短縮されている。
どっちが正しいの?
Re:20min. vs 20sec. (スコア:1, 興味深い)
20秒という記述はどこにもないから,20分程度というのが有力.
因みに,それぞれの記事にはこうも書いてある.
cnetの記事によれば [cnet.com]
> 9月20日にToyocryptを27分間で解読することに成功した。
@ITの記事によれば [atmarkit.co.jp]
> 27分で算出することに成功。
ITProの記事によれば [nikkeibp.co.jp]
> 27分で解読した。
ITmediaの記事によれば [itmedia.co.jp]
> 27分で算出することに成功。
可能性としては,
Re:20min. vs 20sec. (スコア:1, 興味深い)
IPA (スコア:1)
---- I don't Know What You Say !!
(意味わかんねぇ!!)
平文と暗号文の対の数 (スコア:0)
暗号には詳しくないのですが、2^21も実例があるからこそ秘密鍵が推測できるって事ですかね?
参考:@ITの記事 [atmarkit.co.jp]
Re:平文と暗号文の対の数 (スコア:1)
2^21ということで、本文を訂正しました。
すごい! (スコア:0)
Re:すごい! (スコア:3, すばらしい洞察)
解読したのが悪意ある人だった場合を考えてみてください。
Re:すごい! (スコア:2, すばらしい洞察)
生き残ったものだけがあればいい。
Re:すごい! (スコア:1)
一概に安全になるとは言えないんじゃないかなぁ.
旅に出ます.(バグを)探さないで下さい.
Re:すごい! (スコア:2, すばらしい洞察)
危険なものを安全であると信じてる状態よりは、
ましだと思います。
まあ、そんな状況が起こったら、暗号研究者たちにとっては
極めて恥ずかしい状況でしょうが。
Re:すごい! (スコア:2, すばらしい洞察)
> 極めて恥ずかしい状況でしょうが。
いや、そんな状況がおこったら、多くの計算が効率的にできるってことに
なるから、今の大方の予想 P \neq NP を覆すような極めてワクワクな
状況だと思います。暗号研究者の恥じどころか、世の中ひっくりかえす
大革命の口火を切ったってことで、永く尊敬されると思う。
ハードウェアで暗号化 (スコア:0)
全く以って真なのですが「ハードウェアで暗号化よって高速」
な製品は破られるたんびに買い換えるような時代が来るんです
かね。
それともせっかく買ったの
Re:ハードウェアで暗号化 (スコア:0)
>な製品は破られるたんびに買い換えるような時代が来るんです
>かね。
再プログラム可能素子で暗号化素子を組めばよいのではなかろうか。
速度が出ないかな。
Re:ハードウェアで暗号化 (スコア:0)
そう言った箇所で使われるFPGAの多くは外部からMPUを用いて
(ファームウェアのように)書き換えることが可能であり、
また実際にFPGAで動いている機器が多いわけですから、速度が
ネックになることは少ないと思われます。
(ネックになるくらいならベンダーは採用していません)
Re:すごい! (スコア:2, 興味深い)
優れた暗号解読技術なしには良い暗号は作れません。
#暗号を作ったときは、自らその破り方も考えておくものなのだ。
Re:すごい! (スコア:2, 参考になる)
特にToyocryptは、簡単に解読できるので「新しい解読法では、以前よりこれだけ改善された」という、とても判りやすい改良指標として使われているようです。
Re:すごい! (スコア:1)
AESにも適用してみるって話ですが(理論的には弱点がどのぐらい見つかってるんでしょうか?),万が一現実的な時間で破れることが分かったりしたら一大事だなぁ.
Re:すごい! (スコア:0)
これからは暗号と複合に力を割り振りましょうってことで
Re:すごい! (スコア:1)
それとも,CPUパワーが増大してるんだからもっと(鍵長が長くて|アルゴリズムが複雑で)計算に時間が掛かる代わりに安全な暗号を使おうよ,って話?
Re:すごい! (スコア:0)
Re:すごい! (スコア:0)
この論文の爼上にあげられたのはE0 (Bluetooth の仕様に入っている)、LILI-128、Toyocryptでした。この3 つの安全性の低さは、どれもドングリの背比べで、はっきりいってぜんぜんダメです。
Re:すごい! (スコア:1)
IPAのプレスリリースによると... (スコア:0)
なんかイタイなぁ、このプレスリリース
Re:IPAのプレスリリースによると... (スコア:4, 興味深い)
表現がちょっとトンデモ系っぽい。添削してみる。 「Toyocrypt」は、2000年に「実質的に永遠に解けない」と主張 して電子政府推奨暗号の公募に提案された暗号で、○○との理由で推奨暗号には採択されなかったものですが、 暗号学研究の国際学術会議において、Toyocryptの効率的な解読手法の追求がひとつの主要な研究トピックとなっています。 近年、新たに代数的攻撃手法を適用することでより効率的な解読が可能であるとの理論的研究が発表されているところですが、実際に解読した実証例はありませんでした。 IPAは、代数的攻撃手法による実質的な攻撃容易性を評価するため、解読プログラムの開発にIPAが認定したスーパークリエータらを起用し、高速暗号解読プロジェクトを立ち上げました。 プロジェクトの活動の一環として、代数的攻撃に用いる、多次多変数連立方程式の解法 (グレブナー基底探索アルゴリズム)によるプログラム(「IPA-SMW」)を開発しました。これを、IPAが所有する暗号研究専用としては世界最高レベルの演算性能を誇る並列コンピュータ(クラスタコンピュータ)上で、プログラムの高速化および最適化を行った上で、Toyocryptの解読に適用し、世界で初めて、27分間という極めて短い時間での解読に成功しました。 今後は、このIPA-SMWを用いて、継続的に電子政府推奨暗号等の安全性評価を行っていく計画です。
Re:IPAのプレスリリースによると... (スコア:0)
Toyocryptとは (スコア:0)