Passwords are no longer stored online without encryption. When users set a password for their account, the string doesn't appear
in plaintext on any database or server.
A popular mechanism to encrypt users passwords is to keep the hash value of the password in the database itself. A hash function converts
strings of different length into fixed-length strings known as hash values. The cryptographic hash function is one-sided and nobody knows
how hash value can be inverted to produce the original input password. An MD5 hash is created by taking a string of an any length and encoding
it into a 128-bit fingerprint (32 hex-numbers).
Suppose we want to build beforehand a table for ten-letter lowercase passwords hashed with MD5. Attackers can construct such tables
and use them to find out passwords. There are 26^10 such passwords and these data files are very large, though. In order to reduce the amount of storage space long chains of passwords are computed and saved.
Here we need to make a Time-Memory tradeoff: we accept a longer runtime in favor of fewer memory requirements.
Rainbow tables represent a compromise of both.
Let's show how a chain of passwords is constructed within the Rainbow Table. For example three reduction functions R1, R2, R3 are used
(we say that each reduction function has a different color). A chain with three reduction functions R1, R2, R3 is defined as
psswd1 --> H --> R1 --> psswd2 --> H --> R2 --> psswd3 --> H
Reduction step Rn:
a) Take the hash value, interpreted as a 128-bit integer $x$ and compute S = (x + n) mod (26**10)
The v mod(d) function returns the remainder after number v is divided by
divisor d.
Example: 17 mod(7) = 3
b) Write S in base=26 arithmetics (a =0, b=1, c=2, ..., z= 25)
S = A1 A2 ... A10
and convert Aj to letters.
For example if S = 90, then we write S as a number in base=26 arithmetics and convert it to a string of letters (a new password)
90 = 3 * 26 + 12 * 1 ---> 0 0 0 0 0 0 0 0 3 12 --> aaaaaaaadm
Take an example of a password: begisbegis
MD5 hash of this password:
a088a1b955737241ae85b88ee6f9076e
Geocaching task.
Find a password for the following hash:
299116273e0fcfba60917311a51dda2d
It is included into one of 5 chains of passwords, with the key passwords:
vilniusgeo
begisbegis
vytautaslt
palangageo
zarasaigeo
The length of each chain, i.e. the number of reduction steps Rn is n=8.
Coordinates: put the obtained password into the checker.
P.S. The safety of our passwords is guaranteed due to the need to make very very long computations in order to recover the password for
the given hash string. But for the given toy problem my solver solved it in less than 1 second.
Good luck for You.
You can validate your puzzle solution with
certitude.