# Password Similarity Using Probabilistic Data Structures
## 3 Password Similarity
### Analysis of the Hash Function Family  
Another key component of the filter, which impacts on confidentiality, is the distribution of the values returned by the chosen hash function family. In this kind of probabilistic data structures, it may be necessary to deploy a huge number of hash functions. Using a different algorithm for every index can be unfeasible, and in any case a large variability within the hash function set hinders a precise analysis of the randomness of the generator. To overcome these problems, the hash function set can be generated by using the well-known salt approach, as described in Figure 4. When a value has to be inserted, many random numbers (salts) are generated. Prepending these numbers to the value, and using a fixed hash function, the effect is analogous to having adopted different, random hash functions. In our implementation we used \(MD5\) as the base hash function. The salts can be generated using different hash functions, such as Murmur hash [37] or secure cryptographic hash functions, such as SHA512. These are easily interchangeable, as libraries such as OpenSSL ([[https://openssl.org](https://openssl.org)]([https://openssl.org](https://openssl.org))) implement the various methods using interfaces that facilitate high-level use of an hash function. In Section 4 we propose a compared analysis of the speed of two hash cryptographic functions: \(MD5\) and \(SHA512\). The security of the hash function was studied in numerous works [38, 39, 40], in this case, the security of the system also relies on the division in n-grams. The salts are saved in the same location as the filter set, to allow reloading the state in subsequent invocations of the algorithm. We acknowledge that this trivial solution is vulnerable to attacks if the file is saved in clear-text form, like the one described in Section 3.4. Saving salts in a secure way seems not too challenging, and is the subject of current and future investigation aimed at making the filter immune to this kind of attacks. For example, a salt can be generated using a cipher like AES using an user provided key and a fixed payload similarly to AES-CTR mode [41]. AES, in this mode, generates an encryption stream starting from a counter \(c\). The encryption stream is derived by encrypting this counter, initialized to a random \(IV\). After this generation step, the encryption stream can be combined with the payload, using a \(xor\) operation. Similarly, we can extend the hash functions set of the filter with a function \(GenerateHashes(key)\rightarrow\Gamma\) which generates the set of hash functions \(\Gamma\) starting from the key \(key\). The salt of the functions is generated and encrypted with a key using a symmetric cypher such as \(AES\). The security in this case relies on the key, which must be chosen by the user so as to withstand known attacks such as brute force and dictionary attacks. Using this technique, the filter set can be saved without specific protections, since it can be verified only using the chosen secret key. An in-depth analysis of the security of the encryption scheme, particularly concerning the peculiarity of having very short payloads due to the division in n-grams, will be the focus of ongoing research work. These approaches to the generation of hash functions are described in Figure 4. In the first hash set we can see that \(h1\) and \(h2\) are two functions generated with a random padding applied to the \(MD5\) hash function. In this scenario we suppose to have a \(Random(n)\) function that can generate a random string of length \(n\). This generation, when re-applied will lead to a totally different set of hash functions, making the distance function inapplicable. That is the concept of the construction of \(h1^{\prime}\) and \(h2^{\prime}\). These functions can return different results from the functions \(h1\) and \(h2\) described before. Reusing the same value for the salt applied to the functions will lead to the same set of results, making the distance calculation possible.