# Password Similarity Using Probabilistic Data Structures
## 3 Password Similarity
### Anagram Attack  
The system as described in the previous sections is vulnerable to an attack which exploits the order of the discovered n-grams. This attack aims to reconstruct the password as the anagram of the various n-grams. The attack is composed of four steps:  
1. Generate all the hashes for a specific n-gram;
2. Hash the n-grams into a Bloom Filter;
3. Analyze the Bloom Filter and get the position of bits set to the true value;
4. Compose the various n-grams to create a password.  
This scenario can be disruptive and can lead to the full disclosure of hashed password in no time. Additionally, this kind of attack can be enhanced with the help of a word dictionary similar to the one used in classical password attacks: the search tree can be pruned by excluding the words which do not contain the n-gram. For instance, let us imagine that a user inserts the password \"password!!\" in the filter and splitting the input in a list of bi-grams. In this work, we use a general definition  
Figure 4: Different hash functions generation. These functions will lead to different use-cases. In the first two figures we have a fully random generation which leads to different cases every time as we cannot predict the output got from \(Random\) function. The fourth case employs a cryptographic function and a set of fixed strings (\(fixedslt_{n}\)) to generate the same set of hash function based on a secret key \(k\).  
of \(\
u\)-grams functions, a \(\
u\)-gram function will split the input in its \(\
u\)-grams, where \(\
u\) is the number of characters in each substring. In the case of bigrams, obviously \(\
u=2\). Accordingly, the attacker will generate all the possible bi-grams. This, using an alphabet \(\Delta\) will result in a generation of \(|\Delta|^{2}\) bi-grams which, for the ASCII case, is \((127-32)^{2}=9025\) bi-grams, an operation which requires at most a couple of milliseconds on any modern CPU. After this step, the attacker will hash the bi-grams inserting them into the filter, which requires \(\Theta(n)\) insertions with \(n\) as the number of bi-grams. Subsequently, the attacker can create all the possible combinations in the search space generated by the pruned alphabet of bi-grams \(\Delta_{II}\). The research can be conducted by using an incremental number of repetitions. Therefore, the number of combinations which can be generated using the corresponding Bloom Filter are:  
\[\begin{pmatrix}\Delta_{\
u}\\ \dfrac{n}{\
u}\end{pmatrix} \tag{2}\]  
with \(n\) as the length of the searched string. In the case of a common password of 8 ASCII characters and a Bloom Filter constructed with bi-grams the formula will result to:  
\[\begin{pmatrix}9025\\ \dfrac{8}{2}\end{pmatrix}\approx 2.76\times 10^{14} \tag{3}\]  
combinations. If we consider the worst case with repetitions the formula becomes  
\[\begin{pmatrix}\Delta_{\
u}+\dfrac{n}{\
u}-1\\ \dfrac{n}{\
u}\end{pmatrix} \tag{4}\]  
which, in this example, will result to \(\begin{pmatrix}9025+4-1\\ 4\end{pmatrix}\) which is almost the same value as seen for the non-repetition case. Passwords can be longer than eight characters to provide enough security against brute-force or dictionary attacks. For a password varying from \(n\) characters to \(N\) the number of combinations are:  
\[\sum_{i=n}^{N}\begin{pmatrix}\Delta_{\
u}+\dfrac{i}{\
u}-1\\ \dfrac{i}{\
u}\end{pmatrix} \tag{5}\]  
In our data-set the average password size was 11.56, therefore, limits between 8 and 14 can be evaluated resulting in:  
\[\sum_{i=8}^{14}\begin{pmatrix}9025+\dfrac{i}{2}-1\\ \dfrac{i}{2}\end{pmatrix}\approx 9.96\times 10^{23} \tag{6}\]  
The crypto-analysis of the attack should include the details of the filter like the size of the bucket or the number of hash functions used.