Help us understand the problem. What is going on with this article?

普通のデスクトップでハッシュを普通に総当たりで突破するのに、どれくらい時間がかかるのか調べてみた

More than 1 year has passed since last update.

はじめに

パスワードを単純にハッシュに保持しても、簡単に復元できてしまいます。
というのは、ハッシュというのは 総当たりに非常に弱い からです。

ハッシュは元値を復元できないが、文字数が少ないと簡単にバレル

hogehoge という文字列は、どのような環境でも SHA-256では
4C716D4CF211C7B7D2F3233C941771AD0507EA5BACF93B492766AA41AE9F720D
という文字列になります。

つまり、あるサイトのパスワードをhogehogeにしている人は、
そのサイトがハックを受けた場合、攻撃者がハッシュ済パスワードを、
4C716D4CF211C7B7D2F3233C941771AD0507EA5BACF93B492766AA41AE9F720D
で検索すれば、パスワードをhogehogeにしている人を簡単に見つける事ができます。

そうすると、攻撃者はそのサイトで不正ログインできることはもちろん、
同時に盗んだメアドをなどを使って、他のサイトにパスワードリスト攻撃をして、
他のサイトでも不正ログインができてしまいます。

※まぁ、パスワードがhogehogeの人は、ハックされなくてもパスワードリスト攻撃の餌食ですが

ハッシュの攻撃方法

上記の方法を辞書攻撃と言いますが、辞書攻撃を拡大させて、
全部の文字を辞書登録しちゃえばよくね?
という発想の攻撃をレインボーテーブル攻撃と言います。

レインボーテーブル作るのに、普通のデスクトップPCでどれくらい時間かかるのか

実際やってみた。

ソース

static void Main(string[] args)
{
    double 桁数 = 0;

    if (args.Length == 0 || Double.TryParse(args[0],out 桁数) == false ){return;}

    double maxnum = Math.Pow(256 , 桁数);

    Console.WriteLine(maxnum.ToString("#,##0") + "件を総当たり");

    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
    sw.Start();

    System.Security.Cryptography.SHA256 crypto = new System.Security.Cryptography.SHA256CryptoServiceProvider();

    var task = Task.Factory.StartNew(() =>
    {
        for (double i = 1; i < maxnum; i++)
        {
            byte[] bytes = NumToBytes(i);
            byte[] hashedBytes = crypto.ComputeHash(bytes);
            string hashedText = BytesToString(hashedBytes);
            //Console.WriteLine(i.ToString() + ":" + hashedText);
        }
    });
    task.Wait();
    sw.Stop();
    Console.WriteLine(sw.Elapsed);
}

/// <summary>
/// 整数値をByte配列に変換
/// 例) 286 → {0x01,0x1E}
/// </summary>
/// <param name="num">変換される整数値</param>
/// <returns></returns>
static byte[] NumToBytes(double num)
{
    List<byte> byteList = new List<byte>();

    while(num != 0)
    {
        byteList.Add((byte)(num % 256)) ;
        num = Math.Floor(num / 256);
    }

    byte[] bytes = new byte[byteList.Count];
    for (int i = 0; i <= byteList.Count - 1; i ++ )
    {
        bytes[i] = byteList[i];
    }

    return bytes;
}

/// <summary>
/// Byte配列を文字列変換(UTF-8)
/// </summary>
/// <param name="Bytes"></param>
/// <returns></returns>
static string BytesToString(byte[] Bytes)
{
    StringBuilder hashedText = new StringBuilder();
    for (int i = 0; i < Bytes.Length; i++)
    {
        hashedText.AppendFormat("{0:X2}", Bytes[i]);
    }
    return hashedText.ToString();
}

前提

  • 文字は半角英数記号のみ
  • ハッシュアルゴリズムはSHA-256
  • マルチスレッドで実施
  • あくまでハッシュ値作成のみ。DBに書き出したりファイルにI/Oしたりはしないで時間計測
  • 実行環境は Core i7-2600(ハイパースレッディング8コア)+ 8GB + Win7 Enterprise 64bit
  • GPUなんて効果なモノは積んでないのでGPU処理はしない

※半角英数記号って255文字あるんですね!知りませんでした。
※Cf. https://msdn.microsoft.com/ja-jp/library/cc392379.aspx

結果

1文字総当たり:00:00:00.0295976(約30ミリ秒)
2文字総当たり:00:00:00.8476741(約848ミリ秒)
3文字総当たり:00:03:14.3769255(約3分14秒)
4文字総当たり:12:42:35.4586924(約12.5時間)
5文字総当たり:終わらない・・・(推定 135.6
6文字総当たり:終わらない・・・(推定 95

※5文字・6文字は終わりそうになかったので、推定で算出。
※文字が1文字増えると、論理的には256倍になるので、n-1 文字総当たり時間に x 256した

結論

半角英数記号すべてが入りうるパスワードのSHA-256ハッシュは5文字を超えると総当たり突破は現実的ではない。
単にPCを並列にしても、6文字の総当たりに100台のPCで1年かかるので、電気代とかのコストに見合わないような気もしもします。

※GPU使うと結果が大きく変わるのか、だれか検証してくれると嬉しいです。

補足

次は、①数字だけ、②半角英数字だけ、③半角英数字+よくある記号だけで総当たりしたときの突破時間を調べたいと思います。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away