Dynamic Markov Model: Password Guessing Using Probability Adjustment Method

Abstract

In password guessing, the Markov model is still widely used due to its simple structure and fast inference speed. However, the Markov model based on random sampling to generate passwords has the problem of a high repetition rate, which leads to a low cover rate. The model based on enumeration has a lower cover rate for high-probability passwords, and it is a deterministic algorithm that always generates the same passwords in the same order, making it vulnerable to attack. We design a dynamic distribution mechanism based on the random sampling method. This mechanism enables the probability distribution of passwords to be dynamically adjusted and tend toward uniform distribution strictly during the generation process. We apply the dynamic distribution mechanism to the Markov model and propose a dynamic Markov model. Through comparative experiments on the RockYou dataset, we set the optimal adjustment degree α. Compared with the Markov model without the dynamic distribution mechanism, the dynamic Markov model reduced the repetition rate from 75.88% to 66.50% and increased the cover rate from 37.65% to 43.49%. In addition, the dynamic Markov model had the highest cover rate for high-probability passwords. Finally, the model avoided the lack of a deterministic algorithm, and when it was run five times, it reached almost the same cover rate as OMEN.

Keywords

• information security
• password guessing
• Markov model
• machine learning
• dynamic mechanism
• probability adjustment