对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