Rainbow tables - это реально прикольный алгоритм сжатия.
Идея там в том, что в оригинале у нас есть (виртуально) очень большая
таблица для поиска хэшей по паролям типа
hash1 - pass1
hash2 - pass2
...
В "сыром" виде такая таблица занимала бы в миллионы (!) раз больше чем RT,
так что это они на самом деле еще мало весят
Допустим, 0-9a-z 8 знаков - это 2,821,109,907,456 только комбинаций,
а на каждую нам надо хранить допустим (для sha1) 20 байт хэша и 8 байт пароля.

Так вот, идея RT в том, что поскольку паролей очень много, то случайно
сгенеренные пароли в нужном чарсете будут достаточно часто совпадать с
реальными. А дальше, хэши можно использовать в качестве сида для генерации
пароля.
В "сырой" таблице просто пары {pass;hash}, но можно пароли генерить из
хэшей, если правильно функцию генерации накрутить.
Например, если в базе _все_ пароли 0-9a-z 8цифр, то понятно, что можно
большую часть из них и случайно сгенерить.
Получается связь {pass1;hash1} -> f(hash1) -> pass2,
а из pass2 уже обычной хэш-функцией можно вычислить хэш и попробовать опять
повторить процесс.

Получается цепочка хэшей/паролей, если взять достаточно большой чарсет, то
хоть на миллионы хэшей.
А прикол в том, что хранить для такой цепочки достаточно только первый и последний хэш,
потому что все промежуточные можно вычислить из первого.
А второй прикол - что если применить функцию перехода по цепочке к любому
хэшу из цепочки достаточное количество раз то когда-нибудь обязательно
получится последний хэш, который собственно и можно найти в RT.
А найдя последний хэш, можно прочитать и хранящийся с ним первый, и от него
прокрутить по цепочке до пароля, из которого получается искомый хэш.

В общем, поиск в RT выглядит примерно так:
1. мы хотим найти пароль от hash1
2. генерим из hash1 цепочку хэшей до максимальной длины 
(или до хэша с определенными свойствами, например последние 5 цифр нули)
3. ищем в RT записи либо для всех хэшей в цепочке
(либо только для одного "специального" хэша)
4. если удается найти первые хэши каких-то цепочек, 
для которых у нас получились последние, то генерим эти цепочки целиком.
5. находим пароль, из которого получается hash1... или не находим.

т.е. мб несколько миллионов раз все-таки хэш-фунцию вычислить может потребоваться
но это компенсируется того же порядка сокращением размера базы.

Т.е. получается такой уникальный алгоритм сжатия с анти-потерями :)
В том смысле, что обычно сжатие с потерями теряет часть информации,
а тут может добавляться лишняя информация (случайно сгенеренная).
Но зато появляется возможность не хранить все, что можно заново случайно сгенерить.

А ведь при сжатии терабайтов данных ситуация получается примерно та же, и
вычислить хэш несколько тысяч раз вполне может быть выгоднее, чем лезть на
винт за данными.
Так что очень хочется применить этот принцип для универсального сжатия, а
не только для таблиц хэшей :)