The Scale-free Network of Passwords : Visualization and Estimation of Empirical Passwords

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.