Time-memory trade off и нерадужные таблицы

    Нет, я не буду рассказывать с какими параметрами нужно генерировать радужные таблицы, или как придумывать «стойкие» пароли. Сама по себе тематика немного устарела и едва ли поможет в отвлеченных вопросах. Но, как оказалось, в основу «радужных таблиц» положен замечательный способ (я бы не стал называть его методом или алгоритмом) размена времени на память, то бишь «time-memory trade off». Это не первый (и, наверное, не последний) топик про предвычисления, но, надеюсь, он Вам понравится.

    Хеш-функции


    Абзац скучный, те кто знают — пролистывайте. Но если не знаете, или сомневаетесь, то приступим.

    Хэш-функция — функция, выполняющая одностороннее преобразование. По заданной строке (паролю) она получает некое хеш-значение (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 →… → simei, где 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) основан

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 33

      0
      Спасибо, было интересно прочитать.
        +1
        Хотелось бы увидеть конкретные примеры функции редукции. Есть ли какие-либо рекомендации по их выбору, кроме инъективности? В свое время искал и не нашел.
          0
          Хорошо, обязательно про это расскажу в продолжении. Это действительно вопрос не тривиальный — благодаря хитрому выбору функции редукции можно сильно повысить эффективность алгоритма, так что внимания заслуживает однозначно.
            0
            И если вас не затруднит, добавьте в список TODO
            5) distinguished points и их одновременное использование с rt
            6) разбор полётов криптанализа GSM A5/1, который на 5) основан

            Если что, могу помочь
            0
            Чем равномернее — тем лучше. В идеале это обычная хеш-функция с заданной областью определения.
            Ещё можно менять хеш-функцию (добавлять некоторую константу к её аргументу, например) в разных чейнах, таблицах и пр. Это снижает вероятность того, что циклы (на которые алгоритм неизбежно наталкивается) будут повторяться, а значит и эффективность таблицы. Собственно, это и отличает rainbow tables от прочих потомков таблиц Хеллмана.
            0
            А перебрать нужно O(2^разрядности хеш-значения)

            Пополам ещё, безотносительно далее идущего по тексту серого комментария. Потому что учитывается парадокс дней рождения.
              0
              Как бы честнее сказать, тут и так некоторый подвох заключен, ибо разрядность хеш значения — константа, а O(константы) = O(1). Делить на два, или нет, не суть. Правильно читается это так — что за какое-то константное время можно перебрать все значения, но это константное время очень велико, и будет очень велико, даже если поделить его на 2, 22, и 2^64.
                –2
                Да какой подвох… Выражение написано в универсальном виде для любой разрядности, не в константном. И написано не верно.

                Про "константное время очень велико, и будет очень велико": у разных хэш функций может быть разная разрядность значения. Для 32-битных функций константное время очень мало.

                Не для споров, а к сведению просто :)
                  0
                  Так сложно поискать? =)
                    +1
                    Так сложно открыть любой приличный учебник по криптографии и понять в чём разница? :)
                0
                Парадокс дней рождения работает, если мы хотим найти произвольную коллизию (x1 и x2 такие, что f(x1)=f(x2) ). А тут мы хотим найти коллизию к конкретному хешу (x такое, что f(x)=y).
                  –1
                  Парадокс дней рождения работает всегда, когда речь идёт о переборе элементов конечного множества.
                    0
                    В каком смысле?
                      0
                      В прямом. А коллизия «к конкретному хешу (x такое, что f(x)=y)» — это не коллизия, а прообраз. Разные вещи. Это к слову, опять же.

                      Извините, я просто позанудствовал. Просто если уж применять формулы и терминологию, то тогда применять надо грамотно.

                      Никого не хотел обидеть.
                        0
                        Так что он не так сказал про произвольную коллизию?
                          0
                          Я тут поработаю немного миротворцем, оке?
                          Где-то я читал, что коллизиями называются как прообразы, так и совпадения хеша для двух ключей. Эта досадная ошибка в терминологии в незапамятные разожгла лютые споры на vbnet.ru
                          Be wise.
                            –1
                            Коллизии называются коллизиями, прообразы прообразами. И не надо ничего оправдывать надумаными досадными ошибками в терминологии. Терминология совершенно чёткая и устоявшаяся. То, что было прочитано где-то — оно не так.

                            Общего между коллизиями и прообразом то, что они в конечном итоге сводятся к решению одной и той же задачи — для данного y найти x так что бы f(x) = y.

                            Разница в том, для коллизий y выражается через даное или произвольно выбраное z [f(z) = y] и через дифференциалы x и z можно существенно сократить пространство поиска.

                            Если кто-то считает иначе, то не надо здесь философски спорить и минусами самоутверждаться. Приезжайте с докладом на ближайшие Eurocrypt или Asiacrypt. Мы с коллегами вас там внимательно и с удовольствием послушаем.
                              0
                              Вы очень упорны, но я все же советую обратить внимание на слова о «коллизии первого рода» и их прямое отношение к задаче о точном дне рождения. И это не парадокс дней рождения.
                                0
                                Ждём с докладом на конференции. С «коллизиями первого рода» и всем остальным :)
                                  0
                                  Тем не менее, википедия такую терминологию знает.
                                    0
                                    Говорить о том, что ссылаться на википедию, как на серьёзный источник даже неловко как-то.

                                    Если попытаться найти англоязычные эквиваленты, то всё встанет на свои места.
                                      0
                                      Термин «хеш-коллизия первого рода» часто применятся в русскоязычной литературе. Терминология в русскоязычной и англоязычной литературе часто различается.
                                      Ну и да, говорить о том, что придираться к терминологии вместо того чтобы признать свою ошибку это дурной тон даже неловко как-то)
                                      В том месте было явно указано, что мы хотим сделать и вне зависимости от того, как это назвать, парадокс дней рождения там совсем не к месту
                                        –1
                                        Когда не хватает знаний и нет желания понять, но есть острое желание обязательно доказать, тогда ВНЕЗАПНО и терминология начинает отличаться, и парадокс дней рождения начинает избирательно действовать, и подвохи с не сутью всплывают. Это всенепременно :)

                                        На этом плодотворную дискуссию со своей стороны считаю законченой. Кто захотел понять и разобраться, тот, думаю, разобрался. Кому хотелось другого, тем без разницы что минусовать.
                                          +1
                                          Парадокс дней раждений действует всегда, но к данному случаю (найти x такой, что f(x)=y) он не применим. А вы, уважаемый, несете бред и не краснеете
                  –3
                  Интересная тематика, но честно говоря вникать в весь математический аппарат не хочется. Может допишете абзац «просто о сложном»? :)
                    +4
                    по моему тут нет ничего сложного. достаточно знаний школьной математики
                    0
                    Хабраюзеры знают, кто написал UDC. Да, sic? =)
                      0
                      Кстати говоря, у меня есть кое-что сказать вам по поводу этих Hybrid Rainbow Tables, ради которых юзернеймы покупают ваш софт.

                      Все прогрессивные дядьки, как и вы, пользуют RT вкупе с фильтрами Блума и деревьями, но *сюрприз* самые прогрессивные генерируют пароли с помощью boost::spirit::karma. Ибо круто и быстро. Так-то.
                        0
                        Но конкретно про UDC ничего не будет (кроме этих комментариев), тематика себя изжила.
                          0
                          Да вы уже говорили. Даёшь сорс-код в паблик! =)
                        0
                        Хеш функция это отображение множества строк в множество хешстрок.
                        Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.

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

                        Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
                          0
                          что-то в субботу вечером ерунда кажется особенно ерундой :)

                          >Хеш функция это отображение множества строк в множество хешстрок.
                          с этим, пожалуй согласен, кроме новообразования «хешстрока»

                          >Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.
                          Это не сюръективность, это отсутствие инъективности.
                          Сюръекция, это когда f: X -> Y и f (X) = Y

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

                          >Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
                          из двух ошибочных утверждений можно вывести абсолютно все что угодно (простое правило импликации), но данное — еще и бессодержательно. Может поясните тогда?

                            0
                            >Это отображения сюръективно, потому как одной хешстроке может соответствовать не одна исходная строка.
                            Это не сюръективность, это отсутствие инъективности.
                            Сюръекция, это когда f: X -> Y и f (X) = Y
                            Сюръекция, это когда элементу множества Y соответствует хотя бы 1 элемент множества X.
                            >Качество хеш функции в этом и заключается, чтобы выбрать наиболее качественное отображение, чтобы коллизия была редкая.
                            «Редкость коллизии» само по себе бесмысленное понятие, т.к. мы отображаем бесконечное множество строк в конечное множество хеш-значений, и количество коллизий всегда бесконечное.
                            Согласен.

                            Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
                            из двух ошибочных утверждений можно вывести абсолютно все что угодно (простое правило импликации), но данное — еще и бессодержательно. Может поясните тогда?
                            Это уже кал. Если не понимаете мое выражение — вот пример возможной хеш ф-ции: Strlen( str ), отображает строку в множество натуральных чисел (включая ноль)

                        Only users with full accounts can post comments. Log in, please.