In this programming assignment, you will try to recover a password from a hash value. In the Lecture 26 (Slides No. 7-9) we have discussed the concept of password salt. The salted password (i.e. password with a salt attached) can greatly increase the search space for dictionary attack. In this assignment, you will conduct a dictionary attack only knowing hash value of salted password. In other word, you will guess or recover a password given a hash value of a salted password. To simply the guessing process, we provide a password file, which only contains 100 passwords, where each password has merely 6 uppercase letters (please refer to password.txt in uploaded). Note in reality at least 500,000 common passwords should be used in an attack.
Since normally passwords are stored as hash values, the common way to conduct a dictionary attack is to hash every password in the password file and store the hash value. Whenever we obtain a hash value, we can compare this value against the hash values in the file. If we find a match, we would know which password the hash value corresponds to. Then the password is recovered. In our case, for a file with only 100 passwords, only 100 hash values would be generated. It is very easy to search 100 hash values. To increase the difficulty of dictionary attack, password salt is introduced. The salt is a random value that we attach to a plaintext password. The hash value is calculated on the salted password (i.e. H(salt | password)). The salt (i.e. the random value) adds the uncertainty to the password. For each password, the number of possible hash values is equivalent to the number of possible combinations of salt.
In this assignment, you will use a three-digit salt. This means the salt is a decimal number and each digit can be one of 10 possible numbers, namely 0-9. Since a salt has three digits, the number of all possible salt values is 10x10x10=1000. For one password, there are 1000 possible hash values. For a file of 100 passwords, the total hash values are 100×1000=100,000. In other words, the search space for the dictionary attack is 100,000. One way to conduct the dictionary attack for the salted password is to attach every possible salt to a password and then hash the salted password (i.e. password with salt attached). Then we store all the hash values in a dictionary file. When we obtain a hash value for an unknown password, we search this value in the dictionary file. If we find a match, then the password is recovered (since the dictionary file should list which password the hash value corresponds to). With the salt, the size of the dictionary file increases 1000 times in this example.
As mentioned above, each password has 6 uppercase letters. To calculate hash, those letters would be converted to numeric values. Here we use ASCII value to represent a letter. ASCII values are widely used in computer to store character. The ASCII table can be found at https://www.asciitable.com/ (Links to an external site.)Links to an external site.. The uppercase letters have values ranging from 65 to 90. If a password is DEIKAE, you would first lay out the ASCII value of every letter side by side. So for the password of DEIKAE, you would generate 686973756569. Then you would insert the salt in front of this number sequence. For example, if a salt is 109, you would generate 109686973756569. Then apply the following hash function to this number sequence
Hash function = ( ( 243 x left ) + right ) % 85767489
Where, left is the left 8 digits of the number sequence. In this example, it is 10968697, which is treated as a long integer number. And right is the rest 7 digits of the number sequence. In this example. it is 3756569, which is treated as a long integer number.
You have 20 hours to do this. THIS must be functional in linux.
The result of the hash function is the hash value for this salted password. If we want to generate all possible hash values for this password, we need attach all possible values of salt to the password one by one. For the password DEIKAE (whose ASCII string is 686973756569). We should have 1000 salted password possibilities for this password as shown below. Then the hash values for those 1000 salted passwords will be stored in the dictionary file.