結論：SHA-1 は原像攻撃に対して安全ですが、計算が容易であるため、ブルートフォース攻撃や辞書攻撃を仕掛けやすくなります。(SHA-256 などの後継でも同様です。) 状況によっては、計算コストが高くなるように設計されたハッシュ関数 (bcrypt など) の方が適している場合があります。
「SHA-1 は破られている」という発言をよく耳にする人がいますが、それが具体的に何を意味するのか理解しようとしています。SHA-1 パスワードハッシュのデータベースがあり、最先端の SHA-1 破りアルゴリズムと 10 万台のマシンからなるボットネットを持つ攻撃者がそれにアクセスしたとします。(10 万台の家庭用コンピュータを制御できるということは、1 秒あたり約 10^15 回のオペレーションを実行できることを意味します。) 攻撃者がそれを破るにはどのくらいの時間がかかりますか?
- find out the password of any one user?
- find out the password of a given user?
- find out the password of all users?
- find a way to log in as one of the users?
- find a way to log in as a specific user?
How does that change if the passwords are salted? Does the method of salting (prefix, postfix, both, or something more complicated like xor-ing) matter?
Here is my current understanding, after some googling. Please correct in the answers if I misunderstood something.
- If there is no salt, a rainbow attack will immediately find all passwords (except extremely long ones).
- If there is a sufficiently long random salt, the most effective way to find out the passwords is a brute force or dictionary attack. Neither collision nor preimage attacks are any help in finding out the actual password, so cryptographic attacks against SHA-1 are no help here. It doesn't even matter much what algorithm is used - one could even use MD5 or MD4 and the passwords would be just as safe (there is a slight difference because computing a SHA-1 hash is slower).
- To evaluate how safe "just as safe" is, let's assume that a single sha1 run takes 1000 operations and passwords contain uppercase, lowercase and digits (that is, 60 characters). That means the attacker can test 10156060*24 / 1000 ~= 1017 potential password a day. For a brute force attack, that would mean testing all passwords up to 9 characters in 3 hours, up to 10 characters in a week, up to 11 characters in a year. (It takes 60 times as much for every additional character.) A dictionary attack is much, much faster (even an attacker with a single computer could pull it off in hours), but only finds weak passwords.
- To log in as a user, the attacker does not need to find out the exact password; it is enough to find a string that results in the same hash. This is called a first preimage attack. As far as I could find, there are no preimage attacks against SHA-1. (A bruteforce attack would take 2160 operations, which means our theoretical attacker would need 1030 years to pull it off. Limits of theoretical possibility are around 260 operations, at which the attack would take a few years.) There are preimage attacks against reduced versions of SHA-1 with negligible effect (for the reduced SHA-1 which uses 44 steps instead of 80, attack time is down from 2160 operations to 2157). There are collision attacks against SHA-1 which are well within theoretical possibility (the best I found brings the time down from 280 to 252), but those are useless against password hashes, even without salting.
In short, storing passwords with SHA-1 seems perfectly safe. Did I miss something?
Update: Marcelo pointed out an article which mentions 2 106回の演算で2回目の原像攻撃. （編集：としてトーマスは説明するただし、この攻撃は仮想的な構成であり、現実のシナリオには当てはまりません。) ただし、これが SHA-1 をキー導出関数として使用することの危険性を示唆するものかどうかは、まだわかりません。衝突攻撃または第 2 原像攻撃が最終的に第 1 原像攻撃に変わる可能性があると考えるのに、一般的に十分な理由があるのでしょうか。
ベストアンサー1
質問に対する簡潔な答えは、SHA-1は最も安全だということです。MD5でもMD4でも大丈夫ですが、一部の投資家を不安にさせる可能性があります。広報、出力を160ビットまたは128ビットに切り捨てる場合でも（ストレージコストを節約するため）、SHA-256などの「より良い」ハッシュ関数を使用するのが最善です。SHA-3 ラウンド2候補SHA-1 よりも高速であると同時に、おそらく「より安全」であると思われますが、まだ新しいため、現時点では SHA-256 または SHA-512 を使用する方が安全です。プロフェッショナルで用心深い印象を与えられるので、良いことです。
「可能な限り安全」は「完全に安全」と同じではないことに注意してください。 かなり長い説明については以下を参照してください。
既知の攻撃について:
MD4、MD5、SHA-1 に対する既知の攻撃は衝突に関するもので、原像暗号耐性には影響しません。MD4 には、HMAC/MD4 を破る際に (理論上のみ) 悪用される可能性のある弱点がいくつかあることがわかっていますが、これはあなたの問題には当てはまりません。Kesleyと Schneier の論文にある2 106秒の原像暗号攻撃は、非常に長い入力 (2 60バイト、つまり 100 万テラバイト -- 106+60 が 160 を超えることに注意してください。ここで、このトレードオフに魔法のようなものは何もないことが分かります) にのみ適用される一般的なトレードオフです。
このメッセージの残りの部分では、使用するハッシュ関数 (例: SHA-1) が、攻撃者が使用できる特別なプロパティを持たない「ブラック ボックス」であると想定しています。これは、MD5 や SHA-1 などの「壊れた」ハッシュ関数でも、現在存在するものです。
レインボーテーブルについて:
「レインボー攻撃」は、実際には辞書攻撃やブルートフォース攻撃のコストシェアリングです。これは、時間とメモリのトレードオフ1980年にヘルマンによって初めて説明されました。いいえ可能なパスワード（辞書のサイズ、または2ん出力が次のハッシュ関数を総当たり攻撃すると仮定すると、んビット）を事前に計算するタイムシェアリング攻撃があります。いいえパスワードをハッシュ化し、大きなテーブルに保存します。ハッシュ出力をソートすると、1回の検索でパスワードを取得できます。レインボーテーブルテーブルを省スペースで保管する賢い方法です。いいえハッシュ化されたパスワードはO(t2 ) ルックアップ。レインボー テーブルを使用すると、実際に保存できるサイズよりもはるかに大きい事前計算済みテーブルを仮想的に処理できます。
ただし、レインボーであろうとなかろうと、攻撃者は完全な攻撃を少なくとも 1 回は実行する必要があります。これは、いくつかの連続した最適化レイヤーとして考えることができます。
- ブルートフォース/辞書攻撃にはコストがかかるいいえ各パスワードを解読するため。
- 事前に計算されたテーブルでは、攻撃者はそのコストを支払ういいえ 一度そしてその後攻撃できる多くのパスワード 1 つあたりの追加コストが非常に少ないパスワード。
- 事前計算されたテーブルがレインボーテーブルである場合、いいえ多少大きくなる可能性がある。ストレージコストが削減されます。いいえ攻撃者がハードディスクのサイズではなく、集めることができる CPU パワーになります。
もしいいえハッシュのCPUコストが十分に大きいいいえパスワードを盗むのが馬鹿げているのであれば、レインボーテーブルが使用されているかどうかに関係なく、そのような攻撃は実行不可能です。つまり、80 ビット以上の出力を持つ (原像耐性のある) ハッシュ関数があれば、ブルートフォース攻撃を実行不可能にするのに十分です。
塩について:
ソルトは事前計算を無効化する方法です。上記の説明では、ソルトは攻撃者をステップ1に戻します。ソルトは攻撃者がO(いいえ）攻撃されたパスワード間のコスト。事前に計算されたテーブル、ましてやレインボーテーブルはもはや実現可能ではありません。
ハッシュ化されたデータが以下の場合、ソルトが必要になります。パスワードつまり、ランダムな人間の脳に収まるものなら、いいえパスワードの有効性は非常に低くなる可能性があります。人間はパスワードの選択と記憶が本当に苦手です。これが「辞書攻撃」です。つまり、多くのユーザー パスワードがその特別に選択された空間にあるという仮定のもと、パスワード候補の縮小空間 (「辞書」) を使用する攻撃です。
したがって、ソルトは少なくとも攻撃者が事前に計算されたテーブル、特に事前に計算されたレインボーテーブルを使用することを防ぐことができます。これは、攻撃者がだろう1 つか 2 つのパスワードを破ることができるが、追加のオーバーヘッドをほとんどかけずに 1000 個の他のパスワードを破られることは望ましくない。
また、塩漬けは広報にも良いです。
SHA-1 コストについて:
SHA-1 の基本的なコストは、64 バイトのブロックをハッシュするコストです。SHA-1 はこのように動作します。データがパディングされ、64 バイトのブロックに分割されます。1 つのブロックを処理するコストは、Intel Core2 システムで約 500 クロック サイクルで、これは 1 つのコアの場合です。MD5 と MD4 はより高速で、それぞれ約 400 サイクルと 250 サイクルです。ほとんどの最新の CPU には複数のコアがあるため、それに応じて乗算することを忘れないでください。
一部のソルト スキームでは、巨大なソルトが規定されています。たとえば、ハッシュ関数に実際に入力されるのは、1 つの 128 ビット ソルトの連続コピー 40000 個で、その後にパスワード自体が続きます。これにより、正当なユーザーと攻撃者の両方にとって、パスワード ハッシュのコストが高くなります (私の例では 10000 倍)。これがよいアイデアかどうかは、設定によって異なります。デスクトップ システムでのログインの場合、これはよいことです。ユーザーは、パスワードのハッシュに 1 マイクロ秒ではなく 10 ミリ秒かかったことに気付かないでしょう。しかし、攻撃者にとっては、コストが 10000 倍と非常に顕著に増加しています。1 秒あたり数千のクライアントがある共有サーバーでは、合計コストが法外になる可能性があります。概念的には、正当なユーザーと攻撃者に対してハードルを同じ係数で上げることは、最終的にはよいセキュリティとは言えませんが、特定の状況では価値のあるアイデアになる可能性があります。
オンライン攻撃について:
上記のすべては敗北についてですオフラインオフライン攻撃は、攻撃者がパスワードを「テスト」するために必要なすべてのデータを持っている攻撃です。たとえば、攻撃者はハッシュ化されたパスワードを含むデータベースのコピーを入手できます。オフライン攻撃では、攻撃者の制限は計算リソースのみです。逆に、オンライン攻撃とは、攻撃者が推測するたびに正直な検証者を経由しなければならない攻撃です (たとえば、攻撃者は攻撃されたシステムにログインしようとするだけです)。オンライン攻撃は、1 秒あたりに試行できるパスワードの数を制限することで阻止されます。極端な例としては、間違った PIN を 3 回入力するとシャットダウンするスマート カードがあります。
通常、パスワードのセキュリティについては、攻撃者がオフライン攻撃を仕掛けられないようにシステムを整える方がはるかに効果的です。Unix システムでは、これが行われています。以前は誰でも読み取り可能な/etc/passwordファイルにあったハッシュ化されたパスワードは、現在では、/etc/shadow一部の特権アプリケーションを除いて読み取りアクセスから保護されたファイルにあります。ここでの前提は、攻撃者が読み取り可能な場合/etc/shadow、攻撃者はシステムを十分に制御でき、パスワードはもう必要ないということです...