フルバージョンのSHA-1にコリジョン発見 49
ストーリー by yoosee
安全なものを選ぼう 部門より
安全なものを選ぼう 部門より
Anonymous Coward曰く、"ブルース シュナイアー氏のblogによれば、RSA ConferenceでSHA-1のコリジョンが発表されたようです。
前回の話と違い、「SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.」とフルバージョンのSHA-1であることが強調されてます。
blogによると、フルバージョンのSHA-1では2^69のハッシュ操作、58ラウンドに減らしたSHA-1ならば2^33の操作でコリジョンが起こり、これは総当りの場合の2^80よりもとても小さいとあります。
CRYPTRECでは、ハッシュ関数は256bit以上を使用するよう推奨されていますので、これにより移行がいっそう進むことにでしょう。
ただ、PGP/GnuPGではSHA-256以降がつかえないバージョンも存在するので、脆弱性の報告されていないRIPEMD160に移行するのが現実的かもしれません。（ただしRIPEMD160もSHA-1と同じMD4ベースですが）"
2^11 (スコア:3, 参考になる)
# もちろん、すぐにエンドユーザがどうこうなるわけはありませんが…
フルバージョンでのコリジョン検出が2^11=2048倍早くなった、ということで、
ピンと来ませんが、例えば34時間かかる作業が1分で済むようになった、と考えるとまぁすごいのでしょうか。
悪い例え方ですが。
Reduced SHA-1の2^33は結構マズいのでは？
(ちなみにCRC32(もちろん2^32)の総当り [mizna.jp]は簡単でした。(宣伝？))
SHA-1とMD5を同時に使えば当分大丈夫かとは思いますが。
# SHA-1 [nist.gov]、誕生から10年経ってますけど、もったほうなのでは？
"Stupid risks are what make life worth living!" -- Homer Simpson
Re:2^11 (スコア:2, おもしろおかしい)
信頼性が必要な場所には、日本のACCSという機関が発明して
なんと特許申請が行われなかったオープンなノーガード式を
組み合わせるのが大事でしょうね。
なるほど、押し売りお断りシールを貼ってある家ほど押し売りに
弱いと言いますからね。
…それとこれとは話が違うって！
Re:2^11 (スコア:1)
>
>SHA-1とMD5を同時に使えば当分大丈夫かとは思いますが。
フル規格のSHA1は2^160で、コリジョンの確率が2^80だった気がする。
で、それが2^11縮まって、2^69になっただけでしょ。
強度が必要なところならば、フル規格使っているだろうし、将来を見越して強度が必要ならば、SHA256、SHA384、SHA512とか使えば良いだろうし。
フル規格で無い奴と比較しても仕方ないし、計算しての逆算の強度と総当りの強度を並べて比較しても意味無い気がする。
コリジョンの確率を上げる計算式があろうと、総当りでの当たる確率には影響しないのだし。
「当分大丈夫」って、1000年くらい漏らしてはならない外交文書の送信にでも使うのか？
1000年後に、1000年前の電子署名付き公文書として偽公文書を作られない強度を求めるの？
大丈夫か否かは、求める対象物に対する強度があれば良いんじゃないの？
仕事での取引記録とかでも10年や15年くらい経てばどんどん処分するだろうし、古い話の蒸し返しでも時効がある。
一般人にとってはどうでも良い様な違いでの強度差でしかないのでは？
Re:2^11 (スコア:0)
むしろ、ダメな宣伝？(笑)
とうとう来たかー (スコア:1, 興味深い)
一応そのときに、「このままだと近い将来うちの証明書発行サービスにも影響が出て来る、早いうちにそうなったときのことを検討すべきだ」と上の人には言いましたが、その後どうしたのかなあ。
# 昨年暮れにその職場から逃げだしたのでAC
Re:とうとう来たかー（オフトピ:-2^33) (スコア:0)
人間に置き換えると・・・
http://www.sanrio.co.jp/characters/charmmy/welcome.html
あちゃ～:-1 余計なもの (スコア:0)
Re:あちゃ～:-1 余計なもの (スコア:1, おもしろおかしい)
Re:あちゃ～:-1 余計なもの (スコア:0)
Re:あちゃ～:-1 余計なもの (スコア:1, 参考になる)
コリジョンとは何か、何故やばいのか、についてはこちら [uec.ac.jp]をどうぞ。
Re:あちゃ～:-1 余計なもの (スコア:0)
Re:あちゃ～:-1 余計なもの (スコア:0)
... (スコア:0)
Re:... (スコア:1, 参考になる)
今回のSHA-1はコンピュータ上のあるデータを要約して小さいデータ列に一方向変換することを目指したものですし、記事にあるような英数字を組み合わせた銀行ATM向け暗証番号は主に店頭ATMでの認証を前提にした仕組みです。
前者の場合はコンピュータ上で力ずくの解決を行なったりできてしまいますし、何よりもコンピュータそのものの進化が激しいので要約関数の精度もずっと高いものが求められます。
対して後者の場合はロックアウト（一定回数の入力ミスでそれ以降認証しなくなる）が用意されていますし、何よりも店頭のATMで手入力するものですからコンピュータより何千万倍も遅い認証試行になってしまいます。
（もちろんインターネット上での銀行アクセスの場合は、暗証番号そのものの堅牢性よりも盗聴される危険性を真っ先に考えなければなりませんので、それはそれで別の話になってしまいます）
全く目的の違うもの同士を一律に並べて比較するのはナンセンスだと思うのですが、どうお考えでしょうか？
もしかしてあなたのログインパスワードはドラクエ2の「ふっかつのじゅもん」のようにとてつもなく長いんでしょうか？
Re:... (スコア:0)
英数字にすりゃOKと考えているおめでたい人も居るけどどうよ
ってだけの話でしょ
次は、聞きかじった知識をひけらかす前に気付けると良いですね。
Re:... (スコア:0)
だから、きちんと周辺環境が用意されてる前提条件のある店頭ATMにおいては、数字4桁から英数字8桁に直すのも十二分に効果があるし意味を持つでしょ、って言いたいのだけど。
Re:... (スコア:0)
こういうこと書く人に返事すると舞い上がるのでやめておきましょう。
荒らしは無視の方向で。
Re:... (スコア:0)
え? 違う
Re:... (スコア:0)
って書いてあるけど、通帳はないんですかね？
Re:... (スコア:0)
# ハンコであったりとか、家族であること、代理であることの証明とか
もちろんそっちはそっちで、それなりのセキュリティを確保する必要があるわけだけども。
Re:... (スコア:0)
おふとぴ (スコア:0)
「ネット上では当たり前に使っている暗証方式」がなんで特許になるのかさっぱりわからん
まあ「とる」って言うだけならただだけど
SHA=Secure Hash Algorithm? (スコア:0)
Insecure Hash Algorithm。
Re:あわてる必要は無い (スコア:2, すばらしい洞察)
今日明日どうなる問題でもありませんが、
移行の準備を始めるべきです。
ある本家コメント [slashdot.org]によると
2^69 はまだ天文学的な計算量ですが、2^39 なら現実的だそうです。
(電子的に) 署名したこともないものを署名したことになっても、
ふつうの人なら今のところ損することはあまりないはずですが、
ほんとにヤバいことになってからでは遅いので、さっさと代替案を決めなくては。
Re:あわてる必要は無い (スコア:1)
なんだかたいしたことない数字に見えるかも。
暗算できるかも。
＃暗算したところでこれと言った意味は見出せないけれども。
----- 愚者の万能薬本舗
Re:あわてる必要は無い (スコア:2, 興味深い)
ちなみに1日は86400秒ですので、91626秒=1日と1時間27分6秒です。
SHA-1が10000回浮動小数点演算を行うとしても、約916260秒=10日と14時間31分。
これを非現実的と感じますか?
＃もちろん実際にはそんな単純な話では無いでしょうが。あくまで例として。
＃なお、6Gflopsという値は「倍精度」の場合で、単精度ならこの倍になるそうです。
Re:あわてる必要は無い (スコア:2, すばらしい洞察)
仮定が不自然なら、以降の計算はどんなに厳密でも無意味。
そもそも浮動小数点演算と整数演算と論理演算と、演算の質が違うと思うのですけれども。
1から1,000,000,000までの整数を全て足しなさい、と言われて
1秒で5,000,000,005,000,000,000と答えたら999MIPS？
という例はちょっと違うか……。
うーん。
Re:あわてる必要は無い (スコア:1)
計算の精度と言うなら、そもそもSHAのハッシュ関数の内容を知らない時点で論外です。
Re:あわてる必要は無い (お詫び) (スコア:1)
お詫びして訂正いたします。
Re:あわてる必要は無い (スコア:1, すばらしい洞察)
Re:あわてる必要は無い (スコア:1)
＃ただ、また勘違いがあるかも知れませんけど、普通は浮動小数点計算より整数の計算の方が速いでしょうから、
＃小数点演算でないのならさらに問題が大きくなるかも、とも思います。
Re:あわてる必要は無い (スコア:0)
Re:あわてる必要は無い (スコア:0)
浮動小数点演算が関係ないなんて言い切れないでしょ。そもそも
「ハッシュ関数は整数演算のみかならるもの」なんて定義はどこにも
ないわけだし。
「有名どころのハッシュ関数では、浮動小数点演算は使用されていない」
なら別にいいけど (ほんとかどうかは知らんが)。
Re:あわてる必要は無い (スコア:0, フレームのもと)
浮動小数点では実装によって答が違ってくるだろ。
そんなものハッシュ関数になるか。
ハッシュ関数の意味を勉強してから出直してこい。
Re:あわてる必要は無い (スコア:0)
IEEE の規格しらないの?
別に知らなくてもいいけど。
Re:あわてる必要は無い (スコア:1)
ピーク性能まんまで出るわけではないですよ。
計算やによるでしょうが、単純なループじゃないのに一桁下くらいの性能だったらかなりチューニングできてるほうじゃないでしょうか。
# 雑談サイトなんだから脱線しよう
Re:あわてる必要は無い (スコア:1)
というか、厳密な計算かという話であれば、そもそもSHAのハッシュ関数の内容を知らないあたりで既に問題外ですから(^-^;
＃要は本家の指摘にあったという「2^39は現実的」というのが、実際どの程度現実的なのか単純計算で試してみただけでして(^-^;;;
Re:あわてる必要は無い (スコア:1, すばらしい洞察)
Re:あわてる必要は無い (スコア:1)
ただ、#695090 [srad.jp]でも書きましたけど、厳密な計算かと言われると、そもそもSHAのハッシュ関数の内容を知らない時点で、既に論外です。
調べてもよく判らなかったので、目安のつもりで「10回100回ってことは無いだろうし、1000回くらいしてるだろうなぁ」程度の感覚で仮定しています。
そのあたりのことも書いておくべきでした。
Re:あわてる必要は無い (スコア:2, 参考になる)
> 1000回くらいしてるだろうなぁ」程度の感覚で仮定しています。
SHA-1の実装例はRFC3174で公開されていますのでそれを見れば判ると思います。
フルスペックのSHA-1は1ブロックあたりの処理で、撹拌のような処理を80回繰り返してます。
RFC3174でいうところのSHA1ProcessMessageBlockの中です。
平均的に1回の撹拌で
テーブル引き 5回、 rotate 2回、 shift 2回、 and 7回、
or 3回、 xor 3回、 加算 4回、 減算 3回
およそこれくらいはこなさなければならず
これを80回繰り返して1000回に抑えるのは非現実的だと思います。
ただし、通常の実装はそれを整数演算でやっていますので
かかる時間を浮動小数点演算換算で1000回から10000回分の範囲に収めることは可能です。
単純に作っても3GHzのP4で毎秒百万回くらいは出せることから
うまくアセンブラで書いてさらにHTを利用して同時に複数スレッド処理をすれば
毎秒6百万回に近付けることが可能かもしれません。
しかしその速度を出す実装はまだ見たことがありません。あるかどうか分かりません。
結果的にsamayoiさんの結論は実際の速度と近くなるという偶然が起きてますが
その前提となる演算回数が1000回という仮定は間違いだと思います。
そもそも必要な計算が1000回で済むようなアルゴリズムならMD5と同レベルです。
> そのあたりのことも書いておくべきでした。
計算回数が分からないなら、余計なことは書かず、
計算回数の話を素っ飛ばして「毎秒6百万回のSHA1処理ができる」と仮定して
2^39回なら91626秒と結論付けてしまった方が良いのではないでしょうか。
「浮動小数点演算1000回」という記述は
せっかく巧く描けた蛇の絵に足を描き足すようなものです。
Re:あわてる必要は無い (スコア:0)
>うまくアセンブラで書いてさらにHTを利用して同時に複数スレッド処理をすれば
> 毎秒6百万回に近付けることが可能かもしれません。
強調部のところで躊躇してしまいました。
なんでこうなるのでしょうか？HTに意味があるとは思えないんですが。
Re:あわてる必要は無い (スコア:1, 参考になる)
前回のストーリーに付けられたコメントからですが、こういうことですよね。
Re:あわてる必要は無い (スコア:0)
いつのまに盗聴されたんだ？