暗号学的ハッシュ関数を2回繰り返したハッシュ関数は暗号学的ハッシュ関数か？

Caution

この記事は暗号やハッシュ関数について詳しくない人が書いています。

誤りがあったら教えて下さい。予想が正しくても教えてくれると嬉しいです。

経緯(とあるMisskeyの片隅にて)

• Webサイトのパスワード認証のときに、クライアントで暗号化して、サーバーで復号してハッシュ関数にかけると、サーバーが生のパスワードに触れられてしまう問題があった
  • (一般的にこの問題は解決するべき問題とはされていない模様)
• ここで、クライアントでハッシュ化して暗号化し、サーバーで復号して再度ハッシュ関数にかけるようにすることで、この問題を解決できるのでは無いかという話になった
• ハッシュ関数を2回繰り返すことになるが、このハッシュ関数に相性問題のようなものは発生するのだろうか？と疑問になった

ここでの暗号学的ハッシュ関数というのは、以下の条件を満たすものを指す。(Wikipedia日本語版「暗号学的ハッシュ関数」より引用)

• あるハッシュ値から、元のメッセージを復元することが（事実上）不可能であること（原像計算困難性、一方向性）。
• 既知のメッセージAがあるとき、これとハッシュ値が同一となるメッセージBを計算することが（事実上）不可能であること（第二原像計算困難性、弱衝突耐性）。
• 同じハッシュ値となる、異なる2つのメッセージのペアを求めることが（事実上）不可能であること（強衝突耐性）。
• メッセージをほんの少し変えたとき、ハッシュ値は大幅に変わり、元のメッセージのハッシュ値とは相関がないように見えること。

自分なりに考えてみた。証明の書き方がなってなくてすみません。

• あるハッシュ値から、元のメッセージを復元することが（事実上）不可能であること（原像計算困難性、一方向性）。
  • これは2回適用でも成り立ちそう
  • もう少しちゃんと考えると、「hash(hash(A))からAを復元できるならば、hash(A)からAを復元できる」は成り立つので、この性質も成り立つ
    • $\neg P\to \neg Q⟺Q\to P$なので
    • hash(A)に対してhash関数を適用するとhash(hash(A))が得られ、それに対して「hash(hash(A))からAを復元する方法」を適用することでAが得られる
• 既知のメッセージAがあるとき、これとハッシュ値が同一となるメッセージBを計算することが（事実上）不可能であること（第二原像計算困難性、弱衝突耐性）。
  • 条件 : hash(hash(A)) = hash(hash(B))となるBについて、hash(B)を計算することは不可能
  • 結論 : hash(hash(A)) = hash(hash(B))となるBについて、Bを計算することは不可能
  • ¬結論を仮定して¬条件を導けば良い
    • $\neg P\to \neg Q⟺Q\to P$なので
  • つまり、「Bを計算することが可能ならば、hash(B)を計算することが可能」ということを示せば良く、これは明らかに成り立つ
• 同じハッシュ値となる、異なる2つのメッセージのペアを求めることが（事実上）不可能であること（強衝突耐性）。
  • 条件1 : hash(hash(A_1)) = hash(hash(B_1))となる相異なるhash(A_1)とhash(B_1)のペアを求めることは不可能
  • 条件2 : hash(A_2) = hash(B_2)となる相異なるA_2, B_2のペアを求めることは不可能
  • 結論 : hash(hash(A_c)) = hash(hash(B_c)) となる相異なるA_c, B_cのペアを求めることは不可能
  • ¬結論を仮定して¬条件1または¬条件2を導けば良い
    • $(\neg P\wedge \neg Q)\to \neg R⟺R\to \neg (\neg P\wedge \neg Q)⟺R\to (P\vee Q)$なので
  • つまり、「2重ハッシュで等しい相異なるペアを求めることができるならば、以下の2つのうちどちらかが成り立つ」ことを示せば良い
    • ¬条件1 : hash(hash(A_1)) = hash(hash(B_1))となる相異なるhash(A_1)とhash(B_1)のペアを計算できる
    • ¬条件2 : hash(A_2) = hash(B_2)となる相異なるA_2, B_2のペアを計算できる
  • 仮定より、hash(hash(A_c)) = hash(hash(B_c)) となる相異なるA_c, B_cのペアを計算できる
  • hash(A_c) = hash(B_c)の場合
    • ¬条件2が成り立つ
      • A_2 = hash(A_c), B_2=hash(B_c)と代入
  • hash(A_c)≠hash(B_c)の場合
    • ¬条件1が成り立つ
      • A_1 = A_c, B_1 = B_cと代入
• メッセージをほんの少し変えたとき、ハッシュ値は大幅に変わり、元のメッセージのハッシュ値とは相関がないように見えること。
  • まぁ成り立つわな
  • もう少しちゃんと考えると、「2重ハッシュと元の値に相関があるならば、1重ハッシュと元の値に相関がある」は成り立つので、この性質も成り立つ
    • $\neg P\to \neg Q⟺Q\to P$なので
    • 1重ハッシュであるhash(A)に対してhash関数を適用するとhash(hash(A))が得られ、これは2重ハッシュなので元の値に相関があることになる
    • つまり、「もう1回ハッシュ関数を適用すると相関が浮かび上がる」という相関が得られる

つまり、暗号学的ハッシュ関数を2回繰り返したハッシュ関数は暗号学的ハッシュ関数でありそうという結論になりました。自信はそこまで無いですが(主に量化周りとか)。