Pull to refresh

Comments 33

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отсюда вывод, что за хеш функцию можно так же считать и длину строки и количество гласных/согласных и тд
из двух ошибочных утверждений можно вывести абсолютно все что угодно (простое правило импликации), но данное — еще и бессодержательно. Может поясните тогда?
Это уже кал. Если не понимаете мое выражение — вот пример возможной хеш ф-ции: Strlen( str ), отображает строку в множество натуральных чисел (включая ноль)
Only those users with full accounts are able to leave comments. Log in, please.