37

数学関数を逆にすることができるように、なぜアルゴリズムを逆にすることができないのですか?可逆的でないアルゴリズムを作成するにはどうすればよいですか?

そして、レインボーテーブルを使用する場合、塩を使用してそれを割ることが不可能になるのはなぜですか?総当たり攻撃でレインボーテーブルを作成して生成する場合、可能な各プレーンテキスト値を(長さまで)発明します。これにより、可能なパスワードごとのソルトと可能なソルトごとにソルトが含まれることになります(ソルトとパスワード/テキストは1つのテキストとしてまとめるだけです)。

4

5 に答える 5

72

MD5は、暗号的に元に戻せないように設計されています。この場合、最も重要な特性は、ハッシュの逆を見つけることは計算上実行不可能であるということですが、任意のデータのハッシュを見つけることは簡単です。たとえば、数値を操作することだけを考えてみましょう(結局のところ、バイナリファイルは非常に長い数値として解釈される可能性があります)。

番号「7」があり、そのハッシュを取得したいとします。おそらく、ハッシュ関数として最初に試すのは「2を掛ける」ことです。後で説明するように、これはあまり良いハッシュ関数ではありませんが、ポイントを説明するために試してみます。この場合、番号のハッシュは「14」になります。それは計算するのがとても簡単でした。しかし今、それを元に戻すのがどれほど難しいかを見ると、それも同じくらい簡単であることがわかります!任意のハッシュが与えられると、それを2で割って、元の数を取得できます。これは良いハッシュではありません。ハッシュの全体的なポイントは、ハッシュを計算するよりも逆数を計算するのがはるかに難しいということです(これは、少なくとも一部のコンテキストで最も重要なプロパティです)。

それでは、別のハッシュを試してみましょう。これについては、クロック演算の考え方を紹介する必要があります。時計には、無限の数はありません。実際、0から11になります(0と12は時計上で同じであることを忘れないでください)。したがって、11に「1を追加」すると、ゼロになります。乗算、加算、べき乗のアイデアを時計に拡張できます。たとえば、8 + 7 = 15ですが、時計の15は実際には3です。したがって、時計では、8 + 7 = 3と言うでしょう!6 * 6 = 36ですが、時計では36 = 0です!したがって、6 * 6 = 0!さて、力の概念については、あなたは同じことをすることができます。2 ^ 4 = 16ですが、16は4です。したがって、2 ^ 4 = 4!さて、これがハッシュにどのように結びつくかです。ハッシュ関数f(x)= 5 ^ xを試してみてはどうでしょうか。ただし、クロック演算を使用します。ご覧のとおり、これはいくつかの興味深い結果につながります。前と同じように7のハッシュをとってみましょう。

5 ^ 7 = 78125であることがわかりますが、時計では5です(計算を行うと、時計を6510回ラップしたことがわかります)。したがって、f(7)=5が得られます。さて、質問は、私の番号のハッシュが5であると言った場合、私の番号が7であることがわかりますか?さて、一般的なケースでは、この関数の逆を計算することは実際には非常に困難です。私よりはるかに賢い人々は、特定のケースでは、この関数を逆にすることは、それを前に計算するよりもはるかに難しいことを証明しまし(編集:Nemoは、これは実際には「証明」されていないことを指摘しています。実際、あなたが得る唯一の保証は、多くの賢い人々がそうするための簡単な方法を見つけるために長い間試みてきたということです。彼らは成功しました。) この操作を逆にする問題は、「離散対数問題」と呼ばれます。より詳細なカバレッジについては、それを調べてください。これは、少なくとも優れたハッシュ関数の始まりです。

実世界のハッシュ関数でも、考え方は基本的に同じです。元に戻すのが難しい関数がいくつかあります。私よりもはるかに賢い人々は、MD5やその他のハッシュを設計して、それらを元に戻すのを確実に困難にしました。

さて、おそらく以前に、「逆数を計算するのは簡単でしょう!一致するものが見つかるまで、すべての数値のハッシュを取得するだけです!」という考えが思い浮かびました。さて、数がすべて12未満の場合、これは実行可能です。しかし、実際のハッシュ関数のアナログの場合、関係するすべての数が巨大であると想像してください。アイデアは、これらの大きな数のハッシュ関数を計算することはまだ比較的簡単ですが、すべての可能な入力を検索することははるかに速く難しくなるということです。しかし、あなたが偶然見つけたのは、それでも非常に重要なアイデアです。入力スペースを検索して、一致する出力が得られる入力を探します。レインボーテーブルは、アイデアのより複雑なバリエーションであり、入出力ペアの事前計算されたテーブルをスマートな方法で使用して、多数の可能な入力をすばやく検索できるようにします。

ここで、ハッシュ関数を使用してコンピューターにパスワードを保存しているとしましょう。アイデアはこれです:コンピュータは正しいパスワードのハッシュを保存するだけです。ユーザーがログインしようとすると、入力パスワードのハッシュを正しいパスワードのハッシュと比較します。それらが一致する場合、ユーザーが正しいパスワードを持っていると見なします。これが有利な理由は、誰かがあなたのコンピュータを盗んだ場合でも、彼らはあなたのパスワードにアクセスできず、そのハッシュだけにアクセスできるからです。ハッシュ関数は賢い人が逆になりにくいように設計されているため、ハッシュ関数からパスワードを簡単に取得することはできません。

攻撃者の最善の策は、ブルートフォース攻撃です。この攻撃では、一連のパスワードを試します。前の問題で12未満の数字を試すのと同じように、攻撃者は7文字未満の数字と文字で構成されるすべてのパスワード、または辞書に表示されるすべての単語を試す可能性があります。ここで重要なのは、たとえば、16文字のパスワードが多すぎてテストできないため、可能なすべてのパスワードを試すことができないということです。つまり、攻撃者はテストする可能性のあるパスワードを制限する必要があります。そうしないと、攻撃者はそれらのごく一部をチェックすることさえありません。

さて、ソルトに関しては、アイデアは次のとおりです。2人のユーザーが同じパスワードを持っている場合はどうなりますか?それらは同じハッシュを持ちます。あなたがそれについて考えるならば、攻撃者は実際にすべてのユーザーのパスワードを個別に解読する必要はありません。彼は、考えられるすべての入力パスワードを調べ、ハッシュをすべてのハッシュと比較するだけです。それらの1つと一致する場合、彼は新しいパスワードを見つけました。私たちが本当に彼に強制したいのは、すべての新しいハッシュを計算することですチェックしたいユーザーとパスワードの組み合わせ。これはソルトの考え方です。ハッシュ関数をユーザーごとにわずかに異なるものにするため、ユーザーはすべてのユーザーに対して事前に計算された値の単一のセットを再利用できません。これを行う最も簡単な方法は、ハッシュを取得する前に、各ユーザーのパスワードにランダムな文字列を追加することです。ランダムな文字列はユーザ​​ーごとに異なります。したがって、たとえば、パスワードが「shittypassword」の場合、ハッシュはMD5( "6n93nshittypassword")として表示され、パスワードが "shittypassword"の場合、ハッシュはMD5( "fa9elshittypassword")として表示される可能性があります。この小さな「fa9el」は「ソルト」と呼ばれ、ユーザーごとに異なります。たとえば、私の塩は「6n93n」です。今、パスワードに付けられたこの小さなビットは、コンピュータにも保存されます。パスワードXでログインしようとすると、コンピューターはMD5( "fa9el" + X)を計算し、保存されているハッシュと一致するかどうかを確認できます。

したがって、ログインの基本的な仕組みは変更されていませんが、攻撃者にとっては、MD5ハッシュのリストではなく、MD5の合計とソルトのリストに直面するというより困難な課題に直面しています。基本的に2つのオプションがあります。

  1. ハッシュがソルトされているという事実を無視して、ルックアップテーブルをそのまま使用してパスワードを解読しようとすることができます。ただし、実際にパスワードを解読する可能性は大幅に減少します。たとえば、「shittypassword」がチェックする入力のリストに含まれている場合でも、「fa9elshittypassword」は含まれていない可能性があります。以前に持っていたパスワードを解読する可能性のほんのわずかなパーセンテージを取得するために、彼らは桁違いに多くの可能なパスワードをテストする必要があります。

  2. ユーザーごとにハッシュを再計算できます。したがって、MD5(passwordguess)を計算するのではなく、ユーザーXごとに、MD5(Salt_of_user_X + passwordguess)を計算します。これにより、クラックしたいユーザーごとに新しいハッシュを計算する必要があるだけでなく、最も重要なこととして、事前に計算されたテーブル(たとえば、レインボーテーブルなど)を使用できなくなります。 Salt_of_user_Xは事前に用意されているため、テストするハッシュを事前に計算することはできません。

したがって、基本的に、事前計算されたテーブルを使用しようとしている場合、ソルトを使用すると、パスワードを解読するためにテストする必要のある入力が大幅に増加し、事前計算されたテーブルを使用していなくても、速度が低下します。 Nの係数。ここで、Nは保存しているパスワードの数です。

うまくいけば、これはあなたのすべての質問に答えます。

于 2011-07-06T23:35:44.587 に答える
28

1から9999までの2つの数字を考えてください。それらを追加してください。最後の桁を教えてください。

その情報から、あなたが最初に考えた数字を推測することはできません。これは、一方向ハッシュの非常に単純な例です。

ここで、同じ結果をもたらす2つの数値を考えることができます。これが、この単純な例がMD5やSHA1のような「適切な」暗号化ハッシュと異なるところです。これらのアルゴリズムでは、特定のハッシュを生成する入力を考え出すことは計算上難しいはずです。

于 2011-07-06T22:46:23.500 に答える
4

ハッシュ関数を元に戻せない大きな理由の1つは、データが失われるためです。

簡単な関数の例を考えてみましょう:'OR'。これを1と0の入力データに適用すると、1になります。しかし、答えが「1」であることがわかっている場合、元のデータをどのように元に戻すのでしょうか。できません。それは、1.1、あるいは0、1、あるいは1,0であった可能性があります。

塩漬けとレインボーテーブルも。はい、理論的には、考えられるすべてのソルトとパスワードを含むレインボーテーブルを作成できますが、実際には、それは大きすぎます。小文字、大文字、数字、および最大50文字の長さの12個の句読記号の可能なすべての組み合わせを試した場合、それは(26 + 26 + 10 + 12)^ 50 = 2.9 x 10^93の異なる可能性です。それは、目に見える宇宙の原子の数よりも多いです。

レインボーテーブルの背後にある考え方は、可能なパスワードの束のハッシュを事前に計算することであり、パスワードは50文字よりもはるかに短いため、それが可能です。そのため、前にソルトを追加する必要があります。パスワードの前に「57sjflk43380h4ljs9flj4ay」を追加する場合。誰かが「pa55w0rd」のハッシュをすでに計算しているかもしれませんが、「57sjflk43380h4ljs9flj4aypa55w0rd」のハッシュをすでに計算している人は誰もいません。

于 2011-07-06T22:47:20.923 に答える
1

md5で全体の結果が得られるとは思わないので、逆方向に作業してmd5-edであった元のものを見つけることはできません。

于 2011-07-06T22:35:18.327 に答える
1

md5は128ビット、つまり3.4 * 10^38の組み合わせです。

8文字の長さのパスワードの総数:

  • 小文字と数字のみ:36 ^ 8 = 2.8 * 10 ^ 12
  • 小文字と大文字と数字:62 ^ 8 = 2.18 * 10 ^ 14

パスワード用に8バイト、md​​5値用に16バイトを格納する必要があります。これは、エントリごとに合計24バイトです。

したがって、レインボーテーブルには約67000Gまたは5200000Gのストレージが必要です。パスワードを実際に把握できる唯一の理由は、人々が明白なパスワードを使用しているためです。

于 2011-07-06T22:47:29.570 に答える