Радужные таблицы

[spamsink]

Нет, не в этом, а в плохом (хакерском) смысле.

aa_kir упомянул в подзамочном посте "радужные таблицы", использующиеся для вскрытия паролей существенной длины за незначительное (часы) время. Я решил разобраться, как они устроены.

Объясняю на примере, как я самому себе объяснил.

Предположим, у нас есть система, которая хранит хеш - значение какой-нибудь криптографической функции от пароля (например, SHA-1). Также предположим, что мы когда-нибудь в будущем будем искать пароли на множестве всех ASCII-строк, использующих графические символы от ! до ~ длиной 10 символов (это больше, чем 2⁶⁴).

Тогда весьма заблаговременно мы можем проделать следующую работу:

Берем произвольный пароль (например, "passw0rd"). Запоминаем его в качестве головы списка. Вычисляем от него ту системную криптографическую функцию f. Полученное число преобразуем каким-нибудь образом в строку, принадлежащую к рассматриваемому множеству паролей - например, делением на 94¹⁰ и записью остатка в виде 94-ричного числа - от которого снова вычислим f, и так, скажем, 2³² шагов. Допустим, после 2³² шагов получась строка "_)KJVg(&^e". Добавляем строку "_)KJVg(&^e" к списку.
А потом еще 2³² шагов, и еще, до тех пор, пока не надоест (надоесть должно примерно когда в списке окажется 94¹⁰/2³² строк), или на каком-нибудь шаге не встретится один из запомненных паролей. В последнем случае завершаем текущий список, выбираем новый произвольный пароль и начинаем создавать еще один список, и т.п. пока не надоест (см. выше).

Итого, у нас получатся сущие пустяки: 94¹⁰/2³² * 10 = около 116 Гб, а для более коротких паролей еще более сущие пустяки.

Как это помогает вскрывать пароли? Просто: начиная с известного значения хеша, проделываем уже описанную операцию, и если искомый пароль действительно принадлежал к множеству строк, для которых строились списки, то не более чем через 2³² шага мы наткнемся на пароль, хранящийся в базе. Тогда возьмем предыдущий пароль из списка, и прошагаем от него вперед до тех пор, пока не найдем пароль, порождающий искомое значение хеша, что и требовалось.

На очевидный вопрос о сомнительной производительности алгоритма у меня есть ответ.