What is the mechanism of the 'rainbow table' used for password analysis, etc.?

Important data such as passwords and access keys can be converted in one direction with a ' hash function ' to minimize the damage caused by leakage. However, there is also a risk of being attacked by the password being parsed from the hash value by the rainbow table that records the combination of the password and the hash value. Software engineer Kestas 'Chris' Kuliukas illustrates how such a rainbow table works.

How Rainbow Tables work
http://kestas.kuliukas.com/RainbowTables/

The hash function is a function that can convert a character string to another character string, and it is possible to calculate the character string after conversion from the character string before conversion, but the character string before conversion from the character string after conversion. Cannot be calculated. The character string before conversion is called 'Plaintexts', and the character string after conversion is called 'Hashes'. If you convert the password, access key, etc. from plaintext to hash value with a hash function, Even if only the hash value is leaked, it is possible to prevent the original data in plaintext from being restored.

However, since the conversion result from plaintext to hash value by one hash function is always the same, it is possible to 'reduce' plaintext from hash value if you know 'combination of plaintext and hash value'. This property is used in the 'rainbow table' that records the combination of plaintext and hash value, and the plaintext in which the combination is recorded can be derived by querying the hash value.

The idea itself is a simple rainbow table, but Kuliukas says that recording all the huge variety of combinations would make the data capacity too large. The 'reduction function' is built into the rainbow table to solve this problem. The reduction function is a function that can convert a hash value to plaintext, but it cannot calculate the plaintext before conversion from the hash value, and it is a function that generates 'a plaintext different from the plaintext before conversion from the hash value'. Need attention.

In the rainbow table, using the hash function and the reduction function, the plaintext is converted into a hash value, the hash value is converted into a plaintext, and the plaintext is converted into a hash value, and so on. It will be generated as a chain. Kuliukas explains that only the first plaintext and the last hash value in the chain are ultimately recorded.

The method of reducing the hash value from the rainbow table to plain text is as follows. First, compare the obtained hash value with the hash value at the end of the chain. If they match, the chain is restored, and the plaintext corresponding to the hash value at the end of the chain becomes the desired plaintext.

If the hash values do not match in the previous procedure, reduce the obtained hash value to plaintext with the reduction function, and then calculate the hash value with the hash function. Compare the calculated hash value with the hash value at the end of the chain. In other words, assuming that the obtained hash value is included in the 'hash value immediately before the end' of the chain, the processing at the time of chain generation is performed from the middle.

We will add processing to the hash value obtained so as to go back in the chain like this, and compare it with the hash value at the end of the chain each time. Repeat until the last hash value and the processed hash value match.

If at some stage the last hash value matches the processed hash value, Kuliukas explains that the chain contains the hash value obtained. Restoring the chain will lead to the desired plaintext. In this way, the rainbow table supports a huge number of combinations while reducing the amount of data.

The weak point of the rainbow table is that it is a 'collision' that derives the same calculation result from another value. If two chains collide, only the exact same value will be generated after that, reducing the amount of information that can be stored. Kuliukas explains that the rainbow table changes the reduction function step by step to avoid collisions.

A typical rainbow table is ' RainbowCrack ', which enables parallel analysis of hash functions such as MD5, SHA1, and SHA256 on the GPU.

Free software 'RainbowCrack' that decrypts Windows administrator password within 1 hour --GIGAZINE