Android 手勢密碼破解原理與實作：SHA-1 弱點與暴力枚舉完整指南

Android 手勢密碼破解原理與實作完整指南

Android 手勢密碼（Pattern Lock）因其直觀易用廣受歡迎，但其底層加密機制存在嚴重安全缺陷。本文深入剖析其 SHA-1 雜湊儲存機制、鑰匙空間極小的根本原因，並提供完整的 C 語言暴力破解實作代碼，同時探討防護對策。

加密機制詳解

Android 將 3×3 點陣編號為十六進位 0x00~0x08：

00 01 02
03 04 05
06 07 08

手勢軌跡轉為位元組序列（如 L 型：00 03 06 07 08），計算 SHA-1(sequence) 得 160-bit 雜湊值，儲存於 /data/system/gesture.key。關鍵點：SHA-1 是單向雜湊函數，非加密演算法，無金鑰、不可逆，僅適合完整性驗證。

為何極易被破解？鑰匙空間分析

規則：最少 4 點、最多 9 點、不重複點。排列組合總數：

P(9,4) + P(9,5) + ... + P(9,9) = 985,824 < 100 萬

現代 CPU 單核心每秒可計算數百萬次 SHA-1，**全空間暴力破解僅需毫秒級時間**。這是根本弱點：熵過低。

破解演算法核心：組合生成 + 全排列 + SHA-1 比對

採用「先組合、後全排列」的分層遞迴策略：

1. 組合生成 C(n,m)：從 9 個點中選 m 個（m=4~9），遞迴反向選點
2. 全排列 P(m,m)：對每個組合生成所有排列，交換法遞迴實現
3. SHA-1 計算比對：每個排列序列計算 SHA-1，與目標雜湊比對

關鍵代碼片段

// 全排列遞迴
void permute(uint8 *p, int n, int m) {
    if (n == m) { /* 輸出或雜湊比對 */ }
    else {
        for (int i = n; i <= m; i++) {
            swap(p[n], p[i]);
            permute(p, n+1, m);
            swap(p[n], p[i]);  // 回溯還原
        }
    }
}

// 組合生成遞迴
void combine(uint8 *p, uint8 *q, int n, int m, int s) {
    for (int i = n; i >= m; i--) {
        q[m-1] = p[i-1];
        if (m > 1) combine(p, q, i-1, m-1, s);
        else { /* 對 q[0..s-1] 做全排列 */ }
    }
}

完整破解流程

void crack_main(const uint8 *target_hash) {
    uint8 points[9] = {0x00,0x01,...,0x08};
    uint8 comb[9];
    int tried = 0;
    for (int len = 4; len <= 9; len++) {
        if (crack_combine(points, comb, 9, len, len, &tried, target_hash))
            return;  // 找到即退出
    }
    printf("Gesture not found!\n");
}

實測：單執行緒 C 實作約 0.5 秒遍歷全空間。若使用 GPU（OpenCL/CUDA）或多執行緒並行，可縮減至毫秒級。

防護建議與最佳實務

• 用戶端：避免 Root 且開啟 USB Debug；使用複雜手勢（長度 8-9）增加熵
• 開發者：絕不可直接儲存 SHA-1(手勢)。應採用 PBKDF2 / bcrypt / Argon2 等**慢速雜湊**（含鹽值、可配置迭代次數），將單次驗證耗時提升至 100ms 以上，使暴力破解成本指數級上升
• 系統層：Android 10+ 強制要求生物識別或強密碼作為備選，手勢密碼已非首選

法律與道德提醒

本文僅供安全研究與教學用途。**未經授權存取他人裝置、破解鎖屏屬違法行為**（違反《刑法》第 358 條等）。實務中應透過合法授權（如企業 MDM 管理、鑑識取證流程）進行操作。