密码安卓4

软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,2017,28(2):361371[doi:10.
13328/j.
cnki.
jos.
005023]http://www.
jos.
org.
cn中国科学院软件研究所版权所有.
Tel:+86-10-62562563一种随机剔除点的安卓图形解锁方案熊思纯,杨超,马建峰,张俊伟(西安电子科技大学网络与信息安全学院,陕西西安710071)通信作者:杨超,Email:chaoyang@xidian.
edu.
cn摘要:安卓图形解锁(Androidunlockpattern,简称AUP)作为目前移动终端上使用最广泛的图形密码方案,实际应用的密码在理论空间上分布很不均匀,导致其实际安全性远低于理论安全性,所暴露出的巨大安全隐患极易被攻击者利用以加快字典攻击与暴力破解的速度.
提出一种随机剔除点的安卓图形解锁方案(Android-unlock-patternschemethroughrandompointsexclusion,简称AUP-RPE).
在设置密码阶段通过对原界面作一系列改动以规避用户具有安全隐患的使用习惯,并组织了1100余人次的用户测试以收集实际应用的图形密码.
建模分析发现,在保证与AUP相近的可用性前提下,AUP-RPE的安全性提高了3个以上数量级,证明了该方案具有更高的安全性.
关键词:图形密码;安全性分析;马尔可夫模型;猜测熵;安卓中图法分类号:TP309中文引用格式:熊思纯,杨超,马建峰,张俊伟.
一种随机剔除点的安卓图形解锁方案.
软件学报,2017,28(2):361–371.

http://www.
jos.
org.
cn/1000-9825/5023.
htm英文引用格式:XiongSC,YangC,MaJF,ZhangJW.
Androidunlockpatternschemethroughrandompointexclusion.
RuanJianXueBao/JournalofSoftware,2017,28(2):361–371(inChinese).
http://www.
jos.
org.
cn/1000-9825/5023.
htmAndroidUnlockPatternSchemeThroughRandomPointExclusionXIONGSi-Chun,YANGChao,MAJian-Feng,ZHANGJun-Wei(SchoolofCyberEngineering,XidianUniversity,Xi'an710071,China)Abstract:Asthemostwidelyusedgraphicalpasswordschemeonmobileterminals,Androidunlockpattern(AUP)isnotquiteuniformlydistributedinitstheoreticalpasswordspacewheninpracticaluse,whichexposesatremendoushazardthatcanbeeasilyexploitedbytheattackertoexpeditedictionaryattackorviolencecrack.
Toaddressthisissue,thispaperproposesanewscheme,Android-unlock-patternbasedonrandompointexclusion(AUP-RPE),whichhelpstheusertoavoidhabitualchoicesbythenewinterfacearrangement.
Inaddition,patternsinreal-lifeusearecollectedbyperformingalarge-scaleuserstudywithover1100people.
ModelingbasedonthosepatternsshowstheentropyofAUP-RPEincreasesover3ordersofmagnitudethantheentropyofAUP,whichmeansthatAUP-RPEhasamuchstrongersecurity.
Keywords:graphicalpassword;securityanalysis;Markovmodel;guessingentropy;Android长久以来,由数字字母构成的文本密码(text-basedpassword)[1]是身份认证[2]的主要途径.
心理学研究表明[3],人脑对图形化信息的记忆优于文字信息.
此外,随着智能手机、平板电脑等设备的日益更新,图形化设备已成为人们生活中不可替代的通信工具,这使得采用图形化信息的认证方案——图形密码(graphicalpassword)[41f20;BACKGROUND-COLOR:#4ae2f7">4]成为一种更适合在图形化设备上使用的身份认证方案,其安全性研究已成为当前热点课题[5].
现有的图形密码系统,按其认证过程的不同,大致可分为3大类.
1)基于识别型(recognition-based):用户从由各种图片组成的网格中按顺序选出图片.
比较具有代表性的有基金项目:国家自然科学基金(6167241f20;BACKGROUND-COLOR:#4ae2f7">415,6141f20;BACKGROUND-COLOR:#4ae2f7">472310,U141f20;BACKGROUND-COLOR:#4ae2f7">405255)Foundationitem:NationalNaturalScienceFoundationofChina(6167241f20;BACKGROUND-COLOR:#4ae2f7">415,6141f20;BACKGROUND-COLOR:#4ae2f7">472310,U141f20;BACKGROUND-COLOR:#4ae2f7">405255)收稿时间:2015-09-07;修改时间:2015-12-02;采用时间:2015-12-27362JournalofSoftware软件学报Vol.
28,No.
2,February2017RealUser公司设计的PassFaces[6].
该方案通过识别网格中的人脸图片进行认证,文献[7]验证了其良好的可用性,但文献[8]指出PassFaces方案的图片选择受到性别、种族、肤色等特征的极大影响,难以建立一个图形密码设置的安全标准.
所以,此类型的图形密码并没有投入到实际应用中.
2)基于线索的回忆型(cue-basedrecall):利用图形化的提示信息降低用户回忆密码的难度.
典型的有CCP(cuedclickpoint)[9],在一组图片中点击每张图片的特定位置以完成认证.
然而,图片信息显示的清晰度与屏幕大小、精度有很大关系,而且,此方案需存储大量图片以获取足够大的密码空间,这将占据不小的存储空间.
因此,CCP不能普遍应用于移动终端设备.
3)基于回忆型(recall-based):要求用户重复以前的密码设定过程以通过认证.
此类图形密码不需存储大量图片,对设备屏幕大小和精度要求也不高,有广泛的适用性,代表性的有Jeymyn等人设计的DAS(drawasecret)[10].
该方案设置阶段,用户在一个2D栅格上画出图形密码;认证阶段,DAS根据画出的图形经过单元格的坐标顺序判断正确与否.
文献[11]指出,DAS尺寸限制了密码长度,且依赖于使用者所画的东西,易记性较差,并对DAS方案进行改进,提出了Pass-Go方案.
与DAS不同的是,Pass-Go方案利用2D栅格中网格线间的交点而不是单元格,通过给交点设置感应区域,用户划过感应区域即选择了该点,使栅格上的图形密码设计更加灵活,不再局限于水平方向与垂直方向,还可以连接对角线上的两点.
通过对167人进行调查发现,用户使用Pass-Go的认证成功率达78%,验证了Pass-Go方案良好的可用性.
现今最常见的安卓图形解锁(Androidunlockpatterns,简称AUP)[12]就是Pass-Go适应智能手机的一种具体应用,在3*3的九宫格形状的基础上,以网格线之间的交点为圆心形成9个感应区域(sensitiveareas),并隐去网格线,使图形界面简单化以更适应人脑记忆,用户在此点阵上按照一定规则设置图案.
然而,近期AUP却被发现存在巨大的安全隐患.
文献[13]对实际应用中AUP的密码强度以猜测熵(guessingentropy)的形式进行了测量.
通过用户实验收集到近2900个图形密码,在此数据上建模并发现这些图形的密码强度远低于理论上对应的密码强度:从密码熵值计算结果来看,理论上其安全性应与随机5位PINs相当,但在实际应用中安全性却低于随机3位PINs.
此外,用户使用习惯在很大程度上影响了实际应用中图形密码的安全性:高达41f20;BACKGROUND-COLOR:#4ae2f7">40%的用户选择左上角点作为密码的起始点;图案设计时笔划相对简单,如以直线形式连接水平、垂直或对角线上的3点;图案近似于某一特定形状,如字母、数字或几何形状等.
这些使用习惯存在很大的安全隐患,极易被攻击者利用,从而提高攻击成功率.
虽然文中给出了41f20;BACKGROUND-COLOR:#4ae2f7">4种替代方案,但实验证明这41f20;BACKGROUND-COLOR:#4ae2f7">4种方案并没有明显提高实际应用中图形密码的熵值:其中3种方案的熵值明显低于原方案,另一种方案的熵值也仅略高于原方案.
而从人机交互角度看,这41f20;BACKGROUND-COLOR:#4ae2f7">4种方案在可用性上均低于原方案.
因此,这里并没有给出一种能够替代安卓图形解锁且行之有效的解决方案.
针对上述问题,本文提出一种随机剔除点的AUP认证方案——AUP-RPE(random-points-exclusionauthenticatingschemebasedonandroidunlockpatterns).
我们将3*3点阵规模扩大到41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4,在密码设置阶段,鉴于原方案四角处的点作为起始点的概率偏高或偏低,故将41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵四角处的41f20;BACKGROUND-COLOR:#4ae2f7">4点剔除,作为固定不可选点;为增大密码设置的随机性,在每次设置密码时,在剩余的12点中随机剔除两个点,即随机不可选点,因而每次可设置的点数为10.
由于两点是随机剔除的,故等价于在12个点中选取41f20;BACKGROUND-COLOR:#4ae2f7">4个~10个点设置密码,这在密码空间上要远大于AUP从9个点中选取41f20;BACKGROUND-COLOR:#4ae2f7">4个~9个点的情况.
同时,为了测试评估实际使用过程中AUP-RPE的安全性,我们组织了200人模拟用户,收集到1169个图形密码,在此基础上采用5折交叉验证(5-foldcross-validation)并建立三元的马尔可夫模型(3-gramMarkovmodel),依此得出理论密码空间的图案在实际使用中出现的概率,计算出AUP-RPE的猜测熵:当攻击者按照此概率由大到小的顺序发起攻击时,达到某一攻击成功率所对应的攻击次数.

结果表明,AUP-RPE所做的改进,不仅保证了与原方案几乎相同的可用性,而且极大地提高了安全性,具有比安卓图形解锁更高的密码强度.
目前来看,在大规模的实际调查数据的基础上建模分析一种新方案的安全性是非常少见的,这使得AUP-RPE的安全性评估具有极大的现实意义.
熊思纯等:一种随机剔除点的安卓图形解锁方案3631AUP-RPE图形密码方案1.
1AUP-RPE方案设计思路文献[11]通过对实际应用中的AUP进行实验分析发现,由于用户的使用习惯问题,实际应用中AUP的密码强度远低于其理论上的密码强度.
具体表现有以下几点.
(1)在起始点的设置上,41f20;BACKGROUND-COLOR:#4ae2f7">40%以上的用户严重偏向于选择左上角点.

(2)相邻点的选取,偏向于连接水平或垂直方向而不是对角线方向上的点.
(3)"三点一线",以直线连接同一直线上的3点.
(41f20;BACKGROUND-COLOR:#4ae2f7">4)形似于特定符号,将图案设置成近似于某一特定字母、数字或符号的形状.

这一系列的使用习惯问题导致实际应用中的图形密码在理论密码空间上分布过于集中,利用率并不高,被攻击者利用后可显著提高攻击率.
因此,我们从两个方面考虑增强图形解锁方案的安全性.
(1)在尽量不影响用户习惯的前提下,对密码设置界面做改动以强制用户改变可导致密码强度降低的使用习惯.
方案的设计思想是在AUP的基础上做相应的改动,以规避用户设计出具有安全隐患的图形密码,将四角处的41f20;BACKGROUND-COLOR:#4ae2f7">4点作为固定不可选点,再设置两个随机的不可选点,限定用户只能在剩余的10点中设置出图形密码.
这样可避免四角处点使用过多或过少的情况的出现,打乱用户特定的使用习惯.

(2)在尽量不影响用户使用方便性的情况下,增大密码空间,让攻击者的攻击难度成指数增加.
主要措施是将AUP的3*3点阵规模扩大至41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4,且由于两点是随机剔除的,故等价于在12个点中选取41f20;BACKGROUND-COLOR:#4ae2f7">4个~10个点设置密码,这在密码空间上要远大于在9个点中选取41f20;BACKGROUND-COLOR:#4ae2f7">4个~9个点的情况,使密码空间增大了3个以上数量级.
1.
2AUP-RPE具体方案针对用户的使用习惯问题,本文在原3*3点阵的基础上,通过对点阵布局做一系列调整以便能够在一定程度上使用户改变其原有的使用习惯,从而提出了一种41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵的基于安卓图形解锁的改进方案——AUP-RPE.
用户使用此方案设置密码仍遵循安卓图形解锁的规则.
密码认证阶段采用的是一个普通的41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵,如图1所示;密码设置阶段,如图2所示,在41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵上做一些变动.
(1)剔除四角处的点,使其不参与密码的设置,将其作为固定不可选点.
(2)从剩余的12个点中再随机剔除两个点不参与密码的设置,将其作为随机不可选点.
(a)(b)Fig.
1Loadinginterface图1登录认证界面可选点3641f20;BACKGROUND-COLOR:#4ae2f7">4JournalofSoftware软件学报Vol.
28,No.
2,February2017(a)(b)(c)(d)Fig.
2Patternsettinginterface图2图形密码设置界面63AUP理论上可设计出的图形密码数目,即密码空间的大小为389112≈219,若用户设置的图案在此密码空间上服从均匀分布,理论上的密码空间能够得到充分利用,则此方案的密码空间大小是足够的.
然而,由于用户设置密码自身的使用习惯,使得实际应用到的图形密码在理论密码空间上分布得并不均匀.
密码设置主要有以下两步.
(1)进入图形密码设置的初始界面,如图2(a)所示.
(2)选定某一可选点作起始点,再在剩余的可选点中按使用规则设置图形密码,如图2(b)所示.
此时,若手指脱离屏幕,则黄色点的路径即为所设置的图形密码.
此外,若在密码设置过程中选取了固定或随机不可选点,则原已选择的路径将被系统认定为无效.
例如,若在图2(b)中的黄色点7后继续选择了左下角的红色点,此时界面恢复成图2(a),继续往右如图2(c)所示,选择路径如图2(d)所示,此时又形成新的有效路径,如此,直至在可选点中设置一个路径长度在41f20;BACKGROUND-COLOR:#4ae2f7">4~10的图案即为系统认定的合法图形密码.
尽管在设置密码时可供选择的点仅有10个,但由于两个随机不可选点是不固定的,在每次进入密码设置界面时都会改变,因而从66种不同密码设置界面中来看,这相当于实际可供选取的仍有12个,即在12个点中选取41f20;BACKGROUND-COLOR:#4ae2f7">4个~10个点,密码空间约达到222.
显然,此方案的理论密码空间远大于安卓图形解锁方案.
在输入密码进行认证时,展示给用户的是一个16个点均可选的点阵,尽管攻击者可能知道位于四角处的点并未参与密码设置,但由于每次用户设置密码时随机不可选点都不固定使攻击者无从知晓,因而在剩余的12个点中对密码实行攻击的难度明显高于AUP从9个点中进行猜测.
1.
3AUP-RPE方案实现在Android41f20;BACKGROUND-COLOR:#4ae2f7">4.
3平台上对AUP-RPE进行编码实现,为了实现对用户输入的图形密码进行记录以便建模分析,我们分别对41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵中的16个点进行了编码,如图3所示,使每一个输入的图形密码能够转换成字符串的形式.
cabdelhgfijkmnopFig.
3Encoding图3编码图41f20;BACKGROUND-COLOR:#4ae2f7">4(a)为图形密码设置界面,输入欲设置的密码,记录过程为从手指接触屏幕到脱离屏幕,如图41f20;BACKGROUND-COLOR:#4ae2f7">4(b)所示,则熊思纯等:一种随机剔除点的安卓图形解锁方案365记录下来的密码为"cfgjkn".
这里,密码的长度必须不小于41f20;BACKGROUND-COLOR:#4ae2f7">4,且被选择点必须是可选点,这样才能将字符串写入到指定的记录文件中.
(a)(b)Fig.
41f20;BACKGROUND-COLOR:#4ae2f7">4Implementation图41f20;BACKGROUND-COLOR:#4ae2f7">4实现2AUP-RPE方案性能测试为了验证AUP-RPE的可用性,我们进行了用户实验;为了评估AUP-RPE在实际应用环境下的安全性,对此次实验收集到的数据建模,并计算出一个衡量密码强度的值——猜测熵,并根据此熵值对AUP-RPE的密码强度进行分析与评估.
2.
1用户测试方案为了在实际应用环境下对AUP-RPE与AUP的性能进行比较,我们在手机上分别实现了这两种方案,并组织了200名用户参与新方案的测试评估:参与者模拟用户设置密码,再模拟攻击者交叉猜测对方的密码.

首先,将AUP-RPE方案的使用规则介绍给参与者,参与者模拟用户,在手机上用AUP-RPE设置图形解锁密码,这是一种具有抵御攻击性质的密码,称为DefensiveAUP-RPE.
此类密码要求"用户"设置的密码具有较高安全性,即在设置完成后能够抵御来自其他参与者的攻击;而又具有可用性,使用户在30分钟后仍能记住密码从而解锁成功.
然后,在"用户"设置完密码到再次认证的30分钟内,参与者模拟"攻击者",对其他"用户"设置的密码进行猜测以试图破解,这个过程所用到的密码具有"攻击性",称为OffensiveAUP-RPE.
由于密码的设置与攻击都是在参与者中交叉进行的,因而,可分为以下41f20;BACKGROUND-COLOR:#4ae2f7">4步.
(1)设置一个密码(defensiveAUP-RPE).
(2)猜测他人的密码2次~5次(offensiveAUP-RPE).
(3)等待30分钟以供"攻击者"猜测密码.
(41f20;BACKGROUND-COLOR:#4ae2f7">4)再次认证登录.
对于AUP方案,采取同样的步骤进行测试,得到DefensiveAUP与OffensiveAUP.
一般而言,具有"防御性"的DefensiveAUP-RPE安全性应高于具有"攻击性"的OffensiveAUP-RPE,故训练集与测试集均取自DefensiveAUP-RPE,而OffensiveAUP-RPE将作为附加数据添加到训练集中去.
这会带来两种不同的作用:训练集越大,求取的近似值就越精确.
由于这两种数据来自不同的分布(DefensiveAUP-RPE来自安全性较强的分布,OffensiveAUP-RPE来自安全性较弱的分布),OffensiveAUP-RPE的加入会使计算得到的色熵值低于仅有DefensiveAUP-RPE时的结果.
实验过程中,由于仅要求"用户"设置一个能够在30分钟内不被"攻击者"破解且30分钟内仍能记住的图形密码,即时易记性使得"用户"设置的密码强度比实际应用密码的强度更高.
此外,参与此次实验调查的成员均为来自理工科院校的在读研究生,年龄在20岁~30岁之间,男女比例约为3:1,由于专业、年龄等限制,使此次收集366JournalofSoftware软件学报Vol.
28,No.
2,February2017到的密码比一般情况下更专业化,安全性将略高于一般情况.
尽管此次实验数据采集所面向的人群偏单一化,但采集的数据对于评估一种新方案来说仍然具有相当大的参考价值.
实验共收集到defensiveAUP-RPE200个,offensiveAUP-RPE769个,defensiveAUP189个,offensiveAUP569个.
2.
2AUP-RPE方案建模根据收集到的AUP-RPE与AUP,在此基础上建立模型以分析安全性,具体细节如下所述.
2.
2.
1n元马尔可夫模型(N-gramMarkovmodel)马尔可夫过程是具有马尔可夫性质的随机过程:在时刻ti所处的状态已知时,过程在时刻t(t>ti)所处的状态仅与过程在ti时刻的状态有关,而与过程在ti时刻以前所处的状态无关,也称为无后效性.
111212nnnnnnttttttttttPXxXxXxXxPXxXx++在语音识别、概率文法等自然语言处理时,常根据当前字母的前几位来预测当前字母的出现概率.
例如,在一个英文单词中,字母t后所出现字母为h的可能性明显大于q出现的可能性;而在安卓图形解锁的九宫格中,与当前的点距离越近,被选择的概率就越大.
基于这个相似之处,我们在计算图形密码的出现概率时采用这种n元马尔可夫模型[141f20;BACKGROUND-COLOR:#4ae2f7">4],即某一位的出现取决于它的前n–1位.
给定一个m位序列c1c2…cm,用n元马尔可夫模型表示:12121121mmniiinPcccPcccPcccc==∏其中,121(.
.
.
)nPccc为初始概率(initialprobability),121nnPcccc为转移概率(transitionprobability).
由这两个概率可计算得出密码的出现概率.
我们用从样本数据得出的频率来估计初始概率和转移概率.

2.
2.
2建立模型从攻击者的角度考虑,在猜测用户密码时,对于理论上可能出现的密码,根据系统中实际用户的样本数据计算其出现概率,并将密码按出现概率由高到低进行排序,攻击者按此顺序对这一系统的用户密码进行攻击,即出现概率最高的密码将被最先用来进行攻击.
在基于安卓图形解锁的改进方案中,根据给出的41f20;BACKGROUND-COLOR:#4ae2f7">4条使用规则,可以用枚举的方法列出符合规则的可能设计出的所有图案.
因此,利用一个训练集(trainingset)和一个测试集(testset),模型建立的实现算法如下:(1)选取训练集中出现频率较高的图案,使其在测试集中的出现频率也较高.

(2)从训练集计算得出初始概率和转移概率.
(3)根据n元马尔可夫模型计算所有图形密码的出现概率.
(41f20;BACKGROUND-COLOR:#4ae2f7">4)将所有图形密码按照出现概率由大到小进行排列.
(5)在测试集上评估猜测次数.
对采集到的数据集进行5折交叉验证(5-foldcross-validation):将数据集平均分成5个互不相交的子集S1,…,S5.
选择其中一个子集0iS作为测试集,则训练集即为剩余41f20;BACKGROUND-COLOR:#4ae2f7">4个子集的并集.
这样,5个子集中的每一个都做一次训练集,剩余41f20;BACKGROUND-COLOR:#4ae2f7">4个子集的并集即为对应的训练集,最终结果取这5次的平均值.
我们所取的样本容量约为200,因此测试集的容量大小约为50,而测训练集的大小约为160.
2.
2.
3n的选取一般而言,当训练集中的数据足够多时,n的取值越大,建模估算的结果就越准确.
在我们的改进方案中,41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵中只有四角处的点始终不参与图形密码的设置,数据集大小为300且这些图形密码的平均长度为5.
59.
因此,当n=2时,理论上有12*11=132种二元排列,实际的二元两点排列有300*5.
89–300=1377个,即理论上的一种二元排列对应于实际的1377/132≈10个排列;当n=3时,理论上有12*11*10=1320种三元排列,实际的三元排列有300*5.
89–300*2=1077个,即理论上的一种三元排列对应实际的11671320≈0.
88个;当n=41f20;BACKGROUND-COLOR:#4ae2f7">4时,理论上一种四元排列对应实际的0.
66个.
由于当n=3时,理论上每种排列与实际的比值更近似于1,因此,n=3时建立马尔可夫模型的效果最好.
熊思纯等:一种随机剔除点的安卓图形解锁方案3672.
2.
41f20;BACKGROUND-COLOR:#4ae2f7">4密码强度计算密码空间的大小衡量的是AUP-RPE在理论上的安全性,因而具有现实意义的密码强度分析应基于实际应用中的用户数据.
猜测熵(guessingentropy)[15,16]正是基于用户数据来衡量密码强度,即当攻击者处于最佳状态时(按密码出现概率的降序进行猜测),破解全部密码所需要的攻击次数.
熵值越大,密码就越复杂,密码强度也就越高;反之,熵值越小,密码就越简单,密码强度也就越低.
在实际应用中,要攻破系统中所有账户的密码难度很高,攻击者往往对攻破系统中账户达到某个百分比时所需的攻击次数更感兴趣,即部分猜测熵(partialguessingentropy)[17].
也就是说,当某一系统中用户的密码被攻击者破解达到一定百分比时,所需攻击的次数.
设百分比为α,满足0≤α≤1;攻击率达到α时所需的攻击次数为μα,有:{}001min,iiiipαμα==∑≥这里,pi表示第i次猜测时破解密码的百分比.
攻击了μα次后,攻击成功率为01,iiipααμλλα===∑≥根据上述条件,便可计算出部分猜测熵:1()(1),iiGXipαμαααλμ=∑其中,(1)ααλμ表示没有被攻击到的部分,1iiipαμ=∑表示被攻击到的部分.
然而,当面对许多密码时,我们希望用信息位来表示部分猜测熵[7]:2()1()log1log,2GXGXααααλλ=+其中,1log2αλ用来使得到的熵值均匀分布.
这种用数学模型的方法计算的密码强度具有明确的意义,在某种程度上来说也是最佳的,因为它以数学的方法表示出密码对攻击的耐受能力,充分提供了一个对实际安全性的估计值.

3测试结果评估让参与此次实验的200名用户分别使用AUP-RPE和AUP,先完成图形密码设置操作(包括首次输入设计的密码与再次确认密码两个阶段),然后交由他人来模拟攻击者猜测密码,再由原用户进行登录认证操作,最后对收集到的图形密码进行可用性与安全性分析与评估.
3.
1可用性评估如表1和图5所示,对于AUP-RPE和AUP这两种方案,分别统计了参与者在图形密码设置阶段的所需时间分布情况,所有用户均在60s内完成密码设置,其中60%以上的用户所需时间不超过41f20;BACKGROUND-COLOR:#4ae2f7">40s,而超过90%的用户在50s内完成操作.
图6显示了两种方案下,参与者进行密码设置与登录认证所需时间的平均情况,显然,尽管AUP-RPE在平均时间上仍然略多于AUP,但两者的平均时间仍然十分相近.
因而,AUP-RPE进行密码设置与登录认证所需的时间,明确地体现了其具有良好的可理解性与易接受性.
Table1Staticsofpasswordsettingtimeandpeoplecounted表1设置密码所需时间与人数统计所需时间≤20s≤30s≤41f20;BACKGROUND-COLOR:#4ae2f7">40s≤50s>50s人数AUP-RPE62612118812AUP1033141f20;BACKGROUND-COLOR:#4ae2f7">4619641f20;BACKGROUND-COLOR:#4ae2f7">4368JournalofSoftware软件学报Vol.
28,No.
2,February2017Fig.
5Distributionofpasswordsettingtimeandnumberofpeople图5设置密码所需时间与人数分布Fig.
6Averagetimeneededforpasswordsettingandlogin图6密码设置与登录成功所需平均时间图7显示出参与者使用两种方案认证成功时所需尝试的次数与成功率的关系.
显然,80%以上用户首次尝试即通过认证,超过90%的用户在3次尝试内即通过验证.
鉴于AUP-RPE方案的复杂性,两种方案的认证成功率非常相近.
尽管AUP的认证成功率略高,但两者相近的较高认证成功率表明,AUP-RPE充分保持了良好的易记性.
Fig.
7Logintimeanditssuccessrate图7登录次数及成功率考虑到作为AUP的改进方案,AUP-PRE在设计原理上复杂于AUP,密码空间也远大于AUP,因而在密码设置与登录认证所需时间、认证成功所需尝试次数与成功率等用户友好性测试结果中,AUP-RPE与AUP的偏差均在合理范围内.
两者非常相近的测试结果说明,对用户而言,AUP-RPE方案仍具有与AUP相近的良好的可用性.
3.
2安全性评估如图8所示,对收集到的图形密码建立如第2.
2节所述的3-gram马尔可夫模型,由此计算出理论上所有图形密码的出现概率,如图9所示,并将这些图形密码按概率的降序排序.
当攻击者按照理论上密码的出现概率由熊思纯等:一种随机剔除点的安卓图形解锁方案369高到低的顺序对系统中的用户密码进行猜测时,能够使其攻击效率达到最高.

Fig.
8Graphicalpasswordsintheformofstring图8以字符串形式记录的图形密码Fig.
9Probabilityofgraphicalpassword图9图形密码的出现概率如表2所示,分别计算当攻击者对AUP-RPE与AUP的攻击率α达10%,20%,50%时的猜测熵,并进行比较.
由于用户为自己设置的抵御他人攻击的密码安全性高于其"攻击"时所使用的密码,因而DefensiveAUP-RPE在用户密码安全性上更具代表性.
同理,DefensiveAUP的安全性高于OffensiveAUP.
故我们主要将DefensiveAUP-RPE与DefensiveAUP做比较:当攻击率α为10%时,两种方案的安全性相近,AUP-RPE的熵值略低于AUP;当攻击率α为20%时,AUP-RPE的熵值高于AUP,则改进方案的安全性高于原方案;当攻击率α达到50%时,AUP-RPE的熵值明显高于AUP,这表明AUP-RPE在安全性上有非常显著的提高.
Table2Entropycomparisonoftwoschemes表2两种方案的熵值比较Schemesα=0.
1α=0.
2α=0.
5DefensiveAUP-RPE8.
679.
33141f20;BACKGROUND-COLOR:#4ae2f7">4.
95OffensiveAUP-RPE8.
41f20;BACKGROUND-COLOR:#4ae2f7">489.
1513.
41f20;BACKGROUND-COLOR:#4ae2f7">48DefensiveAUP8.
729.
1010.
90OffensiveAUP8.
41f20;BACKGROUND-COLOR:#4ae2f7">441f20;BACKGROUND-COLOR:#4ae2f7">48.
789.
16图10更详细地显示出攻击率的增长(纵坐标)与猜测次数(横坐标)的增长关系.
总体来看,当攻击率在0~20%时,AUP-RPE与AUP所对应的猜测次数非常相近;当攻击率超过20%以后,两种AUP-RPE的熵值曲线均明显位于AUP熵值曲线的下方,这表明当达到相同的攻击率时,AUP-RPE的熵值更高,所需的攻击次数更多.
此外,两种方案的图形密码中具有Defensive性质的密码熵值曲线均高于具有Offensive性质的密码熵值曲线,更直观地说明了用户为保护自身隐私而设置具有Defensive性质的密码,其安全性高于其用以攻击他人账户的密码,即当攻击率相同时,具有Defensive性质的密码所需的攻击次数更多.
Fig.
10Diagramoftherelationbetweenattackrateandattackfrequency图10攻击率与攻击次数的关系示意图图11显示出向原DefensiveAUP-RPE训练集中分别加入50,100,200个OffensiveAUP-RPE后,攻击率的增长(纵坐标)与猜测次数(横坐标)的关系.
不难发现,当加入的OffensiveAUP-RPE使训练集样本容量逐渐增大时,计算得到的图形密码所对应的出现概率更近似于实际概率,从而更有利于攻击率的提高;然而,由于加入的370JournalofSoftware软件学报Vol.
28,No.
2,February2017OffensiveAUP-RPE均来自比DefensiveAUP-RPE的密码强度更低的分布,可能导致最终计算得到的图形密码出现概率偏离于实际率.
因此,当满足相同分布的训练集容量逐渐增大时,相同的猜测次数将达到更高的攻击率,也即同一性质的训练集样本容量越大,攻击者获得的信息就越多,也就越有利于提高攻击效率.

Fig.
11Impactoftrainingsetuponattackrateandattackfrequency图11训练集对攻击次数与攻击率的影响综合以上分析,AUP-RPE在图形密码设置所需时间、认证所需时间及成功率上都与AUP十分相近,在安全性分析中更具有远远大于AUP-RPE的密码熵值.
这表明新方案在保持了与原方案几乎一致的可用性的基础上,极大地提高了图形密码的安全性,充分说明了AUP-RPE的良好实用性.
41f20;BACKGROUND-COLOR:#4ae2f7">4讨论与结论AUP-RPE是进行较大规模调查,基于用户数据建模并以熵值形式计算实际应用中密码强度的安卓图形解锁改进方案.
它在认证阶段是普通的41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵,在密码设置阶段,剔除41f20;BACKGROUND-COLOR:#4ae2f7">4*41f20;BACKGROUND-COLOR:#4ae2f7">4点阵四角处的点,剩余的12个点在每次设置密码时随机剔除其中两点,即每次参与密码设置的仅有10个点,这既保证了密码空间大于原方案,又在一定程度上规避了用户原具有安全隐患的使用习惯,避免了AUP中用户使用四角处点过多或过少的问题,而且AUP-RPE方案在攻击率达到20%后,熵值明显大于AUP,攻击者在攻击AUP-RPE时达到相同攻击成功率时通常比AUP需要更多的攻击次数,因而,AUP-RPE的攻击难度更高,具有比AUP更高、更强的安全性.
AUP-RPE着重于通过改变图形密码设置界面的布局,使用户规避具有安全隐患的使用习惯,所设置出的密码在密码空间上分布更均匀,使攻击者难以利用用户的使用习惯来加快字典攻击和暴力破解.
因此,攻击者对某一系统用户密码了解得越少,实行字典攻击或暴力破解的难度越高,从而达到提高图形密码的熵值与安全性的目标.
如果将AUP-RPE的大小再扩展到5*5,6*6,那么,尽管密码空间越来越大,但设计出的图形也越来越多,密码强度也将随之增大,但考虑到手机屏幕的大小以及用户难以记住复杂的密码,如何在提高安全性的同时兼顾可用性又是一个值得探究的问题.
AUP-RPE在提高安全性的同时兼顾了可用性,具有良好的实用性.
References:[1]SpaffordEH.
Opus:Preventingweakpasswordchoices.
Computers&Security,1992,11(3):273278.
[doi:10.
1016/0167-41f20;BACKGROUND-COLOR:#4ae2f7">4041f20;BACKGROUND-COLOR:#4ae2f7">48(92)90207-8][2]HuXX,ZhangZF,LiuWF.
Universalcomposablepasswordauthenticatedkeyexchangeprotocolinthestandardmodel.
RuanJianXueBao/JournalofSoftware,2011,22(11):28202832(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/3910.
htm[doi:10.
37241f20;BACKGROUND-COLOR:#4ae2f7">4/SP.
J.
1001.
2011.
03910][3]StandingL,ConezioJ,HaberRN.
Perceptionandmemoryforpictures:Single-Triallearningof2500visualstimuli.
PsychonomicScience,1970,19(2):73741f20;BACKGROUND-COLOR:#4ae2f7">4.
[doi:10.
3758/BF0333741f20;BACKGROUND-COLOR:#4ae2f7">426][41f20;BACKGROUND-COLOR:#4ae2f7">4]BiddleR,ChiassonS,VanOorschotPC.
Graphicalpasswords:Learningfromthefirsttwelveyears.
ACMComputingSurveys,2012,41f20;BACKGROUND-COLOR:#4ae2f7">441f20;BACKGROUND-COLOR:#4ae2f7">4(41f20;BACKGROUND-COLOR:#4ae2f7">4):No.
19.

[doi:10.
1141f20;BACKGROUND-COLOR:#4ae2f7">45/2333112.
23331141f20;BACKGROUND-COLOR:#4ae2f7">4]熊思纯等:一种随机剔除点的安卓图形解锁方案371[5]QingSH.
ResearchprogressonAndroidsecurity.
RuanJianXueBao/JournalofSoftware,2016,27(1):41f20;BACKGROUND-COLOR:#4ae2f7">4571(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/41f20;BACKGROUND-COLOR:#4ae2f7">49141f20;BACKGROUND-COLOR:#4ae2f7">4.
htm[doi:10.
13328/j.
cnki.
jos.
0041f20;BACKGROUND-COLOR:#4ae2f7">49141f20;BACKGROUND-COLOR:#4ae2f7">4][6]PassfacesCorporation.
Passfaces.
http://www.
passfaces.
com[7]BrostoffS,SasseMA.
ArePassfacesMoreUsableThanPasswordsAFieldTrialInvestigation.
In:PeopleandComputersXIV—UsabilityorElse!
London:Springer-Verlag,2000.
41f20;BACKGROUND-COLOR:#4ae2f7">405-41f20;BACKGROUND-COLOR:#4ae2f7">4241f20;BACKGROUND-COLOR:#4ae2f7">4.

[doi:10.
1007/978-1-41f20;BACKGROUND-COLOR:#4ae2f7">441f20;BACKGROUND-COLOR:#4ae2f7">471-0515-2_27][8]DavisD,MonroseF,ReiterMK.
Onuserchoiceingraphicalpasswordschemes.
In:Proc.
ofthe13thConf.
onUSENIXSecuritySymp.
,Vol.
13.
USENIXAssociation,20041f20;BACKGROUND-COLOR:#4ae2f7">4.
[9]ChiassonS,vanOorschotPC,BiddleR.
GraphicalPasswordAuthenticationUsingCuedClickPoints.
Berlin,Heidelberg:Springer-Verlag,2007.
[doi:10.
1007/978-3-541f20;BACKGROUND-COLOR:#4ae2f7">40-741f20;BACKGROUND-COLOR:#4ae2f7">4835-9_241f20;BACKGROUND-COLOR:#4ae2f7">4][10]JermynI,MayerAJ,MonroseF,ReiterMK,RubinAD.
Thedesignandanalysisofgraphicalpasswords.
In:Proc.
oftheUsenixSecurity.
1999.
[11]TaoH,AdamsC.
Pass-Go:Aproposaltoimprovetheusabilityofgraphicalpasswords.
Int'lJournalofNetworkSecurity,2008,7(2):273292.
[12]Tafasa.
Patternlock.
2010.
http://www.
tafasa.
com/patternlock.
html[13]UellenbeckS,DürmuthM,WolfC,HolzT.
Quantifyingthesecurityofgraphicalpasswords:Thecaseofandroidunlockpatterns.
In:Proc.
ofthe2013ACMSIGSACConf.
onComputer&CommunicationsSecurity.
ACM,2013.
161172.
[doi:10.
1141f20;BACKGROUND-COLOR:#4ae2f7">45/2508859.
2516700][141f20;BACKGROUND-COLOR:#4ae2f7">4]CastellucciaC,DürmuthM,PeritoD.
Adaptivepassword-strengthmetersfromMarkovmodels.
In:Proc.
oftheNDSS.
2012.
[15]CachinC.
Entropymeasuresandunconditionalsecurityincryptography[Ph.
D.
Thesis].
SwissFederalInstituteofTechnologyZürich,1997.
[16]MasseyJL.
Guessingandentropy.
In:Proc.
oftheIEEEInt'lSymp.
onInformationTheory.
IEEE,19941f20;BACKGROUND-COLOR:#4ae2f7">4.
No.
2041f20;BACKGROUND-COLOR:#4ae2f7">4.
[doi:10.
1109/ISIT.
19941f20;BACKGROUND-COLOR:#4ae2f7">4.
3941f20;BACKGROUND-COLOR:#4ae2f7">47641f20;BACKGROUND-COLOR:#4ae2f7">4][17]BonneauJ.
Thescienceofguessing:Analyzingananonymizedcorpusof70millionpasswords.
In:Proc.
oftheIEEESymp.
onSecurityandPrivacy.
IEEE,2012.
538552.
[doi:10.
1109/SP.
2012.
41f20;BACKGROUND-COLOR:#4ae2f7">49]附中文参考文献:[2]胡学先,张振峰,刘文芬.
标准模型下通用可组合的口令认证密钥交换协议.
软件学报,2011,22(11):28202832.