Радуга в таблицах

Никита Кислицин

Хакер, номер #082, стр. 082-050-2

[новый метод]

Все началось чуть раньше, чем ты предполагал. Еще в 1980 году Мартин Хеллман предложил кардинально новый подход к криптоанализу хэш-функций: он предложил использовать предварительно вычисленные таблицы, размещенные в памяти. Однако совершенно понятно, что хранить хэш-значения всех возможных вариантов ключей - абсурдная затея, которая ни к чему хорошему не приведет. Мало того, что такие таблицы будут занимать умопомрачительное количество терабайт, так еще и поиск по ним будет занимать невероятное количество времени.

Хеллман предложил довольно оригинальную концепцию, которая основывается на разбиении исходного множества ключей на набор подмножеств. На практике это делается следующим образом:

1. Фиксируется рабочий алфавит, то есть задается множество Q всех возможных ключей.

2. Фиксируется элемент q из множества Q и вычисляется значение h хэш-функции на нем.

3. При помощи некоторой «срезающей» функции R из хэша генерируется ключ, принадлежащий множеству Q: q=R(h). Если число элементов в цепочке меньше заданного, осуществляется переход к пункту 2.

Такой итеративный процесс выполняется до тех пор, пока мы не получим цепочку длиной t ключей. Эта последовательность не размещается целиком в памяти, записывается лишь первый и последний ее элементы. В этом и заключается суть метода: если в цепочке, скажем, 1500 ключей, то мы неслабо экономим памяти, обменивая ее на время, необходимое для дальнейшего криптоанализа. К слову, в исходном варианте название этого метода переводится как «компромисс между затратами времени и памяти в криптоанализе», так что все логично. Но вернемся к описанию метода.

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

Задается значение хэш-функции, для которого необходимо получить коллизию. При помощи срезающей функции R строится значение ключа K0, из которого выводится по описанному алгоритму цепочка поиска длиной не более чем t элементов. Если в таблице есть искомый ключ, то один из сгенерированных элементов новой цепочки будет являться терминальным элементом нашей таблицы. Далее не составляет труда по известному начальному элементу вывести всю соответствующую терминалу цепочку, включая элемент, непосредственно предшествующий начальному значению K0, то есть ключ, который мы ищем. Однако такой позитивный расклад возможен только в том случае, если в сгенерированных таблицах действительно есть коллизия. Здесь вплотную встает резонный вопрос: сколько же нужно сгенерировать цепочек, чтобы они покрывали все множество возможных ключей. И к сожалению, дать односложный ответ невозможно.