Sep23th

SHA-1に対する衝突攻撃とSha1coinへの影響

Top / SHA-1に対する衝突攻撃とSha1coinへの影響

2017年2月、SHA-1に対する衝突攻撃に実際に成功し、SHA-1ハッシュ値が一致するPDFファイルの組を作成することが出来たとGoogle Security Blogで公表されました。
https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

この衝突攻撃というのは、内容が異なりハッシュ値が一致する入力メッセージの組を見つけるのが困難という強衝突耐性(単に衝突耐性と呼ばれることもある)を突破するものです。
特定のハッシュ値を持つ入力メッセージを見つけることが困難という性質は弱衝突耐性と呼ばれ、それを突破しようとするのは原像攻撃と呼ばれています。

 

 

衝突攻撃で大きな影響を受ける代表的なものとしては電子署名が挙げられます。

電子署名には様々な形式のものが存在しますが、対象データを公開鍵暗号のプライベートキーで暗号化することを署名する行為とし、対応するパブリックキーで復号を行い対象データと比較することを署名の検証とすることで、特定の者しか署名できず不特定の者が検証できるということが実現されています。

また、公開鍵暗号の処理には時間がかかるため、対象データを一方向ハッシュ関数に通しその出力であるハッシュ値を署名行為やその検証作業の対象とすることで巨大なデータに対する実用性を高めるといった手法も広く使われています。
この場合は署名の検証に利用されるのはハッシュ値のみであるため、強衝突耐性を突破することが到底実現困難であることが求められます。

Google Security Blogで実例として挙げられているのは「shattered-1.pdf」と「shattered-2.pdf」で、ハッシュアルゴリズムにSHA-1を用いて「shattered-1.pdf」に署名をすると、その署名は「shattered-2.pdf」に対しても有効となるはずです。
そのためこれを悪用すると、署名者が意図しないデータに対しても有効になるような署名を入手したり、署名をしておきながら「それは別のデータに対する署名である」と主張して否認するといったことが可能になると思われます。

そういった状況なので、新たに電子署名を施す際にハッシュアルゴリズムにSHA-1を選択することはお勧めできませんし、電子署名のハッシュアルゴリズムにSHA-1が用いられている場合は署名が施された時期を考慮して判断する必要があるかと思われます。

 

 

次にSha1coinや関連が深い12桁版トリップにはどういった影響があるのかを考えます。

SHAtteredと名付けられた今回の衝突攻撃で用いられている手法はSha1coinや12桁版トリップに対しては使えないのではないかと思われますが、他にも様々な攻撃手法があるでしょうし、仮に強衝突耐性を突破できるとどうなるかを考えます。

 

 

まずは分かりやすい12桁版トリップについてです。

2ちゃんねる等の掲示板で使われているトリップのシステムでは、第三者によるなりすましの投稿を行いにくくするために、弱衝突耐性を利用しています。

強衝突耐性を突破できれば同じ出力(トリップ)になる入力(トリップキー)を複数知っているという状況になりますが、同じトリップになるトリップキーを複数知っているかどうかは重要ではないので、強衝突耐性が突破されても脅威にはならないです。

トリップは10桁版も古くから使われ今でも現役ですが(実装依存な面もありますが)元から強衝突耐性は無く、同じトリップになる異なるトリップキーの組を作るのは難しくないです。
例えば、文字コードがShift_JISの場合「#trip123」と「#tripアイウ」はどちらも「◆VVnkVrdjUc」になります。

 

 

いよいよSha1coinへの影響についてです。

Sha1coinでSHA-1アルゴリズムが利用されているのは採掘アルゴリズムで紹介したように、採掘(新たなブロックの発行)時に十分な作業を行ったかどうかの判定部分で、PoW(Proof of Work)と呼ばれる部分です。

一方向ハッシュ関数では入力データをメッセージと呼ぶのが慣例になっているので入力となるブロックヘッダを「M」あるいは「M1」と「M2」とし、PoWで用いられているアルゴリズムを「sha1coinhash()」、SHA-1ハッシュアルゴリズムを「sha1()」、SHA-256ハッシュアルゴリズムを2回繰り返したものを「sha256d()」として話を進めます。

Sha1coinのPoWでは「sha1coinhash(M)」と採掘難易度から計算される「Target」と呼ばれるものを256ビットの整数として比較し、「sha1coinhash(M)」が「Target」以下であれば採掘条件を満たしているとして新たなブロックとして認められ、「Target」より大きければ採掘条件を満たしていないとして引き続き条件を満たすブロックヘッダ「M」を探すことになります。

SHA-1の強衝突耐性を突破できた場合は異なるブロックヘッダ「M1」と「M2」に対して「sha1(M1)」と「sha1(M2)」が同じとなり、「sha1coinhash(M1)」と「sha1coinhash(M2)」もまた同じとなります。
確率は低いですがそれらが採掘条件を満たしていた場合は、ヘッダが「M1」のブロックとヘッダが「M2」のブロックの両方とも有効となり、それぞれ別のブロックチェーンとして扱われます。

ブロックヘッダの識別に用いられるのは「sha256d(M1)」と「sha256d(M2)」であり、「M1」と「M2」は「sha1()」や「sha1coinhash()」では特別な組み合わせですが、「sha256d()」ではそうではないです。
入力「M1」と「M2」が特別な組み合わせでない場合に「sha256d(M1)」と「sha256d(M2)」が一致する確率は2の128乗分の1と考えられ、2の32乗は42億を超え、2の64乗は42億の42億倍を超え、2の128乗は42億の42億倍の42億倍の42億倍を超える天文学的な数字であり、偶然一致するということはまずありえません。

異なる複数の新しいブロックがネットワーク上に存在してブロックチェーンがごく小規模な分岐を起こすということはそれほど珍しいことではなく、更に新しいブロックが十分続いたブロックチェーンが有力なものと判断されます。
有力ではないと判断されたブロックチェーンに含まれるブロックの採掘報酬は無効となり、QT版のウォレットでは「Generated but not accepted」といった感じのメッセージが表示され、採掘プールでは「Orphan」として扱われます。

以上の様に、PoWのアルゴリズムでは出力が同じになるような異なる入力の組を見つけられても問題が発生しないので、SHA-1の強衝突耐性を突破する衝突攻撃の影響は無いと考えられます。
PoWのアルゴリズムで重要なのは、特定の条件を満たす出力になるような入力を総当たり的な方法よりも効率的に見つける方法があるかどうかです。

ブロックヘッダの識別に用いられているハッシュのアルゴリズムは強衝突耐性を持つ必要があると思われますが、Sha1coinではBitcoinと同じくSHA-256を2回繰り返したものが用いられているので現時点(2017年4月)では特に問題は無いと考えられます。