★ 引子
之前在Freebuf上看到一片文章講Andriod的手勢密碼加密原理，覺得比較有意思，所以就寫了一個小程序試試。
★ 原理
Android的手勢密碼加密原理很簡單：
先給屏幕上的每一個點編號（一般是 3 X 3）：
00，01，02
03，04，05
06，07，08
注意這裡的數字都是十六進制。
假設我沿著左邊和下邊畫了一個 L 字，則手勢的點排列順序 sequence 是 00，03，06，07，08。
然後計算密文 C = SHA-1(sequence)，然後將結果寫入到 /data/system/gesture.key 中。
按照上面的操作，則密文 C 應該是：c8c0b24a15dc8bbfd411427973574695230458f0，160 bit 的 SHA-1 散列值。
不過嚴格來講這個過程不叫加密，叫散列，因為SHA-1只是一個數據摘要算法，並不是加密算法。
★ 破解原理
看到了吧，安卓機的手勢加密非常簡單，而且非常脆弱。為什麼說很脆弱，主要是密鑰空間太少！簡單計算一下：
手勢密碼最少要連 4 個點，最多可以連 9 個，忽略掉某些特殊的排列，用排列組合公式計算一下，結果是：（注：P(n, m) 表示從 n 個元素中選 m 個出來排列的情況總數）
P(9, 4) + P(9, 5) + ... ... + P(9, 9) = 985824
滿打滿算，還不到 100 萬，密鑰空間實在太少了，對於計算機窮舉，那是半秒鐘的事。
有了上面的原理，那麼破解程序的制作也就很簡單了：
1. 一個SHA-1 Hash模塊。如果你了解密碼學中的 Hash 算法，那麼可以自己寫，當然也可以去 OpenSSL, Crypto++ 之類的庫中去找。
2. 一個計算排列組合的模塊。這個是關鍵，所以我花多點口水講講。
注：以下的算法均用 C 實現。
考慮到要用到排列組合，那麼我就想到了兩個已經知道的東西：
1. 計算 P(n ,m)，可以用如下的方式計算：（注：C(n, m) 表示從 n 個元素中選 m 個出來組合的情況總數）
P(n, m) = P(m, m) * C(n, m)
2. 計算 P(m, m) 就是在計算 m 個元素的全排列總數，之前在上算法課的時候有講到這個算法，那麼就可以直接拿過來用。
那麼還需要自己構建一個計算組合的算法。
計算全排列 P(m, m)：
假設計算集合 {1，2，3} 的全排列，可以這麼做：先取一個元素，比如 1，再從剩下的集合 {2，3} 中取 2，那麼還剩下 {3}。按照這種搞法，{1，2，3} 的全排列就是：
1 {2， 3} ----> 1，2 {3} 1，3 {2}
2 {1， 3} ----> 2，1 {3} 2，3 {1}
3 {2， 1} ----> 3，2 {1} 3，1 {2}
到此為止，算法的思路已經明確了：依次將集合中的每一個元素和第一個元素交換，然後遞歸進行計算。下面給出代碼：
typedef unsigned char uint8;
#define swap(a, b) \
{ \
uint8 t; \
\
t = a; \
a = b; \
b = t; \
}
void permute(uint8 *p, int n, int m)
{
int i;
if(n == m)
{
for(i = 0; i <= m; i++)
printf("%02X ", p[i]);
printf("\n");
}
else
{
for(i = n; i <= m; i++)
{
swap(p[n], p[i]);
permute(p, n + 1, m);
swap(p[n], p[i]);
}
}
}
注：n，m 都是從下標為 0 開始的。
計算組合 C(n, m)：
一開始我想了好久都沒思路，後來仿照全排列的算法，運用遞歸的方式搞定。看來分治思想還是很重要的。
假設有集合 {1，2，3，4}，要從中選 2 個，列出所有的組合可能，那麼可以這麼做：
先從集合中取出一個元素，比如取出 1，則剩下 {2，3，4}，然後從剩下的集合 {2，3，4} 中取出一個元素，例如取出 2，這時就得到了一種組合情況 1，2，其他情況同理。
{1，2，3，4} ----> 1 {2，3，4} ------> {1，2} {1，3} {1，4}
{2，3，4} --------> 2 {3，4} ---------> {2，3} {3，4}
{3，4} ------------> 3 {4} --------------> {3，4}
可以看出，每次取一個元素，然後對剩余元素進行組合。這樣，組合算法的大概思路就有了：
反向從集合中選出一個元素，放到臨時數組 q 中，然後遞歸調用組合算法，直到 m = 1，即只需要選一個元素為止。
void combine(uint8 *p, uint8 *q, int n, int m, int s) // s 為選出來的序列長度
{
int i, j;
for(i = n; i >= m; i--)
{
q[m - 1] = p[i - 1];
if(m > 1)
{
combine(p, q, i - 1, m - 1, s);
}
else
{
for(j = 0; j < s; j++)
printf("%02X ", q[j]);
printf("\n");
}
}
}
計算排列 P(n, m)：
有了前面兩個算法，計算 P(n, m) 就變得很簡單了，直接把全排列的算法嵌入到組合算法中即可。
★ 破解程序
有了上面的鋪墊，編寫破解程序就很簡單了，下面就直接把代碼貼出來。
#define swap(a, b) \
{ \
uint8 t; \
\
t = a; \
a = b; \
b = t; \
}
static int crack_permute(uint8 *p, int n, int m, int *ct, const uint8 *md)
{
int i;
uint8 cal_md[SHA1_DIGEST_SIZE];
if(n == m)
{
(*ct)++;
sha1_hash(p, m, cal_md);
if(memcmp(cal_md, md, SHA1_DIGEST_SIZE) == 0)
{
printf("\nThe gesture found!\n\nThe gesture is :");
for(i = 0; i < m; i++)
printf("%02X ", p[i]);
printf("\n\nTry %d times!\n", (*ct));
return 1;
}
}
else
{
for(i = n; i <= m; i++)
{
swap(p[n], p[i]);
if(crack_permute(p, n + 1, m, ct, md))
return 1;
swap(p[n], p[i]);
}
}
return 0;
}
static int crack_combine(uint8 *p, uint8 *q, int n, int m, int s, int *ct, const uint8 *md)
{
int i, j;
uint8 r[NUM];
for(i = n; i >= m; i--)
{
q[m - 1] = p[i - 1];
if(m > 1)
{
if(crack_combine(p, q, i - 1, m - 1, s, ct, md))
return 1;
}
else
{
for(j = 0; j < s; j++)
r[j] = q[j];
if(crack_permute(r, 0, s - 1, ct, md))
return 1;
}
}
return 0;
}
void crack_main(const uint8 *md)
{
int ct, ret;
int m, n;
uint8 q[NUM];
uint8 p[NUM] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08};
ct = 0;
n = NUM;
for(m = 4; m <= n; m++)
{
if((ret = crack_combine(p, q, n, m, m, &ct, md)) == 1)
break;
}
if(ret == 0)
printf("\nGesture not found!\n");
}
注：ct 是統計嘗試的次數，md 是從文件中讀到的散列值，NUM 是宏定義：#define NUM 9 。
程序中的SHA-1是我自己寫的，函數原型是：void sha1_hash(const uint8 *input, const size_t len, uint8 *digest);
只要 crack_combine 搜索到手勢序列，返回 1，搜索結束。
上面的 crack_permute 和 crack_combine 兩個函數都是根據前面兩個算法改的。程序中，crack_permute 函數被 crack_combine 函數調用，用於計算每一種組合的全排列。在 crack_permute 函數中，調用 SHA-1 摘要算法計算每個手勢序列的散列值，然後與傳入的 md 進行比較，一旦比較成功則立即返回。
為了避免篇幅太長，上面只列出了部分主要代碼，想要全部的話點【這裡】。程序的話我沒有寫文件讀取的模塊，需要的話可以自己加上去。
★ 總結
安卓手勢密碼的破解，需要拿到 gesture.key 文件（命令：adb pull /data/system/gesture.key gesture.key），要防范此類攻擊，要麼手機不要 root，要麼 root 了之後不要打開 USB Debug 模式，不過可惜的是很多人對操作系統的權限沒有什麼概念，總是在最高權限下運行，這樣被黑的機率就會高很多 :(
安卓的手勢密碼之所以能被快速破解，密鑰空間小是最主要的原因，所以推廣一下，在其他場合下，密碼盡量還是設長一點比較保險。如果在編寫程序中涉及到密碼驗證環節，最好使用超慢算法，比如 PBKDF2 或者 bcrypt，這樣可以降低暴力破解的速度。
版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4418257.html
