SecureComm2017_NetworkOfPasswords

This is the repo of Exploring the Network of Real-World Passwords: Visualization and Estimation, which was accepted by SecureComm 2017.

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.

Citation

@inproceedings{guo2017exploring,
  title={Exploring the Network of Real-World Passwords: Visualization and Estimation},
  author={Guo, Xiujia and Wang, Zhao and Chen, Zhong},
  booktitle={International Conference on Security and Privacy in Communication Systems},
  pages={147--166},
  year={2017},
  organization={Springer}
}

Notes

Note that I have not found a proper way to share the figures without uploading them directly to github repo, which is not such an elegant idea. For those interested, send me a email to xiujiaguo@gmail.com. I will try to solve the problem as soon as possible.

Hard Copy

You can get a copy from Springer: https://link.springer.com/chapter/10.1007/978-3-319-78813-5_8.