# Password Guessability as a Service (PGaaS)
## 4 Architecture Implementation
### Password Guessability Estimator Component
#### 4.2.1 Key Enumeration and Key Rank Estimation Problem  
Let \(\mathbb{K}_{*}=b_{0}b_{1}b_{2}\ldots b_{W}\) be a secret key. Assume it can be represented as a concatenation of \(\mathcal{N}=W/w\) chunks, each on \(w\) bits, i.e., \(\mathbb{K}_{*}=\mathbb{K}_{*}^{0}\parallel\mathbb{K}_{*}^{1}\parallel\ldots \parallel\mathbb{K}_{*}^{N/1}\) with \(\mathbb{K}_{*}^{i}=b_{i\cdot w}b_{i\cdot w+1}\ldots b_{i\cdot w+(w-1)}\) where \(0\leq i<\mathcal{N}\). Let us assume there is an algorithm that generates full candidates \(\mathbb{C}\) for \(\mathbb{K}_{*}\), such that any full candidate \(\mathbb{C}\) can also be represented as a concatenation of chunks \(\mathbb{C}=\mathbb{C}^{0}\parallel\mathbb{C}^{1}\parallel\ldots\parallel \mathbb{C}^{N-1}\). The method of maximum likelihood (ML) estimation then suggests picking as \(\mathbb{C}\) the value that maximizes \(\Pi_{i=0}^{N-1}\mathbb{P}(\mathbb{K}_{*}^{i}|\mathbb{C}^{i})\). Therefore, we can construct \(\mathcal{N}\) lists containing 2-tuples of the form \((\mathfrak{p},\mathfrak{v})\), where \(\mathfrak{p}=\mathbb{P}(\mathbb{K}_{*}^{i}|\mathfrak{v})\) and \(\mathfrak{v}\in\{0,1\}^{w}\), by estimating \(\mathbb{P}(\mathbb{K}_{*}^{i}|\mathfrak{v})\) for each of at most \(1\leq m_{i}\leq 2^{w}\) candidate values \(\mathfrak{v}\) for \(\mathbb{C}^{i}\)[42].  
Let \(L^{i}=[\mathbb{C}_{0}^{i},\mathbb{C}_{1}^{i},\ldots,\mathbb{C}_{m_{i}-1}^{i}]\) be the list of 2-tuples for chunk \(\mathbb{K}_{*}^{i}\). To recover the secret key \(\mathbb{K}_{*}\), we require efficient algorithms that traverse the lists \(L^{i}\) to pick 2-tuples \(\mathbb{C}_{j}^{i}\) and then combine them to obtain full key candidates \(\mathbb{C}\) in decreasing order based on their total probabilities (the product of its chunk candidates probabilities). This problem has been addressed previously in the side-channel analysis literature, with a variety of different algorithms able to solve this problem and the related problem known as the key-rank estimation [43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57]. We remark that each method of enumerating the full key candidates defines a new variant of the key-enumeration problem [42] and that these variants arise in many cryptographic contexts [58; 59; 60; 61; 62; 63].  
The key rank estimation problem, on the other hand, is defined as follows. Given \(\mathcal{N}\) sub-key spaces of sizes \(m_{i}\) with their corresponding probability distributions \(\mathbb{P}(\mathbb{K}_{*}^{i}|\mathfrak{v})\) sorted in non-increasing order of probabilities, a key \(\mathbb{K}_{*}=\mathbb{K}_{*}^{0}\parallel\mathbb{K}_{*}^{1}\parallel\ldots \parallel\mathbb{K}_{*}^{N-1}\) and its probability \(p_{*}=\Pi_{i=0}^{N-1}\mathbb{P}(\mathbb{K}_{*}^{i}|\mathbb{C}_{*}^{i})\), then the key rank estimation problem asks for estimating the number of full key candidates with probability higher than \(p_{*}\), when the probability of a full key is defined as the product of its chunk key probabilities. The idea is to estimate \(\mathbb{K}_{*}\)'s rank, i.e., the position of the key \(\mathbb{K}_{*}\) in the list of \(\Pi_{i=0}^{N-1}m_{i}\) full key candidates when this list is sorted in non-increasing probability order, from the most likely full candidate key to the least likely [9; 43; 44; 45; 55; 56; 57].  
Our password guessability estimator component, explained in more detail in Section 4.2.2, will measure how guessable a given password is as its relative position in a long list of passwords (dictionary) used on the training of the corresponding algorithm. Note that this approach is a natural way to measure how guessable a given password is, since password-cracking tools, such as John the Ripper [6], will attempt to brute force all the passwords within a given dictionary constructed from common passwords, from the most likely to the least.