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

[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³² шага мы наткнемся на пароль, хранящийся в базе. Тогда возьмем предыдущий пароль из списка, и прошагаем от него вперед до тех пор, пока не найдем пароль, порождающий искомое значение хеша, что и требовалось.

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

Comments

[ivan-ghandhi.livejournal.com]

Чем это лучше просто взятия остатков по модулю? Типа по китайской теореме об остатках... и т.д.

[spamsink]

Объясни поподробнее.

[aa-kir.livejournal.com]

На очевидный вопрос о сомнительной производительности алгоритма у меня есть ответ.
И каков же ответ? Сколько я знаю, вроде работает...

[spamsink]

Чтобы эффективно сравнивать на каждом шаге со всеми строками в базе, нужно очень много оперативной памяти. Лучше слегка модифицировать алгоритм и сохранять не ровно каждые 2³² шагов, а строки фиксированного вида, встречающиеся с вероятностью около 2^-32 или чуть больше - например, с последними четырьмя символами !!!! (тогда их и хранить не надо).

[aa-kir.livejournal.com]

Кстати: этот сайт дает возможность всем желающим представить хеш для взлома - у них 0.625 Tb таблиц:

http://www.plain-text.info/view/action/viewallhashes/

[spamsink]

Что забавно, 94⁶ / 2⁴⁰ = 0.627.

[syarzhuk.livejournal.com]

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

[spamsink]

Спасибо, поржал.