Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 103
Смотрите, харабзеры, вот так выглядят образцово-показательные статьи. Спасибо.
а я ничего не понял. может он её вообще сгенерировал генератором псевдонаучных статтей. Я не умаляю заслуги автора в исследовании, но стоило сделать хотябы раздел с человекопонятными выводами. чтобы пожно было прочитать и сразу понять
Не путайте «человекопонятные» и "TheShockпонятные" выводы.
«Мы должны называть лопату лопатой, а полиморфонуклеарный лейкоцит – полимор-фонуклеарным лейкоцитом»
«Мы должны называть лопату лопатой, а полиморфонуклеарный лейкоцит – полимор-фонуклеарным лейкоцитом»
Самое «математически-сложное» в этой статье — это пределы, остальное — таблички и графики. Вывод: перед нами либо школьник из гумманитарного класса, либо кодер-самоучка, забивавший первый семестр любой технической специальности.
Это ппц товарищи. И у этого человека карма больше чем у автора статьи =(
А эта статья выделяется на фоне других как отличаются Рок от попсы
А эта статья выделяется на фоне других как отличаются Рок от попсы
Однако от картинки для привлечения внимания автор не отказался :)
Энциклопедически
Эталон статьи. Спасибо автору, прочёл с удовольствием.
разве от словаря нельзя защитится таким простым методом как проверка хеша не только пароля, а пароля + секретная строка?
например не hash(pass), а hash(pass+login) или hash(pass + 'yandex-xednay')
например не hash(pass), а hash(pass+login) или hash(pass + 'yandex-xednay')
Речь в этих статьях о противостоянии брутфорсу, который победить нельзя, но можно выиграть время.
salt есть вещь хорошая, но ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хеши. а с точки зрения brute-force для хеш-функций одной разрядности, мягко говоря, «пофиг» на изменение выходной строки.
Я всегда думал что salt используют чтобы нельзя было зная hash по таблицам найти исходные данные
то же, только другими словами.
Совсем другое.
объясняю культурно. А каким, по-вашему, способом S. предотвращает успешность работы с таблицами? И что такое таблица, вообще? Радужные таблицы генерируются при помощи подбора возможных паролей и построения для них хеш-функций и функций редукции. То есть, р.т. — это таблицы отношений между паролями и хешами.
дальше. к примеру, в одной системе несколько юзеров обладают одним и тем же паролем. следовательно, результаты хеш-функций одинаковые. если нам удается подобрать хотя бы один пароль, то подбор остальных для того же хеша — тривиальная задача. именно в этом случае и используется salt. как я написал выше: «ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хеши»
дальше. к примеру, в одной системе несколько юзеров обладают одним и тем же паролем. следовательно, результаты хеш-функций одинаковые. если нам удается подобрать хотя бы один пароль, то подбор остальных для того же хеша — тривиальная задача. именно в этом случае и используется salt. как я написал выше: «ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хеши»
Дело в том, что таблицы не берутся из воздуха и получаются методом вычисления. А вычисление их — процесс не быстрый, да и еще места под них очень много нужно. Как результат: вероятность того, что пароль из произвольного (ну, в рамках разумного) набора символов но небольшой дины будет в таблицах — велика, а вот если к нему прибваить salt существенной длины и из всяких спец-символов, то шанс наличия в таблице хаша от результата — ничтожен. PS: Количество значений покрытых таблицами намного меньше, чем количество всех возможнох значений хорошей хэш-функции.
Тут вы тоже не правы. Алгоритму хеширования пофиг на длину пароля. Чтобы пройти авторизацию, нужно знать не исходный пароль, а строку, дающую такой-же хеш. В случае работы без соли, любая строка, найденная по таблице — будет паролем. В случае работы с солью, найденная строка должна удовлетворять правилу, что из нее можно «вычесть» соль.
crypt(pass) = crypt(dict word)
crypt(pass + salt) = crypt(dict word) — но отсюда никак не получить строку fake pass:
crypt(pass + salt) = crypt(fake pass + salt)
crypt(pass) = crypt(dict word)
crypt(pass + salt) = crypt(dict word) — но отсюда никак не получить строку fake pass:
crypt(pass + salt) = crypt(fake pass + salt)
Алгоритму хеширования пофиг на длину пароля.Алгоритму хэширования — пофиг. Не пофиг взломщику, потому что никто не будет делать набор радужных таблиц для множества паролей заканчивающихся на некий конкретный salt.
Чтобы пройти авторизацию, нужно знать не исходный пароль, а строку, дающую такой-же хэш.Верно. Но шанс коллизии для нормальных хэш-функций очень мал. А значит если хэш берется от короткой строки, то скорее всего при поиске совпадений по хэшу путем перебора — будет найдена именно эта строка, а не коллизия. А вот если мы достаточно усложним нашу строку для перебора с помощью salt из длинного набора случайных байт, то взломщику придется надеяться именно на нахождение коллизий.
Если соль генерируется рандомно для каждого юзера — генерировать таблицы боюсь устанете для всех возможных значений соли :)
Солью называют любую строку, добавляемую к паролю перед передачей в шех-функцию. Это не обязательно ник, как, судя по всему, полагаете вы. Эта соль призвана предотвратить поиск пароля по словарю посчитанных хешей. Соль изменяет результат хеш функции, следовательно словарь для функции без соли не подойдет, нужен другой словарь. Но таких словарей просто не существует, потомучто вариантов просаливания паролей бесчетное множество. Следовательно, соль защищает от подбора по словарю.
А защитой от совпадения хешей у пользователей с разными паролями является использование в качестве компонента соли логина, или другой информации и пользователе.
А защитой от совпадения хешей у пользователей с разными паролями является использование в качестве компонента соли логина, или другой информации и пользователе.
«А защитой от совпадения хешей у пользователей с разными паролями является использование в качестве компонента соли логина, или другой информации и пользователе.»
я говорил о защите от совпадения хешей у пользователей с одинаковыми паролями.
«Это не обязательно ник, как, судя по всему, полагаете вы.»
Нет, я так не полагал и не полагаю.
я говорил о защите от совпадения хешей у пользователей с одинаковыми паролями.
«Это не обязательно ник, как, судя по всему, полагаете вы.»
Нет, я так не полагал и не полагаю.
Ваши слова:
Но соль ее используют для того, чтобы у пользователей с одинаковыми паролями были не одинаковые хешиЭто не так, если вы возьмете 2-х пользователей, у которых один пароль, посолите их строкой + 'salt123', то и результаты хеш-функции будут одинаковыми. А вот если вы их посолите логином, то разные. Но ваше утверждение — ложное.
«Обычно», это в скольки процентах случаев? Если даже во многих, это не повод подменять понятия.
Линукс никто не называет «Виндовс Линукс», а называют «операционной системой», хотя Виндовсов 90%.
Линукс никто не называет «Виндовс Линукс», а называют «операционной системой», хотя Виндовсов 90%.
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». Перевести?
Вот вам ключевой момент: «random bits». Перевести?
Ну давайте, авторизуйте пользователей по действительно рандомной соли, а я на вас посмотрю.
Ее (рандомную соль) можно приклеить в исходном виде к результату.
Эта технология называется рандомизация сообщений и используется в т.ч. для шифрования трафика, например, когда передаются короткие однотипные сообщения (телеметрия, управляющие команды и т.п.) и нельзя, чтобы злоумышленник по многократно пролетевшему одинаковому зашифрованному сообщению догадался о его внутренней сути без расшифровки.
Эта технология называется рандомизация сообщений и используется в т.ч. для шифрования трафика, например, когда передаются короткие однотипные сообщения (телеметрия, управляющие команды и т.п.) и нельзя, чтобы злоумышленник по многократно пролетевшему одинаковому зашифрованному сообщению догадался о его внутренней сути без расшифровки.
практическая инструкция для детей:
deforum.ru/forum/sol-v-kriptografii-t62339.html
deforum.ru/forum/sol-v-kriptografii-t62339.html
random здесь может означать «произвольные», а не именно вызов встроенной функции random с неизвестной «затравкой» (seed). Можно один раз на всю таблицу создать одну соль и применять для всех пользователей. Тем не менее, она будет «random».
Там же не сказано, что «random for each user» или даже «random for each check».
Там же не сказано, что «random for each user» или даже «random for each check».
Можно один раз на всю таблицу создать одну соль и применять для всех пользователей. Тем не менее, она будет «random».Вот тут я с вами полностью согласен. Но butteredcat думает, что там написано «для каждого пользователя».
это очевидно, что соль генерируется разная, и все результаты сохраняются в бд. иначе, процесс такой — есть бессмыслица чистейшей воды.
Восе не пофиг. Тем более, что сейчас по возможности вместо чистого брута идет работа с «радужными таблицами», а хороший salt сильно понизит шанс наличия хэша в таблице.
Спасибо, интересно!
Заодно курс теории вероятности в голове освежил:)
Заодно курс теории вероятности в голове освежил:)
вы ничего не сказали о том, как может снижаться стойкость при использовании раундовой соли или других ухищрений вроде aes, как например тут:
code.google.com/p/paranoim/source/browse/trunk/ParanoIM/src/com/paranoim/crypto/utils/SlowHasher.java
так что поднимать панику рано
code.google.com/p/paranoim/source/browse/trunk/ParanoIM/src/com/paranoim/crypto/utils/SlowHasher.java
так что поднимать панику рано
Раундовая соль не влияет на сжатие выходного множества, т.к. не является источником новой информации.
Я не поднимаю панику, а наоборот всецело поддерживаю описанную схему — просто провожу оценки рекомендуемого количества итераций.
Я не поднимаю панику, а наоборот всецело поддерживаю описанную схему — просто провожу оценки рекомендуемого количества итераций.
А изменяемая неслучайная соль, добавляемая в каждой итерации? Разве она не расширит множество? См. пример WinRAR'а.
У меня стойкое убеждение, что — нет, хотя конечно я тоже могу ошибаться.
Ну вот давайте предположим, что добавление этой раундовой соли внесено в саму хеш-функцию. Тогда на каждой итерации мы получается применяем немного другую хеш-функцию, но (!) с теми же самыми параметрами входного и выходного пространства, а, следовательно, все выкладки выше по величинам k и r остаются в силе.
Ну вот давайте предположим, что добавление этой раундовой соли внесено в саму хеш-функцию. Тогда на каждой итерации мы получается применяем немного другую хеш-функцию, но (!) с теми же самыми параметрами входного и выходного пространства, а, следовательно, все выкладки выше по величинам k и r остаются в силе.
Нет, тогда это будет уже другая хеш-функция. Случайно изменённая.
Я имею в виду, мощность выходного пространства не будет зависеть от мощности входного, т.к. входное множество расширяется множеством всех случайных значений соли.
Таким образом, не снижая стойкость алгоритма более 16 бит (а по моему твердому убеждению для 128-битных хеш-функций – это никак не скажется на практической их стойкости на ближайшие скажем 25 лет)
допустим, разрядность снизилась на 16 бит.
(иными словами, возможных хэшей стало в 216 раз меньше)
время вычисления хэша одной строки (по вашим данным), при этом можно увеличить в 130000 ~= 217 раз.
непонятно, почему вообще идет речь о снижении стойкости, если среднее время на поиск коллизии для заданного хэша (опять же, исходя только из ваших данных) только возрастет в ~2 раза.
то есть стойкость практически не меняется от многократного прохешивания х)
и игра получается не стоит свеч
Игра очень даже стоит свеч т.к. при брутфорсе по словарю вам нет выгоды от кол-ва возможных хешей, но время вычисления хеша больше.
При брутфорсе по хешам — вы просто не можете знать какие хеши существуют в конечном наборе, а какие нет, следовательно — опять нет выгоды от сужения пространства.
При брутфорсе по хешам — вы просто не можете знать какие хеши существуют в конечном наборе, а какие нет, следовательно — опять нет выгоды от сужения пространства.
выгода есть всегда, ибо увеличивается число коллизий
Выгода в увеличении шансов на то, что проверенный нами пароль будет иметь искомый хеш.
Если рандомный брутфорс — то да (но это в обоих случаях занимает невообразимое количество времени)
А в случае брута по словарю я не уверен что у нас так же пропорционально повышается вероятность удачно подобрать пароль т.к. множество, в которое отображается весь наш словарь меньше множества хешей в результате. Поэтому ИМХО выгода будет не в 2^16 раз при уменьшении скорости 2^17, а гораздо меньше, и тогда актуальность такого хеширования повышается.
А в случае брута по словарю я не уверен что у нас так же пропорционально повышается вероятность удачно подобрать пароль т.к. множество, в которое отображается весь наш словарь меньше множества хешей в результате. Поэтому ИМХО выгода будет не в 2^16 раз при уменьшении скорости 2^17, а гораздо меньше, и тогда актуальность такого хеширования повышается.
Хабр ещё торт
Это ложный путь.
Если производная от ключа требует 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.
Если производная от ключа требует 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.
Спасибо за комментарий! Я практически во всем с Вами согласен.
Но я бы назвал описанный подход не ложным путем, а «полумерой», массово доступной, позволяющей оттолкнуть определенный весьма значимый процент злоумышленников. Почему бы ей не иметь право на существование?
Я по-прежнему читаю в соответствующих форумах фразы вида: «это RAR-архив с паролем в 12 символов — брось, не подберешь», «это Cisco-вский пароль enable secret 5 — он очень медленно подбирается». Значит, всё-таки у этой полумеры есть определенная ниша.
Но я бы назвал описанный подход не ложным путем, а «полумерой», массово доступной, позволяющей оттолкнуть определенный весьма значимый процент злоумышленников. Почему бы ей не иметь право на существование?
Я по-прежнему читаю в соответствующих форумах фразы вида: «это RAR-архив с паролем в 12 символов — брось, не подберешь», «это Cisco-вский пароль enable secret 5 — он очень медленно подбирается». Значит, всё-таки у этой полумеры есть определенная ниша.
Небольшое уточнение — поскольку хэш вложенный, то пока мы не досчитали предыдущий, мы не можем приступить к расчётам следующего — нет входных данных. Следовательно, параллельные вычисления в классическом виде невозможны.
Возможно лишь параллельно считать некоторые криптоблоки внутри алгоритма, если он это позволяет.
Возможно лишь параллельно считать некоторые криптоблоки внутри алгоритма, если он это позволяет.
На одной единице площади кремния параллельно считаются несколько хешей, например, от разных паролей. Учитывая современную плотность электронных цепей, можно добиться очень большого количества параллельных расчётов на единицу площади.
То есть, как я и писал, из-за отличной распараллеливаемости время расчёта одной производной не уменьшится, но увеличится скорость брут-форса и уменьшится цена атаки.
То есть, как я и писал, из-за отличной распараллеливаемости время расчёта одной производной не уменьшится, но увеличится скорость брут-форса и уменьшится цена атаки.
Ссылка [2] нерелевантна. Ваша идея про вычисление нескольких разных хешей понятна, но это совершенно не то же самое что и «стоимость расчёта N вложенных хешей растёт совсем не пропорционально N». Всё растёт пропорционально. Другой вопрос, что брутфорс сам по себе — embarrassingly parallel. А статья [2] вообще о другом.
Работа [2] как раз об уменьшении стоимости факторизации при использовании аппаратных схем. Здесь стоимость — это функция от времени и стоимости компьютера. И я считаю, что эта стоимость растёт не прямо пропорционально количеству вложений хеша из-за того, что логические вычислители хеша достаточно компактны на кремнии, возможна большая их плотность.
логические вычислители хеша достаточно компактны на кремнии, возможна большая их плотность.
Это даст уменьшение стоимости только в константное количество раз (площадь кристалла / площадь одного вычислителя). Поэтому прямая пропорциональность сохраняется. А в статье предлагается именно улучшать асимптотику алгоритма, но не за счёт параллелизма, а за счёт алгоритмов, которые модно реализовать только в железе.
Предположим, что каждый год число раундов N в нашей функции преобразования ключа увеличивается, так, чтобы время вычисления (для пользователя) оставалось прежним при новом технологическом уровне. При этом каждый год стоимость брут-форса ключа будет рости медленнее N, поскольку логические схемы становятся не только быстрее, но и компактнее по площади, что позволит разместить больше схем за ту же стоимость кремния. Возможно, стоимость будет даже падать.
Выкрутились, перейдя в другие координаты. Это уже совсем не то, о чём вы говорили в самом начале: «стоимость расчёта N вложенных хешей растёт совсем не пропорционально N» — тут полностью отсутствовал временной и технологический аспект изменения N. Тем не менее, статья [2] всё равно не об этом (временном аспекте).
Когда слышал фразу в стиле «много букв по этому верю». Думаю по этому значительный процент за статью (конечно, мало кто признается себе в этом).
Я не говорю что написанное — плохо, я говорю что написано сложно. Да, кажется что расжовано до безобразия, но тем не менее, от чего-то без усилий полно постичь ход доказательства трудно. Не могу объяснить словами. Если Вы с ходу поняли, жму лапу, можете не хвастаться.
Я не говорю что написанное — плохо, я говорю что написано сложно. Да, кажется что расжовано до безобразия, но тем не менее, от чего-то без усилий полно постичь ход доказательства трудно. Не могу объяснить словами. Если Вы с ходу поняли, жму лапу, можете не хвастаться.
Что-то какое-то странное высказывание про пределы: lim(1 — 1/N)^N при N, идущем к бесконечности, какой физический смысл имеет? Ведь, вроде же как бы, N, которое внутри скобок — это размер множества, а N которое в степени — это должно быть количество последовательных применений хэша. Это разные N и откуда там e берётся — загадочно. По крайней мере не очевидно и требует объяснений. И почему стрелок должно быть столько же, сколько элементов во множестве? Тоже не очевидно.
И вообще, вы можете проверить свою модель на идентичной функции f(x) = x, на каком-нибудь небольшом множестве. Она удовлетворяет всем требованиям, но как-то тут никаких экспонент не возникает.
Чего я не понимаю?
И вообще, вы можете проверить свою модель на идентичной функции f(x) = x, на каком-нибудь небольшом множестве. Она удовлетворяет всем требованиям, но как-то тут никаких экспонент не возникает.
Чего я не понимаю?
О. Я понял, откуда столько стрелок, меня предел смутил первоночально. Но… Ну, да… Как-то нормально получается.
Объясните мне пожалуйста, я пока не понял.
Ну. Как я понял, логика там такая: какова вероятность того, что при отображении одного элемента из множества значений для хэша мы НЕ попадём в конкретный элемент h. Стрелочки — это к ответу на вопрос: какова вероятность того, что при отображении всех элементов H мы не попадём в h?
Интуитивно, конечно, тут что-то не так, но это надо обдумывать, а лень. Просто вот identity — это контрпример. То есть, вероятность того, что мы не выберем h при отображении одного элемента, действительно 1 — 1/N. Но при этом, когда отображается всё множество H, каждый элемент из H будет выбран.
Вероятности же перемножать можно только для независимых событий, а тут всё же какая-то зависимость есть, хэш-функция — это не схема Бернулли. Скорее тут надо оперировать условными вероятностями.
Интуитивно, конечно, тут что-то не так, но это надо обдумывать, а лень. Просто вот identity — это контрпример. То есть, вероятность того, что мы не выберем h при отображении одного элемента, действительно 1 — 1/N. Но при этом, когда отображается всё множество H, каждый элемент из H будет выбран.
Вероятности же перемножать можно только для независимых событий, а тут всё же какая-то зависимость есть, хэш-функция — это не схема Бернулли. Скорее тут надо оперировать условными вероятностями.
Ох, не там вы плюсуете. Потому что сомнительны всё же исходные посылы и оценка меры выпадающих из множества элементов. Ведь, как формализуется то, что у хэша значения равновероятные? Я не специалист, но, наверное вот так:
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, потому что все исходные посылки выполняются.
В чём подвох-то? Что я упускаю из виду?
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, потому что все исходные посылки выполняются.
В чём подвох-то? Что я упускаю из виду?
Вы рассматриваете одну h(x), а OLS — все. Он работает с вероятностями (с такой-то вероятностью такой-то элемент будет не выбран). Вы привели пример функции, когда событие, определяемое этой вероятностью, не происходит.
Хм. А можно формальнее, а то я не понимаю :( Я сам попробую, но не факт, что я прав.
Вы говорите, что OLS записывает вероятность P(x | h(x) != y) = 1 — 1/N (кстати, для функции x mod N эта вероятность тоже такой будет). То есть, вероятность того, что никакой из x не отображается в y. Отлично, я тоже так подумал сперва, но тогда возникает вопрос, а какой тогда смысл в перемножении этих вероятностей? Единственное, что мне приходит в голову, так это то, что это перемножение соответствует событию (x'ы не отображаются в y1 И… И x'ы не отображается в yN). Но эти штуки не являются независимыми, потому что куда-то x'ы да отображаются, и если они не отображаются в y1, то вероятность того, что они отобразятся в y2 уже выше.
Вот. А насчёт моего примера, так это просто одна из хэш-функций, удовлетворяющая всем исходным условиям для построений, сделанных OLS. Раз для неё вывод не выполняется, значит, рассуждения OLS не совсем верные.
Вы говорите, что OLS записывает вероятность P(x | h(x) != y) = 1 — 1/N (кстати, для функции x mod N эта вероятность тоже такой будет). То есть, вероятность того, что никакой из x не отображается в y. Отлично, я тоже так подумал сперва, но тогда возникает вопрос, а какой тогда смысл в перемножении этих вероятностей? Единственное, что мне приходит в голову, так это то, что это перемножение соответствует событию (x'ы не отображаются в y1 И… И x'ы не отображается в yN). Но эти штуки не являются независимыми, потому что куда-то x'ы да отображаются, и если они не отображаются в y1, то вероятность того, что они отобразятся в y2 уже выше.
Вот. А насчёт моего примера, так это просто одна из хэш-функций, удовлетворяющая всем исходным условиям для построений, сделанных OLS. Раз для неё вывод не выполняется, значит, рассуждения OLS не совсем верные.
Четта вы мне мозг сломали в другую сторону. Что если сделать поисковик по хеш-ключам, например тот же гугл, может каждое слово, фразу, словосочетание — хранить не только в качестве текста, а и в качестве хеша, и при необходимости делать сверку необходимого хеша по существующей базе. В этом случае все пароли в виде слова — можно будет элементарно обнаружить, другие со временем тоже подтянутся. Эдакая громадная база хеша…
Ну вроде это и есть подбор по словарю. Более того — слов не так много — их и без гугла можно собрать и это не так сложно. Проблема в том, что далеко не все пароли это слова из словаря или даже их сочетания. А если учитывать эту особенность — то случае задача вырождается до брутфорса, с той только разницей что хеш не надо высчитывать, а надо только из базы его брать.
Такие базы уже есть: Радужные таблицы. И есть куча онлайн-сервисов, где, например, по md5-хэшу возвращается строка, соответствующая этому хэшу.
Работа проведена хорошая, но, имхо, несколько неправильный изначальный посыл(поправьте меня, если я не прав). Как мне кажется, изначально нужно рассчитывать не по формуле 
, а по формуле lim(1-K/N)N, где k — это количество одинаковых хешей для набора от 0 до 2N, так как именно количество одинаковых хешей гарантированно дает одинаковый набор хешей после многих итераций.
, а по формуле lim(1-K/N)N, где k — это количество одинаковых хешей для набора от 0 до 2N, так как именно количество одинаковых хешей гарантированно дает одинаковый набор хешей после многих итераций.
Проверил результаты по первым 16 битам: 35 3215, 125 795, 509 153
Но начиная с 442 итерации всё время 153.
По вторым 16 битам: 35 3450, 125 856, >343 — 176
По третьим 16 битам: 35 3204, 125 852, >414 — 197
Сейчас посмотрю 32 бита
Но начиная с 442 итерации всё время 153.
По вторым 16 битам: 35 3450, 125 856, >343 — 176
По третьим 16 битам: 35 3204, 125 852, >414 — 197
Сейчас посмотрю 32 бита
Немного непонятно, что за цифры Вы приводите.
По большому количеству итераций — подтверждаю — в определенный момент происходит резкий останов. Но это несомненно издержки того, что мы взяли настолько усеченную хеш-функцию — при 8 битовом выходном пространстве никакая хеш-функция не обеспечит равномерность распределения: будут и циклы и фиксированные точки и т.п.
По большому количеству итераций — подтверждаю — в определенный момент происходит резкий останов. Но это несомненно издержки того, что мы взяли настолько усеченную хеш-функцию — при 8 битовом выходном пространстве никакая хеш-функция не обеспечит равномерность распределения: будут и циклы и фиксированные точки и т.п.
Да, конечно, не 32 бита, а 24 :-)
Я взял за основу первые 24 бита от md5 хэша и составил аналог таблички из поста от 0 до 0xffffff
Проверил и на sha1, так что можно сделать вывод: оценка точная.
Я взял за основу первые 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, так что можно сделать вывод: оценка точная.
Спасибо!
Мне очень приятно, что поднятая тема заинтересовала Вас вплоть до написания собственного кода — такое встречается на самом деле очень и очень редко.
Мне очень приятно, что поднятая тема заинтересовала Вас вплоть до написания собственного кода — такое встречается на самом деле очень и очень редко.
Кстати, на моем компьютере я еле дождался оценки для 0xFFFF на 509 итераций.
Как Вам удалось вычислить это для всех значений до 0xFFFFFF?
Как Вам удалось вычислить это для всех значений до 0xFFFFFF?
Я, наверное, чего-то не понимаю, но 0xffff у меня отрабатывает за секунды… на perl: paste.org.ru/?t3wqvc
На C будет в 100 раз быстрее :)
На C будет в 100 раз быстрее :)
Автору спасибо, очень хорошо и грамотно написано. Рядом с такими статьями, оставшиеся 90% топиков — безсистемный детский лепет школоты. Хотя конечно, дети не виноваты, что их везде и так окружает одно медиа-барахло, которое заполонило всё инфопространство.
спасибо за статью.
вспомнился сейчас алгоритм Полларда — там тоже ведь свойство сжимающего случайного отображения используется.
вообще про случайные отображения хорошо описано у Колчина. Там вроде написано примерно по вашей задаче, что p(d) при больших d равно приблизительно 2/d^2, p(d) — доля элементов от изначального количества, которые будут существовать, если применить отображение d раз.
вспомнился сейчас алгоритм Полларда — там тоже ведь свойство сжимающего случайного отображения используется.
вообще про случайные отображения хорошо описано у Колчина. Там вроде написано примерно по вашей задаче, что p(d) при больших d равно приблизительно 2/d^2, p(d) — доля элементов от изначального количества, которые будут существовать, если применить отображение d раз.
Хорошая статья, спасибо. Помнится, в RU.CRYPT тов. Межутков как-то тоже говорил о сокращении выходного множества при хэшировании хэша и даже приводил ту же оценку в ~60%, но тогда тред особого интереса не вызвал, а жаль. Ну хотя бы теперь мы узнали, что и почему. :-)
Ещё раз респект.
Ещё раз респект.
Более точную оценку можно провести узнав сколько вариаций хэшей есть от всех возможных вариантов хэша(то есть посчитав кол-во разных хэшей взятых от 0 до 2N-1, где N- длина хэша)
Ну. Если бы мы могли посчитать и задачи бы по анализу не возникло :) Тут как раз интересно, как это всё можно оценить при помощи теории вероятностей.
Просто дело в том, что посыл изначальный берется неверно — с учетом равномерности распределения переходов нельзя вероятности просто перемножать.
Поясню: идеальная равномерность распределения гарантирует, что покрытие будет полное. Но «равномерности» идеальной от хэша ждать не приходится, поэтому считать нужно исходя из равномерности распределения конкретного алгоритма хэширования.
Да, в RU.CRYPT «гостило» множество высококлассных специалистов по криптографии.
Жаль, но сейчас я не знаю ни одного такого представительного ресурса в РуНете.
Жаль, но сейчас я не знаю ни одного такого представительного ресурса в РуНете.
А что если просто добавить несколько десятков мегабайт к паролю? Ведь чем длиннее исходные данные, тем процесс хэширования медленнее. Допустим, пароль+строка длиной 20 мегабайт. Или пароль, записанный 1000000 раз подряд.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Криптостойкость 1000-кратного хеширования пароля