(何度目かの)さようなら SHA-1

no extension

2019年11月に書いた「GnuPG 2.2.18 リリース: さようなら SHA-1」に追記してお終いにしようかと思ったが,思ったより騒がれてる感じなので記事を立ててみた。

というわけで:

要約としては Bruce Schneier さんの記事が分かりやすいので,これを起点に紹介していく。

ハッシュ値の衝突問題

(「SHA-1 衝突問題: 廃止の前倒し」からの抜粋)

暗号技術におけるハッシュ関数とは,以下の機能を持ったアルゴリズムである

  1. 任意のデータ列を一定の長さのデータ列(ハッシュ値)に「要約」する
  2. ハッシュ値から元のデータ列を推測できない
  3. ひとつのハッシュ値に対して複数のデータ列が(実時間で)見つからない

ハッシュ関数はメッセージ認証符号(Message Authentication Code; MAC)や電子署名(digital signature)の中核技術のひとつであり,データの「完全性(Integrity)」を担保する重要な要素である。 特に3番目の「ひとつのハッシュ値に対して複数のデータ列が(実時間で)見つからない」という機能が破られると,そのハッシュ関数では完全性を担保できなくなってしまう。 これを「ハッシュ値の衝突問題」という。

SHA-1 ハッシュ値を力づくで攻略してみる

SHA-1 における「ハッシュ値の衝突問題」は2004年まで遡るが,当時の攻略法は SHA-1 アルゴリズムの危殆化を狙ったもので,しかもその後の進展は殆どなかった。

この状況が変わったのが2015年の “freestart collisions for SHA-1” 論文である。

ここで初めて「SHA-1 ハッシュ値を力づくで攻略」できる可能性が示された。 さらに2017年には Google によって最初の SHA-1 衝突例が公表された。

今回の “SHA-1 is a Shambles” の注目点は

  1. “chosen-prefix collision for SHA-1” なる手法により,衝突可能なデータを用意する際の自由度が高い
  2. ハッシュ値を攻略する際の計算機パワーの調達コストが比較的実用的なレベルまで下がった

の2つである。 特に2番目が重要で, “Nvidia GTX 1060GPU” × 900 の構成で2ヶ月ほどで攻略できたらしい。 コストにして 45k USD だそうだ1

OpenPGP / GnuPG は既に SHA-1 を捨てつつある

SHA-1 is a Shambles” では GnuPG が生成する公開鍵への電子署名をターゲットにしているが,実は現行の GnuPG 2.2 系は既に SHA-1 を捨てつつあり,電子署名に使うハッシュ関数の既定は SHA256 である(“SHA-1 is a Shambles” で指摘されているのはレガシー・バージョンの 1.4 系のほう)。

たとえば私が git コミットへの署名などで普段遣いしている OpenPGP 鍵は2013年に作ったものだが,鍵への署名は SHA256 で行っている。 私の公開鍵をチェックするには以下のコマンドを実行すればよい(何気に拙作の gpgpdump を宣伝しておくw)。

$ wget https://baldanders.info/pubkeys/spiegel.asc -O - | gpgpdump

また,次期 OpenPGP 標準となる RFC 4880bis では新しい V5 パケットを策定中だが,鍵指紋(key fingerprint)に使うハッシュ関数の既定が SHA256 になるようだ。 RFC 4880bis が正式に RFC 標準として公開されれば,かつての MD5 と同じく, SHA-1 は後方互換性のためだけに残されることになるだろう2

OpenPGP の実装は GnuPG だけではなく,今やシマンテック社のおまけプロダクトに成り下がった PGP をはじめ JsvaScriptRust などによる実装がある。 これらの実装が SHA-1 をどのように取り扱っているかは分からない。 どなたか教えて!

Git のコミット・ハッシュはどうなるのか

おそらく今回の件でもっとも議論を呼ぶのは git なんじゃないだろうか。 Git のコミット・ハッシュは SHA-1 を使って行われるが,ハッシュ値の衝突が比較的簡単にできるようになれば,ひとつのコミット・ハッシュに対して複数のコミットが重複してしまうという問題が現実的になるかもしれない(ならないかもしれない)。

ただ,コミットへの電子署名が正しく運用されているなら,なりすましに対してはある程度は抑止(防止ではない)できるだろう。

なので,個人的にはあまり心配はしていない。 Git の今後の活躍にご期待ください,といったところだろうか(笑)

ブックマーク

参考図書

photo
暗号技術入門 第3版 秘密の国のアリス
結城 浩 (著)
SBクリエイティブ 2015-08-25 (Release 2015-09-17)
Kindle版
B015643CPE (ASIN)
評価     

SHA-3 や Bitcoin/Blockchain など新しい知見や技術要素を大幅追加。暗号技術を使うだけならこれ1冊でとりあえず無問題。

reviewed by Spiegel on 2015-09-20 (powered by PA-APIv5)

photo
暗号化 プライバシーを救った反乱者たち
スティーブン・レビー (著), 斉藤 隆央 (翻訳)
紀伊國屋書店 2002-02-16
単行本
4314009071 (ASIN), 9784314009072 (EAN), 4314009071 (ISBN)
評価     

20世紀末,暗号技術の世界で何があったのか。知りたかったらこちらを読むべし!

reviewed by Spiegel on 2015-03-09 (powered by PA-APIv5)


  1. 単純に 1 USD = 110 JPY とするなら 45k USD = 4.95M JPY ほど。まぁ五百万円以下で攻略できてしまうわけですな。 ↩︎

  2. RFC 4880bis では SHA-1 は “SHOULD NOT create messages” となる。GnuPG 2.2.18 以降では,これが前倒しで実装されたわけだ。ちなみに GnuPG 2.2 系では MD5 は既にサポートされていない(1.4 系があるため)。 ↩︎