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

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

## ハッシュは元値を復元できないが、文字数が少ないと簡単にバレル
**hogehoge** という文字列は、どのような環境でも SHA-256では 
__4C716D4CF211C7B7D2F3233C941771AD0507EA5BACF93B492766AA41AE9F720D__
という文字列になります。

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

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

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

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

# レインボーテーブル作るのに、普通のデスクトップPCでどれくらい時間かかるのか
実際やってみた。
## ソース

```C#
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使うと結果が大きく変わるのか、だれか検証してくれると嬉しいです。

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