暗号学の教義について

昨日、ついにLamer Newsの最初のパブリックバージョンをリリースしました。これは、RedisをHacker Newsに似たサイトとして使用する実際の例であり、プログラミングの世界からのニュースに関する完全に独立したサイトのプロジェクトです。

このプロジェクトはコミュニティから好評を博しており、しばらくの間HNのトップに位置しています。 フィードバックをありがとう。

リリース後、データベース内のパスワードをハッシュするために使用するハッシュ関数を変更するためのいくつかのリクエストを受け取りました。

# Turn the password into an hashed one, using # SHA1(salt|password). def hash_password(password) Digest::SHA1.hexdigest(PasswordSalt+password) end 

このコードは、SHA1とソルトを使用しています。 読者が指摘したように、SHA1を非常に迅速に計算する方法があるため、これは最も安全な選択ではありません。 しばらくして、人々はつぶやき、コメントに同じ文を使用し始めました：「BCryptを使う」。 コードに新しい依存関係が追加されないように、ループ内でネストされたSHA1を使用することをお勧めします（READMEを確認する場合、目標の1つは、コードを単純にし、依存関係をできるだけ少なくすることです）。 そして、それは起こりました：暗号化の教義。 暗号プリミティブとその可能なアプリケーションおよび組み合わせについては議論せず、愚かにも「BCryptを使用」してください。 これらの同志の目には、プログラマーは暗号化について決して語ることのできないガイドラインを実行する愚かなドローンにすぎません。 しかし、それについては後で...

少し戻って、このすべての元の問題と、このコードの安全性を見てみましょう。

問題

この問題はかなり簡単に理解できますが、詳細に説明します。 パスワードを平文でデータベースに保存しないために、通常はハッシュされます。

 HP = HASH (password) # HP – hashed password,   

サーバー部分がユーザーを認証する必要がある場合、パスワードを平文で受け取り、再度ハッシュし、データベースにあるパスワードと比較します。 一致する場合、認証は成功です。

しかし、攻撃者（イブに電話しよう）がデータベースダンプを取得した場合はどうなりますか？ Evaはハッシュ化されたパスワードのセットを持っています。HP1、HP2、HP3などと呼びましょう。彼女の目標は、HPをPに戻すような攻撃を見つけることです。

ハッシュアルゴリズムは公開されているため、Eveが最初にすべきことは、一般的な単語で構成される辞書に適用することです。 そのような単語のハッシュがデータベースにあるものと一致する場合、パスワードが見つかります。 英語には多くの単語がないため、この攻撃は非常に簡単かつ迅速に実行できることに注意してください。

しかし、おそらくユーザーであるボブは、辞書にないパスワードを選択し、あまり長くはありません。

Eveは、たとえば最大6文字のパスワードのすべての組み合わせを生成し、ハッシュを計算できます。 この攻撃はより複雑な計算です。 パスワードが、たとえば6文字のバイナリ文字列である場合、合計256 ^ 6の組み合わせ、つまり281474976710656があります。

攻撃者が毎秒10億個のハッシュを計算できる場合（最新のGPUではこれが許可されており、破る必要はありません）、このパスワードをハッキングするには次が必要です。

 281474976710656 / 1000000000 = 281474  

わずか3日、または平均で半分です。 良くない！ 簡単すぎる。 もう1つの問題があります。ユーザーが256文字すべてを同じ確率で使用する可能性は低いです。 最悪の場合を考えてみましょう。小文字は26文字のみで、数字やその他の文字はありません。 今回は8文字のパスワードを使用します。

パスワードは26 ^ 8、つまり208 827 064 576です。今回は、208秒でパスワードを解読できます（平均でこの時間の半分）。

これは間違いなく良くありません。 毎秒10億回のハッシュを計算できる攻撃者がアクセスできないようにするために、アルファベットのパスワードはどのくらいの長さにする必要がありますか？

平均1024年で14文字が選択されます。 16文字の場合、攻撃者は1382824年を費やす必要があります。 12文字は1年半（平均して）抵抗しますが、これはほとんどのアプリケーションでは間違いなく十分ではありません。

では、SHA1はパスワードハッシュに対して安全ですか？ はい、ユーザーが14文字以上の強力なパスワードを選択した場合。 そうでなければ、非常に安全ではありません。 それはすべてパスワードの長さに依存し、ユーザーが短くて弱いパスワードを拾うという悪い習慣を持っていることは秘密ではありません。

しかし、それはさらに悪い

残念ながら、実際には、すべてが悪化しています。 たとえば、12個のパスワード文字に対する攻撃は即座に実行できます。約3年かけてすべての組み合わせのハッシュを計算し、P-> HPの形式のテーブルに書き込むことができます。

ただし、このようなテーブルは多くのスペース（正確には86,792テラバイト）を占有します。また、これは、P、HP（達成不可能なターゲット）のペアに1バイトしか費やさないほどコンパクトにデータを保存することも想定しています。 ただし、テーブルのサイズが合理的な制限内にある場合、これは本当の脅威です。

結論として、多くの場合、暗号化攻撃では、時間をかける代わりに、スペースを犠牲にして実行できます。

良いニュースは、同じアルゴリズムを使用してすべてのサイトに適した単一のテーブルの計算を防ぐ方法があるということです。 塩を使うことです。 Saltは、ハッシュする前にパスワードとともに追加する（パブリック）行です。 たとえば、ソルトが「lame」でパスワードが「foo」の場合、計算します

 HP = HASH ("foolame") 

したがって、テーブル攻撃の場合、Eveは同じソルトを使用したすべてのパスワードの組み合わせのハッシュを計算する必要があります。 そのようなテーブルは、異なるソルトを使用する別のサイトを攻撃するのに役に立たないでしょう。

ランダムソルト

もう少し改善して、HPだけでなくランダムソルトも保存できます。 ユーザーのアカウントを作成するとき、ユーザーのランダムなソルトも生成し、アカウントに保存します。 このアプローチでは、攻撃者は各ユーザーのテーブルを個別に計算する必要があるため、パスワードはさらに安全です。 また、もう1つの興味深い観察結果があります。グローバルなソルトが1つあると、パスワードが安全であっても、攻撃者の手に渡る可能性が高くなります。 個々の塩がある場合、これはほとんどありません。

ハッシュ関数を遅くする

ただし、すべてのテーブルベースの攻撃を防止したとしても、根本的な問題があります。パスワードが短く、Evaが1秒あたり10億回ハッシュを計算できる場合、問題が発生します。

この場合、何かを行うことができます。遅いハッシュ関数を使用します。

ソフトウェアとハ​​ードウェアの両方の計算が非常に遅いアルゴリズムがあります。 または、既存のアルゴリズムを使用して、ループで使用して非常に遅くすることもできます。

たとえば、Blowfishは遅いキー分離アルゴリズムを使用した暗号化アルゴリズムです（アルゴリズム自体はキースケジューリングを実行した後は非常に高速です）。したがって、Blowfishは、異なるキーを使用して多くのショートメッセージを暗号化する場合にのみ適していますが、高速にすることもできます。 1つのキーで大きなメッセージを暗号化する必要がある場合）。

Blowfishのキー共有アルゴリズムが遅いという事実は、BlowfishがHASHに適していることを示しています。

そこで、ニールス・プロボスとデビッド・マジエールは、パスワードのハッシュに使用できるBcryptと呼ばれるアルゴリズムを開発しました。 このアルゴリズムは1999年に導入され、Blowfishのキー分離アルゴリズムの修正版を使用しています。 Blowfish分析をBcryptに適用できるかどうかはわかりません。 また、Bcrypt自体がどの程度分析されたかわからないため、このアルゴリズムのセキュリティについてコメントすることはできません。

ただし、これは一般的な選択肢であり、ProvosとMazièresは2人の有名な暗号作成者であるため、アルゴリズムには明らかな欠陥はおそらくありません。

スローハッシュ関数の使用を開始するとすぐに、攻撃者は問題を抱え始めます。 そのため、たとえば、Bcryptを構成して、高速または低速にすることができます。 速度が非常に遅いため、優れたハードウェアを使用しても1秒あたり1,000ハッシュ以上を計算できない場合、ユーザーにとってはおそらく許容範囲内ですが、Eveにとってはすでに実用的ではありません。 たとえば、小文字のみを使用した8文字のパスワード：

 26 ^ 8 / 1000 / 3600 / 24 / 365 = 6,6218627782 

8文字のパスワードを解読した場合の3.3年（平均）。 おそらくまだ十分なセキュリティではありませんが、ほんの数秒よりも優れています。

ただし、辞書攻撃からはまだ保護されていないことに注意してください 。 ユーザーが一般的な単語を選択した場合、すべてが絶望的です。 それでも、妥当な時間で30kハッシュを計算できます。

ドグマについて

現時点では、いくつかの興味深い考えを検討しています。 たとえば、不正なパスワードでユーザーを保護するようなハッシュスキームはありません。 ユーザーに大文字や数字、その他の文字をパスワードに追加することをユーザーに強制することは非常に重要です（アプリケーションにとってセキュリティが重要な場合）。

物事の仕組みを理解することは重要です。 これはスムーズに次の考えに私たちを導きます。 「use bcrypt」コーラスの後、SHA1の繰り返しに基づく別のソリューションを使用できると答えました。 しかし、どうやら、多くの人はプログラマーが暗号を理解すべきではないと考えています。 彼はそれを教義として認識しなければなりません。 もしあなたが教義を持っているなら、あなたは貧しいプログラマーになるでしょう。 システムにbcryptサポートがないが、それに取り組む必要がある場合はどうでしょう。 簡単なスキームを提案しました：

 SHA1 (SHA1 (SHA1 (...( SHA1 (password | salt)))) 

なんて異端だ！ このようにハッシュ関数をチェーンすることは安全ではないことを理解していないので、私は愚か者と見なされました。 しかし、少し考えるとどうなりますか？

SHA1はハッシュ関数です。 roundsと呼ばれる小さなステップで構成され、何度も繰り返し実行されます。 これはブロック暗号ではないため、キーの分離はありません。この関数は、入力ビットストリームを固定長の出力値に単純に圧縮します。

多くの暗号アルゴリズムは、より単純な関数を使用して数回実行し、その効果を高めることができるという考えに基づいていることを理解することが重要です。 この概念は非常に重要であるため、さらにラウンドを追加すると、アルゴリズムに対する攻撃が非実用的になることがあります。 暗号学者は、完全なラウンド数のオプションがどれだけ強力かをよりよく理解するために、より脆弱な形式でアルゴリズムを分析するために、ラウンド数を減らしたアルゴリズムのバリアントを使用する場合があります。

では、なぜ多くのラウンドを追加しないのですか？ 遅いです。 アマチュアの暗号作成者であっても、安全で遅いアルゴリズムを開発できます。 優れた暗号作成者は、セキュリティと速度の妥協点を見つけることができます。

しかし...ラウンドの概念がわかったため、SHA1にはキー分離アルゴリズムがなく、関数の出力値はその入力のみに依存し、SHA1は反転の可能性を考慮して設計されていないことを知っています（ハッシュによる元の値の取得）。

したがって、私が提案したSHA1スキーム（SHA1（SHA1（..）））がまさにそれを行い、SHA1にラウンドを追加することは非常に自然です。 SHA1の基本的な特性から、SHA1の千倍にネストされた呼び出しに相当し、簡単に計算できる関数SHA1000を計算することは計算上不可能であることがわかります。

SHA1（SHA1（..））の結果は、 SHA1内にさらにラウンドを追加することと同じではないことに注意してください。前処理と後処理もあります。

そして、あなたは何を知っていますか？ 今朝、RFC2898に記述されているPBKDF1アルゴリズムがまさに私が提案したことを行うことを発見しました。

あなたに道を見せてくれることを非常に喜んでいる人もいますが、彼らをよく見ると、彼らが何について話しているのか分からないことがわかります。 実績のある標準を使用し、安全なコードを書いてみてください。また、心を使って、暗号化とプリミティブの結合方法について学習してください。 ドグマ-それは吸う。

プログラマーが自分のブロック暗号を発明し、それを便利な目的のためにどこかで使用しようとするのは良い考えではないかもしれません。 このために特別に訓練された人々がいます。 暗号化を使用して実行できる個々の「ブリック」、プロトコルを正しく使用する方法などを理解することははるかに重要です。

結論として、人々が私に無礼であるとき、同時に彼らが正しいなら、私は冷静であると言いたいです。 Ar慢は、それが心に合っていれば、それほど大きな問題ではありません。 instead慢が無知と出会うなら、これは実に悲しい話です。