對Android系統屏幕圖案鎖的暴力破解

鄭治華，石曙東，樊變霞,3

(1.湖北師范學院 物理與電子科學學院，湖北 黃石　435002；2. 湖北師范學院 計算機科學與技術學院，湖北 黃石　435002;3.湖北師范學院 數學與統計學院，湖北 黃石　435002)

對Android系統屏幕圖案鎖的暴力破解

鄭治華1,2，石曙東2，樊變霞2,3

(1.湖北師范學院 物理與電子科學學院，湖北 黃石435002；2. 湖北師范學院 計算機科學與技術學院，湖北 黃石435002;3.湖北師范學院 數學與統計學院，湖北 黃石435002)

摘要：SHA-1在許多安全協議中廣為使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被視為是MD5的后繼者。依托基于SHA-1加密算法的Android系統屏幕圖案鎖實例，對SHA-1加密算法完成了C語言實現，同時對圖案鎖進行了暴力破解，簡要探討了屏幕鎖安全性問題。 經加密生成的160位消息也即鎖屏圖案的密文，存放在/data/system/gesture.key 文件中，這160位的消息摘要是以40個16進制數存放的，只能通過16進制文檔閱讀器方可看到。如圖3是以圖2(b)的鎖屏圖案路徑編碼“010403060708”為例，經SHA-1加密后的密文內容："C0345DF789D7E46A0118022E77FF757C34CD9CB4"。 2)初始化各參數及緩存區，載入gesture.key文件中鎖屏圖案加密后的消息EC；

關鍵詞：SHA-1；暴力破解；Android系統圖案鎖；隱私安全

中圖分類號：TP309.1

文獻標識碼：A

文章編號：1009-2714(2015)04- 0069- 04

doi:10.3969/j.issn.1009-2714.2015.04.014

收稿日期：2015—06—06

基金項目:國家自然科學基金(61471163)、湖北省自然科學基金(2012FFB01801)資助

作者簡介:鄭治華(1990—)，男，湖北黃岡人，碩士研究生，研究方向為大數據安全、物聯網安全.

Google旗下Android系統在移動操作系統市場上以壟斷性優勢占據絕對主導地位，因而可以認為，針對移動智能設備遭到的攻擊在很大程度上講就是針對Android系統的攻擊，并且隨著大數據時代的到來和物聯網的興起，用戶對自己的隱私安全也越來越關注。自然，作為Android系統第一道防線——被廣泛使用[1]的屏幕圖案鎖的安全性到底如何就被推到了風口浪尖。

0引言

Android系統屏幕圖案鎖作為一種隱私保護手段，無外乎就是鎖屏密碼的輸入、加密和存儲三個步驟的安全，一般來說，鎖屏密碼明文的加密和密文的存儲才是最關鍵的。Android系統屏幕圖案鎖加密過程如圖1：

圖1圖案鎖加密過程

針對Android系統屏幕圖案鎖的安全性有不少人已經進行了探討。從組合數學的角度討論鎖屏圖案的所有可能性問題時，徐金成[2]得出的結論是985824種可能，并且采用字典的方式破解了鎖屏圖案。但由于鎖屏圖案編碼規則的復雜性，其得出的鎖屏圖案可能性總數是錯誤的，這由福建師范大學的倪超凡[3]使用Mathematic軟件編程得到了正確的結果：389112，進一步證明了破解效率可以更高。在具體編程實現上，杜謙[4]描述了SHA-1算法的實現過程，并討論了多語言實現的問題，而朱珍[5]則具體用了C++語言完成了SHA-1算法的實現。

1Android系統屏幕圖案鎖介紹

1.1　鎖屏圖案的輸入

Android系統屏幕圖案由分布類似于9宮格的9個點組成，而作為輸入的密碼正是這9個點中4個以上點按順序連接成的一條帶方向的路徑。生成這樣路徑的具體規則是：1)路徑上點的數量不小于4，且不大于9；2)路徑不允許跳過途中必須要經過的點；3)如果路徑中間的點之前用到過的，那么這個點就可以被跳過。圖1列出了幾種常見的有向路徑，其中c圖的路徑是非法的。

圖2　幾種常見的鎖屏有向路徑

1.2　鎖屏圖案的加密和存儲

在Android系統中這9個點從左往右、從上往下編碼為0X00、0X01、……0X08，每一條合法圖案鎖屏路徑就可以用一串16進制的數字來表示，也即待加密的明文。以圖2(b)的圖案為例，其鎖屏路徑編碼為“010403060708”，接下來就是用加密算法對其進行加密，然后將加密后的密文進行安全存放。

這里采用加密算法是SHA-1，SHA-1是安全散列算法中的一種，本質是將一個不超過264位的明文消息生成一個160位的消息摘要。它有這樣三個特點：1)由消息摘要反推原輸入消息，從計算理論上來說是困難的；2)想要找到兩組不同的消息對應到相同的消息摘要，從計算理論上來說也是困難的；3)任何對輸入消息的變動，都有很高的概率導致其產生的消息摘要迥異，也即函數的雪崩性。因而它通常用作驗證數據完整性、密碼的存放(比如這里的鎖屏密碼)，同時也是數字簽名(Digital Signature Standard，DSS)中廣泛使用的加密算法。但SHA系列算法都存在哈希碰撞攻擊的缺陷，針對SHA-1最近所能達到最好攻擊效果的是2005年8月17日的CRYPTO會議中王小云等[6]提出的SHA-1雜湊函數雜湊沖撞算法的改良版，此改良版能在263個計算復雜度內找到哈希碰撞。

2針對圖案鎖密文的暴力破解

2.1　暴力破解的可行性

暴力破解其實就是窮舉法，簡單來說就是將密碼的可能值進行逐個比較或代入驗證直到找出真正的密碼為止。比如一個四位并且全部由數字組成的密碼共有104種組合，也就是說最多我們嘗試9999次就能找到真正的密碼，因而利用這種方法破解任何一個密碼都只是時間問題。由文獻[3]可知，真正合法的鎖屏路徑只有389 112條，那么對應的密文也只有389 112種可能，這正適合暴力破解方式的特點，事實上以當前個人計算機的運算能力來評估，這樣規模的問題基本上都是“秒破”。

現今稍具嚴密度的密碼驗證機制都會設下試誤的可容許次數以應對使用密碼窮舉法的破解，比如當試誤次數達到可容許次數時，密碼驗證系統就會自動拒絕繼續驗證，有的甚至還會自動啟動入侵警報機制。例如安卓系統則是在試誤達到可容許次數時，要求輸入gmail賬號進行驗證，但現實情況是手機本身設置gmail賬號的用戶并不多，尤其是在國內。

綜合以上兩個因素，安卓系統屏幕圖案鎖被暴力破解的概率是完全可能的。

2.2　破解軟件的設計與實現

針對此問題的解空間大小僅為389 112，可以采取的暴力破解思路是通過將程序生成的所有可能鎖屏路徑編碼經SHA-1加密后的密文字符串與gesture.key中存儲的目標密文對比，當對比結果相同時停止后續的密文對比。SHA-1算法是個比較常用的算法，它的描述隨處可見，在此就不贅述了，這里描述的只是破解軟件的設計思路。

設計思路描述如下：

1)執行adb命令“adb pull /data/system/gesture.key gesture.key”獲取手機gesture.key文件到電腦上；

3)生成串連點數為i(4≤i≤9) 時鎖屏路徑對應數值大小最小的16進制數字串NS，這里的鎖屏路徑后文稱為碰撞有向鎖屏路徑；

4)將NS按二進制位串用SHA-1加密算法生成對應的密文SC；

5)用SC 與EC 進行對比，如若相同則結束程序，返回NS；

6)否則NS=NS+1，跳轉到步驟4，直到串連點數為i的鎖屏路徑取完，執行下一步；

7)i=i+1，循環步驟3到6。

在以上的設計思路描述中有三個細節問題沒有說到，主要因為這不是本文要談的核心問題。其一是將有向鎖屏路徑在輸出窗口畫出的實現；其二是將軟件破解耗時在輸出窗口顯示的實現；其三是將有向鎖屏路徑編碼在輸出窗口顯示的實現。

2.3　破解結果分析

如下圖4即為所涉及的軟件在有向鎖屏路徑為圖2(b)時對gesture.key的暴力破解結果，其中的有向路徑是動態顯示的，用以看出其有向性。同時要交代的一點是：為便于軟件的實現，在碰撞有向鎖屏路徑生成時并沒有嚴格按照Android系統屏幕圖案鎖生成規則執行，也即生成的碰撞有向鎖屏路徑在事實上可能是不允許存在的。

圖4　圖案鎖有向路徑為圖2(b)時的破解結果

由運行結果可知，即使沒有排除那些不合法的有向路徑，暴力破解所耗費的時間只要幾十毫秒，離秒都差兩個數量級，這也反證了軟件設計之初沒有嚴格使用有向鎖屏路徑生成規則的合理性。

當然，如果目的僅為了破除Android系統的屏幕圖案鎖自不必如此麻煩，但假如你想進入別人的手機，但又不想讓其發覺的話，這就是最佳方法。Android系統屏幕圖案鎖主要是因gesture.key文件的存在而存在，只要將這個文件刪除掉即可。目前常用的方式有兩種：一是通過Android調試橋(Android Debug Bridge，adb)運行設備的殼shell來直接操作管理Android設備，將該文件刪掉，不過采用這種方法的前提是Android設備開啟了USB調試模式；二是直接恢復出廠設置，只是這種方法將會使得Android設備里的用戶資料全部清除，因而只適用于設備里沒有重要資料的用戶和實在無法使用其他方法找回鎖屏密碼的用戶。另有通過屏幕污點反射、口令繞過的途徑[7]也可以破除屏幕圖案鎖的安全保障作用。

3總結

鑒于用此種方法破解Android系統的屏幕圖案鎖輕而易舉，還能不被人發覺，所以提出幾點關于Android設備安全使用要點。第一，Android設備不要輕易root，如若root了，那也要在不必要的時候關閉USB調試模式，這樣就阻止了通過adb方式破解的可能；第二，開啟遠程銷毀數據功能，避免在遭破解后的隱私數據泄露；第三，建議設置的有向鎖屏路徑構成點不少于6個，同時也不要以常見字符，比如“Z”、“2”等作為鎖屏圖案。

參考文獻：

[1]北京比達信息咨詢有限公司.2015年4月手機鎖屏APP用戶調查報告[R].北京,2015.

[2]徐金成.Android 手機屏幕保護安全性研究[J].信息通信，2013(3):97～98.

[3]倪超凡.安卓系統屏幕密碼鎖暴力破解的可行性分析[J].衡水學院學報,2014(2):12～14.

[4]杜謙，張文霞.多語言可實現的SHA-1散列算法[J].武漢理工大學學報(信息與管理工程版),2007(7):42～44.

[5]朱珍.數字簽名算法SHA-1的C++實現[J].華南金融電報,2007(4):102～104.

[6]Wang Xiaoyun, Yin Yiqun, Yu Hongbo. Finding Collisions in the Full SHA-1[C]. Advances in Cryptology-Crypto 05. LNCS 3621:17～36,2005.

[7]陳兆煙,黃君燦,魏馳.Android手機屏幕圖形鎖問題分析[J].海峽科學,2014(10):50～51.

Brute force to the android pattern screen lock

ZHENG Zhi-Hua1,2, SHI Shu-Dong2, FAN Bian-Xia2,3

(1.College of Physics and Electronic Science, Hubei Normal University, Huangshi435002, China；

2.College of Computer Science and Technology, Hubei Normal University, Huangshi 435002, China；

3.College of Mathematics and Statistics, Hubei Normal University, Huangshi435002, China)

Abstract:SHA-1 widely used in many security protocols, including TLS and SSL, PGP, SSH, S/MIME and IPsec, has been seen as the successors of the MD5.In this paper, based on the encryption algorithm based on SHA-1 the Android lock screen design examples, the encryption algorithm for SHA-1 completed the C language implementation, design lock for the brute force at the same time, briefly discusses the screen lock security problems.

Key words:SHA-1; Brute force attack; Android screen pattern lock; security privacy