一种基于结构划分及字符串重组的口令攻击方法
|
摘要
身份认证是网络安全的一道重要防线,口令长期以来一直是身份认证的主流方式,口令攻击是口令安全研究的重要手段.基于概率上下文无关文法(Probabilistic Context-Free Grammar,PCFG)和基于Markov链的模型是目前效果最为显著的两类口令攻击方法,它们分别从子结构组成层面和字符前后依赖层面对口令进行有效地建模刻画.该文中,作者在综合上述两类模型优点的基础上提出了一种基于结构划分及字符串重组的口令攻击方法,记为SPSR模型:首先将口令划分成抽象的子结构,然后利用改进的Markov链模型生成子结构中字符、数字和符号等构成的子串,以同时兼顾模型的准确性和泛化能力.此外,作者在结构划分阶段还额外引入了常用字符段,并加入了索引位对特殊字符在口令中的位置进行了明确地刻画;在字符串重组阶段,通过递归的思想减少子串概率计算中的重复计算,给出了一个改进的OMEN算法——Recursive-OMEN算法.为了验证SPSR模型的有效性,分别在6个真实的中英文口令集上进行了实验测试.结果表明,按概率递减顺序生成相同规模的猜测口令集时,新提出的Recursive-OMEN算法比OMEN算法用时缩短了10倍左右;在相同的猜测次数下考察攻击效果时,SPSR模型比基于Markov链的模型能多破解出40%～50%的口令,比基于PCFG的模型能多破解出20%左右的口令.
Identity authentication is a key line of defense for network security,and it is also the last line of defense to protect user's privacy.Passwords are the mainstream of identity authentication.Despite there are a great mass of issues in passwords regarding security and usability,and a large number of new authentication technologies have also been proposed in succession,password-based authentication method will still be the most important authentication method for a long time due to its simplicity,low cost,and easiness to deploy.Therefore,passwords have attracted widespread attention from scholars around the world in recent years,and a large number of significant researches have emerged.With the popularity of password authentication technology,passwords are used more and more frequently in people's daily lives,and passwords have been closely related to personal information and property security.Therefore,password security research has important practical significance.Password attack is an important means of password security research.Probabilistic context-free grammar(PCFG) and Markov chain-based models are the most effective methods of password attack among numerous algorithms at present.They effectively characterize the passwords from the substructure level and the character dependent level respectively.The PCFG algorithm systematically studies the structure of passwords and can effectively abstract the structural features of passwords.The Markov chain-based algorithm profoundly explores the composition of characters,and can dig out the user's character usage habits when constructing passwords.In this paper,we collect 3 Chinese datasets and 3 English datasets:Dodonew,CSDN,JingDong,Yahoo,PhpBB,RockYou.We further study the structure and character composition of passwords and find that some string in the dataset will appear frequently,and special characters always appear in specific locations of the password.Thus,based on the merits of the PCFG and Markov chain-based models,we propose a password attack method based on structure partition and string reorganization,which is denoted as SPSR model.Firstly,the passwords are divided into abstract substructures,and then substrings of characters,numbers and symbols in substructures are generated by using an improved Markov chain model to take account of the accuracy and generalization ability of the model.In addition,we also introduce common character segment in the structure division stage,and add the index bit to explicitly depict the position of the special characters in the passwords.During the string reorganization phase,we reduce repeated calculation in the generation of substring's probability,via proposing an improved OMEN algorithm called Recursive-OMEN.The SPSR model fully exploits the password structure distribution and character composition,and explores the deeper user habit of constructing passwords.It is a systematic and comprehensive trawling password attacking model.Finally,the method is verified by experiment on six real Chinese and English password datasets.The results show that Recursive-OMEN is about 10 times faster than OMEN when generating the same number of strings.On the context of fixed number of guess trials,the SPSR model breaks 40%-50% of the password more than Narayanan's method,about 20% than Weir et al.'s method password between the cross datasets.
Identity authentication is a key line of defense for network security,and it is also the last line of defense to protect user's privacy.Passwords are the mainstream of identity authentication.Despite there are a great mass of issues in passwords regarding security and usability,and a large number of new authentication technologies have also been proposed in succession,password-based authentication method will still be the most important authentication method for a long time due to its simplicity,low cost,and easiness to deploy.Therefore,passwords have attracted widespread attention from scholars around the world in recent years,and a large number of significant researches have emerged.With the popularity of password authentication technology,passwords are used more and more frequently in people's daily lives,and passwords have been closely related to personal information and property security.Therefore,password security research has important practical significance.Password attack is an important means of password security research.Probabilistic context-free grammar(PCFG) and Markov chain-based models are the most effective methods of password attack among numerous algorithms at present.They effectively characterize the passwords from the substructure level and the character dependent level respectively.The PCFG algorithm systematically studies the structure of passwords and can effectively abstract the structural features of passwords.The Markov chain-based algorithm profoundly explores the composition of characters,and can dig out the user's character usage habits when constructing passwords.In this paper,we collect 3 Chinese datasets and 3 English datasets:Dodonew,CSDN,JingDong,Yahoo,PhpBB,RockYou.We further study the structure and character composition of passwords and find that some string in the dataset will appear frequently,and special characters always appear in specific locations of the password.Thus,based on the merits of the PCFG and Markov chain-based models,we propose a password attack method based on structure partition and string reorganization,which is denoted as SPSR model.Firstly,the passwords are divided into abstract substructures,and then substrings of characters,numbers and symbols in substructures are generated by using an improved Markov chain model to take account of the accuracy and generalization ability of the model.In addition,we also introduce common character segment in the structure division stage,and add the index bit to explicitly depict the position of the special characters in the passwords.During the string reorganization phase,we reduce repeated calculation in the generation of substring's probability,via proposing an improved OMEN algorithm called Recursive-OMEN.The SPSR model fully exploits the password structure distribution and character composition,and explores the deeper user habit of constructing passwords.It is a systematic and comprehensive trawling password attacking model.Finally,the method is verified by experiment on six real Chinese and English password datasets.The results show that Recursive-OMEN is about 10 times faster than OMEN when generating the same number of strings.On the context of fixed number of guess trials,the SPSR model breaks 40%-50% of the password more than Narayanan's method,about 20% than Weir et al.'s method password between the cross datasets.
引文
[1]Wang Ping,Wang Ding,Huang Xin-Yi.Advances in password security.Computer Research and Development,2016,53(10):2173-2188(in Chinese)(王平,汪定,黄欣沂.口令安全研究进展.计算机研究与发展,2016,53(10):2173-2188)
[2]Biddle R,Chiasson S,Oorschot P C V.Graphical passwords:Learning from the first twelve years.ACM Computing Surveys,2012,44(4):1-41
[3]Jain A K,Ross A,Pankanti S.Biometrics:A tool for information security.IEEE Transactions on Information Forensics&Security,2006,1(2):125-143
[4]Huang X Y,Yang X,Chonka A,et al.A generic framework for three-factor authentication:Preserving security and privacy in distributed systems.IEEE Transactions on Parallel&Distributed Systems,2010,22(8):1390-1397
[5]Stajano F,Oorschot P C V,Herley C,et al.The quest to replace passwords:A framework for comparative evaluation of web authentication schemes//Proceedings of the 33rd IEEE Symposium on Security and Privacy.San Francisco,USA,2012:553-567
[6]Bonneau J,Herley C,Oorschot P C V,et al.Passwords and the evolution of imperfect authentication.Communications of the ACM,2015,58(7):78-87
[7]Herley C,Oorschot P V.A research agenda acknowledging the persistence of passwords.IEEE Security&Privacy,2012,10(1):28-36
[8]Freeman D,Dürmuth M,Biggio B.Who are you?a statistical approach to measuring user authenticity//Proceedings of the Network&Distributed System Security Symposium.San Diego,USA,2016:1-15
[9]Shen Ying,Liao Liu-Cheng,Dong Tian-Yang.Password strength metric based classification proactive model.Computer Science,2015,42(11):222-227(in Chinese)(沈瑛,廖刘承,董天阳.口令强度评估的分级先验模型研究.计算机科学,2015,42(11):222-227)
[10]Oechslin P.Making a faster cryptanalytic time-memory trade-off.Lecture Notes in Computer Science,2003,2729(4):617-630
[11]Wang Ding.Research on Key Issues in Password Security[Ph.D.dissertation].School of Information Science and Technology,Peking University,Beijing,2017(in Chinese)(汪定.口令安全关键技术研究[博士学位论文].北京大学信息科学技术学院,北京,2017)
[12]Narayanan A,Shmatikov V.Fast dictionary attacks on passwords using time-space trade off//Proceedings of the12th ACM Conference on Computer and Communications Security.Alexander,USA,2005:364-372
[13]Weir M,Aggarwal S,Medeiros B D,et al.Password cracking using probabilistic context-free grammars//Proceedings of the30th IEEE Symposium on Security and Privacy.Washington,USA,2009:391-405
[14]Ma J,Yang W N,Luo M,et al.A study of probabilistic password models//Proceedings of the 35th IEEE Symposium on Security and Privacy 2014.San Jose,USA,2014:689-704
[15]Dürmuth M,Angelstorf F,Castelluccia C,et al.OMEN:Faster password guessing using an ordered Markov enumerator//Proceedings of the 7th International Symposium on Engineering Secure Software and Systems.Milan,Italy,2015:119-132
[16]Houshmand S,Aggarwal S,Flood R.Next gen PCFG password cracking.IEEE Transactions on Information Forensics&Security,2017,10(8):1776-1791
[17]Wang D,Zhang Z J,Wang P,et al.Targeted online password guessing:an underestimated threat//Proceedings of the 2016ACM SIGSAC Conference on Computer and Communications Security.Vienna,Austria,2016:1242-1254
[18]Wang D,Wang P.On the implications of Zipf’s law in passwords//Proceedings of the 21st European Symposium on Research in Computer Security.Heraklion,Greece,2016:111-131
[19]Wang D,Cheng H B,Wang P,et al.Zipf’s law in password.IEEE Transactions on Information Forensics and Security,2017,12(11):2776-2791
[20]Paar C,Pelzl J.Understanding Cryptography.Berlin Heidelberg:Springer,2010:519-551
[21]Klein D V.A survey of,and improvements to,password security.Programming&Computer Software,2001,17(3):5-14
[22]Bonneau J.The science of guessing:Analyzing an anonymized corpus of 70 million passwords//Proceedings of the 33rd IEEE Symposium on Security and Privacy.San Francisco,USA,2012:538-552
[23]Lopez J,Cranor L F,Christin N,et al.Guess again(and Again and Again):Measuring password strength by simulating password-cracking algorithms//Proceedings of the 33rd IEEESymposium on Security and Privacy.San Francisco,USA,2012:523-537
[24]Zou Jing,Lin Dong-Dai,Hao Chun-Hui.A password cracking method based on structure division probability.Chinese Journal of Computers,2014,37(5):1206-1215(in Chinese)(邹静,林东岱,郝春辉.一种基于结构划分概率的口令攻击方法.计算机学报,2014,37(5):1206-1215)
[25]Han Wei-Li,Yuan Lang,Li Si-Si,et al.An efficient algorithm to generate password sets based on samples.Chinese Journal of Computers,2017,40(5):1151-1167(in Chinese)(韩伟力,袁琅,李思斯等.一种基于样本的模拟口令集生成算法.计算机学报,2017,40(5):1151-1167)
[26]Wang D,Cheng H B,Wang P,et al.A security analysis of honeywords//Proceedings of the 25th ISOC Network and Distributed System Security Symposium.San Diego,USA,2018:1-16
[2]Biddle R,Chiasson S,Oorschot P C V.Graphical passwords:Learning from the first twelve years.ACM Computing Surveys,2012,44(4):1-41
[3]Jain A K,Ross A,Pankanti S.Biometrics:A tool for information security.IEEE Transactions on Information Forensics&Security,2006,1(2):125-143
[4]Huang X Y,Yang X,Chonka A,et al.A generic framework for three-factor authentication:Preserving security and privacy in distributed systems.IEEE Transactions on Parallel&Distributed Systems,2010,22(8):1390-1397
[5]Stajano F,Oorschot P C V,Herley C,et al.The quest to replace passwords:A framework for comparative evaluation of web authentication schemes//Proceedings of the 33rd IEEE Symposium on Security and Privacy.San Francisco,USA,2012:553-567
[6]Bonneau J,Herley C,Oorschot P C V,et al.Passwords and the evolution of imperfect authentication.Communications of the ACM,2015,58(7):78-87
[7]Herley C,Oorschot P V.A research agenda acknowledging the persistence of passwords.IEEE Security&Privacy,2012,10(1):28-36
[8]Freeman D,Dürmuth M,Biggio B.Who are you?a statistical approach to measuring user authenticity//Proceedings of the Network&Distributed System Security Symposium.San Diego,USA,2016:1-15
[9]Shen Ying,Liao Liu-Cheng,Dong Tian-Yang.Password strength metric based classification proactive model.Computer Science,2015,42(11):222-227(in Chinese)(沈瑛,廖刘承,董天阳.口令强度评估的分级先验模型研究.计算机科学,2015,42(11):222-227)
[10]Oechslin P.Making a faster cryptanalytic time-memory trade-off.Lecture Notes in Computer Science,2003,2729(4):617-630
[11]Wang Ding.Research on Key Issues in Password Security[Ph.D.dissertation].School of Information Science and Technology,Peking University,Beijing,2017(in Chinese)(汪定.口令安全关键技术研究[博士学位论文].北京大学信息科学技术学院,北京,2017)
[12]Narayanan A,Shmatikov V.Fast dictionary attacks on passwords using time-space trade off//Proceedings of the12th ACM Conference on Computer and Communications Security.Alexander,USA,2005:364-372
[13]Weir M,Aggarwal S,Medeiros B D,et al.Password cracking using probabilistic context-free grammars//Proceedings of the30th IEEE Symposium on Security and Privacy.Washington,USA,2009:391-405
[14]Ma J,Yang W N,Luo M,et al.A study of probabilistic password models//Proceedings of the 35th IEEE Symposium on Security and Privacy 2014.San Jose,USA,2014:689-704
[15]Dürmuth M,Angelstorf F,Castelluccia C,et al.OMEN:Faster password guessing using an ordered Markov enumerator//Proceedings of the 7th International Symposium on Engineering Secure Software and Systems.Milan,Italy,2015:119-132
[16]Houshmand S,Aggarwal S,Flood R.Next gen PCFG password cracking.IEEE Transactions on Information Forensics&Security,2017,10(8):1776-1791
[17]Wang D,Zhang Z J,Wang P,et al.Targeted online password guessing:an underestimated threat//Proceedings of the 2016ACM SIGSAC Conference on Computer and Communications Security.Vienna,Austria,2016:1242-1254
[18]Wang D,Wang P.On the implications of Zipf’s law in passwords//Proceedings of the 21st European Symposium on Research in Computer Security.Heraklion,Greece,2016:111-131
[19]Wang D,Cheng H B,Wang P,et al.Zipf’s law in password.IEEE Transactions on Information Forensics and Security,2017,12(11):2776-2791
[20]Paar C,Pelzl J.Understanding Cryptography.Berlin Heidelberg:Springer,2010:519-551
[21]Klein D V.A survey of,and improvements to,password security.Programming&Computer Software,2001,17(3):5-14
[22]Bonneau J.The science of guessing:Analyzing an anonymized corpus of 70 million passwords//Proceedings of the 33rd IEEE Symposium on Security and Privacy.San Francisco,USA,2012:538-552
[23]Lopez J,Cranor L F,Christin N,et al.Guess again(and Again and Again):Measuring password strength by simulating password-cracking algorithms//Proceedings of the 33rd IEEESymposium on Security and Privacy.San Francisco,USA,2012:523-537
[24]Zou Jing,Lin Dong-Dai,Hao Chun-Hui.A password cracking method based on structure division probability.Chinese Journal of Computers,2014,37(5):1206-1215(in Chinese)(邹静,林东岱,郝春辉.一种基于结构划分概率的口令攻击方法.计算机学报,2014,37(5):1206-1215)
[25]Han Wei-Li,Yuan Lang,Li Si-Si,et al.An efficient algorithm to generate password sets based on samples.Chinese Journal of Computers,2017,40(5):1151-1167(in Chinese)(韩伟力,袁琅,李思斯等.一种基于样本的模拟口令集生成算法.计算机学报,2017,40(5):1151-1167)
[26]Wang D,Cheng H B,Wang P,et al.A security analysis of honeywords//Proceedings of the 25th ISOC Network and Distributed System Security Symposium.San Diego,USA,2018:1-16