200 台の PS3 で 112 ビット楕円曲線暗号の解読に成功

mek 曰く、

暗号学者ヨッパ・W・ボス (Joppe W. Bos)、マルセロ・E・カイハラ (Marcelo E. Kaihara)、トルステン・クラインユング (Thorsten Kleinjung)、アリエン・K・レンストラ(Arjen K. Lenstra)、ピーター・L・モンゴメリ (Peter L. Montgomery) の発表によると、112 ビットの楕円曲線上の離散対数問題の解を求めることに成功、新記録を出したという (スイス連邦工科大学、暗号アルゴリズム研究室の発表記事、本家 /. 記事より) 。

前回の記録は 109 ビット暗号の解読で 2002 年 10 月にさかのぼる。今回のプロジェクトはスイス連邦工科大学ローザンヌ校 (EPFL) にある200 台を越える PS3 を利用して計算が行われた (前回、MD5 衝突攻撃による偽 SSL 証明書の作成に使われたものと同じ設定) 。PS3 上では、今回の問題を解くための計算量は 56 ビット DES のキーサーチを 14 回行うのに相当するものだ。

How long did it take?

[suntear (11933)]

The calculation was started on January 13, 2009, and finished on July 8, 2009. It ran on and off, occasionally interrupted by other cryptanalytic projects such as this [win.tue.nl] or this or PlayLaB [documents.epfl.ch] visits as described here [documents.epfl.ch] (in French), on a cluster of more than 200 PlayStation 3 (PS3) game consoles. When run continuously using the latest version of our code, the same calculation would have taken 3.5 months.

今年の 1/13 から始めて 7/8 に終わったようです。途中、別のプロジェクト [win.tue.nl]やこんな行事 [documents.epfl.ch]によって中断があったそうで、最新のコードで続けて計算すれば 3.5 ヶ月ぐらいかかるでしょうとのこと。

Re:

[suntear (11933)]

最新のコードで続けて計算すれば 3.5 ヶ月ぐらいかかるでしょうとのこと。

「最新のコード続けて計算していたなら 3.5 ヶ月かかったでしょう」かな。

Re:

[Anonymous Coward]

いや

「最新のコードに変えて連続計算していたなら 3.5 ヶ月かかったでしょう」だよたぶん。

Re:

[Anonymous Coward]

MD5のと別のPS3じゃなかったのかorz

by クタラン

ということは、

[MISSION (13232)]

　112bitの楕円曲線暗号の強度は(56bitDES暗号14回 nearly equal 56bitDES暗号2^4回ってことで)、60bitのDES暗号程度と考えて良いと言うことでしょうか？

--
ここは自由の殿堂だ。床につばを吐こうが猫を海賊呼ばわりしようが自由だ。- A.バートラム・チャンドラー 銀河辺境シリーズより

Re:ということは、

[kokorohamoe (38645)]

この場合の56bitって56桁という意味であって、2^nを意味していないはずだから、54桁ｘ14回=756bitと考える方がまだ近似するんじゃないでしょうか？

Re:ということは、

[MISSION (13232)]

　なるほど、ってことは桁数(この場合は＝データ量)を(56->112と)倍にしたことで試行回数が14回増える。このことによる強度の違いを考えればよいって事ですね。
　でも暗号化方式の違いがあるとはいえ、56桁(この場合2^56)分組み合わせが増えたのに、解読に必要な試行回数が14回しか増えないので、楕円曲線暗号はDESに比べるとあまり強くないって事になるような？　まだどっか勘違いしている？

--
ここは自由の殿堂だ。床につばを吐こうが猫を海賊呼ばわりしようが自由だ。- A.バートラム・チャンドラー 銀河辺境シリーズより

ぬー

[a-yasui (30289)]

別にどのデバイスを使って解読したというより、解読にどれだけの時間がかかったという方が重要だと思うのだが、たれ込みには書いてなかったのかなぁ・・・

# 英語苦手だからあれだけど、2009年1月13日〜2009年7月8日、実質半年と半月ぐらいかかったという事かしら。これが暗号解読では早いのか遅いのかわからんが。

Re:

[Anonymous Coward]

半年は早いと言わざるを得ない

ふーん

[Anonymous Coward]

全数探索で解けたからって、ふーん何がすごいの？って印象しかない。
単にやってみました。できました。だけの話題でしょ。
そもそもこの手の研究って技術力とか必要なの？資金は必要だろうけど。

安全面で考えたら鍵長を長くすればいいだけなんだし、
暗号自体を破ったような騒ぎ方も止めてほしいな

Re:ふーん

[kieru_haim (37792)]

今の私には出来ないから、それなりの技術(知識)は必要だと思う
それでも「お金と時間を掛けて出来ました」っという話だというのにも一理ある。
ただ、これが
一般人が何も苦もなく解読出来るようになったら、
破られたって事でいいんじゃない？
ここでいう破られたというのは、暗号として使いもものに
ならなくなったという意味。

Re:

[Anonymous Coward]

たとえ総当たりでも解読のための機械が早くなったり、大量の機械を用意したりして
十分に短い時間でカギにたどり着いたら破られたことになると思います。

Re:

[Anonymous Coward]

全くもって見当はずれな指摘だね。
破られたということ自体に異を唱えたつもりはないんだが。

資金力でごり押ししただけでしかない研究にどれほどの価値を見出せるのかという主張だよ。

Re:

[Anonymous Coward]

まず並列コンピューティングや効率的な解読の実装には技術が必要です。

「実際にごり押しでできた」ということの重要性がわかんないですか？たしかに鍵長を長くすれば強度は上がりますが、実装や運用を考えればむやみやたらと長くできるわけではないですね。どこでトレードオフを取るばいいかという実証になりますね。

むむ

[Anonymous Coward]

暗号解読が終えたら破られなさそうな暗号の試験とかに…。

Re:

[Anonymous Coward]

学術分野での貢献度は高いな。

osusume

[Anonymous Coward]

＞おすすめ
PS3が売れるためには、どんなソフトを出せば良いか･･･という市場分析でもするとか

DESキーサーチ14回分？

[Anonymous Coward]

本当に分からないから教えてくれ。
「56bitDESなんてすぐ破られるから使うなヴォケ」と言われてるが、それの14回分なんてやっぱりすぐじゃないのか？
たいしたことない印象だぞ？

原文は"14 full 56-bit DES key searches"だけど、
これってTripleDESのような、ただし3重を14重にしたものなんじゃないの？
それなら確かに計算量は多そうなんだけど。

素人の印象からの素朴な質問だよ。茶々じゃないから。念のため。

Re:DESキーサーチ14回分？

[nekopon (1483)]

確認したわけではないのですが、その直前には "approximately 10¹⁸ modular additions and multiplications on 112-bit integers" とあるので、56bit DESの全数探索 (2⁵⁶のキーを全部試してみる) 14回分で大体合う気がしますが如何。

Re:

[Anonymous Coward]

楕円曲線暗号については、米国のNISTでアルゴリズムと処理方法について公開されていたと思います。

RSA1024ビット暗号系に対し、感覚では約300ビット前後の楕円曲線暗号が同等な暗号強度をもっていたような。。。？
もともとDES等のブロック暗号と、離散対数暗号を比較するのは？？という感覚ですが、
どうでしょう、専門家のみなさん。

わたしは専門ではありませんので、AC。

あのー

[Anonymous Coward]

誰か馬鹿な私にもわかるように説明して下さい。

Re:

[Anonymous Coward]

PS3を200台位買う経済力と3.5ヶ月待てる根気があれば3.5ヵ月後には解読される危険性があるので、4ヶ月とか半年以上秘密にしたいなら使わないようにしようといった話です。

Re:

[Anonymous Coward]

つまり、PS3が2万台あれば1日ちょい、ってことですね。

この手のストーリーでいつも思う

[Anonymous Coward]

10年前に傍受した暗号通信とか、傍受データが残ってたら面白いのに。
今なら簡単に読解できるでしょ。
データ持ってる人がいたとしても、おおっぴらにはやらないか。

Re:この手のストーリーでいつも思う

[naruenosekai (13637)]

これから作って、公開してみるんだ。
だれかが数年後に解いてくれるかも。

この暗号を作ったのは誰だあっ！！

[Anonymous Coward]

マルセロ・E・カイハラ (Marcelo E. Kaihara)