Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 89
Несколько странное заявление.
Никакой хэш не является однозначным идентификатором сообщения.
Никакой хэш не является однозначным идентификатором сообщения.
Спасибо, поправил для удобного чтения.
MD6, как и MD5 «скрывает за собой пространство сообщений», но проверке это не мешает.
является ли дайджест в данном случае однозначным «идентификатором» конкретного сообщения, или же скрывает за собой пространство сообщений
MD6, как и MD5 «скрывает за собой пространство сообщений», но проверке это не мешает.
пространство он будет в себе скрывать по определению: невозможно однозначно отобразить неограниченое количество входных данных в ограниченное множество (хоть и большое) выходных
Ни к чему такому он не стремится. Принципиально невозможно избавиться от того, что одному хэш-значению будут соответствовать несколько разных сообщений. Но разработчики алгоритма стремятся к тому, чтобы получение коллизий было максимально сложным: groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf
Подозреваю, что стоит пинать русское описание алгоритма, а не сам алгоритм :)
Само понятие хеш-функций подразумевает существование коллизий. А отсылка на возможность использования в качестве уникального идентификатора — подразумевает что коллизии достаточно «равномерны».
Само понятие хеш-функций подразумевает существование коллизий. А отсылка на возможность использования в качестве уникального идентификатора — подразумевает что коллизии достаточно «равномерны».
Кстати, в описании к MD5 у них все то же самое написано.
Слово «проверка» не обязано означать однозначную идентификацию. Это уже скорее придирка.
Фраза «разным сообщениям может соответствовать один MD6» отнюдь не подразумевает неустойчивость к коллизиям первого рода. Конечно, и не исключает, но нельзя делать скороспешных выводов из этой фразы, ибо она скорее всего была рассчитана на тех, кто вообще не знает, что это такое.
Используется для проверки подлинности опубликованных сообщений, путем сравнения дайджеста сообщения с опубликованным.
Господа, Вы уж определитесь, является ли дайджест в данном случае однозначным «идентификатором» конкретного сообщения
Слово «проверка» не обязано означать однозначную идентификацию. Это уже скорее придирка.
MD6 не обладает достаточной стойкостью к коллизиям первого рода.
Фраза «разным сообщениям может соответствовать один MD6» отнюдь не подразумевает неустойчивость к коллизиям первого рода. Конечно, и не исключает, но нельзя делать скороспешных выводов из этой фразы, ибо она скорее всего была рассчитана на тех, кто вообще не знает, что это такое.
ну и плюс MD6 представлено как предложение по замене в будущем для SHA2 (а не для MD5, которое давно заменено SHA1, а далее — SHA2).
интересная информация
будем ждать выхода конкретных реализаций для языков программирования
будем ждать выхода конкретных реализаций для языков программирования
Хотя бы алгоритм опубликовали бы, можно было бы и Non Pure реализацию сделать.
И зачем оно есть? Конкретная реализация, включая код, и алгоритм, есть в proposal«е на NIST submission (http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27). Но поскольку оно в данный момен используется аж ниодной программой, и не вошло ни в какие стандарты, этот код представляет интерес лишь с точки зрения любопытства и анализа.
Определитесь с орфографией хеш/хэш (gramota.ru рекомендует хеш)
Ректальный — это для устаревших разработок. Сейчас все более актуален терморектальный.
Пора начинать производство терморектальных терминалов.
дешифраторов
Не поверишь, они уже существуют.
Выпуск настолько медленного алгоритма, больше похож на маркетинговый ход.
Хотя, я так понимаю MD5(6?) свободно распространяется.
Хотя, я так понимаю MD5(6?) свободно распространяется.
Более медленный алгоритм нужен для замедления нахождения коллизий и переборов.
А почему вы решили что он более медленный?
Спасибо, я все понял.
P.S. и фотка хорошая :)
P.S. и фотка хорошая :)
А с каких это пор md5 считается взломанным? Он лишь 'частично небезопасен'. Ну да, удалось Вонгу, Ю и Климе отыскать коллизии. Но если я правильно понял их работы, то это поиск именно коллизий. То есть, поиск двух строк, для которых md5 будет одинаковое. Но эта задачка несколько отличается от 'взлома', когда надо подыскать строку, у которй md5 равен заданному. Так что, вот как-то так. Надо с терминами быть поосторожнее.
Согласен, допустим, мы защищаем сообщение
«Мама мыла раму!». А найденное сообщение с тем-же хешем, допустим, получилось: «Макс наворачивает свининку в одну харю».
Очевидно, что получатель и так заметит некоторое несоотвествие контексту.
«Мама мыла раму!». А найденное сообщение с тем-же хешем, допустим, получилось: «Макс наворачивает свининку в одну харю».
Очевидно, что получатель и так заметит некоторое несоотвествие контексту.
Там у чуваков был пример с экзешниками, один выводил хеллоу ворлд, другой что-то еще, и за пару дней они вычисляли несколько сотен байт надо поменять во втором файле, чтоб MD5 совпала с первым. Так что совсем небесполезная вещь эти коллизии ;)
Задача «отыскать строку, у которой md5 равен заданному» и есть нахождение коллизий. Задача «найти ту строку с которой кто-то там снял md5» невыполнима.
MD5 на видеокартах перебирается очень быстро, хотя начиная символов с 9-ти, 10-ти все равно почти бесполезно =)
А так на моей не топовой 9600gt — 147 миллионов md5 хешей в секунду.
А так на моей не топовой 9600gt — 147 миллионов md5 хешей в секунду.
3.4e+38 / 1.47e+6 ~= 2.31e+32 (если нигде не ошибся)
2.13e+32 / (3600*24*356) ~= 6.7e+24 лет
имея бесконечное время в запасе можно и перебором на видяшке, да…
2.13e+32 / (3600*24*356) ~= 6.7e+24 лет
имея бесконечное время в запасе можно и перебором на видяшке, да…
Ошиблись, ночю спать надо :)
Сделаем пару простых оценок:
Набор символов — цифры, строчные, заглавные. 54 штуки.
8 символов пароль. Количество комбинаций — 54^8=7.23e+13 Время 7.23e+13/147e+6 (на пару порядков тут ошибка была) = 4.92e+5 секунд = 5.7 суток.
Аналогично 9 символов — 307 дней.
Теперь заменим видеокарту на GTX280 (>400 миллионов) — 2 суток, 113 дней.
Теперь возьмем более сложный пароль и набор компов с видеокартами. К счастью брут паролей замечательно расспаралеливается.
Строчные, прописные, цифры, пробел, символы, чарсет — 85 символов.
Versus
«Кластер» на 8 машин, в каждой 3 GTX280. Суммарная скорость перебора 400*8*3=9.6 миллиарда хешей в секунду.
8 символов ((85^8)/(9.6e+9))/(3600*24)= 3.3 суток.
9 символов 3.3 * 85 = 280.5 суток — тяжело, но возможно.
Сделаем пару простых оценок:
Набор символов — цифры, строчные, заглавные. 54 штуки.
8 символов пароль. Количество комбинаций — 54^8=7.23e+13 Время 7.23e+13/147e+6 (на пару порядков тут ошибка была) = 4.92e+5 секунд = 5.7 суток.
Аналогично 9 символов — 307 дней.
Теперь заменим видеокарту на GTX280 (>400 миллионов) — 2 суток, 113 дней.
Теперь возьмем более сложный пароль и набор компов с видеокартами. К счастью брут паролей замечательно расспаралеливается.
Строчные, прописные, цифры, пробел, символы, чарсет — 85 символов.
Versus
«Кластер» на 8 машин, в каждой 3 GTX280. Суммарная скорость перебора 400*8*3=9.6 миллиарда хешей в секунду.
8 символов ((85^8)/(9.6e+9))/(3600*24)= 3.3 суток.
9 символов 3.3 * 85 = 280.5 суток — тяжело, но возможно.
как вы думаете за сколько дней\месяцев\лет его хакнут?
Английское слово “design” — ложный друг переводчика. Значение собственно ‘дизайн’ у него — одно из последних. “Design” имеет гораздо более широкое значение, чем русское «дизайн».
Лучше перевести как «схема», «модель», «устройство», «механизм», что по контексту лучше подойдёт.
Лучше перевести как «схема», «модель», «устройство», «механизм», что по контексту лучше подойдёт.
Вы уж извините, но статья напоминает вычитанный машинный перевод, при том, не совсем верный.
Нет в функциях хеширования ключей, судя по всему, речь была о размере блока.
Вернее будет «для хеша длиной 256 бит».
6 битная платформа?) исправьте опечатку
ЗЫ: Да и такое количество раундов (106, 168) выглядит необычно большим только при сравнении с прародителями MD4 и MD5, в которых было по 4 раунда. В тех же алгоритмах SHA-0, SHA-1 и SHA-512/384 по 80 раундов.
На данный момент, как уже говорили, SHA-512/384 намного быстрее (благодаря длине блока в 1024бита и размере слова при вычислении в 64 бита) и выгоднее MD6.
MD6 поддерживает также хеширование с ключем 512-бит.
Нет в функциях хеширования ключей, судя по всему, речь была о размере блока.
Так для 256 выхода потребуется 104 раунда, а для 512 – 168 раундов!
Вернее будет «для хеша длиной 256 бит».
При этом MD6-512 медленнее в полтора раза, чем SHA2-512 на 32-битных платформах и почти в четыре раза на 6
6 битная платформа?) исправьте опечатку
ЗЫ: Да и такое количество раундов (106, 168) выглядит необычно большим только при сравнении с прародителями MD4 и MD5, в которых было по 4 раунда. В тех же алгоритмах SHA-0, SHA-1 и SHA-512/384 по 80 раундов.
На данный момент, как уже говорили, SHA-512/384 намного быстрее (благодаря длине блока в 1024бита и размере слова при вычислении в 64 бита) и выгоднее MD6.
харэ минусовать… всё рано или поздно взламывают, такая же судьба ждёт и этот алгоритм
Основная проблема всех новых криптоалгоритмов в том, что они новые. Только проверка временем может дать достаточную уверенность в стойкости алгоритма. Аналитических исследований а ля "… предполагается доказуемо устойчивой к дифференциальному криптоанализу" не достаточно.
за новость спасибо, а за корявость и ошибки незачёт. =)
Статья жуткая, я в итоге не понял чем отличается от MD5, со слов автора получилось только хуже. Вообщем минус в карму, проверять надо перед тем как постить, даже copy/paste криво сделали… :(
Надо сделать страшный хеш алгоритм. Основная его соль будет в том, что вычисления одного хеша занимает, скажем, секунду. Т.е. большая куча вычислений. Вот тут стойкость к брутфорсу и возрастёт.
вполне нормально используют вычисления хеша типа MD5($salt. MD5($word)), которые вполне нормально держатся и более менее устойчивы к взлому через рейнбоу таблицы, потому что по 12символьным и больше значениям я не встречал умельцев сумевших построить.
Главное соль менять.
Главное соль менять.
Ну если MD5(MD5($word)) то можно наверное и без соли, если только в этой рейнбоу таблице нет хеша всех возможных хешей. Мне вот интересно как поиск по рейнбоу таблице работает, там же по идее могут быть триллионы хешей, они в БД находяться? Поиск в БД по такому огромному количеству данных тоже ведь не мало времени будет занимать?
Уважаемые коллеги, советую обратить внимание на проект enRupt. Мало того, что вы ознакомитесь с расширенной информацией об алгоритме MD6 (который на самом деле ничего особенного из себя не представляет), вы сможете «поддержать» проект, который в силу ряда «причин» (с которыми вы можете ознакомиться там же) остается далеко позади многих значительно более хреновых продуктов.
Автор enRupt однажды (на wasm.ru, если мне память не изменяет) очень грамотно сказал относительно того что творится практически в любой науке. Дословно не смогу, но суть:
«Есть три категории людей в любой науке. Те, кто ничего не соображают и ничего не двигают вперед. Те, кто стоит на верху — научная мафия, тоже ничего не соображают, но стопорят любой развитие по понятным причинам. И те, кто тоже ничего не соображают но пытаются двигать прогресс вперед.» (вольная интерпритация слов Sean'a).
Я думаю вы согласитесь с тем, что глупо утверждать криптоалго, который на самом деле адекватны, не имеют backdoor'ов (не тупых в лоб, а тонких, математических).
От себя хочу сказать, что поражен проектом enRupt (включая все реализации криптоалго, в том числе хэш). Более простого и достойного дизайна я еще не встречал. MD6 нервно курит в сторонке.
PS. Я не имею никакого отношения к проекту Defectoscopy / enRupt или любым иным связанным с ними. Всего лишь увлекаюсь криптографией, вижу поверхностно ситуацию «на рынке» и сижу с широко открытыми глазами, глотаю слюну и копя ненависть к этому неразумному миру. Выхлоп.
Автор enRupt однажды (на wasm.ru, если мне память не изменяет) очень грамотно сказал относительно того что творится практически в любой науке. Дословно не смогу, но суть:
«Есть три категории людей в любой науке. Те, кто ничего не соображают и ничего не двигают вперед. Те, кто стоит на верху — научная мафия, тоже ничего не соображают, но стопорят любой развитие по понятным причинам. И те, кто тоже ничего не соображают но пытаются двигать прогресс вперед.» (вольная интерпритация слов Sean'a).
Я думаю вы согласитесь с тем, что глупо утверждать криптоалго, который на самом деле адекватны, не имеют backdoor'ов (не тупых в лоб, а тонких, математических).
От себя хочу сказать, что поражен проектом enRupt (включая все реализации криптоалго, в том числе хэш). Более простого и достойного дизайна я еще не встречал. MD6 нервно курит в сторонке.
PS. Я не имею никакого отношения к проекту Defectoscopy / enRupt или любым иным связанным с ними. Всего лишь увлекаюсь криптографией, вижу поверхностно ситуацию «на рынке» и сижу с широко открытыми глазами, глотаю слюну и копя ненависть к этому неразумному миру. Выхлоп.
Приношу свои извинения за дикие опечатки (ошибки). Слишком эмоционален был, буду мудрее.
Господа, за что минусы? ) Вы хоть обоснуйте вкратце свою позицию.
>Я думаю вы согласитесь с тем, что глупо утверждать криптоалго, который на самом деле адекватны, не имеют backdoor'ов (не тупых в лоб, а тонких, математических).
Я думаю, глупо с этим соглашаться. Математические бэкдоры в опубликованых алгоритмах? На основе очень специальной засекреченой цру-шной/фсб-шной математики? Да ну!
Я думаю, глупо с этим соглашаться. Математические бэкдоры в опубликованых алгоритмах? На основе очень специальной засекреченой цру-шной/фсб-шной математики? Да ну!
Ну давайте прикинем так, не все существующие методики атак на криптоалго находятся на паблике. Криптография слишком недавно возникла, чтобы была «изучена» (если это слово здесь употребимо, конечно) на должном уровне. Раз в год, но появляется какая-либо новая атака, которая универсальна, либо учитывает конкретный дизайн сифира. Я точно знаю, что у некоторых «талантов» в загашнике есть креативные подходы к криптоанализу (не паяльник).
Поехали дальше. NIST & etc. созывают все криптографов мира на очередной компетишен. Сабмитятся сотни алгоритмов, часть из них отсеивается. Остальные начинают внимательно изучаться, изучаются экспертами, другими криптографами и любителями. Учитывается скорость (далеко не первое место в списке), теоретическая устойчивость и куча критериев, о которых я даже не знаю. Кто мешает найти способ достижения коллизии, скрыть его от общественности, сказать что это отличный алго и прожить спокойно еще лет 10? Это на низком уровне абстракции. В ситуацию можно заглянуть еще глубже.
Ну не существует резона в запуске на паблик алгоритма, который совершенен. Я не говорю о всемирном заговоре. Просто посмотрите адекватно.
Давайте пойдем еще дальше. Возьмем наш ГОСТ. Он, если мне память не изменяет, долгое время является (являлся) стандартом защиты в СССР/РФ. Существует куча подходов, чтобы его разбить в пух и прах. Когда на дефектоскопи скинули ГОСТ, он оказался чуть ли не слабее RC4 (а о его уязвимостях я думаю вы наслышаны). Как думаете, почему так?
Поехали дальше. NIST & etc. созывают все криптографов мира на очередной компетишен. Сабмитятся сотни алгоритмов, часть из них отсеивается. Остальные начинают внимательно изучаться, изучаются экспертами, другими криптографами и любителями. Учитывается скорость (далеко не первое место в списке), теоретическая устойчивость и куча критериев, о которых я даже не знаю. Кто мешает найти способ достижения коллизии, скрыть его от общественности, сказать что это отличный алго и прожить спокойно еще лет 10? Это на низком уровне абстракции. В ситуацию можно заглянуть еще глубже.
Ну не существует резона в запуске на паблик алгоритма, который совершенен. Я не говорю о всемирном заговоре. Просто посмотрите адекватно.
Давайте пойдем еще дальше. Возьмем наш ГОСТ. Он, если мне память не изменяет, долгое время является (являлся) стандартом защиты в СССР/РФ. Существует куча подходов, чтобы его разбить в пух и прах. Когда на дефектоскопи скинули ГОСТ, он оказался чуть ли не слабее RC4 (а о его уязвимостях я думаю вы наслышаны). Как думаете, почему так?
Это не просто математика, согласитесь. Криптоалго — слишком сложный механизм, построенный на куче законов. Чем сложнее механизм, тем больше количество подходов для поиска уязвимости.
Ну да, ну да. Не просто математика. Гы. Секретная наука, разработаная в подвалах Лубянки и Пентагона. Смешно. Нормальная математика.
И по предыдущему…
>Кто мешает найти способ достижения коллизии, скрыть его от общественности, сказать что это отличный алго и прожить спокойно еще лет 10?
Вот именно. Кто мешает конкурирующей конторе (ЦРУ vs КГБ) найти способ достижения коллизии или способ дешифровки и скрыть его от противника? При условии, что такой способ заведомо существует, вероятность этого существенно выше, чем если такой способ заранее неизвестен. Зачем же в явном виде давать врагу преимущество?
>Ну не существует резона в запуске на паблик алгоритма, который совершенен.
Не существует резона в запуске «на паблик» алгоритма _заведомо_ уязвимого. Порочность практики «Security Through Obscurity» лежит в основе современной криптографии. История Энигмы очень хорошо это продемонстрировала.
И по предыдущему…
>Кто мешает найти способ достижения коллизии, скрыть его от общественности, сказать что это отличный алго и прожить спокойно еще лет 10?
Вот именно. Кто мешает конкурирующей конторе (ЦРУ vs КГБ) найти способ достижения коллизии или способ дешифровки и скрыть его от противника? При условии, что такой способ заведомо существует, вероятность этого существенно выше, чем если такой способ заранее неизвестен. Зачем же в явном виде давать врагу преимущество?
>Ну не существует резона в запуске на паблик алгоритма, который совершенен.
Не существует резона в запуске «на паблик» алгоритма _заведомо_ уязвимого. Порочность практики «Security Through Obscurity» лежит в основе современной криптографии. История Энигмы очень хорошо это продемонстрировала.
:)
Ни о каком преимуществе в явном виде речь не идет, само собой разумеется. Просто какой резон пускать на волю алгоритм, который не укладывается в существующие лубянопентагоновские разработки?
Я отлично понимаю, что разводим демагогию. В некоторых моментах целиком с Вами согласен.
Ни о каком преимуществе в явном виде речь не идет, само собой разумеется. Просто какой резон пускать на волю алгоритм, который не укладывается в существующие лубянопентагоновские разработки?
Я отлично понимаю, что разводим демагогию. В некоторых моментах целиком с Вами согласен.
Вспомнил нашу дискуссию, когда в очередной раз наткнулся на статью про бэкдоры в Г(П)СЧ и не только.
en.wikipedia.org/wiki/Dual_EC_DRBG, см. статью by Dan Shumow & коллеги.
+ «ГСЧ — это критически важный элемент безопасности системы дискового шифрования, так как он генерирует ключи, которыми шифруются данные. Именно ГСЧ зачастую является слабым местом либо бекдором в различных проприетарных и сертифицированных органами системах шифрования, так как правильность реализации алгоритмов шифрования и методов хранения данных легко поддается проверке даже без наличия исходного кода, а ГСЧ гораздо труднее поддаётся проверке. Возможно создание односторонне стойкого ГСЧ, который позволит лицу, знающему некий секрет, восстановить все генерировавшиеся им ключи и скомпрометировать зашифрованные данные. Хороший пример такого случая — стандарт Dual_EC_DRBG, содержащий бекдор от NSA и применяющийся в Windows Vista.» © ntldr, author of DiskCryptor
en.wikipedia.org/wiki/Dual_EC_DRBG, см. статью by Dan Shumow & коллеги.
+ «ГСЧ — это критически важный элемент безопасности системы дискового шифрования, так как он генерирует ключи, которыми шифруются данные. Именно ГСЧ зачастую является слабым местом либо бекдором в различных проприетарных и сертифицированных органами системах шифрования, так как правильность реализации алгоритмов шифрования и методов хранения данных легко поддается проверке даже без наличия исходного кода, а ГСЧ гораздо труднее поддаётся проверке. Возможно создание односторонне стойкого ГСЧ, который позволит лицу, знающему некий секрет, восстановить все генерировавшиеся им ключи и скомпрометировать зашифрованные данные. Хороший пример такого случая — стандарт Dual_EC_DRBG, содержащий бекдор от NSA и применяющийся в Windows Vista.» © ntldr, author of DiskCryptor
А это действительно бэкдор? Ну, то есть сознательно разработаный и внедрённый?
Как-то слабо в это верится. То, что алгоритмы могут содержать уязвимости я не спорил и не спорю. Я сомневался в том, что кто-то станет сознательно разрабатывать алгоритм, заведомо содержащий уязвимость, поскольку это, в общем-то, фора противнику. Наверное, есть случаи, когда польза от такого фокуса превышает потенциальный вред от раскрытия, но что-то я не очень себе представляю такие случаи :).
Ну и, ГСЧ — это скорее уязвимая реализация идеи. Можно и нарушение протокола обмена ключами ведь назвать бэкдором :).
Как-то слабо в это верится. То, что алгоритмы могут содержать уязвимости я не спорил и не спорю. Я сомневался в том, что кто-то станет сознательно разрабатывать алгоритм, заведомо содержащий уязвимость, поскольку это, в общем-то, фора противнику. Наверное, есть случаи, когда польза от такого фокуса превышает потенциальный вред от раскрытия, но что-то я не очень себе представляю такие случаи :).
Ну и, ГСЧ — это скорее уязвимая реализация идеи. Можно и нарушение протокола обмена ключами ведь назвать бэкдором :).
Судя по аналитике достаточно известных криптографов-андеграундистов ) да. Это не потому что все ищут следы глобального заговора. ГСЧ — основа практически любого крипто. Используя уязвимость в ГСЧ ты накрываешь все алго его использующие. Т.е. backdoor становится несколько универсальным.
Я целиком согласен с вами, что backdoor'ы в криптоалго несколько проблематичнее и значительно сложнее в реализации и скрытии. Но если backdoor не был замечен в относительно открытом ГСЧ, то почему такого не может быть с открытым сифиром?
Я целиком согласен с вами, что backdoor'ы в криптоалго несколько проблематичнее и значительно сложнее в реализации и скрытии. Но если backdoor не был замечен в относительно открытом ГСЧ, то почему такого не может быть с открытым сифиром?
enRUPT был broken — найдена коллизия. Мои соболезнования автору, очень жаль. Быть уверенным, что для MD6 такого не случится — глупо.
Рональд Ривест то бородатый, почти. Видимо, через несколько лет алгоритм совершенства достигнет.
Я болею за шнайеровский Stein! :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Новая хеш-функция MD6