03.10 // Победителем конкурса SHA-3 стал алгоритм KeccaK
После кризиса хэш-функций SHA-1 и потенциального устаревания SHA-2, Национальный Институт Стандартов и Технологий США в 2007 году объявил конкурс на новый безопасный стандарт хэширования SHS SHA-3. Команды криптографов со всего мира предлагали свои варианты и совместно анализировали дизайн разработок, выявляя уязвимости.
Алгоритмы хэширования используются для создания уникальных цифровых отпечатков документов, в качестве элементов цифровых подписей, кодов аутентификации сообщений и как составные элементы многих других протоколов.
2 октября из пяти финалистов (BLAKE, Gr0stl, JH, KECCAK, Skein) был объявлен победитель Keccak (произносится как ketch-ack), разработанный командой авторов:
- Guido Bertoni (Italy) of STMicroelectronics,
- Joan Daemen (Belgium) of STMicroelectronics,
- Michaлl Peeters (Belgium) of NXP Semiconductors,
- Gilles Van Assche (Belgium) of STMicroelectronics.
NIST выбрал KeccaK за множество удивительных качеств, включая элегантный дизайн и возможность эффективной реализации на большом количестве аппаратных платформ. Ясная конструкция KeccaK облегчает проведение его анализа. Алгоритм особенно удачно показывает себя в специализированном исполнении на аппаратных платформах, превосходя в этом плане всех других финалистов и алгоритмы SHA-2.
Эксперт по комьютерной безопасности НИСТ Тим Полк отмечает: "KeccaK имеет преимущество в том, что атаки, рассчитанные против SHA-2 не действуют против него, поскольку эти два алгоритма устроены на совершенно разных принципах".
Полк предполагает, что новые полезные свойства Keccak найдут применение спустя годы, после его принятия. Так, он может быть использован в миниатюрных встраиваемых устройствах, которые не являются полноценными устройствами.
SHA-3 открывает новые возможности перед создателями безопасных протоколов, которых они не имели раньше. И это не пустые слова.
Вслед за экспертами НИСТ следует отметить, что уникальные возможности в универсализации помогают использовать KeccaK в качестве хэш-функции с произвольным размером выхода, в качестве потокового шифра, в качестве функции выработки ключей из пароля, в качестве кодов аутентификации сообщений, в качестве криптостойкого генератора псевдослучайных чисел с подкачкой энтропии из внешнего источника и с затиранием внутреннего состояния, в качестве возможного нового режима дополнения цифровых подписей.
Позднее авторы представили дуплексный режим работы KeccaK — потоковое шифрование с аутентификацией за один проход, что может составить альтернативу использовавшимся ранее блочным шифрам в шифровании пакетной связи.
Благодаря конструкции "Sponge" (губка) — бесключевой перестановки, лежащей в основе алгоритма, открывается масса способов дальнейшей универсализации алгоритма без его изменения. Это потребует более глубокого изучения свойств Sponge-хэшей, пришедших на замену конструкциям Дамгарда-Меркла и их аналогам и окажет стимулирующие влияние как на теоретические, так и на практические направления современной криптографии.
Интересно, что все эти универсальные возможности не являются отдельными нагромождаемыми модулями, как это пытались реализовать в других алгоритмах. Смена режимов использования также не требует каких-либо переключателей предопределённого формата и никак не ухудшает простоту конструкции. На вход могут быть поданы вместе с обрабатываемыми данными и служебные управляющие данные любого формата (например XML), что позволит управлять режимом использования, получая каждый раз новый выход гаммы.
Можно присоединиться к поздравлениям разработчиков этого смелого и достойного алгоритма и пожелать им дальнейших успехов.
Более подробно ознакомиться с новым алгоритмом и посмотреть некоторые предварительные обсуждения можно в статье Хэш-функция Keccak и конструкция Sponge как универсальный криптопримитив.
Источник: Национальный Институт Стандартов и Технологий США
комментариев: 1060 документов: 16 редакций: 32
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
KeccaK в режиме потокового шифра вполне себе будет работать и достаточно безопасно (в отличие от попыток соорудить это на основе SHA-1, SHA-2), хотя и медленно.
комментариев: 9796 документов: 488 редакций: 5664
Зато Шнайеровский Skein быстрее всего в софте на обычных неспециализированных процах.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 1515 документов: 44 редакций: 5786
Да-а, вторая крупная победа в криптографии для Бельгии (после Rijndael). Как недавно сказали за обедом, «теперь наш Жиль знаменитость официально». Когда-то этот человек администрировал у нас локалку, устанавливал Linux'ы на десктопы... Многое из того, что он тогда сделал, прекрасно работает и по сей день.
И кеччак сейчас тоже программно используется в местных текущих научных разработках/проектах, но, в связи с тем что это ещё неопубликовано, распространяться о деталях не могу.
В QKD совокупная задача делится на классическую и квантовую, которые можно считать друг от друга независимыми. По сути, квантовая задача определеяет процент информации, который может быть доступен противнику (и тут всё завязано на физику), а классическая задача решает метод извлечения безопасного ключа при знании этого процента (вероятности). Т.е. если бы откуда-то у Алисы и Боба из астрала взялись сырые биты (не из QKD), и они бы знали процент влияния Евы, они бы тоже смогли бы вывести секретный ключ (reconcilation & privacy amplification). Собственно, в своём PhD по QKD Жиль как раз решал классическую задачу, т.е. по сути это классическая теория информации и классическая криптография.
комментариев: 9796 документов: 488 редакций: 5664
Чуть медленнее SHA-2.
Понятно откуда у алгоритма такая универсальность при одновременной простоте конструкции. Авторам вероятно хотелось создать не просто хэш, а практическую реализацию идеальной псевдослучайной функции, которую применять можно будет практически везде.
Самая яркая работа на конкурсе и это было заметно заранее, чтобы там не говорил Шнайер. Также как и факт принятия именно этого алгоритма весьма значим для будущего криптографии, а с ваших намёков ещё и в квантовом крипто кеччак заметно облегчает создание протоколов.
комментариев: 1515 документов: 44 редакций: 5786
Жиль делал PhD на полставки тут, а остальное время параллельно работал в STMicroelectronics*. Если почитать, чем занимается эта фирма (всякая мелкая электроника для ИБ, где нетребовательность к ресурсам критична), всё становится логичным: смотрится так, как будто штука типа кеччака им была нужна для вполне прикладных и приземлённых целей, но они решили её не только разработать, но ещё и пропихнуть в стандарт. Получилось, что вложились и в свои коммерческие технологии и в общую криптографическую науку одновременно.
Сам кеччак был широко известен ещё до принятия его стандартом; говорят, много где уже применялся для разных целей. Было бы интересно узнать, как он создавался авторами, что их подтолкнуло к этим идеям, но в моём кругу про это почти ничего не известно. Здесь больше знают Жиля по QKD, а деятельностью по кеччаку он занимался там, в фирме.
Забыл сказать, по QKD в непрерывных переменных (в дирскретных эта задача уже давно была решена).
*Трое из соавторов кеччака из этой фирмы, а четвёртый из другой, но, судя по названию, тоже со схожими интересами на рынке.
комментариев: 9796 документов: 488 редакций: 5664
Оба автора Rijndael тоже вроде линуксоиды.
Может и про spinore когда-то скажут, что когда-то он настраивал OpenBSD на роутерах и они всё ещё работают в каком-нибудь местном музее замечательных людей.
комментариев: 1515 документов: 44 редакций: 5786
Из блога Вадима Макарова:
Вообще, по ссылке много интересного.
Здесь было про диссер Лоика, он наш сервер делал — от начала и до конца, включая настройку кучи сервисов и настройку iptables. Жереми говорил, писал shell-скрипты для Linux. А этот человек, как и я, статьи в vim'е набирает. По моим наблюдениям, люди, которые работают в винде и бояться всего UNIX-подобного есть, но составляют около 10% от персонала. Ещё давно когда-то рассказывали, что среди сотрудников теротдела то ли ИЯИ, то ли ИТЭФ есть коммитеры в ядро Linux.
Если бы... Они притащили Raspberry Pi с уже установленным Debian, но кто его настраивать будет? Пришлось пару дней разбираться, почему squid не хочет работать прозрачной проксёй, а iptables не заворачивает на него трафик. И убирать из автостартов кучу сервисов тоже не самое приятное дело. Главное, что BSD на такое железо не поставишь — там его поддержка пока ещё в зачаточном состоянии :( Если серьёзно, то iptables после pf кажется совершенно бесчеловечным ассемблером.
комментариев: 9796 документов: 488 редакций: 5664
Переименовать симлинки /etc/rc2.d/S[servicename] на /etc/rc2.d/K[servicename]
комментариев: 1060 документов: 16 редакций: 32
Вот именно так всё же не очень хорошо, там ещё номера есть, которые определяют последовательность запуска, и тушить демонов лучше бы в порядке, обратном порядку их запуска.
комментариев: 9796 документов: 488 редакций: 5664
/etc/rc2.d/S[servicenumber][servicename] на /etc/rc2.d/K[servicenumber][servicename]
Так они и не запустятся.