Im finding it difficult to understand reverse look up tables and how it works, and the concept of hash chains. This is apart of a computer security model i am taking.
So i understand that brute force, dictionary attack and look up table take up a lot of time, and store all options and then search through all the database. however reverse look up tables addresses this problem, and sacrifices time for storage. But how this happens i am getting confused.
Many thanks
4
Let’s say you want to crack passwords which are stored as MD5 Hashes (This is very old technology). Since brute force takes a real long time, and this function is “non-reversible”, then the attack is the Reverse Lookup table.
The idea is that you create a table storing what you enter as input and the hash it generates. After you run your routine with as many inputs you think are valid, you can then attack the password file with a reverse lookup table: you browse your database browsing not by the password but for what Hash matches.
Reverse lookup then, is simply not looking by the same input, but for inputs which generate the same output. For example:
input | Hash generated
admin | 21232f297a57a5a743894a0e4a801fc3
Instead of looking for the admin string, in your table you would be looking by the string which matches the hash 21232f297a57a5a743894a0e4a801fc3.
For more details, look for Raibow tables in the wikipedia, I think you will note that they are not exactly the same, but in the article you can find the difference between both.
How it sacrifices time for storage?
The idea is that you would need a full database with the data as similar to the one above, and this is storage. The time per query, is only a B-tree lookup (O(log n)) on the database, since the key could be the hash. This does not mean that to generate the table you don’t spend time. It just means that once you have the database, you can query it in a very small time.