20

SHA1アルゴリズムを使用してデータベースに保存されているパスワードを復号化 (実際の文字列を保持) することは可能ですか?

例: パスワードが で"password"あり、それが としてデータベースに保存されている場合、同じもの"sha1$4fb4c$2bc693f8a86e2d87f757c382a32e3d50fc945b24"を保持する可能性はありますか?"password"(string)"sha1$4fb4c$2bc693f8a86e2d87f757c382a32e3d50fc945b24"

4

3 に答える 3

28

SHA1は暗号化ハッシュ関数であるため、設計の意図は、あなたがやろうとしていることを避けることでした.

ただし、SHA1ハッシュを破ることは技術的に可能です。何がハッシュされたかを推測するだけで、これを行うことができます。もちろん、この強引なアプローチは効率的ではありませんが、それがほぼ唯一の方法です。

あなたの質問に答えるには: はい、可能ですが、かなりの計算能力が必要です。一部の研究者は、7 万ドルから 12 万ドルの費用がかかると見積もっています。

今日知る限り、ハッシュ化された入力を推測する以外に方法はありません。これは、 などの操作がmod入力から情報を削除するためです。計算するmod 5と、 が得られ0ます。入力は何でしたか？でしたか0、5それとも500？この場合、実際には「戻る」ことはできません。

于 2013-09-19T06:56:06.580 に答える
8

SHA1 は一方向ハッシュです。したがって、実際には元に戻すことはできません。

そのため、アプリケーションはこれを使用して、パスワード自体ではなく、パスワードのハッシュを保存します。

すべてのハッシュ関数と同様に、SHA-1 は大きな入力セット (キー) を小さなターゲット セット (ハッシュ値) にマップします。したがって、衝突が発生する可能性があります。これは、入力セットの 2 つの値が同じハッシュ値にマップされることを意味します。

明らかに、ターゲット セットが小さくなると、衝突の確率が高くなります。しかしその逆もまた、ターゲット セットが大きくなり、SHA-1 のターゲット セットが 160 ビットである場合に衝突確率が低下することを意味します。

Jeff Preshingは、使用するハッシュ アルゴリズムを決定するのに役立つHash Collision Probabilitiesに関する非常に優れたブログを書きました。ありがとうジェフ。

彼のブログでは、特定の入力セットの衝突の確率を示す表を示しています。

ハッシュ衝突確率表

ご覧のとおり、77163 個の入力値がある場合、32 ビット ハッシュの確率は 2 分の 1 です。

シンプルな Java プログラムは、彼のテーブルが示す内容を示します。

public class Main {

    public static void main(String[] args) {
        char[] inputValue = new char[10];

        Map<Integer, String> hashValues = new HashMap<Integer, String>();

        int collisionCount = 0;

        for (int i = 0; i < 77163; i++) {
            String asString = nextValue(inputValue);
            int hashCode = asString.hashCode();
            String collisionString = hashValues.put(hashCode, asString);
            if (collisionString != null) {
                collisionCount++;
                System.out.println("Collision: " + asString + " <-> " + collisionString);
            }
        }

        System.out.println("Collision count: " + collisionCount);
    }

    private static String nextValue(char[] inputValue) {
        nextValue(inputValue, 0);

        int endIndex = 0;
        for (int i = 0; i < inputValue.length; i++) {
            if (inputValue[i] == 0) {
                endIndex = i;
                break;
            }
        }

        return new String(inputValue, 0, endIndex);
    }

    private static void nextValue(char[] inputValue, int index) {
        boolean increaseNextIndex = inputValue[index] == 'z';

        if (inputValue[index] == 0 || increaseNextIndex) {
            inputValue[index] = 'A';
        } else {
            inputValue[index] += 1;
        }

        if (increaseNextIndex) {
            nextValue(inputValue, index + 1);
        }

    }

}

私の出力は次で終わります：

Collision: RvV <-> SWV
Collision: SvV <-> TWV
Collision: TvV <-> UWV
Collision: UvV <-> VWV
Collision: VvV <-> WWV
Collision: WvV <-> XWV
Collision count: 35135

35135 回の衝突が発生しましたが、これは 77163 回のほぼ半分です。30084 個の入力値でプログラムを実行した場合、衝突回数は 13606 回です。これは正確には 10 分の 1 ではありませんが、確率にすぎず、サンプル プログラムは完全ではありません。Aとの間のアスキー文字のみを使用するためzです。

最後に報告された衝突を確認してみましょう

System.out.println("VvV".hashCode());
System.out.println("WWV".hashCode());

私の出力は

86390
86390

結論：

SHA-1 値があり、入力値を取得したい場合は、ブルート フォース攻撃を試すことができます。これは、可能なすべての入力値を生成し、それらをハッシュして、所有している SHA-1 と比較する必要があることを意味します。しかし、それは多くの時間と計算能力を消費します。一部の人々は、一部の入力セットに対していわゆるレインボー テーブルを作成しました。しかし、これらはいくつかの小さな入力セットに対してのみ存在します。

また、多くの入力値が 1 つのターゲット ハッシュ値にマップされることに注意してください。したがって、たとえすべてのマッピングを知っていたとしても (入力セットが無限であるため、これは不可能です)、それがどの入力値であったかを言うことはできません。

于 2013-09-19T06:47:04.497 に答える
6

SHA-1 は複数のバイト シーケンスを 1 つにマップするため、ハッシュを「復号化」することはできませんが、理論的には衝突 (同じハッシュを持つ文字列) を見つけることができます。

現在、単一のハッシュを解読すると、約270 万ドル相当のコンピューター時間がかかるようです。

于 2013-09-19T06:58:52.773 に答える