# Password Guessability as a Service (PGaaS)
## 4 Architecture Implementation
### Password Guessability Estimator Component
#### 4.2.2 Guessability Problem
Hence, the probability distribution is computed over the resulting equivalence classes. Training Phase  
Given a list of passwords \(\mathcal{D}\) generated by the dataset generator component, it is processed as follows [9]. 1. From the dictionary \(\mathcal{D}\), five lists \(L_{1},L_{2},L_{3},L_{4},L_{5}\) are constructed. The list \(L_{1}\) contains the prefixes from the passwords in \(\mathcal{D}\), \(L_{2}\) contains the corresponding lowercase, l33t-transformed base words, \(L_{3}\) contains the corresponding suffixes, \(L_{4}\) contains the corresponding list representations for the change patterns, and \(L_{5}\) contains the corresponding list representations for the l33t transformations. 2. From each list \(L_{i},1\leq i\leq 5\), we find the frequency of elements in the list and compute a list \(L_{i}^{p}\), having 2-tuple entries, where an entry is the form \((\text{p},\text{v})\) with p being a probability and v being a unique value. This list \(L_{i}^{p}\) essentially represents the probability space \(\mathcal{P}_{i}\). 3. Each representation of \(\mathcal{P}_{i}\) is stored persistently in an independent table of a database. This approach allows sorting these data in non-increasing order according to the first component, or querying them efficiently. 4. After computing the representations of each \(\mathcal{P}_{i}\), these representations, along with other parameters, are used to initialize the rank estimator algorithm, ESRank, which returns two lists that are stored persistently. These lists are then internally used by the algorithm to evaluate a given password efficiently. Since updated dictionaries may be generated by the dataset generator component once in a while, our service has to update the inner workings of the key-rank algorithm by running the training process described above. The running of this lengthy process may be configurable as its running frequency does not overload our service. Guessability Phase  
To evaluate how guessable a given password is, the corresponding function first decomposes it into the dimensions described above, which allows for the calculation of each probability \(p_{i},1\leq i\leq 5\) and so \(p_{*}=p_{1}p_{2}p_{3}p_{4}p_{5}\). By calling the ESrank algorithm, it finds an estimate of the password's rank \(r\) in the dictionary used for training [9]. Once the rank \(r\) of a given password is estimated, we can calculate \(\texttt{nbits}=\lceil\log_{2}(r)\rceil\), where \(\texttt{nbits}\) represents the level of security (strength) for the given password. That is, \begin{table}
\begin{tabular}{c c c} \hline \hline
**Character** & **Replacement** & **Integer Representation** \\ \hline
0 & o & 1 \\ \hline
1 & i & 12 \\ \hline! & i & 13 \\ \hline @ & a & 2 \\ \hline
4 & a & 3 \\ \hline
3 & e & 6 \\ \hline
5 & s & 5 \\ \hline
2 & z & 11 \\ \hline
5 & x & 14 \\ \hline
7 & t & 10 \\ \hline + & t & 9 \\ \hline
9 & g & 8 \\ \hline
6 & g & 7 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Correspondence for a l33t transformation. based on nbits we can then assign a security level to the given password, since guessing the password would require a full enumeration of 2\({}^{\texttt{nbits}}\) password candidates in non-increasing order of probability to find it based on the dictionary used for training [9]. Furthermore, based on nbits, some explainability may be added to the responses returned to the users utilizing the service [21]. A desirable feature to add to this guessability phase is making this computation privacy preserving. Since the input password is a sensitive piece of information, it should be kept private from this component, i.e., a user may consider it desirable to compute the strength of the given password without the cloud component learning the password itself. After a user submits their password, it will be out of their control, so the trustworthiness of the cloud servers plays a vital role in data security and privacy.