# Dynamic Markov Model: Password Guessing Using Probability Adjustment Method
## 5 Discussion  
In the task of password guessing, the core is to build a generative model that can generate real passwords. The Markov model based on the statistical method is still widely used due to its good generation effect and high efficiency. The standard Markov model uses the random sampling method to generate passwords, which leads to a high repetition rate, thus affecting the cover rate of generated passwords. The Markov model based on enumeration is a deterministic algorithm. It always generates the same passwords in the same order and can be attacked easily in some specific cases. In addition, the cover rate of high-probability passwords by the enumeration method is not as good as the random sampling algorithm.  
To address the above problems, we first design a dynamic distribution mechanism for use in the process of password generation. This mechanism continuously decreases the probability value of high-probability passwords, then the distribution of passwords continues to tend to be uniform distribution strictly, so as to achieve the effect of reducing the repetition rate and improving the cover rate. The dynamic distribution mechanism is designed based on the random sampling method, so it can avoid the shortcomings of the deterministic algorithm and enhance the cover effect of high-probability passwords. In addition, considering practical difficulties and generation efficiency, we fine-tune the dynamic distribution mechanism. We successfully apply it to the Markov model, and propose the dynamic Markov model. These changes mainly include the following: (1) randomly choose an n-gram fragment responded distribution to adjust; (2) just verify whether the probability of the n-gram fragment is greater than \(\alpha\); and (3) the adjustment range of probability distribution is limited to some passwords of the support set.  
In the dynamic Markov model, the selection of parameter \(\alpha\) has a significant impact on the performance. A larger parameter setting may not only significantly reduce the repetition rate, but also reduce the cover rate, and a smaller parameter setting may not be able to exert the effect of the dynamic distribution mechanism. By comparing the results of  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Times** & **Dynamic Markov** & **Standard Markov** & **OMEN** \\ \hline
1 & 43.49\% & 37.65\% & 57.10\% \\
2 & 49.29\% (plus 5.80\%) & 39.11\% (plus 1.46\%) & 57.10\% (plus 0\%) \\
3 & 52.59\% (plus 3.30\%) & 39.98\% (plus 0.87\%) & 57.10\% (plus 0\%) \\
4 & 54.90\% (plus 2.31\%) & 42.18\% (plus 2.20\%) & 57.10\% (plus 0\%) \\
5 & 56.88\% (plus 1.98\%) & 43.42\% (plus 1.24\%) & 57.10\% (plus 0\%) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Change of cover rate with generation time.  
a series of experiments, we selected the optimal \(\alpha\) value so that it would take into account both the repetition rate and the cover rate. Compared with the standard Markov model, 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%. However, the cover rate still had a gap of 13.61% compared to OMEN. Through the analysis of the cover number of high-probability passwords, we find that the generation algorithm based on random sampling has better results than the method based on enumeration (OMEN), and the dynamic Markov model performed better than the standard Markov model every time. The dynamic Markov model is a random algorithm, and every password is generated randomly, while the deterministic algorithm (OMEN) does not contain any randomness and can be attacked easily. In addition, considering the effects of multiple password generation, the dynamic Markov model could achieve almost the same cover rate as OMEN.