57

Java のアルゴリズムは次のとおりです。

public String getHash(String password, String salt) throws Exception {
    String input = password + salt;
    MessageDigest md = MessageDigest.getInstance(SHA-512);
    byte[] out = md.digest(input.getBytes());
    return HexEncoder.toHex(out);
}

塩分はわかっているものとします。パスワードが辞書単語の場合と辞書単語でない場合のブルートフォースのタイミングを知りたいです。

4

3 に答える 3

122

あなたの場合、ハッシュアルゴリズムを壊すことは、ハッシュアルゴリズムで衝突を見つけることと同じです。つまり、パスワード自体を見つける必要はなく (プリイメージ攻撃になります)、有効なパスワードのハッシュと等しいハッシュ関数の出力を見つけるだけで済みます (つまり、「衝突」)。誕生日攻撃を使用して衝突を見つけるには、O(2^(n/2)) 時間かかります。ここで、n はハッシュ関数の出力長 (ビット単位) です。

SHA-2 の出力サイズは 512 ビットであるため、衝突を検出するには O(2^256) 時間かかります。アルゴリズム自体に巧妙な攻撃がないことを考えると (現在、SHA-2 ハッシュ ファミリで知られているものはありません)、これがアルゴリズムを破るのに必要なことです。

2^256 が実際に何を意味するかを理解するには: 現在、宇宙 (全体!!!) の原子の数はおよそ 10^80、つまりおよそ 2^266 であると考えられています。32 バイトの入力 (あなたのケースでは妥当です - 20 バイトのソルト + 12 バイトのパスワード) を想定すると、私のマシンは 65536 (=2^16) の計算に ~0.22 秒 (~2^-2 秒) かかります。したがって、2^256 の計算は 2^240 * 2^16 の計算で実行されます。

2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years

これを数百万年と呼ぶのもばかげています。そして、何千ものハッシュを並行して計算する地球上で最速のハードウェアでは、それほど良くはなりません. 人間の技術では、この数を許容できるものにまで処理することはできません。

したがって、ここでは SHA-256 のブルート フォーシングを忘れてください。次の質問は、辞書の単語についてでした。このような脆弱なパスワードを取得するために、従来はレインボー テーブルが使用されていました。レインボー テーブルは通常、事前に計算されたハッシュ値のテーブルにすぎません。アイデアは、考えられるすべてのハッシュを事前に計算してその入力と共に保存できる場合、指定されたハッシュを検索して取得するのに O(1) かかるということです。そのための有効なプレイメージ。もちろん、これほど膨大な量のデータを保存できるストレージ デバイスは存在しないため、これは実際には不可能です。このジレンマは、メモリ時間のトレードオフとして知られています. 非常に多くの値しか格納できないため、典型的なレインボー テーブルには、中間リダクション関数を使用した何らかの形式のハッシュ チェーンが含まれています (これについては、ウィキペディアの記事で詳しく説明されています)。

そんなレインボーテーブルを無理にするための対策がソルトでした。攻撃者が特定のソルトのテーブルを事前計算するのを思いとどまらせるには、ユーザーごとのソルト値を適用することをお勧めします。ただし、ユーザーは安全で完全にランダムなパスワードを使用していないため、salt を知っていて、単純な試行錯誤方式で一般的なパスワードの大規模な辞書を反復処理した場合に、どれほど成功するかは依然として驚くべきことです。自然言語とランダム性の関係はエントロピーで表されます。典型的なパスワードの選択は一般にエントロピーが低く、完全にランダムな値には最大のエントロピーが含まれます。

一般的なパスワードのエントロピーが低いため、一般的なパスワードの比較的小さなデータベースのパスワードをユーザーの 1 人が使用する可能性が比較的高い可能性があります。それらをグーグルで検索すると、そのようなパスワードデータベースのトレントリンクが見つかり、多くの場合、ギガバイトサイズのカテゴリに分類されます. 攻撃者がなんらかの制限を受けていなければ、通常、このようなツールを使用して成功するのは数分から数日の範囲です。

そのため、通常、ハッシュとソルティングだけでは十分ではなく、他の安全メカニズムもインストールする必要があります。PKCS#5で説明されている PBKDF2 などの人為的に速度を落としたエントロピー誘発方式を使用する必要があり、特定のユーザーがパスワードの入力を再試行する前に待機期間を強制する必要があります。0.5 秒から始めて、試行が失敗するたびにその時間を 2 倍にすることをお勧めします。ほとんどの場合、ユーザーはこれに気付かず、平均で 3 回以上失敗することはありません。ただし、アプリケーションを攻撃しようとする悪意のある部外者の速度が大幅に低下します。

于 2011-07-21T21:30:51.513 に答える
35

パスワードが辞書単語の場合と辞書単語でない場合のブルートフォースのタイミングを知りたいです。

辞書パスワード

概算図: 約 1,000,000 の英単語があり、ハッカーが 1 秒あたり約 10,000 SHA-512 ハッシュを計算できる場合 (更新: CodesInChaos のコメントを参照してください。この見積もりは非常に低いです)、1,000,000 / 10,000 = 100 秒. そのため、1 人のユーザーの単語辞書のパスワードをクラックするには、1 分強かかります。ユーザーが辞書にある2 つの単語を連結した場合、数日で終わりますが、攻撃者が十分に注意を払っていれば、その可能性は十分にあります。それ以上になると、タフになり始めます。

ランダムパスワード

パスワードが大文字と小文字の英数字の真にランダムなシーケンスである場合、長さ N の可能なパスワードの数は 60^N です(60 の可能な文字があります)。今回は反対方向の計算を行います。質問します:特定の期間が与えられた場合、クラックできるパスワードの長さはどれくらいですか? 次の式を使用してください。

N = Log60(t * 10,000)ここで、t は秒単位のハッシュの計算に費やされた時間です (ここでも 1 秒あたり 10,000 ハッシュを想定しています)。

1 minute:    3.2
5 minute:    3.6
30 minutes:  4.1
2 hours:     4.4
3 days:      5.2

したがって、3 日あれば、パスワードが 5 文字であれば解読できます。

これはすべて非常に大ざっぱですが、アイデアはわかります。更新: 以下のコメントを参照してください。これよりもはるかに長いパスワードをクラックすることは実際には可能です。

何が起きてる？

いくつかの誤解を解いてみましょう。

  • ソルトによって hash の計算が遅くなることはありません。各ユーザーのパスワードを個別にクラックする必要があるだけであり、事前に計算されたハッシュ テーブル (バズワード: rainbow tables ) は完全に役に立たなくなります。事前に計算されたハッシュ テーブルがなく、パスワード ハッシュを 1 つだけクラックしている場合、ソルティングは何の違いもありません。

  • SHA-512 は総当たり攻撃が困難になるようには設計されていません。BCrypt、PBKDF2、SCryptなどのより優れたハッシュ アルゴリズムは、計算に時間がかかるように構成でき、平均的なコンピューターは 1 秒間に 10 ～ 20 個のハッシュしか計算できない場合があります。まだ読んでいない場合は、パスワードハッシュに関するこの優れた回答を読んでください。

  • 更新: CodesInChaos のコメントに書かれているように、適切なハードウェアを使用して SHA-512 ハッシュを計算すると、エントロピーの高いパスワード (約 10 文字) でさえブルートフォースされる可能性があります。

受け入れられた回答に関するメモ:

2014 年 9 月の時点で受け入れられている回答は正しくなく、危険なほど間違っています。

あなたの場合、ハッシュアルゴリズムを壊すことは、ハッシュアルゴリズムで衝突を見つけることと同じです。つまり、パスワード自体を見つける必要はありません (プリイメージ攻撃になります)...誕生日攻撃を使用して衝突を見つけるには、O(2^n/2) の時間がかかります。ここで、n はハッシュの出力長です。ビット単位で機能します。

誕生日攻撃は、特定のハッシュのクラックとはまったく関係ありません。実際、これはプリイメージ攻撃の完璧な例です。この式と次の数段落では、危険なほど高く、まったく意味のないアタック タイムの値が得られます。上で示したように、ソルトされた辞書のパスワードを数分でクラックすることは完全に可能です。

典型的なパスワードのエントロピーが低いため、ユーザーの 1 人が、一般的なパスワードの比較的小さなデータベースのパスワードを使用する可能性が比較的高い可能性があります...

そのため、通常、ハッシュとソルティングだけでは十分ではなく、他の安全メカニズムもインストールする必要があります。PKCS#5 で説明されている PBKDF2 などの人為的に速度を落としたエントロピー誘導方法を使用する必要があります...

はい、計算が遅いアルゴリズムを使用してください。しかし、「エントロピー誘導」とは何ですか? 低エントロピーのパスワードをハッシュに渡しても、エントロピーは増加しません。エントロピーを保持する必要がありますが、ゴミのパスワードをハッシュで改善することはできません。そのようには機能しません。PBKDF2 を介して入力された脆弱なパスワードは、依然として脆弱なパスワードです。

于 2014-09-24T22:12:20.207 に答える
8

変数が多すぎるため、この質問に対する答えは 1 つではありませんが、SHA2 はまだ実際にはクラックされていないため (「暗号化ハッシュ関数の有効期間」を参照)、パスワードを格納するために使用するアルゴリズムとしては依然として優れています。ソルトは、辞書攻撃やレインボー テーブルからの攻撃を防ぐため、優れています。ソルトの重要性は、パスワードごとに一意であることです。ハッシュされたパスワードを保存するときは、[128 ビット ソルト][512 ビット パスワード ハッシュ] のような形式を使用できます。

攻撃する唯一の実行可能な方法は、さまざまな可能性のあるパスワードのハッシュを実際に計算し、最終的にハッシュを照合して正しいものを見つけることです。

1 秒間にどれだけの数のハッシュを実行できるかを考えると、Bitcoin が適切な例だと思います。ビットコインは SHA256 を使用しており、簡単に言えば、生成するハッシュが多いほど、より多くのビットコイン (実際のお金と交換できる) が得られるため、人々はこの目的のために GPU を使用するよう動機付けられています。ハードウェアの概要を見ると、わずか 150 ドルの平均的なグラフィック カードで 1 秒あたり 2 億以上のハッシュを計算できることがわかります。パスワードが長くて複雑であるほど、時間がかかります。200M/s で計算すると、8 文字の英数字 (大文字、小文字、数字) のすべての可能性を試すには、約 300 時間かかります。パスワードが適切なものまたは一般的な英語の単語である場合、リアルタイムはおそらく少なくなります。

そのため、コンテキストで確認する必要があるセキュリティはすべてそうです。攻撃者の動機は何ですか？アプリケーションの種類は何ですか？それぞれにランダムなソルトを含むハッシュを持つことで、何千ものパスワードが危険にさらされた場合に対してかなり良い保護が得られます.

できることの 1 つは、ハッシュ手順を遅くすることで、ブルート フォース保護を追加することです。パスワードのハッシュは 1 回だけで、攻撃者は何度もハッシュ化する必要があるため、これは有利に機能します。典型的な方法は、値を取得し、それをハッシュし、出力を取得し、再度ハッシュするということを一定量の反復で行うことです。たとえば、1,000回または10,000回の反復などを試すことができます。これにより、攻撃者が各パスワードを見つけるのが何倍も遅くなります。

于 2011-07-21T20:50:52.327 に答える