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

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を使うため、正常に動作しなくなったようだ。
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 同じ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, 参考になる)

    by Anonymous Coward on 2017年02月25日 20時00分 (#3167346)

    衝突の発見に110GPU年ということは、
    スーパーコンピューターのTSUBAME2で4224GPUらしいので
    およそ10日で発見できる可能性があるという事ですか。
    国家や大企業であれば実用的な攻撃方法になるかもしれませんね。

    クラウドでもできそうだけど1回あたりのお金がすごそうです。

    • by Anonymous Coward

      ラフに言えばそうなるね。実際にはプロセッサ間の通信があるからもうすこしおそいはず

    • by Anonymous Coward

      クラウド提供業者限定だけど、クラウドはピークに合わせて設備投資しているだろうから、暇なときにタスクを動かせば、比較的安くできそう。
      あとはボットネットで、PC所有者に気づかれないように、アイドル時に計算するとか。

    • by Anonymous Coward

      bitcoin全盛期?に一部のCryptocurrencyがSHA-1を使ってた気がするんだけど、
      それの採掘用に作られたASICを流用できないのかな?

  • by Anonymous Coward on 2017年02月25日 20時11分 (#3167348)

    リンク先のPDF、ほんとにSHA-1一致するな。
    しかも、内容もランダムデータでなく、意味のあるデータになっているのはすごい。

    当然ながらCRC-32は一致しないな。
    いくつものハッシュを組み合わせるのはダメなんだろうか、とふと思った。
    ・・・まあ、それができるぐらいならSHA-1を捨てればいいか。

    • by Printable is bad. (38668) on 2017年02月25日 21時00分 (#3167355)

      リンク先のPDF、ほんとにSHA-1一致するな。
      しかも、内容もランダムデータでなく、意味のあるデータになっているのはすごい。

      概ね 64 bytes のランダムデータのような意味のないゴミデータが注入されています。PDFは可変長のゴミデータを入れても正常に表示されるので、それを利用しているのでしょう。

      2つの PDFファイル (422,435 bytes) の内、差異があるのは 192byte~256byte の箇所のみであとは完全一致でした。ヘッダ部分を除いた最初の部分 64 bytes に違いがあるだけなので(背景色の情報もこの 64 bytes に含まれているはず)、僅か 64 bytes 任意のデータを入れられるファイル形式であるならば、この攻撃は成功することになります。

      当然ながらCRC-32は一致しないな。 いくつものハッシュを組み合わせるのはダメなんだろうか、とふと思った。

      ありとあらゆるハッシュ関数を試してみましたが、確かに SHA-1 以外は全部一致していませんでした。しかし、これは SHA-1 のみをターゲットにした検証用ファイルなので、当然のことです。

      (無駄に長くなるし貼るべきか悩みましたが、ダウンロードしてハッシュ値を調べるのが面倒な人もいるかもしれないので、私がさっき調べたそれぞれのファイルのハッシュ値を貼っておきます)

      * shattered-1.pdf [shattered.io] (422,435 bytes)

      Adler32: 36f477bb
      BLAKE2sp: 4b64ce383ec747ec67895dacf8a7d4af8d62f9b7a8f8fbaf7ccb352ff2bf17f8
      BTIH: f86f6faf4d2e18e12b95b4471fc6a92cabe49004
      CRC32: 348150fb
      ED2K: 38373b377cf16c032d08cef0855cb820
      GOST: 2cca14e553eff6d1c99fb37b8134c2d1d92bf65217185a0e2eca044d9747745b
      MD2: 27fa33d94a14ba237bf4dbee401f1df0
      MD4: 38373b377cf16c032d08cef0855cb820
      MD5: ee4aa52b139d925f8d8884402b0a750c
      RIPEMD-128: 70f07699de87e6520c80f5f7b5e2e430
      RIPEMD-256: 8fbfc5a8a6a1f26eff8b4b0759717df161f1ece1c0674c9501ecb827f5e1db35
      RIPEMD-320: 90d7a15075c1c20c85865eefb5dca8ad18d7f9c1d4a77dfae6e52a654f8a1abf216749994041a78e
      SHA-1: 38762cf7f55934b34d179ae6a4c80cadccbb7f0a
      SHA-256: 2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0
      SHA-256 Base64: K7eHpz43NS+SODq+fikCk20QWa2fG6baqpweWO5pcNA=
      SHA-384: 27f937a0849be559affa109f97744024bc494b2b81dcd9684845cd14574953cc6310398b89e150ad3819188309e59996
      SHA-512: 3c19b2cbcf72f7f5b252ea31677b8f2323d6119e49bcc0fb55931d00132385f1e749bb24cbd68c04ac826ae8421802825d3587fe185abf709669bb9693f6b416
      SHA3-224: ef525305e821be4de14ce03aacf8f85a8252102e1f0884dae22a92ee
      SHA3-256: 36c1d2055da04440bb955880d6dd174d68b660d449d2f3ce42e4ef02bc718bd1
      SHA3-384: c3f292c8ec1a97ade3d64393fc5ba61de018f289479df18372a5f99d4d78974f12c27fc7c5fb8c58ddbac8499cd109a6
      SHA3-512: fa00d2b9e9322fd0bdd83e17277496f55563959f54de76b79eec08537c75a4d84f2a12017e1efeb1bc44b6d4f7fe1847a4570a18147a7e974465bd971c51504b
      TTH: raly2ga4whbetx5m3xzspacr3fv6dt6jbdeiqkq
      Tiger: f23e7ac5991136b1b28bd2ea729a4bd64c64c5a14db20e21
      Whirlpool: 68e7a8d6622d2a02b9008b4eb610a5f9b95e66191b4267072b751af8722333fc1585892d898fbbe1a3aeb566aa1a1ca6c3f9d08ef8d5282eea677a82e41826f5

      * shattered-2.pdf [shattered.io] (422,435 bytes)

      Adler32: 49907353
      BLAKE2sp: cd064189a2433601e798629e90e76537c663ca1e406234dcaef8feace2f20379
      BTIH: 65522388faeae826bb5890ea18d98f240becd46c
      CRC32: b3fbab1c
      ED2K: 4881d13b4265c952a9ed032ea4a1a043
      GOST: 85205642f0ebfa8e5b58639505e2ac4b84fa75939c181892e728b8cf4cbc95bb
      MD2: be972896748cc45244ff6c3e7154d05a
      MD4: 4881d13b4265c952a9ed032ea4a1a043
      MD5: 5bd9d8cabc46041579a311230539b8d1
      RIPEMD-128: 75d04513f1faee490567b7869730e815
      RIPEMD-256: e4326309ded334093caad2968d52239b162134d3d314810fa235a6fb298e8c2f
      RIPEMD-320: 33f83953dc061704b32bcb124983731244f4fe3c9d7c08514ffecde6ff1db5ff4c4dec33df9b0727
      SHA-1: 38762cf7f55934b34d179ae6a4c80cadccbb7f0a
      SHA-256: d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff
      SHA-256 Base64: 1EiHddKb3veZM2fVQQZNvdpQ04P4nwqhOm/y4IlLpf8=
      SHA-384: e04944841a251d5bbed5dbb0d07486d254bcddd2c11341ee9bb045bfd678aa7b784e1b7a7d56ece

      親コメント
      • by Anonymous Coward on 2017年02月25日 21時28分 (#3167365)

        PDF中のJPEG画像のコメント領域に、調整用のバイナリデータが埋め込まれているようです。

        PDFの見た目に影響しているのは、PDFファイルの0xC0番地の1バイトのみで、
        shattered-1.pdfとshattered-2.pdfの表示の違いは、この1バイトの違いによって発生しています。
        その後、127バイト使用して、ハッシュ値を衝突させるためのバイナリデータが埋め込まれていました。

        親コメント
        • by Anonymous Coward

          この画像 [shattered.it]がわかりやすいですね。

          PDFの見た目を変えたのは改竄可能性の例示に為でしょう。
          同じ見た目でハッシュが同じでも何もすごくないですしね。

          しかし、SHA-1を確認すれば同じになるというだけの話に110GPU年ですか。
          今まで同一性チェックに使って、たまたま衝突したらどうしようとか考えていましたが認識を改めます。
          まぁそれは確率の問題だし、いつも使ってるのはCRC-32なので改竄は容易ですけどね。

      • by Anonymous Coward

        「ハッシュ値を調べるのが面倒」なんて言う人にとってはハッシュ値なんて意味のないものだろう?

    • by Anonymous Coward

      ハッシュを組み合わせても強度はほとんど上がらない。MD5 + SHA-1では8ビット程度しか強度が上がらないそうだ。
      それどころか下手に組み合わせると弱くなるおそれすらある。どうしてそういうことが起こりうるのかについてはスラドの過去記事を参照 [srad.jp]。
      素直に暗号の専門家が設計したハッシュを使っておけ。

      • by Anonymous Coward

        MD5ハッシュとSHA1ハッシュの併記という意味で、混合ではないのでは?

        そして記事についてだけど。
        ハッシュについての話でブルートフォース攻撃って何よ?鍵関係ないじゃん。

        • by Anonymous Coward

          埋め込むバイト列を総当たりで試すのであれば、それだってブルートフォースです。
          (ブルートフォースには力技程度の意味しかないです。)

          00〜FF、0000〜FFFF、000000〜FFFFFF……ってな具合。

          • by Anonymous Coward

            とはいえブルートフォース攻撃よりはブルートフォース解析ないし総当り解析などと表現するほうが自然かなともおもったり。

            • by Anonymous Coward

              符号理論ではこういうのは全部「攻撃」と一括りにまとめています。

              • by Anonymous Coward

                まあ専門用語がいっぱんてきなようほうとずれているのはよくあること

              • by Anonymous Coward

                「ご褒美」が代表例かな?

        • by Anonymous Coward

          次の中からブルートフォース攻撃を選べ(5点)
          1) 英数記号の組み合わせを生成し、ログインサーバに対して送信することで他人のアカウントでログインした。
          2) パスワードがハッシュ値で記録されたアカウント情報を入手したので、英数記号の組み合わせを生成し、記録されているハッシュ値と同じになる値を見つけた。
          2-1) そのようにして見つけたパスワードを使用して、他人のアカウントでログインした。
          3) 取得したZIPファイルがパスワードで暗号化されていたので、英数記号の組み合わせを生成して解読した。
           (パスワードが正しいことの判定は、復号後のファイルの

          • by Anonymous Coward

            8) アームが弱いので台パンした

      • by Anonymous Coward

        MD5とSHA-1の両方を合わせた実例。
        https://roastingbugs.blogspot.jp/2017/03/eat-more-hashes.html [blogspot.jp]
        弱い者同士を組み合わせたところでほとんど意味はない。

    • by Anonymous Coward

      ブレーンテキストなら改変は難しいってことか!

      • by Anonymous Coward

        Brain text?

      • by Anonymous Coward

        ある程度の長さのコメントブロック /* */ があれば
        0x00〜0xFFまでなんでも入れられるし、*/ というシーケンスさえ出ないように
        気をつければいいのでわりとハードルは低いかもしれない

    • by Anonymous Coward

      そもそもデモにPDFを使うのはMD5コリジョンのときにも行われていた技法で、別に目新しくない。

  • by Anonymous Coward on 2017年02月25日 19時37分 (#3167340)

    ブロックや非サポートになるからアクセスできなくなる。
    SSLでない(=安全な接続でない)のはアクセスできるのに、SHA1(=そこそこ安全な接続)のはアクセスできないって対応の仕方はどこかおかしい。
    デッカク「SHA1は危ないかもよ!非SSLも危ないかもよ!」って警告する程度にしてもらいたい

    • Mozillaはその対応ですね。ぱっと見有効期限が切れてる証明書とかと似たような警告の画面が表示される模様。
      SHA1証明書に対する各社の対応@サイバートラスト [cybertrust.ne.jp]

      まぁSHA1証明書が今後廃止に向けて動くってのは間違い無いですし、
      徐々に対応してもらえば良いんじゃないでしょうか。

      現状110GPU年であれば、よっぽど裕福なクラッカーでもない限り
      攻撃にソコソコ長時間掛かるので、事実上問題が出る前に
      収束するでしょうしね。

      #まぁSSL=安全って事でもないんだけどねぇ・・・
      #LetsEnclypt使えば無料でDV取れちゃうし、EV/OVとの表示の違いなんて気にしてる一般人なんて殆どいないしなー
      #IT系企業でもEVとかOVとかDVとか証明書の種類があることすら知らない人も居たりする位だからなぁ・・・

      親コメント
      • by Anonymous Coward

        まあ、or.jpやco.jpなら.comより安全とか思われてたりする嘘のような話が実際にあったりしますからね……

        たまにDVの販売ページとかを見つけてきて、安いからこれにしたらどうかと言われるけど毎回説明するのが面倒です。とはいえ私もEVじゃなきゃOVもDVも大差ないとは思っています。
        せめてOV発行している認証局はDV発行できないようにでもなってくれないと、OV入れているところが逆に情弱企業として認定されてしまいそうです。

    • by Anonymous Coward

      「危ないかもよ」ぐらいの警告じゃ、技術的詳細に明るくなく、リスクを正当に評価できない人(orする気もない人)には
      あまり意味が無いからなぁ。

      5分ぐらいの教育ビデオを流して、そのあと(数百問のうちからランダムに選ばれる)10問くらいの
      セキュリティリテラシーチェックのテストを受けさせて、全問正解だったらアクセスできるというのはどうか?

    • by Anonymous Coward

      > SSLでない(=安全な接続でない)のはアクセスできるのに、SHA1(=そこそこ安全な接続)のはアクセスできないって対応の仕方はどこかおかしい。
      危険かもしれないものをそうと知って使うのと、危険なものを安全と思い込んで使うのでは、後者の方が有害だろうから、ブロックするのは妥当かと思う。

      > デッカク「SHA1は危ないかもよ!非SSLも危ないかもよ!」って警告する程度にしてもらいたい
      ……ので、これも同意したいのだけど、証明書は通信の暗号化以外にも運営者の実在証明とかそんな感じの役割があったはずなので、単に危険性だけでなくそちらの詐称とか攪乱のリスクもあるんだろうか?
      教えてエロい人

      • by Anonymous Coward

        運営者の実在証明

        それはEV SSL。

        • by Anonymous Coward

          EVは実在性の証明の度合い(厳しさ)の違い。

      • by Anonymous Coward

        非実在でもアウトです///

      • by Anonymous Coward

        せめてhttpsでアクセスしてエラーが出た場合、URLを手動でhttpに書き換えて繋がればいいのだけど、それすら拒否するサイトがあるからなあ。しかもログインしなくても見れるはずのサイトで。

  • by Anonymous Coward on 2017年02月25日 22時52分 (#3167385)

    全ユーザ強制パスワード変更にするしかないの?
    自ら「SHA-1使ってま〜す!」って言ってるようなものだけどね

    • PHP Manual: パスワードのハッシュ [php.net] より引用(太字強調は引用者)

      MD5 や SHA1 そして SHA256 といったハッシュアルゴリズムは、 高速かつ効率的なハッシュ処理のために設計されたものです。 最近のテクノロジーやハードウェア性能をもってすれば、 これらのアルゴリズムの出力をブルートフォースで(力ずくで)調べて元の入力を得るのはたやすいことです。

      最近のコンピュータではハッシュアルゴリズムを高速に「逆算」できるので、 セキュリティ技術者の多くはこれらの関数をパスワードのハッシュに使わないよう強く推奨しています。

      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 アルゴリズムが使われていますが、もし将来的に新しくてより強力なアルゴリズムが登場したときには、新たに作成するパスワードハッシュがそれに切り替わるようになっているので、昔作ったプログラムが放置されても安全なアルゴリズムに自動的に移行することができるという優れものです。コストパラメータの適切な設定値を調整し、ストレッチング負荷を適切に設定することも容易です。こういった最先端の方法でパスワードハッシュを保存すべきです。

      親コメント
      • by Anonymous Coward

        PHPのpassword_hashってインターフェイスを統一するための単なるラッパーじゃない? と思って
        少し調べてみました。

        一番気になるのは、異なるアルゴリズムでハッシュ化されたパスワードが混在してもうまく扱えるのか、
        でしたが、ハッシュにはどのアルゴリズムか等の情報も含まれているとのこと。password_verifyの説明を
        見て理解しました。

        「password_」で始まる命令 [php.net]をひととおり見ておくとよいと思います。

      • by Anonymous Coward

        > (PHP 5 >= 5.5.0, PHP 7)

        PHPの関数は導入バージョンを見れば使っていいかどうかだいたいわかるのがすぐれものですね(褒め殺し)

    • つまり、
      パスワードを定期的に強制変更するポリシーは、内部のハッシュ化方式を変更するのに向いているし、
      変更したタイミングを悟らせない効果もあるってことだな。

      親コメント
    • by Anonymous Coward
      パスワードを知ってる場合に、それと同じハッシュ値を持つ別のパスワード(偽)を作れるってことでしょ。
      ハッシュ値からパスワードを算出できるわけではない。
    • by Anonymous Coward

      今回破られたのは強衝突耐性で、弱衝突耐性が破られたわけではないから、
      まだ一応猶予はある。
      移行期間を用意して、順次変えてもらえば良かろ

    • by Anonymous Coward

      ログインしたときにパスワードを入力してもらえるのだから
      古いアルゴリズムで認証した後に、新しいアルゴリズムで再ハッシュすれば良いかと

      それとは別にハッシュ単体でのパスワード認証は危険なので
      パスワードを考慮した鍵導出アルゴリズムに変更した方が良いでしょう。
      去年RFC 7914となったばかりのscryptなどがおすすめです。

  • by Anonymous Coward on 2017年02月26日 11時06分 (#3167458)

    SH1が乗ってた無線AP今でもありますが、それでも結構安定かどうしてます

typodupeerror

ソースを見ろ -- ある4桁UID

読み込み中...