SHA-1ハッシュの衝突を現実的な時間で生成する攻撃「Shatterd」 46
ストーリー by headless
粉砕 部門より
粉砕 部門より
オランダ・CWI AmsterdamとGoogleの研究チームは23日、SHA-1ハッシュ値の衝突を現実的な時間で生成する攻撃手法「Shattered (SHAtterd)」を発表した(CWIのニュース記事、
Google Security Blogの記事、
Phoronixの記事、
Ars Technicaの記事、
論文: PDF)。
Shattered攻撃は多数の暗号解析技術を組み合わせたもので、同じSHA-1ハッシュ値を持ち、内容の異なる2つのPDFファイルの生成などが可能だ。高速といっても263回の試行が必要となり、攻撃の第1フェーズは6,500 CPUで1年間、第2フェーズは110 GPUで1年間を要する。それでもブルートフォース攻撃と比較すると10万倍以上高速だという。shatterd.ioではPoCとして、同じSHA-1ハッシュ値で内容の異なる2つのPDFファイル (PDF 1/PDF 2)を公開している。また、Shattered攻撃で使われているPDFかどうかを確認するテスター機能もWebページ上で提供される。研究チームではShattered攻撃がきっかけとなってSHA-1の危険性に対する認知度を高め、より安全なSHA-256などへの移行が進むことを期待しているとのこと。
SHA-1の危険性は何年も前から指摘されており、現在も文書の署名やHTTPS証明書、バージョン管理システムなど幅広く使われている。ただし、SHA-1のHTTPS証明書に関しては、CA/Browser Forumが2016年1月1日以降発行を禁じている。Googleでは2014年リリースのChrom 39からSHA-1証明書の廃止を進め、今年1月リリースのChrome 56でSHA-1のサポートを終了した。Firefox 51も昨年11月のリリース以降、SHA-1証明書を無効化するユーザーを徐々に増やしていたが、24日で移行を終了したそうだ。Firefox 52ではデフォルトで無効化される。一方、MicrosoftはInternet Explorer 11/Microsoft EdgeでSHA-1証明書を使用するWebサイトをブロックする計画だったが、2017年半ばまで延期する方針を22日に発表している。
なお、ShatterdのソースコードはGoogleの脆弱性公表ポリシーに従って90日後にリリースされるが、既に影響が出ているようだ。WebKitのリポジトリはPoCのPDFファイル2本がアップロードされたことで障害が発生したという。Apache SVNは重複ファイルの検出にSHA-1を使うため、正常に動作しなくなったようだ。
Shattered攻撃は多数の暗号解析技術を組み合わせたもので、同じSHA-1ハッシュ値を持ち、内容の異なる2つのPDFファイルの生成などが可能だ。高速といっても263回の試行が必要となり、攻撃の第1フェーズは6,500 CPUで1年間、第2フェーズは110 GPUで1年間を要する。それでもブルートフォース攻撃と比較すると10万倍以上高速だという。shatterd.ioではPoCとして、同じSHA-1ハッシュ値で内容の異なる2つのPDFファイル (PDF 1/PDF 2)を公開している。また、Shattered攻撃で使われているPDFかどうかを確認するテスター機能もWebページ上で提供される。研究チームではShattered攻撃がきっかけとなってSHA-1の危険性に対する認知度を高め、より安全なSHA-256などへの移行が進むことを期待しているとのこと。
SHA-1の危険性は何年も前から指摘されており、現在も文書の署名やHTTPS証明書、バージョン管理システムなど幅広く使われている。ただし、SHA-1のHTTPS証明書に関しては、CA/Browser Forumが2016年1月1日以降発行を禁じている。Googleでは2014年リリースのChrom 39からSHA-1証明書の廃止を進め、今年1月リリースのChrome 56でSHA-1のサポートを終了した。Firefox 51も昨年11月のリリース以降、SHA-1証明書を無効化するユーザーを徐々に増やしていたが、24日で移行を終了したそうだ。Firefox 52ではデフォルトで無効化される。一方、MicrosoftはInternet Explorer 11/Microsoft EdgeでSHA-1証明書を使用するWebサイトをブロックする計画だったが、2017年半ばまで延期する方針を22日に発表している。
なお、ShatterdのソースコードはGoogleの脆弱性公表ポリシーに従って90日後にリリースされるが、既に影響が出ているようだ。WebKitのリポジトリはPoCのPDFファイル2本がアップロードされたことで障害が発生したという。Apache SVNは重複ファイルの検出にSHA-1を使うため、正常に動作しなくなったようだ。
突破されたのは強衝突耐性 (スコア:5, 参考になる)
同じSHA-1ハッシュを持つ2ファイルを作ることに成功したという報告。
特定のファイルに対して、同じSHA-1ハッシュを持つファイルを作る、というのはまだできていない模様。
日本語のわりとわかりやすい解説がありました。
https://www.slideshare.net/herumi/googlesha1 [slideshare.net]
SHA-1の作り方は、
・20バイトの内部状態(CV)を持つ
・ファイルの次64バイト(1ブロック)と現在のCVから次のCVを計算する
・ファイルの最後まで進んだらCVを出力する(これがSHA-1)
という作りになっている。
従って、途中でCVを同じでにきれば、それ以降が同じデータであれば同じSHA-1になる。
今回はPDFのヘッダ192バイト(3ブロック)までのCVを出発点(CV3)として、
・ファイルAでは4ブロック目でCV4aを計算、5ブロック目でCV5aを計算
・ファイルBでは4ブロック目でCV4bを計算、5ブロック目でCV5bを計算
したときにCV5a == CV5bとなる4ブロック目5ブロック目を発見した。
ほんの僅かな部分だけ異なるファイルを作るのは簡単(といっても110GPU年)ですが、
中身が全体的に異なるものを作るのは逆に難しそうです。
その組み合わせを探索するのにDVという特別なデータが入っていると効率がいいらしく、
SHATTEREDのサイト [shattered.it]ではファイルにDVが入っているかどうかチェックしてくれます。
そのへんはNew collision attacks on SHA-1based on optimal joint local-collision analysis [marc-stevens.nl]という論文に書かれてるみたいなのですが……さっぱりわからん。
110GPU年 (スコア:3, 参考になる)
衝突の発見に110GPU年ということは、
スーパーコンピューターのTSUBAME2で4224GPUらしいので
およそ10日で発見できる可能性があるという事ですか。
国家や大企業であれば実用的な攻撃方法になるかもしれませんね。
クラウドでもできそうだけど1回あたりのお金がすごそうです。
Re: (スコア:0)
ラフに言えばそうなるね。実際にはプロセッサ間の通信があるからもうすこしおそいはず
Re: (スコア:0)
クラウド提供業者限定だけど、クラウドはピークに合わせて設備投資しているだろうから、暇なときにタスクを動かせば、比較的安くできそう。
あとはボットネットで、PC所有者に気づかれないように、アイドル時に計算するとか。
Re: (スコア:0)
bitcoin全盛期?に一部のCryptocurrencyがSHA-1を使ってた気がするんだけど、
それの採掘用に作られたASICを流用できないのかな?
ほんとに一致する (スコア:1)
リンク先のPDF、ほんとにSHA-1一致するな。
しかも、内容もランダムデータでなく、意味のあるデータになっているのはすごい。
当然ながらCRC-32は一致しないな。
いくつものハッシュを組み合わせるのはダメなんだろうか、とふと思った。
・・・まあ、それができるぐらいならSHA-1を捨てればいいか。
Re:ほんとに一致する (スコア:4, 興味深い)
概ね 64 bytes のランダムデータのような意味のないゴミデータが注入されています。PDFは可変長のゴミデータを入れても正常に表示されるので、それを利用しているのでしょう。
2つの PDFファイル (422,435 bytes) の内、差異があるのは 192byte~256byte の箇所のみであとは完全一致でした。ヘッダ部分を除いた最初の部分 64 bytes に違いがあるだけなので(背景色の情報もこの 64 bytes に含まれているはず)、僅か 64 bytes 任意のデータを入れられるファイル形式であるならば、この攻撃は成功することになります。
ありとあらゆるハッシュ関数を試してみましたが、確かに SHA-1 以外は全部一致していませんでした。しかし、これは SHA-1 のみをターゲットにした検証用ファイルなので、当然のことです。
(無駄に長くなるし貼るべきか悩みましたが、ダウンロードしてハッシュ値を調べるのが面倒な人もいるかもしれないので、私がさっき調べたそれぞれのファイルのハッシュ値を貼っておきます)
* shattered-1.pdf [shattered.io] (422,435 bytes)
* shattered-2.pdf [shattered.io] (422,435 bytes)
Re:ほんとに一致する (スコア:1)
PDF中のJPEG画像のコメント領域に、調整用のバイナリデータが埋め込まれているようです。
PDFの見た目に影響しているのは、PDFファイルの0xC0番地の1バイトのみで、
shattered-1.pdfとshattered-2.pdfの表示の違いは、この1バイトの違いによって発生しています。
その後、127バイト使用して、ハッシュ値を衝突させるためのバイナリデータが埋め込まれていました。
Re: (スコア:0)
この画像 [shattered.it]がわかりやすいですね。
PDFの見た目を変えたのは改竄可能性の例示に為でしょう。
同じ見た目でハッシュが同じでも何もすごくないですしね。
しかし、SHA-1を確認すれば同じになるというだけの話に110GPU年ですか。
今まで同一性チェックに使って、たまたま衝突したらどうしようとか考えていましたが認識を改めます。
まぁそれは確率の問題だし、いつも使ってるのはCRC-32なので改竄は容易ですけどね。
Re: (スコア:0)
「ハッシュ値を調べるのが面倒」なんて言う人にとってはハッシュ値なんて意味のないものだろう?
Re: (スコア:0)
ハッシュを組み合わせても強度はほとんど上がらない。MD5 + SHA-1では8ビット程度しか強度が上がらないそうだ。
それどころか下手に組み合わせると弱くなるおそれすらある。どうしてそういうことが起こりうるのかについてはスラドの過去記事を参照 [srad.jp]。
素直に暗号の専門家が設計したハッシュを使っておけ。
Re: (スコア:0)
MD5ハッシュとSHA1ハッシュの併記という意味で、混合ではないのでは?
そして記事についてだけど。
ハッシュについての話でブルートフォース攻撃って何よ?鍵関係ないじゃん。
Re: (スコア:0)
埋め込むバイト列を総当たりで試すのであれば、それだってブルートフォースです。
(ブルートフォースには力技程度の意味しかないです。)
00〜FF、0000〜FFFF、000000〜FFFFFF……ってな具合。
Re: (スコア:0)
とはいえブルートフォース攻撃よりはブルートフォース解析ないし総当り解析などと表現するほうが自然かなともおもったり。
Re: (スコア:0)
符号理論ではこういうのは全部「攻撃」と一括りにまとめています。
Re: (スコア:0)
まあ専門用語がいっぱんてきなようほうとずれているのはよくあること
Re: (スコア:0)
「ご褒美」が代表例かな?
Re: (スコア:0)
次の中からブルートフォース攻撃を選べ(5点)
1) 英数記号の組み合わせを生成し、ログインサーバに対して送信することで他人のアカウントでログインした。
2) パスワードがハッシュ値で記録されたアカウント情報を入手したので、英数記号の組み合わせを生成し、記録されているハッシュ値と同じになる値を見つけた。
2-1) そのようにして見つけたパスワードを使用して、他人のアカウントでログインした。
3) 取得したZIPファイルがパスワードで暗号化されていたので、英数記号の組み合わせを生成して解読した。
(パスワードが正しいことの判定は、復号後のファイルの
Re: (スコア:0)
8) アームが弱いので台パンした
Re: (スコア:0)
MD5とSHA-1の両方を合わせた実例。
https://roastingbugs.blogspot.jp/2017/03/eat-more-hashes.html [blogspot.jp]
弱い者同士を組み合わせたところでほとんど意味はない。
Re: (スコア:0)
ブレーンテキストなら改変は難しいってことか!
Re: (スコア:0)
Brain text?
Re: (スコア:0)
ある程度の長さのコメントブロック /* */ があれば
0x00〜0xFFまでなんでも入れられるし、*/ というシーケンスさえ出ないように
気をつければいいのでわりとハードルは低いかもしれない
Re: (スコア:0)
そもそもデモにPDFを使うのはMD5コリジョンのときにも行われていた技法で、別に目新しくない。
各ブラウザの対応が・・・ (スコア:0)
ブロックや非サポートになるからアクセスできなくなる。
SSLでない(=安全な接続でない)のはアクセスできるのに、SHA1(=そこそこ安全な接続)のはアクセスできないって対応の仕方はどこかおかしい。
デッカク「SHA1は危ないかもよ!非SSLも危ないかもよ!」って警告する程度にしてもらいたい
Re:各ブラウザの対応が・・・ (スコア:1)
Mozillaはその対応ですね。ぱっと見有効期限が切れてる証明書とかと似たような警告の画面が表示される模様。
SHA1証明書に対する各社の対応@サイバートラスト [cybertrust.ne.jp]
まぁSHA1証明書が今後廃止に向けて動くってのは間違い無いですし、
徐々に対応してもらえば良いんじゃないでしょうか。
現状110GPU年であれば、よっぽど裕福なクラッカーでもない限り
攻撃にソコソコ長時間掛かるので、事実上問題が出る前に
収束するでしょうしね。
#まぁSSL=安全って事でもないんだけどねぇ・・・
#LetsEnclypt使えば無料でDV取れちゃうし、EV/OVとの表示の違いなんて気にしてる一般人なんて殆どいないしなー
#IT系企業でもEVとかOVとかDVとか証明書の種類があることすら知らない人も居たりする位だからなぁ・・・
Re: (スコア:0)
まあ、or.jpやco.jpなら.comより安全とか思われてたりする嘘のような話が実際にあったりしますからね……
たまにDVの販売ページとかを見つけてきて、安いからこれにしたらどうかと言われるけど毎回説明するのが面倒です。とはいえ私もEVじゃなきゃOVもDVも大差ないとは思っています。
せめてOV発行している認証局はDV発行できないようにでもなってくれないと、OV入れているところが逆に情弱企業として認定されてしまいそうです。
Re: (スコア:0)
「危ないかもよ」ぐらいの警告じゃ、技術的詳細に明るくなく、リスクを正当に評価できない人(orする気もない人)には
あまり意味が無いからなぁ。
5分ぐらいの教育ビデオを流して、そのあと(数百問のうちからランダムに選ばれる)10問くらいの
セキュリティリテラシーチェックのテストを受けさせて、全問正解だったらアクセスできるというのはどうか?
Re: (スコア:0)
> SSLでない(=安全な接続でない)のはアクセスできるのに、SHA1(=そこそこ安全な接続)のはアクセスできないって対応の仕方はどこかおかしい。
危険かもしれないものをそうと知って使うのと、危険なものを安全と思い込んで使うのでは、後者の方が有害だろうから、ブロックするのは妥当かと思う。
> デッカク「SHA1は危ないかもよ!非SSLも危ないかもよ!」って警告する程度にしてもらいたい
……ので、これも同意したいのだけど、証明書は通信の暗号化以外にも運営者の実在証明とかそんな感じの役割があったはずなので、単に危険性だけでなくそちらの詐称とか攪乱のリスクもあるんだろうか?
教えてエロい人
Re: (スコア:0)
それはEV SSL。
Re: (スコア:0)
EVは実在性の証明の度合い(厳しさ)の違い。
Re: (スコア:0)
非実在でもアウトです///
Re: (スコア:0)
せめてhttpsでアクセスしてエラーが出た場合、URLを手動でhttpに書き換えて繋がればいいのだけど、それすら拒否するサイトがあるからなあ。しかもログインしなくても見れるはずのサイトで。
ハッシュでパスワード保存しているデータベース (スコア:0)
全ユーザ強制パスワード変更にするしかないの?
自ら「SHA-1使ってま〜す!」って言ってるようなものだけどね
パスワードハッシュは SHA-2 (SHA-256 等) も駄目 (スコア:5, 興味深い)
PHP Manual: パスワードのハッシュ [php.net] より引用(太字強調は引用者)
SHA のような fast hash は、大きなファイルから固定長のダイジェストを得るのには便利に設計されており、例えば 1GB = 1,073,741,824 bytes のファイルの SHA-256 ハッシュ値をスマホで短時間で算出することも容易にできます。
一方、bcrypt のような slow hash はパスワードの保護などを目的としており、大きなファイルのダイジェストを現実的な時間で求めることは普通のコンピュータの演算能力では難しいほど計算に時間がかかる設計になってます。というか、Blowfish アルゴリズムは、そもそも 72 bytes までしか対応していません(つまりパスワードの文字数制限を72文字にする必要があります)。パスワードは、こういったパスワードの保護に相応しいハッシュ関数を通してから保存すべきです。
TLS (https など) の証明書のハッシュが SHA-2 で今のところ十分なのは、ハッシュ関数にかけるデータのデータ長がそれなりにあるからであって、fast hash 関数は、総当たりが容易な短いパスワードには使うべきではありません。全ユーザ強制パスワード変更で、ハッシュ関数を SHA-1 から SHA-2 に移行するというのは論外な愚策です。
php の password_hash 関数 [php.net] は大変素晴らしく、現在 bcrypt アルゴリズムが使われていますが、もし将来的に新しくてより強力なアルゴリズムが登場したときには、新たに作成するパスワードハッシュがそれに切り替わるようになっているので、昔作ったプログラムが放置されても安全なアルゴリズムに自動的に移行することができるという優れものです。コストパラメータの適切な設定値を調整し、ストレッチング負荷を適切に設定することも容易です。こういった最先端の方法でパスワードハッシュを保存すべきです。
Re: (スコア:0)
PHPのpassword_hashってインターフェイスを統一するための単なるラッパーじゃない? と思って
少し調べてみました。
一番気になるのは、異なるアルゴリズムでハッシュ化されたパスワードが混在してもうまく扱えるのか、
でしたが、ハッシュにはどのアルゴリズムか等の情報も含まれているとのこと。password_verifyの説明を
見て理解しました。
「password_」で始まる命令 [php.net]をひととおり見ておくとよいと思います。
Re: (スコア:0)
> (PHP 5 >= 5.5.0, PHP 7)
PHPの関数は導入バージョンを見れば使っていいかどうかだいたいわかるのがすぐれものですね(褒め殺し)
Re:ハッシュでパスワード保存しているデータベース (スコア:1)
つまり、
パスワードを定期的に強制変更するポリシーは、内部のハッシュ化方式を変更するのに向いているし、
変更したタイミングを悟らせない効果もあるってことだな。
Re: (スコア:0)
「変更」は条件ではないから、定期変更時でなくても、password verify時にこっそり更新すればいいよ。
Re:ハッシュでパスワード保存しているデータベース (スコア:1)
そういやそうだった。忘れてた…恥ずかしい
Re: (スコア:0)
ハッシュ値からパスワードを算出できるわけではない。
Re: (スコア:0)
今回破られたのは強衝突耐性で、弱衝突耐性が破られたわけではないから、
まだ一応猶予はある。
移行期間を用意して、順次変えてもらえば良かろ
Re: (スコア:0)
ログインしたときにパスワードを入力してもらえるのだから
古いアルゴリズムで認証した後に、新しいアルゴリズムで再ハッシュすれば良いかと
それとは別にハッシュ単体でのパスワード認証は危険なので
パスワードを考慮した鍵導出アルゴリズムに変更した方が良いでしょう。
去年RFC 7914となったばかりのscryptなどがおすすめです。
Re: (スコア:0)
SH1が乗ってた無線AP今でもありますが、それでも結構安定かどうしてます
ひらがなだと (スコア:0)
安定か?どうしてます?
と尋ねているようにも読める。
Re:ひらがなだと (スコア:1)
# ルネサスのアレ