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 как универсальный криптопримитив.
Источник: Национальный Институт Стандартов и Технологий США
комментариев: 9796 документов: 488 редакций: 5664
С немарковвскими шифрами пусть разбирается тот, кто хочет предлагать их, как альтернативу. Пожалуйста, стройте модели, доказывайте, сравнивайте, кто ж запрещает.
ЗЫ. Даже во времена недавнего свирепого материализма вопрос о роли личностей в истории глупым совсем не считался.
увеличениястойкости, пусть и за счёт большей затраты ресурсов. Или сие науке пока неизвестно?А задаче формирования у населения такой веры способствуют некоторые из местных "гуру". Надеюсь, неосознанно.
комментариев: 11558 документов: 1036 редакций: 4118
А вы, это... "отличие криптоанализа марковских от немарковских (в т.ч. и с независимыми раундовыми ключами) шифров уже изучили? Там сильный выигрыш в стойкости получается или не очень?"
И Вы тоже.
комментариев: 1515 документов: 44 редакций: 5786
Напомнило проблему ECC.
Как я понимаю, публика хочет сказать следующее:
Это то, как понял я вышенаписанные посты, но прокомментирует пусть лучше unknown.
- Сложность взлома должна быть 2n, где n — число битов ключа.
- Каждый бит должен иметь одинаковое влияние (при изменении любого бита ключа в среднем меняется половина бит шифртекста).
- Все биты ключа должны быть в равной мере невычислимы из пары/пар { открытый текст / шифртекст }.
Требования вроде понятные и логичные, но они приводят к необходимости ключевого расписания, что в реальных применениях понижает (может понижать?) стойкость.Предлагается:
Например, если преобразовать AES256 в вышепредложенную форму, потребуется ключ длиной 1920 бит. При этом он заведомо не будет иметь недостатков ключевого расписания, которые имеет оригинальный AES (и которые могут быть еще неизвестны). Кроме того, появится еще одно замечательное свойство: недостатки раундовой функции можно замаскировать увеличением количества раундов. Можно увеличивать их число сколько угодно, стойкость от этого не может упасть.* Считаем, что атакующий имеет много шифртекста и часть открытого текста, при этом успешной атакой считается расшифровка неизвестной части. Вот такая модель.
Если атакующий выбирает ключ, то вся система рассыпается. Предлагаемый вариант имеет огромное множество oчевидно слабых ключей, поэтому должно быть строгое требование: ключ только случайный и только независимый. Это требование настолько же важно, насколько для потоковых шифров важно требование, чтобы поток не повторялся.**
Unknown, не могли бы вы прокомментировать это более развёрнуто, чем просто сказать в общих словах, что это «неакадемическая и никому не интересная фигня»?
*Может только возрасти или не измениться. Длина ключа, соответственно, при этом растет линейно.
**Если поток повторяется, они тривиально взламываются (кстати, это типичная ошибка говнописателей). Так же и тут: если ключ не случайный, получим тривиальный взлом, поэтому такой шифр требует аккуратного применения.
комментариев: 9796 документов: 488 редакций: 5664
Во-вторых, ещё раз спасибо Spinore, за отснятые слайды Андреевой, которые почему-то потерялись на сайте конференции. Там рассматривается общая теория не блочного шифра (PRP), а псевдослучайной функции (PRF) на примере Keccak. В частности, отмечен факт невозможности создания идеального симулятора RO и наличия допуска на нестойкость. См. стр. 13:
AdvHIndif(A) = |Pr[AREAL = 1] – Pr[AIDEAL = 1]| < ε
Если условная единица стойкости равна 2128 … 2256 бит, то размер допуска можно считать допустимым в пересчёте на доли бита.
Теперь вернёмся к слайдам Кнудсена. Поскольку идеальную PRP в готовом виде создать невозможно, то используется идеальная, но с допуском по нестойкости раундовая функция g, такая, чтобы с ростом числа раундов r, стойкость росла экспоненциально gr.
Возьму на себя смелость подглядывая к Андреевой и Кнудсену ввести обозначение для стойкости раундовой функции λ.
Тогда, с ростом числа раундов: 1 – (1 – λ)r < 1 или (1 – λ)r = ε.
Т.е., опять же, сколько раундов не делай, но при числе операций, меньшем, чем брутфорс, идеальная PRP недостижима. А теперь подумаем, что есть идеальная PRP, построеная из идеальных раундовых функций, но с допуском стойкости. Есть идеальнок PRF в качестве ключевого расписания. Как совместить их допуски при наложении друг на друга при создании шифра? Какая-то готовая формула наверняка есть, надо у Беллейра-Рогавея и прочих смотреть. Думаю, что там применяется PRP/PRF-switching Lemma.
Иначе говоря, используя большой случайный ключ вместо ключевого расписания можно выкрутиться с проблемой допуска на неидеальность и свести зазор к нулю и в некоторых моделях сделать ключевое расписание со стойкостью, равной единице.
Проблема с конструированием раундовой функции останется ведущей. Собственно, все проблемы начинаются с замены идеальных блоков на реальные. Если она неидеальная с допуском, а дефектная, то её стойкость может не описываться простой формулой 1 – (1 – λ)r. Возможны атаки, не только снижающие λ, но и вводящие некий снижающий коэффициент в степень.
Если с ключевым расписанием ещё как-то можно расправиться такими тривиальными методами, как замена на большой ключ, то смешивание раундовых функций с разными величинами λ будет нетривиально по отношению к возможным атакам. Дальше я увы не могу ничего вывести, могу только также спекулировать рассуждениями.
Моё мнение, что при серьёзной разработке шифра допуски на (не)стойкость учтены, обоснованы и могут быть проверены другими экспертами, в т.ч. на мини-моделях с масштабируемостью. Давать пользователям поиграться с увеличением стойкости вслепую за счёт масштабирования параметров может привести к сложностям в стандартизации и ошибкам в реализации. Так, в RC-5 было гибкое ключевое расписание и возможность легко устанавливать неограниченное число раундов, но не было защиты от случая смены числа раундов при несменяющемся ключе. Что могло бы приводить к атакам на практической реализации при согласовании числа раундов — слайд-атака в этом сценарии становилась успешной, а какой-нибудь программер мог не знать тонкостей того, что так реализацию делать нельзя. У Шнайера тоже были отсылки к тому, чтобы криптозащита была на уровне вкл./выкл. без всяких там тонких подстроек псевдоэкспертами горе-реализаторами. KeccaK, опять же, расчитан на универсализацию без параметризации, чтобы программеры не думали о дополнениях, тонкостях отличий HMAC, PRF, KDF и просто хэша и не удивлялись, почему для этого всего нужны раздельные конструкции.
В итоге, я склоняюсь к мнению, что в будущих стандартах масштабирование стойкости если и будет реализовано, то это должно быть сделано не грубо в лоб, а во-первых, с хорошей теоретической обоснованностью без доказателсьтв на незнании и запутывании. А во-вторых, с привязкой к практическим потребностям реализации, чтобы взломы легковесных и сменяемых режимов не означали взлом стандарта.
Наконец, для упорных философствований в духе "всё равно симметричная криптография построена на незнании, запутывании и трюкачестве", можно давать ответ — она построена на минимизации неясности. Т.е. доказательству в духе "мы знаем всё, кроме вот этого маленького кусочка (суррогата т.н. трудной проблемы), чем он меньше, тем нам лучше, но если кто-то может его разобрать лучше нас (сообщества криптоспециалистов), возможно, он разрушит наше доказательство (редукционстское обоснование стойкости)".
Противоположный антипозитивистский подход теперь уже неконструктивен и непродуктивен, т.к. его приверженцы вообще снимают с себя бремя сколь-нибудь обоснованных доказательств стойкости своих творений.
комментариев: 1515 документов: 44 редакций: 5786
Unknown, спасибо за развёрный и интересный пост! Ниже некоторые вопросы, в меру моего понимания:
s/неидеальности/идеальности/?
Извиняюсь за глупый вопрос, но всё же. Следует ли из теории информации невозможность создания
Т.е. вариант 1 — мы не знаем никаких идеальных конструкций, и вариант 2 — мы знаем заранее, что они невозможны. Если имеется вариант 2, то сразу возникает вопрос, насколько близко можно приблизиться к идеалу, т.е. известны ли абсолютные теоретические границы. Я имею в виду не столько идеальность в формальном её определении через RO, сколько идеальность в «общечеловеческом» смысле.1
Смутно припоминаю ролик на youtube с объяснением работы DH. Там показывалось, кажется, что возведение в степень в группе даёт практически случайные числа на циферблате, т.е. непредсказуемые. Грубо говоря, у нас есть(?) какой-то доказанный источник «случайности» в матконструкции, на который можно опереться. Есть ли что-то подобное для криптопримитивов в целом (шифров и хэшей)?
s/идеальная/неидеальная/(?)
идеальная? Не бывает идеальных PRP, но бывают идеальные PRF?
Т.е. взлом обычно происходит не за счёт выяснения новых свойств хорошо изученных конструкций, а за счёт узнавания нового о том, что было малоизученно (трудная проблема)? Грубо говоря, «чем меньше запутывания, тем лучше» и «стойкость хорошо изученных конструкций можно доказать строго, не аппелируя к какому-то незнанию, сложным проблемам и их неизученности (пример — одноразовый блокнот), поэтому надо использовать преимущественно их — в них сюрпризы практически исключены и внезапный взлом нереален, т.к. их стойкость — математическая (опирается на формально доказанные теоремы)». Так получается?
Как обычно бывает в таких случаях, организаторы пишут просьбу участникам прислать свои слайды для выкладывания их на сайте.2 Но:
2. Бывает, что слайды содержат интересные и ещё неопубликованные идеи, поэтому авторы боятся их выкладывать в публичный доступ.
3. Другой вариант — они считают, что слайды недостаточно хороши, чтобы их было нестыдно выкладывать, или ничего не содержат такого, что поясняет идеи лучше, чем их статьи.
Эти варианты касаются не только выкладывания информации на сайтах конференций, но и выкладывания слайдов на личных страницах авторов. Это примерно то, что я понял из общения с организаторами подобных мероприятий и участниками.
Кстати, на одном из недавних воркшопов поступили вообще интересно: слайды выложили на сайт, но страницу с ними закрыли паролем, дав его только тем, кто участвовал в конференции. Надо бы скачать
и слить на wikileaks^W в паблик, если там есть что-то действительно интересное.1Те требования, которые предъявляются к шифрам и хэшам при их реальном применении в приложениях, типа невзламываемости ключа даже при знании пар {открытый текст, шифртекст} и т.д.
2Ну, или дать разрешение на выкладывание в паблик, если слайды уже у организатора.
комментариев: 9796 документов: 488 редакций: 5664
Сложно копать куда-то глубоко на эту тему, поэтому пост получился неаккуратный, торопливый (несмотря на потраченное время) и относительно поверхностный. Попробую слегка привести мысли впорядок.
Здесь пост я уже неоднократно редактирую, пока не надоест, следите за актуальной версией :)
Небольшие пояснения:
Т.е. не так как предлагали здесь ранее — полностью независимые ключи, а наборот, практически один и тот же ключ для всех раундов с незначительными изменениями. Суперлегковесное расписание.
Поэтому:
Т.е. в "легковесной криптографии" предлагают забить на ключевое расписание, но не заменой его большим ключом для усиления, а наоборот, сделав такое расписание максимально слабым, неидеальным, но сосредоточиться на стойкости раундовой функции.
Да, следует невозможность создания всех идеальных конструкций. Потоковые шифры и прочие функции туда же относятся. В слайдах Андреевой это показано как раз не только для Keccak, а для любой попытки реализации некоего сферического хэша в реальном мире.
Это, примерно как для вас кто-то бы сказал на уровне "а электроны в атоме — это такие шарики на картинках". В DH и число не вполне случайное /comment62987 — утечки битов через вычисления символов Якоби и опять же дискретный логарифм ищется быстрее брутфорса методом Полларда (также как делается факторизация RSA), это лишь вычислительная псевдослучайность в любом случае. Использовать именно такие фундаментальные матпроблемы в симметричных алгоритмах пытались. Давно известен потоковый шифр и криптостойкий ГПСЧ BBS. Перед конкурсом SHA-3 был предложен VSH — Very Smooth Hash. Кроме непрактичности его ещё и поломали, обойдя все нижележащие "трудные математические проблемы" и на конкурс он не попал, но теоретические исследования в этой области продолжаются.
Проблемы этих алгоритмов помимо непрактичности из-за сильной тормознутости и прочей ресурсоёмкости ещё и в неполноте симуляции RO. Они не просто имеют зазор стойкости, как симметричные, они симулируют только какие-то отдельные качества RO, но вообще не симулируют другие (или заведомо очень плохо — другой уровень неполноты) и из них не склеить протокол напрямую без промежуточных хэширований/шифрований обычными симметричными алгоритмами. Тогда, спрашивается, зачем они нужны на замену традиционной симметрики ценой такой дикой негибкости, непрактичности, переусложнения, сложности создания протоколов? Т.е. они тянут за собой все недостатки асимметричных алгоритмов, которые традиционно сглаживают симметричными. А здесь выверт наоборот. Пока интересный только с точки зрения теории.
Почти сколь угодно близко к 2127.99999…9 … 2255.99999…9, но для идеализированных (а не идеальных моделей, т.е. которые неуязвимы, а только имеют допуски на неидеальность). Но это на уровне сравнения полуидеальности с RO, а не в «общечеловеческом» смысле, который имеет многоуровневую абстрактность.
Тут надо градации вводить. Идеально стойкая, или идеализированная с заведомо известным недостатком стойкости, в которой точно померян уровень дефектности. Таких тоже не бывает, они тоже в каком-то смысле идеальные. Надо поднимать терминологию из работ, но там даже на общие формулировке накладываются разные контексты.
Т.е. — финальный шифр, как идеальная модель ICM или Key Depended PRP. Или раундовая функция, которая идеально-сферична, просто имеет строго померянное отклонение от идеальности. Поэтому можно на основе примитивного теорвера в красивой обёртке с оракулами считать раунды.
Ни того, ни другого не бывает.
Опять же, правильно указываете на некорректность и непроработанность формулировок. Есть (на уровне формулировок, представлений) совсем идеальная, как RO. А есть "реально неотличимая от идеальной" с фиксированным допуском на нестойкость ε. И это ещё тоже далёкая от реальности модель.
Теперь у вас самого слегка
взаимоисключающие параграфыпутанно, это кажущаяся парадоксальность, пока не переформулировано яснее. Взлом может произойти и за счёт:1. "Выяснения новых свойств хорошо изученных конструкций". Значит, плохо изучили, неаккуратно сконструировали.
2. И "за счёт узнавания нового о том, что было малоизученно (трудная проблема)". Но на этом пункте хотя бы можно строить доказательство: если всё кроме этой проблемы ясно, а она трудная и её никто не знает, как решать, то давайте всю трудность сведём к ней.
Строго доказанных вообще нет. Кроме одноразового блокнота и его аналогов. Есть общепризнанные трудные математические проблемы и есть их суррогаты (инженерные конструкции), например "S-блок с такими-то свойствами ведёт себя так-то. В рамках наших знаний он неидеален с известной погрешностью, значит посчитав наши знания о нём (на данный момент, с поправками на будущее, с перестраховками) полными и исчерпывающими, на основе их можно скомбинировать S-блоки, подключи и линейные функции для построения раундовой функции стойкостью λ, из которых создать криптоалгоритм с допуском на неидеальность ε".
Подводя некоторый итог.
Есть разные уровни абстракции идеальности. Самый верхний: случайный оракул (RO) и идеальный блочный шифр (ICM) или PRF/PRP. Они абсолютно идеальны.
Уровнем ниже. Ближе к реальности: неидеальные, но идеализированные конструкции с допуском на неидеальность. Как весь алгоритм, так и его составные части (раундовые функции).
Ещё ниже: особенности конкретных допусков для конкретных реализаций. Алгебраическая сложность, дифференциальная, линейная и пр.: каждая задаёт свой допуск в рамках более конкретной модели.
Может ещё уровень глубже есть. И взлом (атаки) могут быть из-за ошибок в конструировании на любом из уровней. На самых верхних уровнях проще всего исключить ошибки, сделать максимально полное покрытие от возможных атак. Незнание загоняется на самый нижний уровень, где неприятные сюрпризы считаются наименее вероятными до какой-то фундаментальной смены парадигмы.
Т.е. это и уровни идеализации и уровни исключения незнания, сведения его к минимуму, минимизации.
P.S. Теперь понимаю, насколько наивной была попытка поместить понимание фундаментальных основ в FAQ.
комментариев: 11558 документов: 1036 редакций: 4118
А вдруг они раздают персонализированные копии файлов в целях traitor tracing?