2015/11/26 by Xiujia Guo, Guo, Xiujia, Haibo Chen +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Fractal and DNA sequence analysis #User Authentication and Security Systems
paper · pdf · doi:10.48550/arxiv.1511.08324
openalex publication_date 2015/11/26 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.