Криптостойкость 1000-кратного хеширования пароля



    Поднявшаяся в этом топике дискуссия о криптостойкости многократного применения хеша над паролем (проскальзывавшая, кстати, и в других форумах), подтолкнула меня к этому немного математическому топику. Суть проблемы возникает из идеи многократной (1.000 и более раз) обработки пароля перед хранением каким-либо криптостойким алгоритмом (чаще всего хеш-функцией) с целью получить медленный алгоритм проверки, тем самым эффективно противостоящий brute force-у в случае перехвата или кражи злоумышленником этого значения. Как совершенно верно отметили хабрапользователи Scratch (автор первой статьи), mrThe и IlyaPodkopaev, идея не нова и ею пользуются разработчики оборудования Cisco, архиватора RAR и многие другие. Но, поскольку хеширование – операция сжимающая множество значений, возникает вполне закономерный вопрос – а не навредим ли мы стойкости системы? Попытка дать ответ на этот вопрос –

    Снижение стойкости будем рассматривать в двух моделях угроз:
    1. перебор злоумышленником случайных входных наборов байт в надежде найти коллизию из-за сужения пространства значений («полный перебор»);
    2. перебор по словарю.

    Начнем с первого, более теоретического, вопроса: «сможет ли такое огромное пространство значений современной хеш-функции 2128 (MD5), 2160 (SHA-1), 2256 (ГОСТ Р 34.11, SHA-256) в результате многократного применения сузиться до такой степени, что коллизию к нему можно будет подобрать простым случайным поиском ?».

    Начало


    Одним из основных свойств/требований к криптостойким хеш-функциям является очень хорошая равномерность распределения выходных результатов. Это позволяет оперировать в потребующихся далее оценках обычной теорией вероятности и комбинаторикой.

    Возьмем входное множество из N элементов и каждому из его объектов сопоставим в выходном множестве также из N объектов случайным образом какой-либо элемент (см. рис.). Очевидно, что несколько отображений покажут на одинаковые элементы, а, следовательно, останутся и элементы, к которым не подходит ни одной стрелки:



    Вероятность того, что конкретный элемент выходного множества НЕ будет выбран конкретным отображением (стрелкой) равна , соответственно, вероятность того, что он НЕ будет выбран ни одной из N стрелок равна или что тоже самое (благодаря свойству криптостойкой хеш-функции все N отображений – события независимые в первом приближении).

    Предел является следствием второго замечательного предела и равен , т.е. примерно 0,3679. Это вероятность того, что элемент в выходном множестве «станет серым». Попутно отметим, что при больших N (больше 232) степень «ухудшения» не зависит от разрядности хеш-функции. В итоге после первого повтора хеширования от пространства значений останется только около 63%. Если дальше всё пойдет также, то это будет катастрофой – всего за 150 итераций мы «съедим» 100 бит выходного пространства, оставив, например, для MD5 только 2128-100=228 вариантов. К счастью, это не так.

    Детально


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



    Пусть во входном множестве было активно только kN элементов, где 0<k<1. Тогда вероятность НЕ выбора конкретного элемента равна , что по тому же следствию равно , а сужение выходного множества на этой итерации составит всего . Вот таблица первых 6 итераций:

    Номер итерации, i Доля множества значений, k
    1 1,0000
    2 0,6321
    3 0,4685
    4 0,3740
    5 0,3120
    6 0,2680

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

    Для того чтобы оценить степень снижения стойкости для большого количества итераций удобнее изучать не само число k, а обратное ему – во сколько раз сократилось выходное множество, причем сразу в логарифмической шкале по основанию 2, чтобы единицами измерения стали биты: . Именно это число будет характеризовать снижение стойкости к полному перебору – его необходимо вычесть из разрядности выбранной хеш-функции, чтобы получить разрядность эквивалентно стойкой хеш-функции. График зависимости r до 50.000 итераций приведен на рисунке:



    Точки, в которых график пересекает целые значения r, сведены в таблицу:

    Снижение стойкости, r (бит) Кол-во итераций, i
    4 30
    5 61
    6 125
    7 253
    8 509
    9 1.020
    10 2.044
    11 4.092
    12 8.188
    13 16.379
    14 32.763
    15 65.531
    16 131.067
    ... ...
    20 2.097.146
    ... ...
    24 33.554.425

    Как видим, снижение стойкости с определенного момента нарастает очень медленно. Более того, количество итераций в точности следует степеням двойки: . Во всех случаях, когда наблюдаются подобные закономерности, их можно доказать аналитически, но я уже не ставил это своей целью. Таким образом, не снижая стойкость алгоритма более 16 бит (а по моему твердому убеждению для 128-битных хеш-функций – это никак не скажется на практической их стойкости на ближайшие скажем 25 лет), можно выполнить 130.000 итераций хеширования пароля. Для 256-битных хеш-функций (SHA-256, ГОСТ Р 34.11, RIPEMD-256 и т.п.), очевидно, эта планка еще во много раз выше.

    Проверка адекватности модели


    Как всегда после большого количества теоретических измышлений, возникает желание хоть как то оценить, насколько далека полученная теория от практики. В качестве подопытной хеш-функции мною были взяты первые 16 бит от MD5 (криптостойкая хеш-функция позволяет выбирать любой набор бит результата для формирования усеченной хеш-функции с аналогичными свойствами, хотя и, естественно, меньшей стойкости – соответственно своей новой разрядности). На вход алгоритма подаются все возможные значения от 0 до 0xFFFF, над каждым из значений проводится i итераций, каждая итерация заключается в вычислении первых 16 бит MD5-результата (получается 16-разрядная хеш-функция). «Результаты опытов» приведены в таблице:

    Планируемое снижение стойкости, r (бит) Кол-во итераций, i Ожидаемое кол-во элементов в множестве Наблюдаемое кол-во элементов в множестве
    4 30 216-4=4.096 3.819
    6 125 216-6=1.024 831
    8 509 216-8=256 244

    Конечно, при таком малом значении N и особенно kN начинает сразу сказываться тот факт, что все выкладки выше приведены для пределов (для N сравнимых и больших 2128 – там всё хорошо). Но даже и здесь общая тенденция прослеживается и приемлемо укладывается в полученные выше формулы.

    Следствие – стойкость к словарной атаке


    Пришло время проанализировать, «ощутимо ли сужение области значений в тех случаях, когда в качестве парольной фразы выбран словарный или легко конструируемый пароль?». Очевидно, что в этом случае «активное» входное множество значений уже чрезвычайно сужено – оно находится в зависимости от методик подбора в диапазоне от 216 до 248. Таким образом, мы сразу попадаем в «разряженную» ситуацию – в правую часть графика. Здесь вероятность отображения двух разных входных элементов на один и тот же выходной чрезвычайно мала. Миллионы и миллионы операций практически нисколько не изменят количество элементов в выходном множестве. Отсеются единицы/десятки – ни о каком практическом снижении стойкости речи не идет.

    Выводы


    Описанную схему защиты от brute force-а можно свободно применять на практике практически без ограничений со стороны криптографической стойкости. Рекомендуемые верхние пределы количества итераций (разрешенное снижение стойкости r выбрано субъективно в размере 1/8 разрядности хеш-функции) приведены в таблице:

    Разрядность хеш-функции (бит) Разрешенное снижение стойкости, r (бит) Верхний предел разрешенного количества итераций, i
    128 16 130.000
    160 20 2.000.000
    192 24 32.000.000
    224 28 500.000.000
    256 32 8.000.000.000
    Поделиться публикацией

    Похожие публикации

    Комментарии 103

      +119
      Смотрите, харабзеры, вот так выглядят образцово-показательные статьи. Спасибо.
        –66
        а я ничего не понял. может он её вообще сгенерировал генератором псевдонаучных статтей. Я не умаляю заслуги автора в исследовании, но стоило сделать хотябы раздел с человекопонятными выводами. чтобы пожно было прочитать и сразу понять
          +22
          Не путайте «человекопонятные» и "TheShockпонятные" выводы.
          «Мы должны называть лопату лопатой, а полиморфонуклеарный лейкоцит – полимор-фонуклеарным лейкоцитом»
            +5
            мнение субъективно, согласен
            –1
            Самое «математически-сложное» в этой статье — это пределы, остальное — таблички и графики. Вывод: перед нами либо школьник из гумманитарного класса, либо кодер-самоучка, забивавший первый семестр любой технической специальности.
              –8
              толсто
                –4
                Это не борды, «толсто» за универсанльный ответ не сойдет, лигивонер ты наш.
                • НЛО прилетело и опубликовало эту надпись здесь
                +5
                по вашему школьник из гумманитарного класса почти тоже что кодер-самоучка, забивавший первый семестр любой технической специальности?

                по мне так стоящая хабра статья не под стать многим копипастам)
                  +3
                  а может хабр не стоит этой статьи?
                –2
                Это ппц товарищи. И у этого человека карма больше чем у автора статьи =(
                А эта статья выделяется на фоне других как отличаются Рок от попсы
                  0
                  поменьше дрочите на карму
                0
                Однако от картинки для привлечения внимания автор не отказался :)
                +6
                Энциклопедически
                  +2
                  Диссертабельно
                    +4
                    нет
                    • НЛО прилетело и опубликовало эту надпись здесь
                        +1
                        Именно это я и хотел сказать
                    +14
                    Эталон статьи. Спасибо автору, прочёл с удовольствием.
                      0
                      разве от словаря нельзя защитится таким простым методом как проверка хеша не только пароля, а пароля + секретная строка?
                      например не hash(pass), а hash(pass+login) или hash(pass + 'yandex-xednay')
                        +6
                        Речь в этих статьях о противостоянии брутфорсу, который победить нельзя, но можно выиграть время.
                          +2
                          salt есть вещь хорошая, но ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хеши. а с точки зрения brute-force для хеш-функций одной разрядности, мягко говоря, «пофиг» на изменение выходной строки.
                            +6
                            Я всегда думал что salt используют чтобы нельзя было зная hash по таблицам найти исходные данные
                              –6
                              то же, только другими словами.
                                +5
                                Совсем другое.
                                  –1
                                  объясняю культурно. А каким, по-вашему, способом S. предотвращает успешность работы с таблицами? И что такое таблица, вообще? Радужные таблицы генерируются при помощи подбора возможных паролей и построения для них хеш-функций и функций редукции. То есть, р.т. — это таблицы отношений между паролями и хешами.

                                  дальше. к примеру, в одной системе несколько юзеров обладают одним и тем же паролем. следовательно, результаты хеш-функций одинаковые. если нам удается подобрать хотя бы один пароль, то подбор остальных для того же хеша — тривиальная задача. именно в этом случае и используется salt. как я написал выше: «ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хеши»
                                    –1
                                    Дело в том, что таблицы не берутся из воздуха и получаются методом вычисления. А вычисление их — процесс не быстрый, да и еще места под них очень много нужно. Как результат: вероятность того, что пароль из произвольного (ну, в рамках разумного) набора символов но небольшой дины будет в таблицах — велика, а вот если к нему прибваить salt существенной длины и из всяких спец-символов, то шанс наличия в таблице хаша от результата — ничтожен. PS: Количество значений покрытых таблицами намного меньше, чем количество всех возможнох значений хорошей хэш-функции.
                                      +1
                                      Тут вы тоже не правы. Алгоритму хеширования пофиг на длину пароля. Чтобы пройти авторизацию, нужно знать не исходный пароль, а строку, дающую такой-же хеш. В случае работы без соли, любая строка, найденная по таблице — будет паролем. В случае работы с солью, найденная строка должна удовлетворять правилу, что из нее можно «вычесть» соль.

                                      crypt(pass) = crypt(dict word)
                                      crypt(pass + salt) = crypt(dict word) — но отсюда никак не получить строку fake pass:
                                      crypt(pass + salt) = crypt(fake pass + salt)
                                        +1
                                        Алгоритму хеширования пофиг на длину пароля.
                                        Алгоритму хэширования — пофиг. Не пофиг взломщику, потому что никто не будет делать набор радужных таблиц для множества паролей заканчивающихся на некий конкретный salt.

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

                                        А защитой от совпадения хешей у пользователей с разными паролями является использование в качестве компонента соли логина, или другой информации и пользователе.
                                          0
                                          «А защитой от совпадения хешей у пользователей с разными паролями является использование в качестве компонента соли логина, или другой информации и пользователе.»
                                          я говорил о защите от совпадения хешей у пользователей с одинаковыми паролями.

                                          «Это не обязательно ник, как, судя по всему, полагаете вы.»
                                          Нет, я так не полагал и не полагаю.
                                            –3
                                            Ваши слова:
                                            Но соль ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хеши
                                            Это не так, если вы возьмете 2-х пользователей, у которых один пароль, посолите их строкой + 'salt123', то и результаты хеш-функции будут одинаковыми. А вот если вы их посолите логином, то разные. Но ваше утверждение — ложное.
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                «Обычно», это в скольки процентах случаев? Если даже во многих, это не повод подменять понятия.
                                                Линукс никто не называет «Виндовс Линукс», а называют «операционной системой», хотя Виндовсов 90%.
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                    0
                                                    In cryptography, a salt consists of random bits that are used as one of the inputs to a key derivation function. en.wikipedia.org/wiki/Salt_(cryptography)

                                                    Вот вам ключевой момент: «random bits». Перевести?
                                                      –3
                                                      Ну давайте, авторизуйте пользователей по действительно рандомной соли, а я на вас посмотрю.
                                                        +1
                                                        Ее (рандомную соль) можно приклеить в исходном виде к результату.

                                                        Эта технология называется рандомизация сообщений и используется в т.ч. для шифрования трафика, например, когда передаются короткие однотипные сообщения (телеметрия, управляющие команды и т.п.) и нельзя, чтобы злоумышленник по многократно пролетевшему одинаковому зашифрованному сообщению догадался о его внутренней сути без расшифровки.
                                                          +2
                                                          практическая инструкция для детей:
                                                          deforum.ru/forum/sol-v-kriptografii-t62339.html
                                                            +2
                                                            random здесь может означать «произвольные», а не именно вызов встроенной функции random с неизвестной «затравкой» (seed). Можно один раз на всю таблицу создать одну соль и применять для всех пользователей. Тем не менее, она будет «random».
                                                            Там же не сказано, что «random for each user» или даже «random for each check».
                                                              0
                                                              Можно один раз на всю таблицу создать одну соль и применять для всех пользователей. Тем не менее, она будет «random».
                                                              Вот тут я с вами полностью согласен. Но butteredcat думает, что там написано «для каждого пользователя».
                                                      +1
                                                      это очевидно, что соль генерируется разная, и все результаты сохраняются в бд. иначе, процесс такой — есть бессмыслица чистейшей воды.
                                          0
                                          Восе не пофиг. Тем более, что сейчас по возможности вместо чистого брута идет работа с «радужными таблицами», а хороший salt сильно понизит шанс наличия хэша в таблице.
                                        +2
                                        Спасибо, интересно!
                                        Заодно курс теории вероятности в голове освежил:)
                                          –3
                                          вы ничего не сказали о том, как может снижаться стойкость при использовании раундовой соли или других ухищрений вроде aes, как например тут:
                                          code.google.com/p/paranoim/source/browse/trunk/ParanoIM/src/com/paranoim/crypto/utils/SlowHasher.java
                                          так что поднимать панику рано
                                            0
                                            Раундовая соль не влияет на сжатие выходного множества, т.к. не является источником новой информации.
                                            Я не поднимаю панику, а наоборот всецело поддерживаю описанную схему — просто провожу оценки рекомендуемого количества итераций.
                                              0
                                              А изменяемая неслучайная соль, добавляемая в каждой итерации? Разве она не расширит множество? См. пример WinRAR'а.
                                                0
                                                У меня стойкое убеждение, что — нет, хотя конечно я тоже могу ошибаться.

                                                Ну вот давайте предположим, что добавление этой раундовой соли внесено в саму хеш-функцию. Тогда на каждой итерации мы получается применяем немного другую хеш-функцию, но (!) с теми же самыми параметрами входного и выходного пространства, а, следовательно, все выкладки выше по величинам k и r остаются в силе.
                                                  0
                                                  Нет, тогда это будет уже другая хеш-функция. Случайно изменённая.
                                                    0
                                                    Я имею в виду, мощность выходного пространства не будет зависеть от мощности входного, т.к. входное множество расширяется множеством всех случайных значений соли.
                                                      0
                                                      Давайте, тогда всё таки сначала определимся: для разных входных значений, например, PASS1 и PASS2, значение соли на j-ом раунде одинаковое или нет?

                                                      (3 поста назад Вы говорили о неслучайной соли и приводили пример WinRAR-а — там соль зависит только от j).
                                                        0
                                                        Ну, можно взять, например, псевдослучайную последовательность, инициируемую начальным значением соли (одинаковую для одинаковых солей).
                                                        Для случая WinRAR'a тоже интересно, но там, мне кажется, нужно исследовать влияние конкретных чисел соли на сужение выходного диапазона.
                                            +2
                                            Таким образом, не снижая стойкость алгоритма более 16 бит (а по моему твердому убеждению для 128-битных хеш-функций – это никак не скажется на практической их стойкости на ближайшие скажем 25 лет)


                                            допустим, разрядность снизилась на 16 бит.
                                            (иными словами, возможных хэшей стало в 216 раз меньше)
                                            время вычисления хэша одной строки (по вашим данным), при этом можно увеличить в 130000 ~= 217 раз.

                                            непонятно, почему вообще идет речь о снижении стойкости, если среднее время на поиск коллизии для заданного хэша (опять же, исходя только из ваших данных) только возрастет в ~2 раза.
                                              +1
                                              то есть стойкость практически не меняется от многократного прохешивания х)
                                                0
                                                и игра получается не стоит свеч
                                                  +1
                                                  Игра очень даже стоит свеч т.к. при брутфорсе по словарю вам нет выгоды от кол-ва возможных хешей, но время вычисления хеша больше.
                                                  При брутфорсе по хешам — вы просто не можете знать какие хеши существуют в конечном наборе, а какие нет, следовательно — опять нет выгоды от сужения пространства.
                                                    0
                                                    выгода есть всегда, ибо увеличивается число коллизий
                                                      +2
                                                      А разве есть какой либо более-менее приемлемый способ поиска коллизий первого рода, чтобы его было выгоднее использовать?
                                                        +1
                                                        я не в теме
                                                      0
                                                      Выгода в увеличении шансов на то, что проверенный нами пароль будет иметь искомый хеш.
                                                        0
                                                        Если рандомный брутфорс — то да (но это в обоих случаях занимает невообразимое количество времени)
                                                        А в случае брута по словарю я не уверен что у нас так же пропорционально повышается вероятность удачно подобрать пароль т.к. множество, в которое отображается весь наш словарь меньше множества хешей в результате. Поэтому ИМХО выгода будет не в 2^16 раз при уменьшении скорости 2^17, а гораздо меньше, и тогда актуальность такого хеширования повышается.
                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                  +17
                                                  Хабр ещё торт
                                                    +5
                                                    Это ложный путь.

                                                    Если производная от ключа требует 2s операций, стоимость брут-форс атаки против пароля с энтропией t возрастает с 2t до 2s+t операций [1]. Применим 130 000 итераций к паролю из англ. букв длиной в 10 символов (энтропия 21 бит), получим 217 × 2n = 217+n, стоимость расчёта увеличивается с 2n+21 до 217+n+21 операций. Плюс, согласно исследованиям выше, стойкость ещё и снижается на 16 бит. Отсюда видно, что эффект не настолько велик, как некоторые могут ожидать.

                                                    Более того, сейчас аппаратные решения очень хорошо распараллеливаются, и стоимость расчёта N вложенных хешей растёт совсем не пропорционально N [2]. Хотя аппаратные решения не ускоряют время расчёта, но они значительно уменьшают стоимость, и эта стоимость падает каждый год.

                                                    Для сравнения, на текущий момент аппаратный SHA256 блок с ≈ 20000 логическими элементами может хешировать со скоростью 2500 Mbps (при 130 nm процессе). И это число улучшается в разы ежегодно, и при распараллеливании.

                                                    Выводы о правильности пути делайте сами.

                                                    [1] J. Kelsey, B. Schneier, C. Hall, and D. Wagner. Secure applications of low-entropy keys. In ISW ’97: Proc. of the first international workshop on information security, pages 121–134, 1998.
                                                    [2] Circuits for integer factorization.
                                                      +4
                                                      Спасибо за комментарий! Я практически во всем с Вами согласен.

                                                      Но я бы назвал описанный подход не ложным путем, а «полумерой», массово доступной, позволяющей оттолкнуть определенный весьма значимый процент злоумышленников. Почему бы ей не иметь право на существование?

                                                      Я по-прежнему читаю в соответствующих форумах фразы вида: «это RAR-архив с паролем в 12 символов — брось, не подберешь», «это Cisco-вский пароль enable secret 5 — он очень медленно подбирается». Значит, всё-таки у этой полумеры есть определенная ниша.
                                                        +1
                                                        Небольшое уточнение — поскольку хэш вложенный, то пока мы не досчитали предыдущий, мы не можем приступить к расчётам следующего — нет входных данных. Следовательно, параллельные вычисления в классическом виде невозможны.

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

                                                          То есть, как я и писал, из-за отличной распараллеливаемости время расчёта одной производной не уменьшится, но увеличится скорость брут-форса и уменьшится цена атаки.
                                                          0
                                                          Ссылка [2] нерелевантна. Ваша идея про вычисление нескольких разных хешей понятна, но это совершенно не то же самое что и «стоимость расчёта N вложенных хешей растёт совсем не пропорционально N». Всё растёт пропорционально. Другой вопрос, что брутфорс сам по себе — embarrassingly parallel. А статья [2] вообще о другом.
                                                            0
                                                            Работа [2] как раз об уменьшении стоимости факторизации при использовании аппаратных схем. Здесь стоимость — это функция от времени и стоимости компьютера. И я считаю, что эта стоимость растёт не прямо пропорционально количеству вложений хеша из-за того, что логические вычислители хеша достаточно компактны на кремнии, возможна большая их плотность.
                                                              0
                                                              логические вычислители хеша достаточно компактны на кремнии, возможна большая их плотность.


                                                              Это даст уменьшение стоимости только в константное количество раз (площадь кристалла / площадь одного вычислителя). Поэтому прямая пропорциональность сохраняется. А в статье предлагается именно улучшать асимптотику алгоритма, но не за счёт параллелизма, а за счёт алгоритмов, которые модно реализовать только в железе.
                                                                0
                                                                Предположим, что каждый год число раундов N в нашей функции преобразования ключа увеличивается, так, чтобы время вычисления (для пользователя) оставалось прежним при новом технологическом уровне. При этом каждый год стоимость брут-форса ключа будет рости медленнее N, поскольку логические схемы становятся не только быстрее, но и компактнее по площади, что позволит разместить больше схем за ту же стоимость кремния. Возможно, стоимость будет даже падать.
                                                                  +1
                                                                  Выкрутились, перейдя в другие координаты. Это уже совсем не то, о чём вы говорили в самом начале: «стоимость расчёта N вложенных хешей растёт совсем не пропорционально N» — тут полностью отсутствовал временной и технологический аспект изменения N. Тем не менее, статья [2] всё равно не об этом (временном аспекте).
                                                          +5
                                                          Когда слышал фразу в стиле «много букв по этому верю». Думаю по этому значительный процент за статью (конечно, мало кто признается себе в этом).
                                                          Я не говорю что написанное — плохо, я говорю что написано сложно. Да, кажется что расжовано до безобразия, но тем не менее, от чего-то без усилий полно постичь ход доказательства трудно. Не могу объяснить словами. Если Вы с ходу поняли, жму лапу, можете не хвастаться.
                                                            –2
                                                            Что-то какое-то странное высказывание про пределы: lim(1 — 1/N)^N при N, идущем к бесконечности, какой физический смысл имеет? Ведь, вроде же как бы, N, которое внутри скобок — это размер множества, а N которое в степени — это должно быть количество последовательных применений хэша. Это разные N и откуда там e берётся — загадочно. По крайней мере не очевидно и требует объяснений. И почему стрелок должно быть столько же, сколько элементов во множестве? Тоже не очевидно.

                                                            И вообще, вы можете проверить свою модель на идентичной функции f(x) = x, на каком-нибудь небольшом множестве. Она удовлетворяет всем требованиям, но как-то тут никаких экспонент не возникает.

                                                            Чего я не понимаю?
                                                              +1
                                                              О. Я понял, откуда столько стрелок, меня предел смутил первоночально. Но… Ну, да… Как-то нормально получается.
                                                                0
                                                                Объясните мне пожалуйста, я пока не понял.
                                                                  0
                                                                  Ну. Как я понял, логика там такая: какова вероятность того, что при отображении одного элемента из множества значений для хэша мы НЕ попадём в конкретный элемент h. Стрелочки — это к ответу на вопрос: какова вероятность того, что при отображении всех элементов H мы не попадём в h?

                                                                  Интуитивно, конечно, тут что-то не так, но это надо обдумывать, а лень. Просто вот identity — это контрпример. То есть, вероятность того, что мы не выберем h при отображении одного элемента, действительно 1 — 1/N. Но при этом, когда отображается всё множество H, каждый элемент из H будет выбран.

                                                                  Вероятности же перемножать можно только для независимых событий, а тут всё же какая-то зависимость есть, хэш-функция — это не схема Бернулли. Скорее тут надо оперировать условными вероятностями.
                                                                  0
                                                                  Ох, не там вы плюсуете. Потому что сомнительны всё же исходные посылы и оценка меры выпадающих из множества элементов. Ведь, как формализуется то, что у хэша значения равновероятные? Я не специалист, но, наверное вот так:

                                                                  P(h(x) = hi) = 1/N, то есть, просто вероятность при отображении чего-то попасть в hi — это одно из водможных значений для хэш-функции h. За этим событием стоит целове множество (бесконечное) различных x, и берётся мера этого множества.

                                                                  А у OLS оценивается, судя по всему, вероятность события: при отображении xi попасть (ну, я прямое событие беру) в hj (речь же об одной стрелочке). Лично вот для меня не очевидно, почему это должно быть 1/N. Ну. Я, конечно, не знаю, из чего он исходит, но раз перемножает потом вероятности, то так и должно быть, потому что, как мне кажется, он потом берёт вероятность для события: h1 не попадает в hj и h2 не попадает и… hn не попадает. И поэтому, делаю вывод, что одна стрелка — это как раз hi попадает в hj и для этого берётся вероятность 1/N.

                                                                  Эти все циферки надо обосновывать. Потому что, как я уже и говорил, есть контр-пример. Давайте рассматривать строки, от которых берётся хэш, как натуральные числа — это без проблем (для сомневающихся: берём двоичную запись строк, и интерпретируем её как запись натурального числа в двоичной системе счисления). И полагаем h(x) = x mod N.

                                                                  Для такой h условие равновероятности распределения результатов выполняется, и даже вероятность того, что одной, случайно выбранной, стрелкой мы попадём в конкретный элемент xi равна 1/N. Но при этом, никаких сужений множества возможных значений при применении h к самой себе не происходит. А должно происходить согласно модели OLS, потому что все исходные посылки выполняются.

                                                                  В чём подвох-то? Что я упускаю из виду?
                                                                    0
                                                                    Вы рассматриваете одну h(x), а OLS — все. Он работает с вероятностями (с такой-то вероятностью такой-то элемент будет не выбран). Вы привели пример функции, когда событие, определяемое этой вероятностью, не происходит.
                                                                      0
                                                                      Хм. А можно формальнее, а то я не понимаю :( Я сам попробую, но не факт, что я прав.

                                                                      Вы говорите, что OLS записывает вероятность P(x | h(x) != y) = 1 — 1/N (кстати, для функции x mod N эта вероятность тоже такой будет). То есть, вероятность того, что никакой из x не отображается в y. Отлично, я тоже так подумал сперва, но тогда возникает вопрос, а какой тогда смысл в перемножении этих вероятностей? Единственное, что мне приходит в голову, так это то, что это перемножение соответствует событию (x'ы не отображаются в y1 И… И x'ы не отображается в yN). Но эти штуки не являются независимыми, потому что куда-то x'ы да отображаются, и если они не отображаются в y1, то вероятность того, что они отобразятся в y2 уже выше.

                                                                      Вот. А насчёт моего примера, так это просто одна из хэш-функций, удовлетворяющая всем исходным условиям для построений, сделанных OLS. Раз для неё вывод не выполняется, значит, рассуждения OLS не совсем верные.
                                                                –1
                                                                Четта вы мне мозг сломали в другую сторону. Что если сделать поисковик по хеш-ключам, например тот же гугл, может каждое слово, фразу, словосочетание — хранить не только в качестве текста, а и в качестве хеша, и при необходимости делать сверку необходимого хеша по существующей базе. В этом случае все пароли в виде слова — можно будет элементарно обнаружить, другие со временем тоже подтянутся. Эдакая громадная база хеша…
                                                                  +1
                                                                  Ну вроде это и есть подбор по словарю. Более того — слов не так много — их и без гугла можно собрать и это не так сложно. Проблема в том, что далеко не все пароли это слова из словаря или даже их сочетания. А если учитывать эту особенность — то случае задача вырождается до брутфорса, с той только разницей что хеш не надо высчитывать, а надо только из базы его брать.
                                                                    0
                                                                    Такие базы уже есть: Радужные таблицы. И есть куча онлайн-сервисов, где, например, по md5-хэшу возвращается строка, соответствующая этому хэшу.
                                                                    0
                                                                    Работа проведена хорошая, но, имхо, несколько неправильный изначальный посыл(поправьте меня, если я не прав). Как мне кажется, изначально нужно рассчитывать не по формуле , а по формуле lim(1-K/N)N, где k — это количество одинаковых хешей для набора от 0 до 2N, так как именно количество одинаковых хешей гарантированно дает одинаковый набор хешей после многих итераций.
                                                                      0
                                                                      Хотя, в общем-то, при идеально равномерном распределении K=1. На самом же деле, даже и эта формула не совсем верна, т.к. не учитывает того, что возможны случаи неравномерной сходимости ряда распределения от количества итераций.
                                                                        0
                                                                        И, кстати, при идеальном равномерном распределении, не будет снижения крипкостойкости, т.к. не будет вариантов пересечений хэшей.
                                                                      0
                                                                      Проверил результаты по первым 16 битам: 35 3215, 125 795, 509 153
                                                                      Но начиная с 442 итерации всё время 153.

                                                                      По вторым 16 битам: 35 3450, 125 856, >343 — 176
                                                                      По третьим 16 битам: 35 3204, 125 852, >414 — 197

                                                                      Сейчас посмотрю 32 бита
                                                                        0
                                                                        Немного непонятно, что за цифры Вы приводите.
                                                                        По большому количеству итераций — подтверждаю — в определенный момент происходит резкий останов. Но это несомненно издержки того, что мы взяли настолько усеченную хеш-функцию — при 8 битовом выходном пространстве никакая хеш-функция не обеспечит равномерность распределения: будут и циклы и фиксированные точки и т.п.
                                                                          +1
                                                                          Да, конечно, не 32 бита, а 24 :-)

                                                                          Я взял за основу первые 24 бита от md5 хэша и составил аналог таблички из поста от 0 до 0xffffff

                                                                          bits   iterations       plan         real
                                                                          3       15            2097152      1889863
                                                                          4 	30            1048576       882995
                                                                          5 	61             524288       523780
                                                                          6 	125            262144       261902
                                                                          7 	253            131072       131445
                                                                          8 	509             65536        66545
                                                                          


                                                                          Проверил и на sha1, так что можно сделать вывод: оценка точная.
                                                                            0
                                                                            Спасибо!
                                                                            Мне очень приятно, что поднятая тема заинтересовала Вас вплоть до написания собственного кода — такое встречается на самом деле очень и очень редко.
                                                                              0
                                                                              Кстати, на моем компьютере я еле дождался оценки для 0xFFFF на 509 итераций.
                                                                              Как Вам удалось вычислить это для всех значений до 0xFFFFFF?
                                                                                +1
                                                                                Я, наверное, чего-то не понимаю, но 0xffff у меня отрабатывает за секунды… на perl: paste.org.ru/?t3wqvc

                                                                                На C будет в 100 раз быстрее :)
                                                                            0
                                                                            Автору спасибо, очень хорошо и грамотно написано. Рядом с такими статьями, оставшиеся 90% топиков — безсистемный детский лепет школоты. Хотя конечно, дети не виноваты, что их везде и так окружает одно медиа-барахло, которое заполонило всё инфопространство.
                                                                              0
                                                                              спасибо за статью.
                                                                              вспомнился сейчас алгоритм Полларда — там тоже ведь свойство сжимающего случайного отображения используется.
                                                                              вообще про случайные отображения хорошо описано у Колчина. Там вроде написано примерно по вашей задаче, что p(d) при больших d равно приблизительно 2/d^2, p(d) — доля элементов от изначального количества, которые будут существовать, если применить отображение d раз.
                                                                                0
                                                                                Хорошая статья, спасибо. Помнится, в RU.CRYPT тов. Межутков как-то тоже говорил о сокращении выходного множества при хэшировании хэша и даже приводил ту же оценку в ~60%, но тогда тред особого интереса не вызвал, а жаль. Ну хотя бы теперь мы узнали, что и почему. :-)
                                                                                Ещё раз респект.
                                                                                  +1
                                                                                  Более точную оценку можно провести узнав сколько вариаций хэшей есть от всех возможных вариантов хэша(то есть посчитав кол-во разных хэшей взятых от 0 до 2N-1, где N- длина хэша)
                                                                                    0
                                                                                    Ну. Если бы мы могли посчитать и задачи бы по анализу не возникло :) Тут как раз интересно, как это всё можно оценить при помощи теории вероятностей.
                                                                                      0
                                                                                      Просто дело в том, что посыл изначальный берется неверно — с учетом равномерности распределения переходов нельзя вероятности просто перемножать.
                                                                                        0
                                                                                        Поясню: идеальная равномерность распределения гарантирует, что покрытие будет полное. Но «равномерности» идеальной от хэша ждать не приходится, поэтому считать нужно исходя из равномерности распределения конкретного алгоритма хэширования.
                                                                                      +1
                                                                                      Да, в RU.CRYPT «гостило» множество высококлассных специалистов по криптографии.
                                                                                      Жаль, но сейчас я не знаю ни одного такого представительного ресурса в РуНете.
                                                                                      +1
                                                                                      А что если просто добавить несколько десятков мегабайт к паролю? Ведь чем длиннее исходные данные, тем процесс хэширования медленнее. Допустим, пароль+строка длиной 20 мегабайт. Или пароль, записанный 1000000 раз подряд.
                                                                                        0
                                                                                        Плюс, наверное, можно хранить соль одну на всю базу, но циклически ее сдвигать на разное колво шагов для каждого пароля.

                                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                      Самое читаемое