# Dynamic Markov Model: Password Guessing Using Probability Adjustment Method
## 3 Method
### Dynamic Distribution Mechanism  
For all of the above problems, we propose the dynamic distribution mechanism during the generation process in the Markov model to reduce the repetition rate, so as to improve \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Total Number** & \(\mathbf{10^{5}}\) & \(\mathbf{10^{6}}\) & \(\mathbf{10^{7}}\) & \(\mathbf{10^{8}}\) & \(\mathbf{10^{9}}\) \\ \hline Repeated number & \(3.41\times 10^{4}\) & \(4.79\times 10^{5}\) & \(5.94\times 10^{6}\) & \(6.86\times 10^{7}\) & \(7.59\times 10^{8}\) \\ Repetition rate & 34.12\% & 47.93\% & 59.37\% & 68.61\% & 75.89\% \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Number of repeated passwords and repetition rate for standard Markov model. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Probability** & **Total** & **Dynamic Markov** & **Standard Markov** & **OMEN** \\ \hline \(10^{-2}\)\(\sim\)\(10^{-3}\) & 4 & 4 & 4 & 4 \\ \(10^{-3}\)\(\sim\)\(10^{-4}\) & 243 & 243 & 243 & 243 \\ \(10^{-4}\)\(\sim\)\(10^{-5}\) & 2701 & 2701 & 2701 & 2671 \\ \(10^{-5}\)\(\sim\)\(10^{-6}\) & 19,827 & 19,827 & 19,826 & 19,456 \\ \(10^{-6}\)\(\sim\)\(10^{-7}\) &the cover rate. In establishing the dynamic distribution mechanism, we mainly consider four points, as follows:  
First, the dynamic distribution mechanism is apply only in the random sampling method. Second, each time a password \(P_{G}\) is generated, the dynamic distribution mechanism is adopted. It prohibits \(P_{G}\) by reducing its probability value, thereby reducing the possibility of subsequent appearance of \(P_{G}\). As the probability of the password in the Markov model is the product of multiple conditional probabilities, the passwords' probability expression has a complex interwoven relationship, then we can consider subtracting \(p(P_{G})\) by a small constant. Third, since the sum of the probability of all passwords in support set \(S_{M}\) is 1, prohibiting \(P_{G}\) would inevitably lead to a change in probability of other passwords in \(S_{M}\). Here, we could increase the probability value of all passwords in \(S_{M}\) other than \(P_{G}\), thus the model would focus more on obtaining other passwords in the next. Finally, it should be pointed out that for strings other than \(S_{M}\), we think they have little meaning for cracking, and adjusting their probability would require a large amount of computing resources, so the dynamic distribution mechanism only changes the probability of passwords in support set \(S_{M}\). There are several advantages to the dynamic distribution mechanism:  
1. It can decrease the repetition rate. Once a password is generated, it will be restricted, and the chance of being randomly sampled will be reduced. At the same time, the chance of other passwords being randomly sampled will be increased. The degree of constraint is related to the probability value. Considering the situation that the higher the password's probability, the larger its contribution to the repetition rate, so this mechanism can decrease the repetition rate accordingly. On the other hand, we find that the dynamic distribution mechanism pushes the probability distribution of passwords toward uniform distribution \(U_{uni}\) according to Theorem 1. The closer the probability distribution gets to the uniform distribution \(U_{uni}\), the smaller the repetition rate. 2. It can improve the cover rate. Compared with simple random sampling, the dynamic distribution mechanism can help the model to adjust distribution constantly. This adjustment makes the model avoid useless attempts, but encourages it to try completely new passwords. 3. It can cover high-probability passwords better. In the random sampling method, the appearance frequency of passwords is relevant to their probability. The dynamic distribution mechanism designs a smooth and slow process which ensures that some passwords will keep a high probability value for a long time. At the same time, its effect of reducing repeated passwords expands the search range of high-probability passwords.