Национальный институт стандартов и технологий США (NIST) выбрал (http://www.nist.gov/itl/csd/sha-100212.cfm) победителя в проводимом с 2007 года конкурсе криптоалгоритмов, претендовавших на то чтобы стать новым стандартом криптографических хэш-функций, более стойких чем предшествующие аналоги.
Финалистами конкурса, которые были анонсированы еще около года назад, являлись 5 криптоалгоритмов, отобранные из 64 представленных на конкурс работ. Преобладали в основном кандидаты от европейских криптографов и лишь один алгоритм был представлен американцами. Алгоритмы попавшие в финал конкурса: BLAKE (https://www.131002.net/blake/), Grøstl (http://www.groestl.info/), JH , Keccak (http://keccak.noekeon.org/) и Skein (http://www.skein-hash.info/). В процессе конкурса все алгоритмы были предложены для изучения общественностью с целью поиска уязвимостей и слабых мест.
В результате NIST выбрал в качестве окончательного варианта алгоритм Keccak, реализующий (http://en.wikipedia.org/wiki/Keccak) метод хэширования с переменной разрядностью, основанный на использовании конструкции Sponge (http://sponge.noekeon.org/) (SHA-1, SHA-2 и MD5 базировались на структуре Меркла-Дамгарда (http://ru.wikipedia.org/wiki/%D0%A1%D1%8.... Одним авторов Keccak является Йоан Даймен (http://ru.wikipedia.org/wiki/%D0%94%D0%B... известный созданием алгоритма Rijndael, используемого в стандарте AES (Advanced Encryption Standard). Keccak является достаточно быстрым алгоритмом (12.5 циклов на байт на системах с CPU Intel Core 2) и эффективно реализуется без больших затрат ресурсов, что позволит использовать его без особых проблем в различных по своим параметрам системах. Аппаратная реализация Keccak оказалась наиболее быстрой из всех представленных на конкурс работ.
В целом отмечается, что большая часть представленных алгоритмов продемонстрировала высокие качества, поэтому жюри было вынуждено отбирать алгоритмы руководствуясь кроме криптостойкости и рядом иных параметров. Например, некоторые алгоритмы были отсеяны как слишком быстрые. С другой стороны, были отсеяны и алгоритмы которые слишком медленны или сложны в реализации.URL: http://www.nist.gov/itl/csd/sha-100212.cfm
Новость: http://www.opennet.me/opennews/art.shtml?num=35003
А в чем недостаток "слишком быстрых алгоритмов"?
Слишком быстро перебираются брутом, не?
Но при достаточной длине хэша, имхо, это не недостаток.
А также ускоряется построение словарей и радужных таблиц. Если радужные таблицы строить быстро - хаксоры осилят радугу для еще более длинных паролей. Ну а те кто продолбал свои хэши будут рады возможности по простому узнать пароль, ага :)
Хотя, думаю, что соглашусь, увеличение размера хэша приведёт к использованию всего лишь большего числа памяти, а вот время уменьшится. Угу.
> А также ускоряется построение словарей и радужных таблиц.Хорошо бы раз и навсегда приучить всех к соленым паролям.
Тогда актуальность радужных таблиц упала бы на пару порядков.
да кого тут приучать... не солёные пароли в хешах -- только у отявленных web-master-делетантов можно найти.
> да кого тут приучать… не солёные пароли в хешах — только у
> отявленных web-master-делетантов можно найти.в друпале, говорят…
>> да кого тут приучать… не солёные пароли в хешах — только у
>> отявленных web-master-делетантов можно найти.
> в друпале, говорят…Уже почти два года прошло с выхода 7 друпала где используется пароли шифрованные SHA512 (по умолчанию) и соль.
FYI http://api.drupal.org/api/drupal/includes%21password.in...
лучше поздно, чем никогда.
> да кого тут приучать...http://www.linkedin.com/ - этих недавно приучили.
Стянув и выложив в инет пароли юзеров, зашифрованные без соли.
В mysql зашифрованные пароли хранятся до сих пор без соли (к самой mysql, а не в юзерских табличках).
Ещё есть сомнения насчет соли в 100500 самописных сайтов на просторах инета.
Как говорится, есть две бесконечные вещи...
Тем не менее, если операция будет умерено накладной, это дополнительная защита и вполне оправданная. Мнений может быть миллион, эти товарищи очевидно думают как-то так. Хотя заглянуть им в голову у меня не получится ;)
Для хранения паролей _всегда_ следует применять key stretching.
> Например, некоторые алгоритмы были отсеяны как слишком быстрыеO_o поясните, пожалуйста
Если быстро вычислять, быстро и брутить. Хэш блока данных вычисляется единожды, если время его вычисления много меньше времени подготовки самого блока и операций с ним, то ускорение только вредит.
> Если быстро вычислять, быстро и брутить.Скорее хуже быстрая генерация радужных таблиц и прочая. Чем быстрее - тем менее затратно генерить таблицы для все более длинных паролей. Хотите требование вида "минимальный пароль - 20 символов? Ну чтоб при утечке базы с хэшами его через 5 минут не восстановили по радужной таблице вида "все alphanumeric пароли на 8 символов"? :)
РаДуЖнЫе таблици идут лесом если пароли с солью.[сообщение отредактировано модератором]
> РаДуЖнЫе таблици идут лесом если пароли с солью.Спасибо, Капитан!
Автор новости на OpenNet ошибся, пошутил или предположил, с учетом того что Keccak по быстродействию программной реализации (одного экземпляра) отстает от Skein и BLAKE (двух других финалистов) вдвое. Официально такого критерия отбора никто не называл - назывался противоположный - а Keccak всё же был выбран по сочетанию многих критериев.Это место в новости я сейчас исправил (ждет модератора).
Там IIRC было несколько итераций а исходных алгоритмов было еще больше. И критерии отсева были разными, в том числе и чрезмерная скорость - тоже. Даже если иных проблем найти не удалось. Если меня подводит склероз - поправьте.
> Там IIRC было несколько итераций а исходных алгоритмов было еще больше.Да.
> И критерии отсева были разными, в том числе и чрезмерная скорость - тоже. Даже если иных проблем найти не удалось.
Я не слышал о наличии в конкурсе на SHA-3 (на любом этапе) такого критерия. У некоторых кандидатов в SHA-3 в процессе конкурса увеличивали количество round'ов, многие выбыли из конкурса или были отозваны авторами, но это было в ответ на опасения о недостаточном запасе по безопасности, а не на высокую скорость саму по себе.
>...отсеяны как слишком быстрыеКто-нибудь возьмет и оптимизирует Keccak сделав его тоже "слишком быстрым" :)
> Кто-нибудь возьмет и оптимизирует Keccak сделав его тоже "слишком быстрым" :)Да он и так не тормоз.
Шнейер вообще пишет, что это НИНУЖНА, например.
Один и тот же криптограф, что и для AES... хм... Не уж-то и вправду гений? Или, это таки заговор спецслужб? :)
На PHD Шнайер рассказывал ка проходил выбор AES.
ООоочень демократично дал понять что это просто свой карманный криптограф спецслужб.
> На PHD Шнайер рассказывал ка проходил выбор AES.
> ООоочень демократично дал понять что это просто свой карманный криптограф спецслужб.Тем не менее, все алгоритмы - в открытом доступе. Ничто не мешает изучать их и искать уязвимости. Даже sha-1 и то не доломали до реально крякабельного состояния до сих пор. Т.е. хоть каких нибудь коллизий которые можно на практике продемонстрировать. При том что даже так это сильно нишевая атака.
> На PHD Шнайер рассказывал ка проходил выбор AES.
> ООоочень демократично дал понять что это просто свой карманный криптограф спецслужб.Что такое PHD?
> Что такое PHD?Конференция в Москве: http://phdays.ru
Что за бред? Шнайер никогда такого не говорил, даже "оооочень демократично".А вообще немного обидно за Шнайера, его Skein и в этот раз дошёл до финала, но так и не стал победителем.
> дошёл до финала, но так и не стал победителем.Да уж. А так сильный криптограф. И всегда дело говорит.
> На PHD Шнайер рассказывал ка проходил выбор AES.
> ООоочень демократично дал понять что это просто свой карманный криптограф спецслужб.Я там был и такого не помню. Можно цитату? Не очевидный совет посмотреть видео, а именно конкретную цитату из которой получается такой вывод, пожалуйста. ;-)
Опять Шнайера обломали. Теперь за то, что алгоритм слишком быстрый. А если кому-то и нужен быстрый алгоритм? Если кому-то нужен медленный, то SHA-2 уже для них существует. Прогнило у них там что-то.
> А если кому-то и нужен быстрый алгоритм?то что запрещает его использовать? Чёрные Вертолёты не прилетят, я гарантирую это.
прилетят, но по другому поводу
> прилетят, но по другому поводуинтересно, по какому?
обнаружат дифицит демократии. Ты не одобрил выбор демократического большинства :)
или захотят раздать паспорта и принудить к миру
> Чёрные Вертолёты не прилетят, я гарантирую это.Действительно - нынче в моде беспилотники :)
> были отсеяны как слишком быстрые. С другой стороны, были отсеяны и алгоритмы которые слишком медленныНу бред же. Что сложно было взять медленный алгоритм для хэширования паролей и быстрый для проверки целостности данных?
для проверки целостности данных есть crc разновидности, быстрые шопипец. Ну и, как выше уже несколько раз написали, - бери что хочешь, тебя никто в этом не ограничивает.
Внимание !
Крупные Российские "конторы" очень обеспокоены SHA-3 и еще несколько месяцев назад собирали компетентную группу по анализу этого алгоритма
Подробностей точно не знаю но в госе SHA-3 использоваться не будетПравильно выше написали - Разработчик алгоритма "свой человек"
> в госе SHA-3 использоваться не будетАмерикосы в панике.
Насколько я понимаю, для целей криптозащиты вообще зарубежные методы не должны использоваться, не? Или у нас официально разрешён и рекомендован к применению тот же PGP, например?
>> в госе SHA-3 использоваться не будет
> Америкосы в панике.
> Насколько я понимаю, для целей криптозащиты вообще зарубежные методы не должны использоваться,
> не? Или у нас официально разрешён и рекомендован к применению тот
> же PGP, например?Официально конечно же не разрешен и не рекомендован
Но вы будете удивлены что очень часто используется криптозащита именно зарубежного вендора - просто она вешается по верх нашей супер надежной отечественной
Сами знаете для чего это делается
Ни кому верить нельзя
#31 - мой.
Всё, что я там написал, естественно, о применении в госструктурах.
> и еще несколько месяцев назад собирали компетентную группу по анализу этого алгоритмаИ где результаты?
> Подробностей точно не знаю но в госе SHA-3 использоваться не будет
Конечно, там используются только ГОСТы. При том алгоритмы оных вообще не участвуют в конкурсах и не особо обсуждаются - просто вываливают и все. С чего вдруг им надо доверять больше - не понятно.
С другой стороны, алгоритм Keccak относительно новый и отличается от того что было ранее в SHA-образных хэшах. Собственно там было довольно много алгоритмов замтено отличающихся от классических.
P.S. тем не менее, имхо сша не резонно оставлять бэкдоры в таких вещах. В случае чего comodohacker-ы всякие с удовольствием оттянутся на именно их стране, нанеся максимальный урон инфраструктуре и экономике страны.
я не криптограф, но. если у хэш-функции дофига collisions, то она элементарно непригодна в качестве хэш-функции, и использовать её глупо — тем более глупо себе в карман так гадить. а хорошо посоленый хэш ломать можно до третьего пришествия.но, конечно, тушканчиков с ZOG'ом межушного ганглия это не остановит, они всенепременно будут Открывать Глаза На Вражьи Происки.
> я не криптограф, но. если у хэш-функции дофига collisions,У любой хэш функции априори есть дофига collisions. Даже бесконечно много, в допущении что на вход хэш-функции может быть подана последовательность бесконечного размера. Просто потому что мы маппим более мощное множество исходных значений в менее мощное пространство хэшей. В менее мощном - меньше допустимых вариантов значений. Значит коллизиям априори быть.
> то она элементарно непригодна в качестве хэш-функции, и использовать её глупо
Ты забыл ключевую оговорку, отличающую криптостойкие функции от нестойких: мерой криптостойкости выступает простота отыскания коллизий. Если она сравнима с перебором тупым брутфорсом всего пространства хэшей - это делает атаку нереализуемой на практике и функция претендует на криптостойкость. Если же находится путь существенно упростить атаку и сделать сильно меньше итераций чем это потребовалось бы при тупом брутфорсе - это уже считается взломом, особенно если сложность вычислений снижается до практически реализуемых величин.
> — тем более глупо себе в карман так гадить. а хорошо посоленый хэш ломать
> можно до третьего пришествия.Не совсем так. Свойства функции хэширования - имеют значение. Понимаешь, целью взлома является чтобы введенный пароль прошел проверку или блок с неправильным содержимым обладал бы тем же хэшом.
Утрированный пример: проверка пароля в BIOS setup по чексумме пароля в CMOS. Чексумма - не есть крптостойкий хэш. Поэтому есть навалом утилит которые читают это значение и считают чексумм для рандомных наборов символов до тех пор пока чексумм не совпадет. Да, это не будет оригинальным паролем. Но вбив полученную бредятину однако можно успешно зайти в bios setup. Коллизия, типа. В совсем детском виде, но зато очень хорошо показывает чем криптостойкое хэширование отличается от нестойкого :)
> но, конечно, тушканчиков с ZOG'ом межушного ганглия это не остановит, они всенепременно
> будут Открывать Глаза На Вражьи Происки....потому что выбор криптографической функции все-таки важен. Другое дело что оно вывалено для публичного анализа и криптографы так сходу откровенной халтуры не нашли. Но все-таки это менее изученная схема чем то что было раньше. Поэтому на все 100% исключать что некоторые знают что-то дополнительное о свойствах функции что позволяет проабузить это знание - совсем сбрасывать со счетов нельзя. Оптимизм в криптографии недопустим, все криптографы - профессиональные параноики :)
Годный пост. Благодарю!
> Ты забыл ключевую оговорку, отличающую криптостойкие функции от нестойких: мерой
> криптостойкости выступает простота отыскания коллизий.именно об этом я и говорил, просто очень коряво. и на старуху бывает.
> Но все-таки это менее изученная схема чем то что было раньше.
> Поэтому на все 100% исключать что некоторые знают что-то дополнительное о
> свойствах функции что позволяет проабузить это знание - совсем сбрасывать со
> счетов нельзя.я и не сбрасываю, само собой. но очень слабо верю в то, что выложеная на публику функция может содержать какие-то совершенно неизвестные мегадыры. в неё ведь пялимся не только мы, но и те, кто криптой занимается профессионально.
скажите, сударь: а вы часом не противник ГМО?
> скажите, сударь: а вы часом не противник ГМО?Ну вот, началось. Вместо того, чтоб не спешить с категорическими выводами по малоизученным вообще (и практически неизученным озвучивающим выводы) вещам -- бывает полезней подумать.
В частности, насчёт непрозрачности выбора в стандарте наборов чисел, от которых неочевидным образом зависит устойчивость хэша при одном и том же алгоритме, когда-то давно по конкретной ситуации в bugtraq@ читал.
Ни разу не эксперт и даже не специалист в крипто, но вполне понимаю желание спецслужб облегчить именно себе подбор при необходимости. А потому понимаю и заворачивающих одно в другое :)
>> скажите, сударь: а вы часом не противник ГМО?
> Ну вот, началось.форма и стиль поста провоцируют. это же классический сторонник теории заговора.
> скажите, сударь: а вы часом не противник ГМО?Кэп, ну это уже совсем жирнота и без грамма конструктива. Что-то ты совсем квалификацию порастерял.
>> скажите, сударь: а вы часом не противник ГМО?
> Кэп, ну это уже совсем жирнота и без грамма конструктива. Что-то ты
> совсем квалификацию порастерял.а я и не троллю, на этот раз я действительно просто интересуюсь. иногда и такое бывает.
> Крупные Российские "конторы" очень обеспокоены SHA-3 и еще несколько месяцев назад собирали компетентную группу по анализу этого алгоритмаAFAIK, SHA-3 утвержден буквально на днях, так что его никак не могли анализировать несколько месяцев назад. А если вы про 5 алгоритмов-кандидатов на утверждение, то конкурс начался еще аж в 2007, - что-то эти российские конторы долго чесались.
> Подробностей точно не знаю но в госе SHA-3 использоваться не будет
Ясное дело. К чему тогда вся эта паника?
> AFAIK, SHA-3 утвержден буквально на днях, так что его никак не могли
> анализировать несколько месяцев назад. А если вы про 5 алгоритмов-кандидатов на
> утверждение, то конкурс начался еще аж в 2007, - что-то эти
> российские конторы долго чесались.Я написал что еще несколько месяцев назад СОБИРАЛИ ГРУППУ
вы не представляете себе сколько надо времени подобрать компетентные кадры и тем более в данной области знаний
Подобрали группу, подготовили, дообучили
Когда сам уже алгоритм утвердили то группа может действовать уже с первого дня
Мне просто кажется что на основе существующего алгоритма Наши хотят сделать что то свое
> подготовили, дообучилиЗвучит как-то стремно. Если криптографа надо дообучать - что-то сомнительно что он много наанализирует. А для эксперта в области основные конструкции и их свойства и так не загадка.
хотят сделать ещё одну ни на что не похожую херню. Так, чтобы с ней ничего не умело работать, сдирать килобабки за свои убогие реализации и ставить палки в колёса всему остальному ПО, которое не отстегнуло этим ублюдкам $большего у нас обычно не хотят, да и нечем хотеть в контексте кадров.
Ну ГОСТ (шифрование) и хэш-функция по ГОСТу вроде как открыты, причем ГОСТ за рубежом считается неплохим алгоритмом. Бери, реализуй да раздавай бесплатно. Бабла стоит сертификация, но это уже другое дело.
Хотя, учитывая, что у нас творится в стране с образованием и борзостью чиновников, наш новый стандарт может быть принят примерно как вы описали :(
> AFAIK, SHA-3 утвержден буквально на днях,... но вон те 5 финалистов известны уже около года... :)
> Крупные Российские "конторы" очень обеспокоены SHA-3 и еще несколько месяцев назад собирали компетентную группукомпетентную группу из 3х дебилов взятых на работу по-знакомству? Ну да, наверняка вскрыли все косяки алгоритма как нехрен делать.
> вскрыли все косяки...дверные :)
Так быстрый или надёжный? Компромиссы - это правильно, но в приоритетах собака порылась.
Аппаратная реализация Keccak оказалась наиболее быстрой из всех представленных на конкурс работ. Вот что самое важное для спец служб. Ведь им потом придётся с ним мучаться.
> Аппаратная реализация Keccak оказалась наиболее быстрой из всех представленных на конкурс
> работ. Вот что самое важное для спец служб. Ведь им потом
> придётся с ним мучаться.Это сейчас очень обсуждаемая тема, и даже такой уважаемый и знающий человек как Ben Laurie допустил, с нужными оговорками, подобный блог-пост: http://www.links.org/?p=1283
Мое мнение, что у нас на данный момент недостаточно данных для корректного сравнения эффективности будущих оптимизированных для атаки реализаций SHA-1, SHA-2, SHA-3 (причем в случае SHA-2 и SHA-3 надо сравнивать еще и по нескольку вариантов из них). Из аппаратных, оптимальными для атаки обычно оказываются fully-pipelined реализации. Идем на http://cryptography.gmu.edu/athenadb/fpga_hash/table_view и пытаемся сравнить pipelined реализации SHA-2 и Keccak. Мне не удалось из этой таблицы получить для них однозначный результат - получается во-первых сравнение apples/oranges (отличаются поля Arch Type и Max Streams), а во-вторых Keccak не оказывается однозначно меньше. (С точки зрения спецслужб, актуальнее было бы сравнивать ASIC, а не FPGA реализации, но по ним у нас данных еще меньше.)
Для оптимизированных по размеру аппаратных реализаций, да, Keccak сильно выигрывает, и это хорошо - смарт-карты и т.п.
Что касается оптимизированных для атаки программных реализаций, то SIMD можно использовать (именно при атаке) и для SHA-1 и SHA-2 тоже. SHA-3, в отличие от SHA-1 и SHA-2, позволяет делать более эффективные bitslice реализации, но актуальность их сомнительна при том что распространенные ныне процессоры позволяют SIMD-реализации всех этих хешей (увы, только при наличии параллелизма уровнем выше, т.е. как при атаке) и без необходимости bitslicing'а. Вот если бы у нас, например, 256-битные операции в реализациях первого AVX'а были бы быстрее, чем 128-битные, в расчете на один бит, тогда да - это что-то дало бы. Но на существующих процессорах это не так (я проверял на Sandy Bridge и Bulldozer), а с AVX2 у нас будет возможность не-bitslice реализаций под 256-бит. Да, bitslice позволяет избавиться от затрат на перестановку битов (операции rotate в Keccak), но мы за это платим использованием L1 cache вместо регистров - так что в целом эффект не очевиден. На GPU тем более потребность в памяти будет играть бОльшую роль, чем количество операций. Какие реализации окажутся эффективнее и как они будут сравниваться с SHA-2 и SHA-1, пока не очевидно. Почти наверняка SHA-3 окажется быстрее для атак, чем SHA-512, но будет ли он быстрее для атак, чем SHA-256 и SHA-1, мне на данный момент не очевидно. Посмотрим.
А кто знает где скачать исходный код SHA3 Keccak ?