[解決済み] SHA-1はパスワードの保存に安全か？

質問

結論 SHA-1はプリ画像攻撃に対しては安全ですが、計算が簡単なため、ブルートフォース攻撃や辞書攻撃がしやすくなっています。(状況によっては、計算コストの高いハッシュ関数（bcryptなど）の方がよいかもしれません。

SHA-1 is broken"といった発言をよくする人がいるので、それが具体的にどういう意味なのか理解しようと思っています。私がSHA-1パスワードハッシュのデータベースを持っていて、最先端のSHA-1破壊アルゴリズムと10万台のマシンを持つボットネットを持つ攻撃者がそれにアクセスしたと仮定しましょう。(10万台の家庭用コンピュータを操るということは、1秒間に約10^15回の演算が可能であることを意味する）。このような場合、どの程度の時間が必要でしょうか。

1. あるユーザーのパスワードを知るには？
2. 指定されたユーザーのパスワードを確認しますか？
3. 全ユーザーのパスワードを確認しますか？
4. ユーザーの一人としてログインする方法を見つけるか？
5. 特定のユーザーでログインする方法は？

パスワードが塩漬けになっているとどう変わるのでしょうか？塩漬けの方法（プレフィックス、ポストフィックス、両方、あるいはxor-ingのようなもっと複雑なもの）は重要なのでしょうか？

以下、ググってみた結果、私の現在の理解です。何か誤解があれば回答で訂正をお願いします。

• ソルトがない場合、レインボーアタックですべてのパスワードをすぐに見つけることができます（極端に長いものを除く）。
• 十分に長いランダムなソルトがある場合、パスワードを見つける最も効果的な方法はブルートフォース攻撃または辞書攻撃です。衝突攻撃も前像攻撃も実際のパスワードを知る助けにはならないので、SHA-1に対する暗号攻撃はここでは役に立ちません。どのアルゴリズムを使うかはあまり重要ではなく、MD5やMD4を使ってもパスワードは同じように安全です（SHA-1ハッシュの計算速度が遅いので若干の違いはあります）。
• 1回のsha1処理に1000回、パスワードに大文字、小文字、数字（つまり60文字）が含まれると仮定して、「同じくらい安全」というのがどの程度安全かを評価します。つまり、攻撃者は10個の ¹⁵ *60*60*24 / 1000 ~= 10 ¹⁷ 1日あたりのパスワードの可能性 ブルートフォースアタックの場合、3時間で9文字まで、1週間で10文字まで、1年で11文字までの全パスワードをテストすることになります。(辞書を使った攻撃は、はるかに速く（コンピュータ1台で数時間）実行できますが、弱いパスワードしか見つけられません。
• ユーザーとしてログインする場合、攻撃者は正確なパスワードを知る必要はなく、同じハッシュ値になる文字列を見つければ十分である。これを第1次プリ画像攻撃と呼ぶ。私が調べた限りでは、SHA-1に対する前置イメージ攻撃は存在しない。(ブルートフォース攻撃では、2 ¹⁶⁰ 演算が必要であり、理論上の攻撃者は10個の ³⁰ 年かかる。理論的な可能性の限界は 約2 ⁶⁰ この場合、攻撃には数年かかる)。そこには SHA-1の縮小版に対する前画像攻撃 は無視できるほどの効果があります（80ステップの代わりに44ステップを使用する縮小SHA-1では、攻撃時間は2秒から3秒に短縮されます）。 ¹⁶⁰ 操作から2 ¹⁵⁷ ). SHA-1に対する衝突攻撃は、理論的には十分可能な範囲にある( 私が見つけたベスト から2へ短縮されました。 ⁸⁰ から2 ⁵² ) が、これらはパスワードハッシュに対しては、ソルティングなしでも役に立ちません。

つまり、SHA-1を使ったパスワードの保存は、完全に安全だと思われます。何か見落としがあったのでしょうか？

更新しました。 Marceloから、以下の記事について指摘がありました。 での2回目のプリ画像攻撃。 ¹⁰⁶ オペレーション . ( 編集する として トーマスの説明 この攻撃は仮定の構成であり、現実のシナリオには当てはまらない)。しかし、これが鍵の導出関数としてのSHA-1の使用にどのような危険をもたらすのか、私にはまだわからない。衝突攻撃や第二次プリ画像攻撃が、最終的に第一次プリ画像攻撃に転化できると考える一般的な正当な理由があるのでしょうか？

どのように解決するのか？

SHA-1が最も安全です。MD5でもいいし、MD4でもいいのですが、一部の投資家を不安にさせる可能性があります。理由は 広報 たとえ出力を160ビットや128ビットに切り詰めたとしても（ストレージコストを削減するため）、SHA-256のような「より優れた」ハッシュ関数を使用するのがベストです。いくつかの SHA-3 ラウンド2候補 SHA-1よりも高速で、より安全であることは間違いないようですが、まだ少し新しいので、今はSHA-256かSHA-512にこだわるのが安全な方法でしょう。その方がプロフェッショナルで慎重な印象を与えることができ、良いことです。

ただし、quot;as secure as you can get"とquot;perfect safe"は同じ意味ではないので注意してください。かなり長い説明なので、以下を参照してください。

既知の攻撃について

MD4、MD5、SHA-1に対する既知の攻撃は衝突に関するものであり、耐予像性には影響しません。MD4にはいくつかの弱点があり、HMAC/MD4を破ろうとするときに（理論的にのみ）利用できることが示されていますが、これはあなたの問題には当てはまりません。2つの ¹⁰⁶ KesleyとSchneierの論文にある第2次プリマージュ攻撃は、非常に長い入力（2,000文字以上）にのみ適用される一般的なトレードオフです。 ⁶⁰ バイト、つまり100万テラバイトです。106+60が160を超えることに注目してください。）

このメッセージの残りの部分は、あなたが使っているハッシュ関数（例えばSHA-1）が、攻撃者が利用できる特別な性質を持たないブラックボックス（quot;black box"）であると仮定します。これは、MD5やSHA-1というハッシュ関数が壊れているにもかかわらず、今あなたが持っているものです。

レインボーテーブルについて。

レインボーアタックとは、辞書攻撃やブルートフォースアタックをコストシェアリングしたものです。これは 時間-メモリトレードオフ は、1980年にヘルマンによって初めて記述された。仮に、あなたが N 可能なパスワード（これは辞書のサイズ、つまり2 ⁿ の出力を持つハッシュ関数をブルートフォースすることを考えるなら、その出力は n ビット)を事前に計算するタイムシェアリング攻撃がある。 N ハッシュ化されたパスワードを大きなテーブルに格納します。ハッシュ出力をソートすれば、1回のルックアップでパスワードを得ることができる。A レインボーテーブル は、そのテーブルをずっと少ないスペースで保存する賢い方法です。だけを格納するのです。 N/t ハッシュ化されたパスワードを、O( t ² ) のルックアップを行うことができます。レインボーテーブルでは、現実的に格納できるサイズよりもはるかに大きな事前計算されたテーブルを仮想的に扱うことができます。

しかし、レインボーであろうとなかろうと、攻撃者は少なくとも一度は完全な攻撃を実行しなければならないことに変わりはない。これは、いくつかの連続した最適化レイヤーと見なすことができます。

1. ブルートフォース/辞書攻撃には、以下のコストがあります。 N 各パスワードをクラックするための
2. 事前に計算されたテーブルを使えば、攻撃者はそのコストを支払うことになる N 一度 であり、以後は攻撃できる 多数 を、1パスワードあたりわずかな追加コストで利用できます。
3. 事前計算されたテーブルがレインボーテーブルである場合 N は多少大きくてもかまいません。 ストレージ が削減されます。のボトルネックは N は、ハードディスクの大きさではなく、攻撃者が使えるCPUパワーになります。

もし N が十分大きいので、ハッシュ化する際のCPUコストは N レインボーテーブルを使うか使わないかに関わらず、パスワードがおかしなことになれば、そのような攻撃は実行不可能になります。つまり、80ビット以上の出力を持つ（先入観に強い）ハッシュ関数があれば、ブルートフォース攻撃は実現不可能である。

塩について。

ソルトは事前計算を破るための手段です。上記の説明では、ソルトは攻撃者をステップ1に戻すものです。ソルトは攻撃者がO( N ) のコストを、攻撃された複数のパスワード間で比較することができます。事前に計算されたテーブル 必然的に レインボーテーブルは、もはや実現不可能である。

ハッシュ化されたデータが以下のようなものである場合、ソルティングが必要です。 パスワード つまり、ランダムな人間の脳内に収まるようなものであれば N 人間はパスワードを選んだり、覚えたりするのがとても苦手だからです。これは、多くのユーザーパスワードがその特別に選択された空間にあるという仮定のもと、潜在的なパスワードの縮小された空間（「辞書」）を使用することである。

したがって、ソルティングは少なくとも、攻撃者が事前に計算されたテーブル、特に事前に計算されたレインボーテーブルを使用することを防ぐことができます。これは、攻撃者が になります。 1つか2つのパスワードを破ることができても、他の1000のパスワードをわずかなオーバーヘッドで破られるようでは困ります。

また、ソルティングは広報活動にも有効です。

SHA-1のコストについて。

SHA-1の初歩的なコストは、64バイトのブロックをハッシュ化することです。これがSHA-1の仕組みです。データはパディングされた後、64バイトのブロックに分割されます。1つのブロックを処理するコストは、Intel Core2システムで約500クロックサイクルになります。MD5とMD4はより高速で、それぞれ約400サイクルと250サイクルを要します。最近のCPUは複数のコアを持つので、それに応じて倍率が上がることをお忘れなく。

例えば、ハッシュ関数に入るのは、実際には1つの128ビットソルトを40000回コピーしたもので、その後にパスワードそのものが続きます。これはパスワードのハッシュ化を、正当なユーザーと攻撃者の両方にとってより高価にします（私の例では10000分の1）。これが良いアイデアかどうかは、セットアップによります。デスクトップシステムのログインでは、これは良いことです。ユーザーは、パスワードのハッシュ化に1μsではなく10msかかったことに気づきません。しかし、攻撃者が負担するコストは1万分の1になります。1秒間に数千のクライアントを抱える共有サーバーでは、このコストは法外なものになるかもしれません。概念的には、正規のユーザーと攻撃者のコストを同じにすることは、最終的には良いセキュリティではありません。

オンライン攻撃について。

上記はすべて、打倒 オフライン の攻撃を受けます。オフライン攻撃とは、攻撃者がパスワードのテストに必要なデータをすべて持っている状態のことです。例えば、攻撃者はハッシュ化されたパスワードを保持しているデータベースのコピーを入手することができます。オフライン攻撃では、攻撃者は自分の計算資源によってのみ制限されます。逆に、オフライン攻撃では オンライン 攻撃は、攻撃者が推測するたびに、正直な検証者を通さなければならない攻撃です（例えば、攻撃者は攻撃されたシステムに単にログインしようとします）。オンライン攻撃は、1秒間に試行できるパスワードの数を制限することによって阻止されます。極端な例としては、暗証番号を3回間違えるとシャットダウンするスマートカードがある。

通常、パスワードのセキュリティのためには、攻撃者にオフライン攻撃をさせないようにシステムを整備する方がずっと得策です。ハッシュ化されたパスワードは、以前は世界で読み取り可能な /etc/password ファイルは、現在では /etc/shadow ファイルは、少数の特権的なアプリケーションを除いて、読み取りアクセスから保護されています。ここでの仮定は、もし攻撃者が /etc/shadow ということは、パスワードが不要になるほどの支配力があるのだろう...。