Coding4Fun - 試玩 SHA256 密碼雜湊暴力破解

2023-06-03 09:50 PM

早上提到我的 SCH (Self-Contained Html) SideProject，文件保護是「用密碼字串 SHA256 雜湊當金鑰加隨機 IV 對內容做 AES256 加密」，但因解密會在瀏覽器執行，JavaScript 端解密邏輯是公開的祕密，有心想破解的人，寫支程式用不同密碼嘗試解密，就是最簡單的暴力破解。

嚴格來說，「用密碼字串的 SHA256 雜湊產生金鑰」不算專業設計，理由是 SHA256 運算不夠複雜，擋不住當代 CPU/GPU 的強大運算能力。要有效保護密碼，通常建議使用 PBKDF2、Scrypt、Bcrypt、Argon2... 等密碼專用雜湊演算法，它們的共同特色是每次計算雜湊要花的資源是 SHA256 的 N 倍，對駭客而言，暴力攻擊成本將被放大數百萬倍，幾已無實現可能。延伸閱讀：密碼要怎麼儲存才安全？該加多少鹽？-科普角度

講到這裡，我不免好奇：從專業角度，用 SHA256 強度不足有可能被攻破，但實際難度如何，能擋下我這種非專業駭客用 i5 發動攻擊嗎？感覺挺好玩的，不如就來試試。

SCH 目前使用的加密演算法如下。用密碼字串產生 SHA256 雜湊(byte[32] 256bit)當 AES Key、Random().NextBytes() 隨機生成 byte[16] 當 IV 執行 AES256 加密 1KB 的資料：

using System;
using System.IO;
using System.Security.Cryptography;
using System.Text;

public class CodecNetFx
{
    private class AesKeyIV
    {
        public Byte[] Key = new Byte[32];
        public Byte[] IV = new Byte[16];
        public AesKeyIV(string strKey)
        {
            var sha = SHA256.Create();
            var hash = sha.ComputeHash(Encoding.ASCII.GetBytes(strKey));
            Array.Copy(hash, 0, Key, 0, 32);
            new Random().NextBytes(IV);
        }
    }
    public static (byte[] data, byte[] iv) AesEncrypt(string key, byte[] data)
    {
        var keyIv = new AesKeyIV(key);
        var aes = Aes.Create();
        aes.Key = keyIv.Key;
        aes.IV = keyIv.IV;
        using (var ms = new MemoryStream())
        {
            using (var cs = new CryptoStream(ms,
                aes.CreateEncryptor(), CryptoStreamMode.Write))
            {
                cs.Write(data, 0, data.Length);
                cs.FlushFinalBlock();
                return (ms.ToArray(), keyIv.IV);
            }
        }
    }

    public static byte[] AesDecrypt(string key, byte[] data, byte[] iv)
    {
        var keyIv = new AesKeyIV(key);
        var aes = Aes.Create();
        aes.Key = keyIv.Key;
        aes.IV = iv;
        using (var ms = new MemoryStream(data))
        {
            using (var cs = new CryptoStream(ms,
                aes.CreateDecryptor(), CryptoStreamMode.Read))
            {
                using (var sr = new StreamReader(cs))
                {
                    using (var dec = new MemoryStream())
                    {
                        cs.CopyTo(dec);
                        return dec.ToArray();
                    }
                }
            }
        }
    }
}

程式模擬三種密碼字元組合：純數字(0-9)、數字加大小寫字母、數字字母加符號(ASCII 32 ~ 126)，指定不同密碼長度，程式會試遍所有可能的字串組合，來測能否猜到隨機產生的密碼並測量跑完所有組合的時間。

我的第一個版本，靠遞迴列舉所有組合，解密部分則用 Task.Run() 跑平行運算(延伸閱讀：新時代 .NET ThreadPool 程式寫法)火力全開，

using System.Diagnostics;

int pwdLength = 3;
string pwdCharSet = "*"; // N-Number, A-AlphaDigit, *-Any
int minThreads = Environment.ProcessorCount * 4;
int maxQueueItems = 65536;
if (args.Length > 0)
    int.TryParse(args[0], out pwdLength);
if (args.Length > 1)
    pwdCharSet = args[1];
if (args.Length > 2)
    int.TryParse(args[2], out minThreads);
if (args.Length > 3)
    int.TryParse(args[3], out maxQueueItems);

// 密碼字元範圍：ASCII 32~126
char[] pwdChars;
switch (pwdCharSet.ToUpper())
{
    case "N":
        pwdChars = "0123456789".ToArray();
        break;
    case "A":
        pwdChars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".ToArray();
        break;
    default: // All
        pwdChars = Enumerable.Range(32, 95).Select(i => (char)i).ToArray();
        break;
} 

// 原始資料：1KB byte[]
var plain = new byte[1024];
// 隨機密碼：4字元
var password = new string(Enumerable.Range(0, pwdLength).Select(i => pwdChars[new Random().Next(pwdChars.Length)]).ToArray());
var ecn = CodecNetFx.AesEncrypt(password, plain);
Console.ForegroundColor = ConsoleColor.Yellow;
Console.WriteLine("SAH256 產生 AES256 金鑰暴力破解測試");
Console.ResetColor();
Console.WriteLine($"密碼長度: {pwdLength}");
Console.WriteLine($"可用密碼字元: {new string(pwdChars)}");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine($"隨機密碼: {password}");
Console.ResetColor();
Console.WriteLine($"AES加密內容: {BitConverter.ToString(ecn.data.Take(16).ToArray())}...");
Console.WriteLine($"AES-CBC IV: {BitConverter.ToString(ecn.iv)}");

var cts = new CancellationTokenSource();
var sw = new Stopwatch();
var startTime = DateTime.Now;
long total = Enumerable.Range(1, pwdLength).Sum(i => Convert.ToInt64(Math.Pow(pwdChars.Length, i)));
long queued = 0;
long completed = 0;
ThreadPool.SetMinThreads(minThreads, 16);
Task.Run(() =>
    {

        // 檢查 CancellationTokenSource 是否已經被取消
        while (!cts.Token.IsCancellationRequested)
        {
            Console.CursorLeft = 0;
            Console.Write($"{(DateTime.Now - startTime).TotalSeconds,3:n0}s | {ThreadPool.ThreadCount,7} | {ThreadPool.PendingWorkItemCount,7} | {completed:n0} / {total:n0} ({completed * 1.0 / total:p0})");
            Thread.Sleep(1000);
        }
    }, 
    cts.Token //允許還沒執行前取消(例如：還在 Queue 排隊時就取消)
);
var tasks = new List<Task>();
sw.Start();
explore(string.Empty);

Task.WaitAll(tasks.ToArray());
Console.WriteLine();
cts.Cancel();
sw.Stop();
Console.Write($"已嘗試{completed:n0}種組合，");
Console.ForegroundColor = ConsoleColor.Cyan;
Console.WriteLine($"耗時: {sw.ElapsedMilliseconds:n0}ms");
Console.ResetColor();


// DFS 產生所有組合
void explore(string pfx)
{
    var pwd = pfx;
    if (!string.IsNullOrEmpty(pwd))
    {
        // 雖然 ThreadPool 待處理 Work Item 沒有上限，但為避免耗用過多資源，加上限制
        while (ThreadPool.PendingWorkItemCount > maxQueueItems)
        {
            Thread.Sleep(1);
        }
        queued++;
        tasks.Add(Task.Run(() =>
        {
            try
            {
                var dec = CodecNetFx.AesDecrypt(pwd, ecn.data, ecn.iv);
                if (dec.SequenceEqual(plain))
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                    Console.WriteLine($" ** 發現密碼：{pwd} **");
                    Console.ResetColor();
                }
            }
            catch { }
            finally
            {
                Interlocked.Increment(ref completed);
            }
        }));
    }
    if (pfx.Length < pwdLength)
    {
        foreach (var c in pwdChars)
        {
            explore(pfx + c);
        }
    }
}

若只用純數字，4、5、6、7 位密碼破解時間為 250ms、1,904ms、17s、302s。

計算到七位數字時，建立 Task 丟給 ThreadPool 的方式雖然無腦又好寫，但需要建立超過 1,111 萬個物件，記憶體不時會衝上 3GB (等 GC 時再降下來)，CPU 也無法吃滿 100% (CPU 總使用率約 85% 到 90%，.NET 程式部分不到 70%)

思考了一下，我想到可以用 IEnumerable + yield return 節省記憶體，再配合 Parallel.ForEach() 平行運算，修改成第二版：

//... 略 ...
long errCount = 0;
long completed = 0;
Task.Run(() =>
    {
        // 檢查 CancellationTokenSource 是否已經被取消
        while (!cts.Token.IsCancellationRequested)
        {
            Console.CursorLeft = 0;
            Console.Write($"{(DateTime.Now - startTime).TotalSeconds,3:n0}s | {completed:n0} / {total:n0} ({completed * 1.0 / total:p0}) | {errCount:n0}");
            Thread.Sleep(1000);
        }
    },
    cts.Token //允許還沒執行前取消(例如：還在 Queue 排隊時就取消)
);
var tasks = new List<Task>();
sw.Start();
Parallel.ForEach<string>(explore(""), new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount * 2 },
(pwd) =>
{
    if (token.IsCancellationRequested)
        return;
    try
    {
        var dec = CodecNetFx.AesDecrypt(pwd, ecn.data, ecn.iv);
        if (dec.SequenceEqual(plain))
        {
            Console.ForegroundColor = ConsoleColor.Red;
            Console.WriteLine($" ** 發現密碼：{pwd} **");
            Console.ResetColor();
        }
    }
    catch { 
        Interlocked.Increment(ref errCount);
    }
    finally
    {
        Interlocked.Increment(ref completed);
    }
});

Console.WriteLine();
cts.Cancel();
sw.Stop();
Console.Write($"已嘗試{completed:n0}種組合，");
Console.ForegroundColor = ConsoleColor.Cyan;
Console.WriteLine($"耗時: {sw.ElapsedMilliseconds:n0}ms");
Console.ResetColor();

IEnumerable<string> explore(string currPwd)
{
    if (!string.IsNullOrEmpty(currPwd))
        yield return currPwd;
    if (currPwd.Length < pwdLength)
    {
        foreach (var c in pwdChars)
        {
            foreach (var res in explore(currPwd + c))
                yield return res;
        }
    }
}

yield return + Parallel.ForEach() 版在記憶體使用量及 CPU 使用率方面完勝遞迴 + Task.Run() 版本：

實測速度，6 位數字小輸 5 秒，7 位數字則快了 86s，整體效能有所改善。

而由以上結果，用 7 位甚至 8 位純數字字串 SHA256 產生 AES 256 金鑰，一台普通 12 代 i5 不到一小時內就能破解。

至於密碼混合字母及符號的測試數據如下：

分析測試數據，耗用時間跟字元組合數量成正比，大致可推算出 50 次/ms，以此預估破解不同長度密碼所需時間如下表：

若用我的小 PC 跑破解，純數字 1 ~ 10 字元最多兩天、英數字 1 ~ 6 字元 13 天可破、英數字加符號 1 ~ 5 字元則需兩天，都在可接受範圍內；程式還有一堆待優化的地方(例如：使用字典檔常用字元縮小範圍、找更快的加密函式庫(至少 .NET 內建 API 比 BouncyCastle 快)、避開解密失敗 Catch Exception 的效能衝擊...)，故以上數據要視為「非專業駭客使用家常設備發動的二流攻擊」，若是專業人士搭配八卡機，破解速度或許可再提高數十到數百倍。

至此，我們可得到結論：SCH 目前用 SHA256 產生金鑰的寫法確實不夠安全，靠家用 PC 跑非專業程式都有機會破解。我有想到一些簡單但能提高破解難度的點子，後面再來試試。

2023-06-04 更新：經過簡單加鹽翻炒，已能將破解難度提升數千倍。

Comments

# 2023-06-03 10:41 PM by KunYi

不是直接加鹽就可以得到一個長度長很多的密碼，直接提高計算難度

# 2023-06-03 11:26 PM by Jeffrey

to KunYi, SCH 是在瀏覽器端用 JavaScript 解密，鹽也必須送到前端才能順利解密，因此鹽無法對使用者保密，不算直接提升計算難度，但可讓彩虹表破功，確實有效果。

# 2023-06-04 12:15 AM by Alexhsu

如果增加標點符號的話，難度是不是又更高了？

# 2023-06-04 05:23 PM by Asasin

會這麼好破是因為你在對自己實施「已知演算法」攻擊，在不知道你怎麼創造密鑰的前提下，這方式是安全的，但在知道的前提下，那個hash只是為了變成256位，實際套用到aes的強度跟原本密碼hash前一樣，當然強度不夠。

# 2023-06-04 05:29 PM by Jeffrey

to Asasin, 本案例是用瀏覽器在客戶端解密，金鑰產生邏輯無法保密，另外如Word/PDF，也是演算法已知，面臨類似考驗。

# 2023-06-05 08:03 AM by Anonymous

如果用顯卡來跑呢？

# 2023-06-06 11:22 AM by Milk

自己設定密碼長度和字元限制，基本上就自己規定了key space的大小，倒不是sha-256或AES的錯。這一大串程式基本等效於「在0~10000」之間猜一個數字，和AES或sha-256一點關係都沒有。板主知道為甚麼要用雜湊函數嗎?

# 2023-06-06 12:05 PM by Jeffrey

to Milk，「在0~10000」之間猜一個數字，雜湊用 MD5 或 SHA512，加密用 DES 或 AES256，破解難度大不相同。在密碼長度跟字元限制相同的前題下，雜湊跟加密演算法會決定安全強度。這也是為什麼 MD5、SHA1、DES 近年會被視為資安弱點，以此推論，我不認為一點關係都沒有。