Time-memory trade off и нерадужные таблицы
Нет, я не буду рассказывать с какими параметрами нужно генерировать радужные таблицы, или как придумывать «стойкие» пароли. Сама по себе тематика немного устарела и едва ли поможет в отвлеченных вопросах. Но, как оказалось, в основу «радужных таблиц» положен замечательный способ (я бы не стал называть его методом или алгоритмом) размена времени на память, то бишь «time-memory trade off». Это не первый (и, наверное, не последний) топик про предвычисления, но, надеюсь, он Вам понравится.
Абзац скучный, те кто знают — пролистывайте. Но если не знаете, или сомневаетесь, то приступим.
Хэш-функция — функция, выполняющая одностороннее преобразование. По заданной строке (паролю) она получает некое хеш-значение (hex-нотация: обычно последовательность из цифр и букв a — f), такое, что по нему очень сложно получить какую-либо информацию об исходной строке-пароле.
Изначально слово взято из английского языка: hash — мешанина, мусор, ненужная информация. На русском языке возможны два варианта транслитерации: хеш или хэш.
Смысл слова можно трактовать так: по хеш-значению мы не получим никакой полезной информации, поэтому само по себе оно является бессмысленным набором байт, мусором.
Однако, обладая свойством обычных функций (то есть по одинаковым строчкам в любое время мы получим одинаковые хеш-значения), хеш-функции пригодились в области авторизации (разграничении доступа). По паролю очень легко получить хеш-значение, которое можно хранить, и использовать для сравнения паролей с оригинальным. В то же время, даже имея доступ к базе хеш-значений, казалось бы, нельзя получить доступ к паролям.
Простой пример: Мы хотим сохранить строку test, как пароль для пользователя Admin. Для этого мы записываем в базу паролей:
Admin:
Теперь мы можем проверить любую строку на соответсвие нашему паролю очень легко — посчитаем от нее хеш-значение, и сравним с тем, которое мы сохранили в базе.
Для примера, MD5 от строки rest — это
В то же время, MD5 от строки test — это всегда
Забудем слово «взлом», и о том что «восстанавливать» можно только «свои» пароли — сейчас это не важно. У нас есть всего-ничего, хеш-функция f и хеш-значение y. Требуется найти строку x (пароль), такую, что f(x)=y, математика.
И мы без труда решили бы задачу, если бы f(x) было равно x^2, кажется в школе учили. Но не тут-то было, математики утверждают, что для любой честной хеш-функции найти обратную в конкретной точке можно разве что прямым перебором. А перебрать нужно O(2^разрядности хеш-значения).
На самом деле это не так, и для всех реально существующих функций этот перебор имеет меньший порядок, а честные хеш функции могут и вовсе не существовать, этот вопрос зависит от существования псевдослучайных генераторов, а они в свою очередь… и мы не будем опровергать этот тезис, хотя бы потому, что не сможем.
Значит перебор.
Задача перебора формализуется очень легко (хоть и множеством способов). Пусть у нас есть алфавит A (Вы ещё запоминаете буквы?). Для заданного n (пока запоминайте) построим все строки из n символов алфавита A. Для каждой строки посчитаем ее хеш-значение. Если оно совпадет с y, то, кажется, мы решили задачу.
Тут я хочу сильно расстроить тех, кто до сих пор считает надежность пароля зависимым от длины пароля фактором. От длины она зависит едва ли больше, чем от содержимого алфавита.
И в качестве примера, возьмем алфавит состоящий из 4 строк:
Для n = 2 перебор охватит строки aa, ab, atest, arest, ba, bb, btest, brest… и так далее, всего 4^2 = 16 вариантов.
Сложность переборного алгоритма составляет O(|A|^n).
Перебор будет успешен в одном из двух случаев:
1. мы наткнемся на хеш-коллизию первого рода.
2. исходный пароль будет содержаться в A^n (то есть его можно составить словами алфавита).
Касательно первого случая могу сказать, что эту идею стоит оставить. Даже для MD5, имеющей всего-то 2^128 различных хеш-значений на это потребуется очень много времени (тысячелетия при переборе миллиарда хеш-значений в секунду). Только не стоит путать коллизии первого рода в свободными коллизиями (второго рода), их действительно искать легко, но на практике совершенно бесполезно.
Значит целимся на ситуацию 2. Несложно прикинуть параметры и порядок вычислений для типичных ситуаций.
Так вот, таблицы не позволят сократить этот порядок. Это было бы и противоречиво тезису о «необратимости» хеш-функций. Все что могут таблицы — это хранить некоторую предвычисленную (за время, большее времени прямого перебора!) информацию, позволяющую для каждого конкретного значения найти соответствующий ему пароль довольно быстро.
Будем записывать в таблицу пары из двух хеш-значений si и ei. Много-много таких пар.
Где si = f ( случайной строки из алфавита ).
si1 = f ( r ( si ) )
si2 = f ( r ( si1 ) )
…
ei = f ( r ( sim ) )
Так, стоп, что за r? А это такая специальная функция редукции. Она отображает хеш-значение функции f обратно в алфавит A^n по любому закону, но по возможности сохраняя инъективность (от разных аргументов функция должна давать разные значения).
Если на время забыть способ получения значений то их можно записать в цепочку:
si → si1 → si2 →… → sim → ei, где m длина цепочки, одинаковая для всех цепочек одной таблицы.
Сложность получения одной пары O(m), всего в таблице N пар, соответственно на генерацию таблицы будет затрачено O(N*m) времени. На сохранение на диск O(N) памяти. А пароль к любому из промежуточных значений sik может быть найден за O(m).
Перевод на «человеческий язык» будет звучать как-то так: для того чтобы уметь восстанавливать любой пароль алфавита A^n потребуется порядка A^n/5000 (для m = 5000) байт места на диске, порядка 5000 шагов алгоритма восстановления.
Чем больше предвычислили, тем большее число паролей можем восстановить, за то же время. Но и «весить» такие таблицы будут больше. Вот и time-memory trade off.
Крайние случаи просты: для m=1 нам потребуется сохранить на диск все хеш-значения заданного алфавита, а это очень много. Но и время восстановления будет O(1) (на самом деле O(log(|A|^n) из-за применения поиска, ну да ладно).
А для m=|A|^n, таблица займет всего н-надцать байт, но и поиск займет столько же времени, сколько без таблицы. Да еще и может не увенчаться успехом из-за вероятностного характера таблицы (ой, зря я это сказал, придется потом отдуваться).
Отлично, пусть у нас есть то самое хеш-значение y и таблица из пар (s0, e0); (s1, e1);… (sN, eN).
На первой итерации алгоритма мы поищем значение y среди конечных точек цепочек: ei.
Пусть не повезло, тогда мы вычисляем y1 = f ( r ( y ) ). И невезение наше повторяется, yi = ((f ○ r) ^ i) (y), это я так записал i раз подряд примененные f и r по очереди (так же как в цепочках в таблице). Стоит отметить, что нет смысла считать yN+1 и далее — даже если они найдутся в таблице, то таблица нам не поможет. Значит здесь максимум N шагов, на каждом из которых мы считаем yi и ищем среди ek. И если, наконец, оно найдется:
Стрелочки здесь обозначают всё то же — композицию f и r. А значит, r ( skv ) пароль для y!
Вот и объяснение, почему считать yN и дальше не нужно: «нижня» цепочка должна быть короче верхней, мы обращаемся к предыдущему относительно y элементу.
Остались не затронутыми несколько вопросов:
1. как быстро искать хеш в таблице
2. «что-то там про вероятность» :)
3. зачем же нужны радужные таблицы и как они устроены
4. быть может, нужно больше примеров
5) distinguished points и их одновременное использование с RT
6) разбор полётов криптанализа GSM A5/1, который на 5) основан
Хеш-функции
Абзац скучный, те кто знают — пролистывайте. Но если не знаете, или сомневаетесь, то приступим.
Хэш-функция — функция, выполняющая одностороннее преобразование. По заданной строке (паролю) она получает некое хеш-значение (hex-нотация: обычно последовательность из цифр и букв a — f), такое, что по нему очень сложно получить какую-либо информацию об исходной строке-пароле.
Изначально слово взято из английского языка: hash — мешанина, мусор, ненужная информация. На русском языке возможны два варианта транслитерации: хеш или хэш.
Смысл слова можно трактовать так: по хеш-значению мы не получим никакой полезной информации, поэтому само по себе оно является бессмысленным набором байт, мусором.
Однако, обладая свойством обычных функций (то есть по одинаковым строчкам в любое время мы получим одинаковые хеш-значения), хеш-функции пригодились в области авторизации (разграничении доступа). По паролю очень легко получить хеш-значение, которое можно хранить, и использовать для сравнения паролей с оригинальным. В то же время, даже имея доступ к базе хеш-значений, казалось бы, нельзя получить доступ к паролям.
Простой пример: Мы хотим сохранить строку test, как пароль для пользователя Admin. Для этого мы записываем в базу паролей:
Admin:
098f6bcd4621d373cade4e832627b4f6 (эта последовательность символов есть хеш-значение MD5 от строки test).Теперь мы можем проверить любую строку на соответсвие нашему паролю очень легко — посчитаем от нее хеш-значение, и сравним с тем, которое мы сохранили в базе.
Для примера, MD5 от строки rest — это
65e8800b5c6800aad896f888b2a62afc и оно не совпадает с тем, что мы сохранили. А значит, rest — не пароль для Admin.В то же время, MD5 от строки test — это всегда
098f6bcd4621d373cade4e832627b4f6, что совпадает с сохраненным значением. А значит, test всегда подойдет как пароль к Admin.Восстановление пароля
Забудем слово «взлом», и о том что «восстанавливать» можно только «свои» пароли — сейчас это не важно. У нас есть всего-ничего, хеш-функция f и хеш-значение y. Требуется найти строку x (пароль), такую, что f(x)=y, математика.
И мы без труда решили бы задачу, если бы f(x) было равно x^2, кажется в школе учили. Но не тут-то было, математики утверждают, что для любой честной хеш-функции найти обратную в конкретной точке можно разве что прямым перебором. А перебрать нужно O(2^разрядности хеш-значения).
На самом деле это не так, и для всех реально существующих функций этот перебор имеет меньший порядок, а честные хеш функции могут и вовсе не существовать, этот вопрос зависит от существования псевдослучайных генераторов, а они в свою очередь… и мы не будем опровергать этот тезис, хотя бы потому, что не сможем.
Значит перебор.
Параметры перебора
Задача перебора формализуется очень легко (хоть и множеством способов). Пусть у нас есть алфавит A (Вы ещё запоминаете буквы?). Для заданного n (пока запоминайте) построим все строки из n символов алфавита A. Для каждой строки посчитаем ее хеш-значение. Если оно совпадет с y, то, кажется, мы решили задачу.
Тут я хочу сильно расстроить тех, кто до сих пор считает надежность пароля зависимым от длины пароля фактором. От длины она зависит едва ли больше, чем от содержимого алфавита.
И в качестве примера, возьмем алфавит состоящий из 4 строк:
a, b, test, rest.Для n = 2 перебор охватит строки aa, ab, atest, arest, ba, bb, btest, brest… и так далее, всего 4^2 = 16 вариантов.
Сложность переборного алгоритма составляет O(|A|^n).
Оценка параметров
Перебор будет успешен в одном из двух случаев:
1. мы наткнемся на хеш-коллизию первого рода.
2. исходный пароль будет содержаться в A^n (то есть его можно составить словами алфавита).
Касательно первого случая могу сказать, что эту идею стоит оставить. Даже для MD5, имеющей всего-то 2^128 различных хеш-значений на это потребуется очень много времени (тысячелетия при переборе миллиарда хеш-значений в секунду). Только не стоит путать коллизии первого рода в свободными коллизиями (второго рода), их действительно искать легко, но на практике совершенно бесполезно.
Значит целимся на ситуацию 2. Несложно прикинуть параметры и порядок вычислений для типичных ситуаций.
Никакого обмана
Так вот, таблицы не позволят сократить этот порядок. Это было бы и противоречиво тезису о «необратимости» хеш-функций. Все что могут таблицы — это хранить некоторую предвычисленную (за время, большее времени прямого перебора!) информацию, позволяющую для каждого конкретного значения найти соответствующий ему пароль довольно быстро.
Алгоритм предвычисления
Будем записывать в таблицу пары из двух хеш-значений si и ei. Много-много таких пар.
Где si = f ( случайной строки из алфавита ).
si1 = f ( r ( si ) )
si2 = f ( r ( si1 ) )
…
ei = f ( r ( sim ) )
Так, стоп, что за r? А это такая специальная функция редукции. Она отображает хеш-значение функции f обратно в алфавит A^n по любому закону, но по возможности сохраняя инъективность (от разных аргументов функция должна давать разные значения).
Если на время забыть способ получения значений то их можно записать в цепочку:
si → si1 → si2 →… → sim → ei, где m длина цепочки, одинаковая для всех цепочек одной таблицы.
Сложность получения одной пары O(m), всего в таблице N пар, соответственно на генерацию таблицы будет затрачено O(N*m) времени. На сохранение на диск O(N) памяти. А пароль к любому из промежуточных значений sik может быть найден за O(m).
Перевод на «человеческий язык» будет звучать как-то так: для того чтобы уметь восстанавливать любой пароль алфавита A^n потребуется порядка A^n/5000 (для m = 5000) байт места на диске, порядка 5000 шагов алгоритма восстановления.
Чем больше предвычислили, тем большее число паролей можем восстановить, за то же время. Но и «весить» такие таблицы будут больше. Вот и time-memory trade off.
Крайние случаи просты: для m=1 нам потребуется сохранить на диск все хеш-значения заданного алфавита, а это очень много. Но и время восстановления будет O(1) (на самом деле O(log(|A|^n) из-за применения поиска, ну да ладно).
А для m=|A|^n, таблица займет всего н-надцать байт, но и поиск займет столько же времени, сколько без таблицы. Да еще и может не увенчаться успехом из-за вероятностного характера таблицы (ой, зря я это сказал, придется потом отдуваться).
Использование таблицы
Отлично, пусть у нас есть то самое хеш-значение y и таблица из пар (s0, e0); (s1, e1);… (sN, eN).
На первой итерации алгоритма мы поищем значение y среди конечных точек цепочек: ei.
Пусть нам повезло, y = ek для какого-нибудь k. Тогда мы регенерируем цепочку, начиная с соответствующего sk: а ведь идущий перед ek элемент skN-1 обладает по построению замечательным свойством: f ( r ( skN-1 ) ) = ek = y, а значит r ( skN-1 ) искомый пароль!
Пусть не повезло, тогда мы вычисляем y1 = f ( r ( y ) ). И невезение наше повторяется, yi = ((f ○ r) ^ i) (y), это я так записал i раз подряд примененные f и r по очереди (так же как в цепочках в таблице). Стоит отметить, что нет смысла считать yN+1 и далее — даже если они найдутся в таблице, то таблица нам не поможет. Значит здесь максимум N шагов, на каждом из которых мы считаем yi и ищем среди ek. И если, наконец, оно найдется:
sk → sk1 → ... → skv → skv+1 → ... → ... → ek
y → y1 → ... → yi
Стрелочки здесь обозначают всё то же — композицию f и r. А значит, r ( skv ) пароль для y!
Вот и объяснение, почему считать yN и дальше не нужно: «нижня» цепочка должна быть короче верхней, мы обращаемся к предыдущему относительно y элементу.
А дальше?
Остались не затронутыми несколько вопросов:
1. как быстро искать хеш в таблице
2. «что-то там про вероятность» :)
3. зачем же нужны радужные таблицы и как они устроены
4. быть может, нужно больше примеров
5) distinguished points и их одновременное использование с RT
6) разбор полётов криптанализа GSM A5/1, который на 5) основан
комментарии (33)