The Scale-free Network of Passwords : Visualization and Estimation of Empirical Passwords
This work addresses password security for cybersecurity researchers and practitioners by providing a novel set-level analysis, though it is incremental in applying network theory to password data.
The paper tackles the problem of understanding password security at the set level by visualizing empirical password data from sources like Yahoo and Phpbb, revealing spatial structures and clustering patterns. It proposes a statistical guessing attack model based on topological space, proving that the minimal dictionary problem for compromising passwords is NP-complete.
In this paper, we present a novel vision of large scale of empirical password sets available and improve the understanding of passwords by revealing their interconnections and considering the security on a level of the whole password set instead of one single password level. Through the visualization of Yahoo, Phpbb, 12306, etc. we, for the first time, show what the spatial structure of empirical password sets are like and take the community and clustering patterns of the passwords into account to shed lights on the definition of popularity of a password based on their frequency and degree separately. Furthermore, we propose a model of statistical guessing attack from the perspective of the data's topological space, which provide an explanation of the "cracking curve". We also give a lower bound of the minimum size of the dictionary needed to compromise arbitrary ratio of any given password set by proving that it is equivalent to the minimum dominating set problem, which is a NP-complete problem. Hence the minimal dictionary problem is also NP-complete.