イメージハッシュ衝突の作成

イメージハッシング

問題

あなたは顧客が写真をアップロードすることができますし、いくつかの迷惑な写真のセットを禁止するAPIを持っていると言う.あなたはすぐに1つのhash functions あなたは既に拒否リストに対して新しいアップロードをチェックする知っている.ハッシュ関数MD5 , SHA1 , または他のいくつかの暗号ハッシュ関数が気になるかもしれません.そして、これは写真が一つのビットによって決して変わらないと仮定します.
残念ながら私たちと私たちの仮説APIは非常に簡単に人間によって知覚される2つのイメージを作成するのは非常に簡単ですが、その暗号ハッシュは全く異なっている.次の2つの写真を例に挙げてください.

左手の写真にはSHA 1 SUMがあります

bb3ff9bdf224e8a058d3c4c3c5fb0dd45034519b  wedding.jpeg

右側の写真にはSHA 1の合計があります

ed14e6d3eb42ad66d5a5f49e554b9e0f765da0cd  wedding-compressed.jpeg

人間は、これらの2つの写真が同じイメージであると認めるでしょう.唯一の違いは、右の写真が1 %圧縮されているということです.この効果はまた、ピクセルの1行または列をトリミングすることによって、または、灰色から「わずかにより暗いか軽い灰色」にイメージの1つの画素を変更することによって、なしとげられることが可能である.

その他のハッシュ法

したがって、明らかに暗号ハッシュはここで私たちのために働くつもりはありません.人間が同じように知覚する能力を失うことなく、イメージを修正するにはあまりに多くの方法があります.この問題の1つの解決策はperceptual hashes . いくつかの知覚的なハッシュはAhash、Phash、およびDashです.ここで詳細に議論し、衝突/衝突発生器を提供するものはdifference hashing ( dhash ).
私が言うことができる限り、これらのハッシュの決定的な源は、博士ネールKrawetzによって書かれるブログです:http://www.hackerfactor.com/blog/ 特にDashの場合は、読むべきですthis post . あなたがそのポストを読むならば、Krawetz博士が私がそうするより深さにおいて行くように、次のセクションをスキップするのを自由に感じるべきです.

ハックワークス

非常に高いレベルでは、Dashアルゴリズムは以下の通りです.

ハッシュ出力であるBooleansの8 x 8配列を作成します

画像をグレースケールに変換する

画像を9 x 8ピクセルにリサイズする

各ピクセルの場合は、右側に左手のピクセルを比較する

右側が左より明るい場合は、対応するインデックスのハッシュ配列にTRUEを格納します

それ以外の場合はfalse

ハッシュ配列を平らにする

boolsをビットに変換し、文字列に変換する

その文字列をハッシュとして返す

たとえば、変換され圧縮されたときの上記の結婚式の写真は次のようになります.

結果は以下のハッシュになります.

[[ True False False False False  True False False]
 [ True False  True False False  True False False]
 [ True  True False  True False  True  True False]
 [ True False False  True  True False  True False]
 [ True False False  True  True False False  True]
 [ True False False  True  True False  True  True]
 [ True  True False False False False  True  True]
 [ True  True  True False False  True False False]]

ハッシュ行列( 0 , 0 )の最初の項目がTrue ( 0 , 0 )のイメージのピクセルが( 0 , 1 )でイメージのピクセルよりわずかに暗いので.
このハッシュ配列を折り畳み、文字列に変換すると、Dash値84a4d69a999bc3e4 . Krawetz博士(私がするより大きいデータセットを持っている)によると、この方法は比較的低い偽陽性と偽陰性率を持ち、テストされた他の知覚ハッシュよりかなり速いです.

衝突の作成

だから、Dashはかなりクールです!しかし、もし私が意図的に衝突を作成したいですか?私が2つのイメージを持っているならば、私は彼らに全く異なるイメージであるために人間によって知覚されている間、彼らに同じDash値が欲しいです?それは私が私自身に尋ねた質問であり、誰も答えなかった(私が言うことができる限り)答えたことに驚いた.誰かがそれに答えたとしても、フェアであるために、私はおそらくとにかく自分でそれをしようとしたでしょう.
私は、我々がマッチするハッシュをイメージと呼びますcollision target そして、我々が修正するつもりであるイメージmod image . 衝突を起こすアルゴリズムは以下の通りです.

ハッシュを得るcollision target

画像を9 x 8のサブイメージに分割する

のハッシュを反復処理するcollision target :

現在のハッシュの計算mod_image

trueの場合、現在の右側のサブイメージが現在より明るいことを確認します.それがないならば、それを明るくしてください!

falseの場合:現在の右側のサブイメージが現在より暗いことを確認します.それがそうでないならば、それを暗くしてください

サブイメージから復元MOD画像

リサイズの間に使用されたサンプリングが衝突を中断しないようにするために必要な繰り返しを繰り返します

例

左手のイメージがある次の2つのイメージを与えられますcollision target 右手はmod image :

我々は、上記のアルゴリズムを実行することができますし、次の画像を生成するとDashの衝突collision target :

これらのイメージの両方にはDashの値があります0193210ed49192c8

概念コードの証明

概念コードの証明はここで見つかります.https://github.com/LivingInSyn/image_collsion_gen
現時点では、このコードは非常に暗いイメージでは、事実上の明るい黒だけで結果が動作しません.もっと黒い.私は、それを彼らの状況で働くようにしようとする若干の時間を費やします.

結論

正確に攻撃者が発生した衝突がどこに最大の影響を及ぼすかはわからない.悪意のあるアクターが、他の合法的な写真を原因として、拒否されたサービスの状態になるようなリストを取得することができます.また、悪意のある俳優が許可リストの画像と衝突することによって拒否されることになっているイメージを投稿することができます.最終的には、単にこれらのハッシュが完璧であるか衝突耐性であると予想してはならないという証明です.
これは楽しいコードを書くことでした.It nerd sniped 私は数日間ハードハードとここから行く方法がたくさんあります.複数のハッシュタイプの間の衝突を生成するためにこのコードを拡大することは論理的な次のステップであるでしょう、あるいは、イメージをより少なく修正されないようにする方法を見つけるために.あなたがそれらを持っているならば、私はあなたの考えを聞きたいです:)