Password Cracking Method Based On Variable Order Markov Model

At present,the most popular user authentication method is based on the username-password pair,which is easy to understand,implement,and use.However,there is a problem of insufficient password security.Therefore,the study of the password security has been a hot topic now.Among them,using different password guessing techniques to crack the password sets is the main method of studying the security of the passwordCommonly used password guessing methods include brute force,dictionary attack,probabilistic password model based attack,etc..The probabilistic password model based attack is a hot topic in recent years,and the method with best cracking effect.Probabilistic password model can be divided into two kinds,one is the password model based on template,which divides password into several segments,and calculates the password probability according to the probability of different template;Another is the full password model,which calculates the password probability as a whole.There are many studies on the password guessing methods based on template password model,and the research on the password guessing methods based on full password model is few,whose main direction is to introduce the Markov model in natural language processing technology into the calculation of password probability.Most researchers used a Markov model with fixed order.When the order is too low,it will make the calculation of each character's probability inaccurate because of the small use of historical character information;When the order is too high,the high-order Markov model is over-fitted due to the sparse problem of the training set.In this paper,we proposed a method of implementing the Markov model with variable order to solve the problems above,the BackOff method,that is,when computing the probability of the whole password,this method selects the Markov model order adaptively,which means selecting the length of historical character information adaptively according to the specific location to calculate the probability.The method is to set a count threshold,and then start from the highest order of the Markov model to try,reduce the order of the model until the count of N-gram is greater than the threshold.The process of the whole guessing method starts from the training of the real password set,then gets the collection of N-gram grammar model and the corresponding frequency.In the generating password stage,the method concats the N-grammar and the characters in the character space,calculates the password probability with Markov chain.Finally,the method gets the guessing password collection in descending order with the priority queue,and matchs the test set with the guessing set to get the corresponding crack rate of different guessing times.After four sets of comparison experiments,the proposed method based on Markov model with variable order has achieved good results.After 20 million guess times,the proposed method have been improved obviously compared to the traditional JTR tool,PCFG method and password guessing method based on Markov model with fixed order.