Research Article
Exploring the Network of Real-World Passwords: Visualization and Estimation
@INPROCEEDINGS{10.1007/978-3-319-78813-5_8, author={Xiujia Guo and Zhao Wang and Zhong Chen}, title={Exploring the Network of Real-World Passwords: Visualization and Estimation}, proceedings={Security and Privacy in Communication Networks. 13th International Conference, SecureComm 2017, Niagara Falls, ON, Canada, October 22--25, 2017, Proceedings}, proceedings_a={SECURECOMM}, year={2018}, month={4}, keywords={Computer security Visualization Password sets Power-law distribution Scale-free network NP-complete}, doi={10.1007/978-3-319-78813-5_8} }- Xiujia Guo
Zhao Wang
Zhong Chen
Year: 2018
Exploring the Network of Real-World Passwords: Visualization and Estimation
SECURECOMM
Springer
DOI: 10.1007/978-3-319-78813-5_8
Abstract
The distribution of passwords has been the focus of many researchers when we come to security and privacy issues. In this paper, the spatial structure of empirical password sets is revealed through the visualization of disclosed password sets from the website of hotmail, 12306, phpbb and yahoo. Even though the choices of passwords, in most of the cases, are made independently and privately, on closer scrutiny, we surprisingly found that the networks of passwords sets of large scale individuals have similar topological structure and identical properties, regardless of demographic factors and site usage characteristics. The visualized graph of passwords is considered to be a scale-free network for whose degree distribution the power law is a good candidate fit. Furthermore, on the basis of the network graph of the password set we proposed, the optimal dictionary problem in dictionary-based password cracking is demonstrated to be equivalent in computing complexity to the dominating set problem, which is one of the well-known NP-complete problems in graph theory. Hence the optimal dictionary problem is also NP-complete.