パスワードを忘れたことが引き起こすアルゴリズム思考

2日前、ウェブサイトにログインしようとしていたとき、よく使うパスワードを何回か試して失敗した後、「パスワードを忘れた場合」をクリックし、巧みに携帯電話番号を入力しました。すぐに、知らない番号から6桁の文字列を含むテキストメッセージが届きました。この数字の文字列をウェブサイトの入力ボックスに入力し、パスワードリセットプロセスに入りました。

[[253582]]

ここで、注意すべき小さな点があります。パスワードを忘れたときに、元のパスワードを返して頂けませんか? その代わりに、パスワードをリセットするための無関係なパスワードを教えて頂けるのですか?

少し前に、大手ホテルチェーンである華珠ホテルで再び在庫切れ事件が発生しました。社内のプログラマーのミスにより、データベースのパスワードがGithub上で公開され、何億人ものユーザーのアカウント開設記録やログイン情報（パスワードを含む）が盗まれる恐れがありました。これらのパスワードがプレーンテキストで保存されている場合、犯罪者はデータベースを盗んでプレーンテキストのパスワードを入手した後、あなたの電子メールアドレスとパスワードを簡単に使用して、さまざまなソーシャルネットワーキングサイトやさまざまな金融口座にログインしようとすることができます。多くの人がアカウントのセキュリティに十分な注意を払わず、金融アカウントとソーシャルアカウントの両方に同じパスワードを使用していることを知っておく必要があります。このような規模（数億件）でのアカウントパスワードの漏洩は、インターネットセキュリティにとって大きな災害となります。

サーバーはユーザーパスワードをプレーンテキストで保存しないようです。これにより、元のパスワードが単純に返されない理由も説明されます。だって彼らも知らないんだから。

では、データベースには何が保存されるのか、という疑問が生じます。データベースは何らかのアルゴリズムで暗号化された暗号文である必要があり、逆解読は不可能であるため、たとえハッカーがデータを入手したとしても、相対的なデータのセキュリティは確保されます。そしてこのアルゴリズムが次に紹介するハッシュアルゴリズムです。

ハッシュ アルゴリズムは、その不可逆的な解読可能性により、個人情報の保護と検証に広く使用されています。

ハッシュ アルゴリズムは比較的一般的な概念であり、多くの具体的な実装があり、最もよく知られているものには MD5、SHA256 などがあります。

ここで、MD5 を例に挙げてみましょう。広く使用されている暗号化ハッシュ関数である MD5 メッセージ ダイジェスト アルゴリズム (英: MD5 Message-Digest Algorithm) は、128 ビット (16 バイト) のハッシュ値を生成できます。

しかし、人間は実際にはバイナリに慣れていないため、128 ビットのバイナリは通常、同等の 32 ビットの 16 進数 (0 ～ 9、a ～ f で構成) として表されます。

ここまで述べてきましたが、このハッシュ値はどのようになっているのでしょうか?

Pythonの場合

ハッシュライブラリをインポートする
 
 m1 =ハッシュライブラリ.md5 ()
 m1.update("こんにちは")
印刷(m1.hexdigest())
 # 5d41402abc4b2a76b9719d911017c592

シェルを使えばさらに簡単

エコー -n hello | md5sum
 # 5d41402abc4b2a76b9719d911017c592 -

多くの人がハッシュと暗号化を混同していますが、実際には異なります。

• ハッシュ: ターゲット テキストを、同じ長さの不可逆な文字列に変換します。これはメッセージ ダイジェストとも呼ばれ、1 対多のマッピング関係です (つまり、複数のプレーン テキストが同じハッシュ値に対応する場合があります)。
• 暗号化: 対象テキストを、1対1のマッピング関係である、長さの異なる可逆暗号文に変換します（つまり、1つの暗号文は1つの平文にのみ対応します）。

ハッシュ アルゴリズムは 1 対多のマッピングであるため、異なる入力が同じハッシュ値を取得する可能性があり、その場合に「ハッシュ衝突」が発生します。

ハッシュ衝突の可能性は低いですが、一度発生すると深刻なセキュリティ上の問題が発生します。

ケース1

多くのネットワーク サービスでは、ハッシュ関数を使用してトークンを生成し、ユーザーの ID と権限を識別します。

2 人の異なるユーザーが同じトークンを取得すると、ハッシュ衝突が発生します。サーバーはこれら 2 人のユーザーを同一人物と見なすため、ユーザー B はユーザー A の情報を読み取ったり変更したりすることができ、間違いなく大きなセキュリティ リスクが生じます。

ケース2

私たちは皆、オンライン決済ツールを使ったことがあります。口座Aから口座Bに1,000元を送金すると、取引情報がインターネット上で送信され、ハッカーに傍受されてデータが改ざんされ、ターゲット口座がハッカー自身の口座に変更される可能性があります。このようにして、私たちのお金は盗まれます。

ハッシュ アルゴリズムを使用すると、転送情報はクライアントで処理できます。処理方法は、暗号化するデータを合意された文字列に追加し、それらをハッシュして情報サマリーを生成することです。

万が一、ネットワーク送信プロセス中にハッカーによってターゲットアカウントと送金金額が変更された場合、それが決済プラットフォームのサーバーに到達すると、送信された情報と以前に合意された文字列が再度ハッシュ化されます。次に、以前のハッシュと比較します。以前のデータは改ざんされているため、検証は失敗し、転送は失敗します。これにより、当社の資金の安全性が確保されます。

これまで、ハッシュの実際の応用について数多く説明してきました。ハッシュはセキュリティ分野で広く使用されていることがわかります。ではハッシュを解読するのは本当に不可能なのでしょうか?

もちろんあります。よくある例を 3 つ挙げます。

1. ブルートフォース法

ブルートフォース法とは、単純に大まかに原文をすべて列挙し、そのハッシュ値を計算し、その計算結果を一つずつ対象のハッシュ値と比較していく方法です。元のテキストには無数の可能性があるため、この方法は時間計算量が非常に高く、非常に望ましくありません。膨大な計算量を必要とするため、解読速度は非常に遅いです。14文字の英数字で構成されるパスワードを例にとると、1.24×10^25通りの可能性があり、たとえコンピューターが1秒間に10億回の演算を実行できたとしても、解読には4億年かかります。

ある日、ターゲットと同じハッシュ値を持つ元のテキストが見つかったとしても、ハッシュの競合が存在するため、この元のテキストが必ずしも答えであるとは限りません。複数の元のテキストが同じハッシュ値を持つ可能性があります。

2. 辞書方式

ブルートフォース列挙法について考えてみると、実際には無駄な計算が多すぎます。ほとんどの人のパスワードには、誕生日やイニシャルなど特別な意味を持つ文字が含まれています。よく使われる高頻度のパスワードの組み合わせを計算して保存しようとする人もいます。必要な場合は、データベース内の対応するハッシュ値を照会するだけです。

ブルートフォース列挙法が時間とスペースを交換するものであるならば、辞書法は時間とスペースを交換するものである。

データの保存には膨大なディスク容量が必要です。14 文字の文字と数字で構成されるパスワードを例にとると、生成されたパスワードの 32 ビット ハッシュ文字列比較テーブルは 2.64 * 10^14 TB のストレージ容量を占有します。パスワードの長さを増やしたり、記号を追加したりすると、必要な時間やディスク容量はさらに想像を絶するものになり、これら 2 つの方法が人々を満足させることが難しいことは明らかです。

 (62^14*192)/8/1024/1024/1024/ 1024 =2.64 * 10^14 (GB)

3. レインボーテーブル法

ブルートフォース列挙法と辞書法は、長さが短く組み合わせが単純なパスワードにのみ適しています。

次に、効率的なパスワード攻撃方法であるレインボーテーブルを紹介します。より複雑なパスワードにも使用できます。

レインボー テーブルは、本質的には辞書クラッキングの一種ですが、単純な平文とパスワードの対応ではありません。辞書の保存スペースを節約するために、レインボー テーブルでは計算可能なデータを省略しています。これを実現するための鍵は、ハッシュ暗号文スペースを平文文字スペースにマッピングする関数ファミリ Rk (k=1、2、3、4...) を設計することです。

レインボーテーブルの記憶領域は辞書方式の 1 k 倍ですが、コストとして演算回数が元の k 倍以上になります。

レインボー テーブルは、少なくともハッカーの目には、その名前が示すとおり美しいものです。次の表は、異なる文字セットで 7 文字以内のパスワード用に構築されたレインボー テーブルを示しています。レインボー テーブル内のハッシュ チェーンの長さと数は文字セットの増加とともに増加し、レインボー テーブルのサイズと生成時間も指数関数的に増加します。 7 桁の組み合わせは、虹の表面の前では数秒で解読されます。最も複雑な 7 桁のパスワードでも、1 時間以内に解読できます。通常のブルート フォース攻撃を使用すると、解読に 3 週間かかる場合があります。

この記事は比較的分かりやすく書かれています。インターネット上の優れた記事を参考にしており、ポピュラーサイエンスの記事と見なすことができます。深く理解したい場合は、さらに自分で調査して考える必要があります。