Конкурс на разработку SHA-3
Конкурс хеш-функций NIST — это открытый конкурс, проводимый Национальным институтом стандартов и технологий США (NIST) с целью разработки новой хеш-функции под названием SHA-3 в дополнение к более старым SHA-1 и SHA-2 . О конкурсе было официально объявлено в Федеральном реестре 2 ноября 2007 года. [1] «NIST инициирует разработку одного или нескольких дополнительных алгоритмов хеширования посредством публичного конкурса, аналогично процессу разработки усовершенствованного стандарта шифрования (AES). ." [2] Конкурс завершился 2 октября 2012 года, когда NIST объявил, что Keccak станет новым алгоритмом хеширования SHA-3. [3]
Победившая хеш-функция была опубликована как NIST FIPS 202, «Стандарт SHA-3», в дополнение к FIPS 180-4, Стандарт безопасного хеширования .
Соревнование NIST послужило вдохновением для проведения других соревнований, таких как соревнование по хэшированию паролей .
Процесс
Подача заявок должна была быть подана 31 октября 2008 г., а список кандидатов, принятых в первый тур, был опубликован 9 декабря 2008 г. [4] В конце февраля 2009 г. NIST провел конференцию, на которой подавшие заявки представили свои алгоритмы, а представители NIST обсудили критерии сужения круга заявок. поле кандидатов во 2 тур. [5] Список из 14 кандидатов, допущенных во 2 тур, был опубликован 24 июля 2009 г. [6] Еще одна конференция прошла 23–24 августа 2010 г. (после CRYPTO 2010) в Университете Калифорния, Санта-Барбара , где обсуждались кандидаты второго тура. [7] Объявление кандидатов финального тура произошло 10 декабря 2010 года. [8] 2 октября 2012 года NIST объявил победителя, выбрав Keccak , созданный Гвидо Бертони, Джоан Демен и Жилем Ван Ашем из STMicroelectronics и Микаэлем. Петерс из NXP. [3]
Абитуриенты
Это неполный список известных материалов. NIST отобрал 51 заявку для первого раунда. [4] 14 из них прошли во второй раунд, [6] из которых были выбраны 5 финалистов.
Победитель
2 октября 2012 года победителем был объявлен Кечак . [9]
Финалисты
NIST выбрал пять алгоритмов-кандидатов SHA-3 для перехода в третий (и последний) раунд: [10]
NIST отметил некоторые факторы, которые повлияли на его выбор при объявлении финалистов: [11]
- Производительность: «Несколько алгоритмов были повреждены или исключены из-за очень больших требований к площади [аппаратного шлюза] – казалось, что требуемая область не позволяла их использовать в слишком большой части потенциального пространства приложения».
- Безопасность: «Мы предпочитали быть консервативными в вопросах безопасности и в некоторых случаях не выбирали алгоритмы с исключительной производительностью, главным образом потому, что что-то в них заставляло нас нервничать, хотя мы не знали ни о какой явной атаке на весь алгоритм».
- Анализ: «NIST исключил несколько алгоритмов из-за масштабов их доработок во втором раунде или из-за относительного отсутствия сообщений о криптоанализе - и то, и другое имело тенденцию создавать подозрения, что конструкция, возможно, еще не полностью протестирована и не доработана».
- Разнообразие: в финалисты вошли хеши, основанные на разных режимах работы, включая HAIFA и конструкции губчатых функций , а также с разными внутренними структурами, в том числе на основе AES, битовой нарезки и попеременного XOR со сложением.
NIST опубликовал отчет с пошаговым объяснением своего алгоритма оценки. [12] [13] [14]
Не прошел в финальный тур
Следующие заявки на хэш-функции были приняты во второй раунд, но не прошли в финальный раунд. Как отмечается в объявлении финалистов, "ни один из этих кандидатов не был явно сломлен".
Не прошел во второй тур
Следующие заявки на хэш-функции были приняты для первого раунда, но не прошли во второй раунд. Они не были признаны заявителями и не имели существенных криптографических недостатков. Однако у большинства из них есть некоторые недостатки в компонентах конструкции или проблемы с производительностью.
Абитуриенты с существенными недостатками
У следующих непрошедших участников первого раунда были объявлены существенные криптографические слабости:
- АВРОРА ( Университет Sony и Нагои ) [28] [29]
- Блендер [30] [31] [32]
- Гепард [33] [34]
- Динамический SHA [35] [36]
- Динамический SHA2 [37] [38]
- ЭКО
- Эдон-Р [39] [40]
- ЭнРУПТ [41] [42]
- СУТЬ [43] [44]
- ЛЮКС [45]
- МЦСША-3 [46] [47]
- НАША
- Сгайль [48] [49]
- Спектральный хэш
- Твистер [50] [51]
- Вихрь [52] [53]
Пропущенные участники
Участники первого тура были официально сняты с конкурса своими заявителями; согласно официальному веб-сайту кандидатов первого раунда NIST, они считаются сломанными. [54] Таким образом, они сняты с конкурса.
- Счеты [4] [55]
- Буль [56] [57]
- ДЧ [4] [58]
- Хичиди-1 [4] [59]
- МешХэш [4] [60]
- ШАМАТА [4] [61]
- СтримХэш [4] [62]
- Клубок [4] [63]
- ВаММ [64] [65]
- Водопад [66] [67]
Отклоненные заявки
Несколько заявок, полученных NIST, не были приняты в качестве кандидатов в первом туре после внутренней проверки, проведенной NIST. [4] В целом, NIST не сообщил подробностей о том, почему каждый из них был отклонен. NIST также не предоставил полного списка отклоненных алгоритмов; Известно, что их 13, [4] [68] , но общедоступны только следующие.
- HASH 2X [ нужна ссылка ]
- Марака [69] [70]
- МИКСИТ [71]
- НКС 2Д [72] [73] [74]
- Поник [75] [76]
- ЗК-Склеп [77]
Смотрите также
Рекомендации
- ^ «Федеральный реестр / Том 72, № 212» (PDF) . Федеральный реестр . Государственная типография. 2 ноября 2007 года . Проверено 6 ноября 2008 г.
- ^ «Проект криптографического хеширования - Справочная информация» . Ресурсный центр компьютерной безопасности . Национальный институт стандартов и технологий. 2 ноября 2007 года . Проверено 6 ноября 2008 г.
- ^ ab «NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)» . НИСТ. 2 октября 2012 года . Проверено 2 октября 2012 г.
- ^ abcdefghijk «Раунд 1». 9 декабря 2008 года . Проверено 10 декабря 2008 г.
- ^ Национальный институт стандартов и технологий (9 декабря 2008 г.). «Первая кандидатская конференция SHA-3» . Проверено 23 декабря 2008 г.
- ^ ab «Кандидаты второго тура». Национальный институт стандартов и технологий. 24 июля 2009 года . Проверено 24 июля 2009 г.
- ^ Национальный институт стандартов и технологий (30 июня 2010 г.). «Вторая кандидатская конференция SHA-3».
- ^ «Предположительный график разработки новых хэш-функций». НИСТ. 10 декабря 2008 года . Проверено 15 сентября 2009 г.
- ^ NIST выбирает победителя конкурса алгоритмов безопасного хеширования (SHA-3)
- ^ Кандидаты третьего (последнего) раунда получены 9 ноября 2011 г.
- ↑ Финалисты SHA-3 объявлены NIST. Архивировано 9 июля 2011 года в Wayback Machine , сообщение в блоге, полностью цитирующее объявление NIST.
- ^ Отчет о состоянии первого раунда конкурса алгоритмов криптографического хеширования SHA-3 (PDF).
- ^ Отчет о состоянии второго раунда конкурса алгоритмов криптографического хеширования SHA-3 (PDF). Проверено 2 марта 2011 г.
- ^ Отчет третьего раунда конкурса алгоритмов криптографического хеширования SHA-3 (PDF) .
- ^ Свейн Йохан Кнапског; Данило Глигороски; Властимил Клима; Мохамед Эль-Хадеди; Йорн Амундсен; Стиг Фроде Мьёлснес (4 ноября 2008 г.). "blue_midnight_wish" . Проверено 10 ноября 2008 г.
- ^ Сорен С. Томсен (2009). «Псевдокриптоанализ Blue Midnight Wish» (PDF) . Архивировано из оригинала (PDF) 2 сентября 2009 г. Проверено 19 мая 2009 г.
- ^ Анри Жильбер; Риад Бенаджила; Оливье Билле; Жиль Макарио-Ра; Томас Пейрин; Мэтт Робшоу; Янник Сёрин (29 октября 2008 г.). «Предложение SHA-3: ECHO» (PDF) . Проверено 11 декабря 2008 г.
- ↑ Озгюль Кюджюк (31 октября 2008 г.). «Хеш-функция Хамси» (PDF) . Проверено 11 декабря 2008 г.
- ^ Дай Ватанабэ; Кристоф Де Каньер; Хисаёси Сато (31 октября 2008 г.). «Хеш-функция Luffa: спецификация» (PDF) . Проверено 11 декабря 2008 г.
- ^ Жан-Франсуа Мисарский; Эммануэль Брессон; Энн Канто ; Бенуа Шевалье-Мамес; Кристоф Клавье; Томас Фур; Алин Гуже ; Томас Икарт; Жан-Франсуа Мисарский; Мария Ная-Пласенсиа; Паскаль Пайе; Томас Порнин; Жан-Рене Рейнхард; Селин Тюйе; Марион Видео (28 октября 2008 г.). «Шабал, заявка на конкурс алгоритмов криптографического хеширования NIST» (PDF) . Проверено 11 декабря 2008 г.
- ^ Эли Бихам; Орр Данкельман. «Хеш-функция SHAVite-3» (PDF) . Проверено 11 декабря 2008 г.
- ^ Чонгин Лим; Донхун Чанг; Сохи Хонг; Чанхон Кан; Джинкеон Кан; Чонсон Ким; Чанхун Ли; Джесанг Ли; Чонтэ Ли; Санджин Ли; Юсеоп Ли; Джечоль Сон (29 октября 2008 г.). «АРИРАНГ» (PDF) . Проверено 11 декабря 2008 г.
- ^ Филип Хоукс; Кэмерон Макдональд (30 октября 2008 г.). «Заявка на участие в конкурсе SHA-3: семейство криптографических алгоритмов хеширования CHI» (PDF) . Проверено 11 ноября 2008 г.
- ^ Жак Патарен; Луи Губен; Микаэль Иваскот; Уильям Джалби; Оливье Ли; Валери Начеф; Джоана Трегер; Эммануэль Вольте. «ХРУСТ». Архивировано из оригинала 29 января 2009 года . Проверено 14 ноября 2008 г.
- ^ Хиротака Ёсида; Шоичи Хиросе; Хиденори Кувакадо (30 октября 2008 г.). «Предложение SHA-3: Лесамнта» (PDF) . Проверено 11 декабря 2008 г.
- ^ Керем Варычи; Онур Озен; Челеби Коджайр. «Хеш-функция Сармала». Архивировано из оригинала 11 июня 2011 года . Проверено 12 октября 2010 г.
- ^ Дэниел Пенацци; Мигель Монтес. «Хеш TIB3» (PDF) . Проверено 29 ноября 2008 г.[ постоянная мертвая ссылка ]
- ^ Тецу Ивата; Кёдзи Сибутани; Тайдзо Сираи; Шихо Мориай; Тору Акисита (31 октября 2008 г.). «AURORA: семейство алгоритмов криптографического хеширования» (PDF) . Проверено 11 декабря 2008 г.
- ^ Нильс Фергюсон ; Стефан Лакс (2009). «Атаки на АВРОРУ-512 и преобразование Меркла-Дамгорда Double-MIX» (PDF) . Проверено 10 июля 2009 г.
- ↑ Колин Брэдбери (25 октября 2008 г.). «BLENDER: Предлагаемое новое семейство криптографических алгоритмов хеширования» (PDF) . Проверено 11 декабря 2008 г.
- ^ Крейг Ньюболд. «Наблюдения и атаки на блендер-кандидат SHA-3» (PDF) . Проверено 23 декабря 2008 г.
- ^ Флориан Мендель. «Атака прообразом на Blender» (PDF) . Проверено 23 декабря 2008 г.
- ^ Дмитрий Ховратович; Алексей Бирюков; Ивица Николич (30 октября 2008 г.). «Хеш-функция Cheetah: спецификация и сопроводительная документация» (PDF) . Проверено 11 декабря 2008 г.
- ↑ Данило Глигороски (12 декабря 2008 г.). «Данило Глигороски – хэш-функция Cheetah не устойчива к атакам с расширением длины» . Проверено 21 декабря 2008 г.
- ^ Цзыцзе Сюй. «Динамический SHA» (PDF) . Проверено 11 декабря 2008 г.
- ↑ Властимил Клима (14 декабря 2008 г.). «Динамический SHA уязвим для универсальных атак» . Проверено 21 декабря 2008 г.
- ^ Цзыцзе Сюй. «Динамический SHA2» (PDF) . НИСТ . Проверено 11 декабря 2008 г.
- ↑ Властимил Клима (14 декабря 2008 г.). «Динамический SHA2 уязвим для универсальных атак» . Проверено 21 декабря 2008 г.
- ^ Данило Глигороски; Руна Стайнсмо Эдегорд; Мария Михова; Свейн Йохан Кнапског; Люпко Кочарев; Алеш Драпал (4 ноября 2008 г.). "эдон-р" . Проверено 10 ноября 2008 г.
- ^ Дмитрий Ховратович; Ивица Николич; Ральф-Филипп Вайнманн (2008). «Криптоанализ Эдона-Р» (PDF) . Проверено 10 июля 2009 г.
- ^ Шон О'Нил; Карстен Ноль; Лука Хенцен (31 октября 2008 г.). «EnRUPT – Чем проще, тем лучше» . Проверено 10 ноября 2008 г.
- ↑ Себастьян Индестидж (6 ноября 2008 г.). «Коллизии для EnRUPT». Архивировано из оригинала 18 февраля 2009 года . Проверено 7 ноября 2008 г.
- ↑ Джейсон Уорт Мартин (21 октября 2008 г.). «ESSENCE: кандидатский алгоритм хеширования для конкурса NIST» (PDF) . Архивировано из оригинала (PDF) 12 июня 2010 года . Проверено 8 ноября 2008 г.
- ^ «Криптоанализ СУЩНОСТИ» (PDF) .
- ^ Ивица Николич; Алексей Бирюков; Дмитрий Ховратович. «Семейство хэшей LUX - спецификации алгоритмов и сопроводительная документация» (PDF) . Проверено 11 декабря 2008 г.
- ^ Михаил Масленников. «Алгоритм хеширования MCSSHA-3». Архивировано из оригинала 2 мая 2009 года . Проверено 8 ноября 2008 г.
- ^ Жан-Филипп Омассон; Мария Ная-Пласенсия. «Вторые прообразы на МЦССХА-3» (PDF) . Проверено 14 ноября 2008 г.[ постоянная мертвая ссылка ]
- ^ Питер Максвелл (сентябрь 2008 г.). «Криптографическая хеш-функция Sgàil» (PDF) . Архивировано из оригинала (PDF) 12 ноября 2013 года . Проверено 9 ноября 2008 г.
- ↑ Питер Максвелл (5 ноября 2008 г.). «Ой, блин!». Архивировано из оригинала 9 ноября 2008 года . Проверено 6 ноября 2008 г.
- ^ Майкл Горски; Юэн Флейшманн; Кристиан Форлер (28 октября 2008 г.). «Семейство хеш-функций Twister» (PDF) . Проверено 11 декабря 2008 г.
- ^ Флориан Мендель; Кристиан Рехбергер; Мартин Шлеффер (2008). «Криптоанализ Twister» (PDF) . Проверено 19 мая 2009 г.
- ^ Майкл Кунавис; Шей Герон (3 ноября 2008 г.). «Vortex: новое семейство односторонних хэш-функций, основанное на раундах Рейндала и умножении без переноса» . Проверено 11 ноября 2008 г.
- ^ Жан-Филипп Омассон; Орр Данкельман; Флориан Мендель; Кристиан Рехбергер; Сорен С. Томсен (2009). «Криптоанализ Vortex» (PDF) . Проверено 19 мая 2009 г.
- ^ Отдел компьютерной безопасности, Лаборатория информационных технологий (4 января 2017 г.). «Проект SHA-3 – Хэш-функции». CSRC: НИСТ . Проверено 26 апреля 2019 г.
- ↑ Нил Шолер (29 октября 2008 г.). «Счеты: кандидат на SHA-3» (PDF) . Проверено 11 декабря 2008 г.
- ^ Грегори Г. Роуз. «Проектирование и примитивная спецификация для Boole» (PDF) . Проверено 8 ноября 2008 г.
- ↑ Грегори Г. Роуз (10 декабря 2008 г.). «Официальный комментарий: Буль» (PDF) . Проверено 23 декабря 2008 г.
- ↑ Дэвид А. Уилсон (23 октября 2008 г.). «Хеш-функция DCH» (PDF) . Проверено 23 ноября 2008 г.
- ^ Натараджан Виджаяранган. «Новый алгоритм хеширования: Хичиди-1» (PDF) . Проверено 11 декабря 2008 г.
- ^ Бьорн Фэй. «МешХэш» (PDF) . Проверено 30 ноября 2008 г.
- ^ Орхун Кара; Адем Аталай; Ферхат Каракоч; Джеват Манап. «Хеш-функция SHAMATA: алгоритм-кандидат на участие в конкурсе NIST». Архивировано из оригинала 1 февраля 2009 года . Проверено 10 ноября 2008 г.
- ↑ Михал Тройнара (14 октября 2008 г.). «Спецификации алгоритма StreamHash и сопроводительная документация» (PDF) . Проверено 15 декабря 2008 г.
- ^ Рафаэль Альварес; Гэри Макгуайр; Антонио Самора. «Хеш-функция Tangle» (PDF) . Проверено 11 декабря 2008 г.
- ^ Джон Уошберн. «WaMM: алгоритм-кандидат на участие в конкурсе SHA-3» (PDF) . Архивировано из оригинала (PDF) 19 апреля 2009 г. Проверено 9 ноября 2008 г.
- ^ «Официальный комментарий: WaMM отозван» (PDFauthor = Джон Уошберн) . 20 декабря 2008 года . Проверено 23 декабря 2008 г.
- ↑ Боб Хэттерсли (15 октября 2008 г.). «Водопадный хэш – спецификация и анализ алгоритма» (PDF) . Проверено 9 ноября 2008 г.
- ↑ Боб Хаттерсли (20 декабря 2008 г.). «Официальный комментарий: Водопад сломан» (PDF) . Проверено 23 декабря 2008 г.
- ↑ Брюс Шнайер (19 ноября 2008 г.). «Моток и Новости SHA-3» . Проверено 23 декабря 2008 г.
- ^ Роберт Дж. Дженкинс-младший «Спецификация алгоритма» . Проверено 15 декабря 2008 г.
- ^ Анн Канто и Мария Найя-Пласенсия. «Атака на Мараку с внутренним столкновением» (PDF) . Проверено 15 декабря 2008 г.
- ^ Майкл П. Франк. «Спецификация алгоритма для MIXIT: кандидатный алгоритм криптографического хеширования SHA-3» (PDF) . Архивировано из оригинала (PDF) 4 марта 2016 года . Проверено 12 января 2014 г.
- ^ Джеффри Парк. «Хеш клеточных автоматов NKS 2D» (PDF) . Проверено 9 ноября 2008 г.
- ↑ Кристоф Де Каньер (13 ноября 2008 г.). «Столкновения для НКС2Д-224» . Проверено 14 ноября 2008 г.
- ^ Брэндон Энрайт (14 ноября 2008 г.). «Столкновения для НКС2Д-512» . Проверено 14 ноября 2008 г.
- ^ Питер Шмидт-Нильсен. «Поник» (PDF) . Проверено 9 ноября 2008 г.
- ^ Мария Ная-Пласенсия. «Вторая атака прообраза на Поника» (PDF) . Проверено 30 ноября 2008 г.
- ^ Николя Т. Куртуа; Карми Грессель; Ави Хехт; Грегори В. Бард; Ран Гранот. «Домашняя страница ZK-Crypt». Архивировано из оригинала 9 февраля 2009 года . Проверено 1 марта 2009 г.
Внешние ссылки
- Веб-сайт NIST для соревнований
- Официальный список кандидатов второго тура
- Официальный список кандидатов первого тура
- ША-3 Зоопарк
- Классификация кандидатов SHA-3
- Зал хэш-функций
- Исходный код VHDL, разработанный Исследовательской группой криптографической инженерии (CERG) Университета Джорджа Мейсона.
- FIPS 202 – Стандарт SHA-3