id: Гость   вход   регистрация
текущее время 16:07 28/03/2024
Владелец: unknown (создано 03/10/2012 10:43), редакция от 03/10/2012 12:19 (автор: unknown) Печать
Категории: криптография, алгоритмы, хэширование, стандарты, разное, события
http://www.pgpru.com/Новости/2012/ПобедителемКонкурсаSHA-3СталАлгоритмKeccaK
создать
просмотр
редакции
ссылки

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 как универсальный криптопримитив.


Источник: Национальный Институт Стандартов и Технологий США


 
На страницу: 1, 2, 3, 4, 5, 6, 7 След.
Комментарии [скрыть комментарии/форму]
— Гость (19/04/2013 14:19)   <#>
А от увеличения количества раундов тоже?
Увеличение количества раундов может ослабить шифр вытащив наружу слабости ключевого расписания. Это актуально в частности для AES. Поэтому отказ от ключевого расписания может быть оправдан в ряде случаев.
— unknown (19/04/2013 14:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Количество раундов для идеальной сети Файстеля, для идеальной перестановки (с разными типами добавления ключа) строго посчитано (хотя есть некоторые разночтения). Пусть это и сферические модели в вакууме. Но их можно увязывать с неидеальностью раундовой функции и выбирать оптимум по числу раундов. Можно с запасом. Эта модель мне в общем виде хотя бы понятна.

С немарковвскими шифрами пусть разбирается тот, кто хочет предлагать их, как альтернативу. Пожалуйста, стройте модели, доказывайте, сравнивайте, кто ж запрещает.
— Гость (19/04/2013 14:20)   <#>
Можете выдвигать политические объяснения на базе технических, а не в обратном порядке?
Могу, но предоставляю эту возможность вам.
ЗЫ. Даже во времена недавнего свирепого материализма вопрос о роли личностей в истории глупым совсем не считался.
— Гость (19/04/2013 14:25)   <#>
Увеличение количества раундов может ослабить шифр вытащив наружу слабости ключевого расписания.
Замечательно! А можете вы порекомендовать, какой параметр и как менять для гарантированного увеличения стойкости, пусть и за счёт большей затраты ресурсов. Или сие науке пока неизвестно?
— Гость (19/04/2013 14:26)   <#>
хотя бы не уменьшения
— Гость (19/04/2013 14:47)   <#>
хотя бы не уменьшения
Делать каскады, пусть даже из одного шифра, с независимыми ключами. И не забывать о том что каскад по свойствам не эквивалентен одиночному шифру. В частности из каскада нельзя делать хэш.
— Гость (19/04/2013 14:47)   <#>
Чего тут непонятно? Обыватель должен незыблемо верить, что любое отклонение от предписанного в любую сторону – например повторное шифрование – ведёт только к ухудшению. Иначе как работать секретным службам?

А задаче формирования у населения такой веры способствуют некоторые из местных "гуру". Надеюсь, неосознанно.
— SATtva (19/04/2013 15:04)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Перечитайте второй абзац.
— Гость (19/04/2013 17:53)   <#>

А вы, это... "отличие криптоанализа марковских от немарковских (в т.ч. и с независимыми раундовыми ключами) шифров уже изучили? Там сильный выигрыш в стойкости получается или не очень?"


И Вы тоже.
— spinore (21/04/2013 01:19)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Напомнило проблему ECC.

Как я понимаю, публика хочет сказать следующее:

Изначально создаётся какой-то шифр/хэш/конструкция с какими-то заявленными и доказанными свойствами криптостойкости. Чтобы добиться большей производительности, шифр/хэш преднамеренно упрощают, считая, что криптостойкость при этом не понижается, или считая, что понижается незначительно. Соответственно, публика предлагает: давайте возьмём шифр/хэш и откатим обратно изменения, внесённые для повышения производительности (и которые ещё не понятно как сказываются на криптостойкости). По теории криптостойкость при таком откате не должна пострадать. Например, в местах, где используются связанные ключи, будем брать независимые ключи и т.д. Создаётся впечатление, что есть много мест в хэше/шифре, которые можно тривиально улучшить, и доказательство того, что улучшения не сделают хуже, тоже тривиальны.

Это то, как понял я вышенаписанные посты, но прокомментирует пусть лучше unknown.
— Гость (21/04/2013 02:00)   <#>
К свойствам шифров есть требования относительно ключа:
  1. Сложность взлома должна быть 2n, где n — число битов ключа.
  2. Каждый бит должен иметь одинаковое влияние (при изменении любого бита ключа в среднем меняется половина бит шифртекста).
  3. Все биты ключа должны быть в равной мере невычислимы из пары/пар { открытый текст / шифртекст }.
Требования вроде понятные и логичные, но они приводят к необходимости ключевого расписания, что в реальных применениях понижает (может понижать?) стойкость.

Предлагается:
  1. Все эти требования к ключу снять. Пусть стойкость вычисляется относительно размера блока.
  2. Ввести правило, что на вход могут подаваться только гарантированно случайные ключи, и атакующий не может их выбирать. То, что при этом некоторые биты ключа будут вычисляться — пофиг.

Например, если преобразовать AES256 в вышепредложенную форму, потребуется ключ длиной 1920 бит. При этом он заведомо не будет иметь недостатков ключевого расписания, которые имеет оригинальный AES (и которые могут быть еще неизвестны). Кроме того, появится еще одно замечательное свойство: недостатки раундовой функции можно замаскировать увеличением количества раундов. Можно увеличивать их число сколько угодно, стойкость от этого не может упасть.* Считаем, что атакующий имеет много шифртекста и часть открытого текста, при этом успешной атакой считается расшифровка неизвестной части. Вот такая модель.

Если атакующий выбирает ключ, то вся система рассыпается. Предлагаемый вариант имеет огромное множество oчевидно слабых ключей, поэтому должно быть строгое требование: ключ только случайный и только независимый. Это требование настолько же важно, насколько для потоковых шифров важно требование, чтобы поток не повторялся.**

Unknown, не могли бы вы прокомментировать это более развёрнуто, чем просто сказать в общих словах, что это «неакадемическая и никому не интересная фигня»?


*Может только возрасти или не измениться. Длина ключа, соответственно, при этом растет линейно.
**Если поток повторяется, они тривиально взламываются (кстати, это типичная ошибка говнописателей). Так же и тут: если ключ не случайный, получим тривиальный взлом, поэтому такой шифр требует аккуратного применения.
— unknown (21/04/2013 21:05)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Во-первых, смотрите матчасть здесь: fileBlock Ciphers – The Basics, © Lars R. Knudsen. Обратите внимание, что все атаки рассматриваются без привязки к ключевому расписанию. Т.е. они и так будут работать. Слабое ключевое расписание позволяет доломать шифр. Собственно, есть два экстремальных направления: создание сверхсильного и ресурсоёмкого ключевого расписания, близкого к идеальной PRF (единственный "взлетевший" пример — Blowfish, в котором единственной же широко известной атакой, что забавно, оказался небольшой класс слабых ключей); второе экстремальное направление — отказ от ключевого расписания. В т.н. "легковесной криптографии" выдвинута гипотеза, что можно сконструировать идеальную раундовую функцию, в которой вполне можно использовать ключевое расписание, наподобие ГОСТ-89 или вообще один подключ в каждом раунде с каким-нибудь примитивным счётчиком для генерации раундовых констант. Стремления создать шифр с полностью независимыми раундовыми подключами всерьёз нет. Хотя ещё в семидесятые годы что-такое обсуждалось, но только для изучения DES и сравнительного анализа стойкости. Вроде как раз были выводы в том, что идеальное ключевое расписание покрывает небольшой класс атак. Оптимизация в сторону неидеальности допустима. Смотрите ещё раз слайды Кнудсена, думайте. Похоже это тривиальные идеи, которые давно пройденный этап. Но и не до конца формализованный в то же время.

Во-вторых, ещё раз спасибо 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 и просто хэша и не удивлялись, почему для этого всего нужны раздельные конструкции.

В итоге, я склоняюсь к мнению, что в будущих стандартах масштабирование стойкости если и будет реализовано, то это должно быть сделано не грубо в лоб, а во-первых, с хорошей теоретической обоснованностью без доказателсьтв на незнании и запутывании. А во-вторых, с привязкой к практическим потребностям реализации, чтобы взломы легковесных и сменяемых режимов не означали взлом стандарта.

Наконец, для упорных философствований в духе "всё равно симметричная криптография построена на незнании, запутывании и трюкачестве", можно давать ответ — она построена на минимизации неясности. Т.е. доказательству в духе "мы знаем всё, кроме вот этого маленького кусочка (суррогата т.н. трудной проблемы), чем он меньше, тем нам лучше, но если кто-то может его разобрать лучше нас (сообщества криптоспециалистов), возможно, он разрушит наше доказательство (редукционстское обоснование стойкости)".

Противоположный антипозитивистский подход теперь уже неконструктивен и непродуктивен, т.к. его приверженцы вообще снимают с себя бремя сколь-нибудь обоснованных доказательств стойкости своих творений.
— spinore (22/04/2013 02:17, исправлен 22/04/2013 02:21)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Unknown, спасибо за развёрный и интересный пост! Ниже некоторые вопросы, в меру моего понимания:



s/неидеальности/идеальности/?



Извиняюсь за глупый вопрос, но всё же. Следует ли из теории информации невозможность создания

  1. Идеального шифра?
  2. Идеального хэша?

Т.е. вариант 1 — мы не знаем никаких идеальных конструкций, и вариант 2 — мы знаем заранее, что они невозможны. Если имеется вариант 2, то сразу возникает вопрос, насколько близко можно приблизиться к идеалу, т.е. известны ли абсолютные теоретические границы. Я имею в виду не столько идеальность в формальном её определении через RO, сколько идеальность в «общечеловеческом» смысле.1


Смутно припоминаю ролик на youtube с объяснением работы DH. Там показывалось, кажется, что возведение в степень в группе даёт практически случайные числа на циферблате, т.е. непредсказуемые. Грубо говоря, у нас есть(?) какой-то доказанный источник «случайности» в матконструкции, на который можно опереться. Есть ли что-то подобное для криптопримитивов в целом (шифров и хэшей)?



s/идеальная/неидеальная/(?)



идеальная? Не бывает идеальных PRP, но бывают идеальные PRF?



Т.е. взлом обычно происходит не за счёт выяснения новых свойств хорошо изученных конструкций, а за счёт узнавания нового о том, что было малоизученно (трудная проблема)? Грубо говоря, «чем меньше запутывания, тем лучше» и «стойкость хорошо изученных конструкций можно доказать строго, не аппелируя к какому-то незнанию, сложным проблемам и их неизученности (пример — одноразовый блокнот), поэтому надо использовать преимущественно их — в них сюрпризы практически исключены и внезапный взлом нереален, т.к. их стойкость — математическая (опирается на формально доказанные теоремы)». Так получается?



Как обычно бывает в таких случаях, организаторы пишут просьбу участникам прислать свои слайды для выкладывания их на сайте.2 Но:

1. Участники могут отказаться или просто проигнорировать такие письма без объяснения причин («просто лень, незачем»).
2. Бывает, что слайды содержат интересные и ещё неопубликованные идеи, поэтому авторы боятся их выкладывать в публичный доступ.
3. Другой вариант — они считают, что слайды недостаточно хороши, чтобы их было нестыдно выкладывать, или ничего не содержат такого, что поясняет идеи лучше, чем их статьи.

Эти варианты касаются не только выкладывания информации на сайтах конференций, но и выкладывания слайдов на личных страницах авторов. Это примерно то, что я понял из общения с организаторами подобных мероприятий и участниками.


Кстати, на одном из недавних воркшопов поступили вообще интересно: слайды выложили на сайт, но страницу с ними закрыли паролем, дав его только тем, кто участвовал в конференции. Надо бы скачать и слить на wikileaks^W в паблик, если там есть что-то действительно интересное.



1Те требования, которые предъявляются к шифрам и хэшам при их реальном применении в приложениях, типа невзламываемости ключа даже при знании пар {открытый текст, шифртекст} и т.д.
2Ну, или дать разрешение на выкладывание в паблик, если слайды уже у организатора.

— unknown (22/04/2013 10:17, исправлен 22/04/2013 13:03)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Сложно копать куда-то глубоко на эту тему, поэтому пост получился неаккуратный, торопливый (несмотря на потраченное время) и относительно поверхностный. Попробую слегка привести мысли впорядок.


Здесь пост я уже неоднократно редактирую, пока не надоест, следите за актуальной версией :)


Небольшие пояснения:


Собственно, есть два экстремальных направления:

второе экстремальное направление — отказ от ключевого расписания.

Т.е. не так как предлагали здесь ранее — полностью независимые ключи, а наборот, практически один и тот же ключ для всех раундов с незначительными изменениями. Суперлегковесное расписание.


Поэтому:

Оптимизация в сторону неидеальности допустима.

Т.е. в "легковесной криптографии" предлагают забить на ключевое расписание, но не заменой его большим ключом для усиления, а наоборот, сделав такое расписание максимально слабым, неидеальным, но сосредоточиться на стойкости раундовой функции.


Извиняюсь за глупый вопрос, но всё же. Следует ли из теории информации невозможность создания
1. Идеального шифра?
2. Идеального хэша?

Да, следует невозможность создания всех идеальных конструкций. Потоковые шифры и прочие функции туда же относятся. В слайдах Андреевой это показано как раз не только для Keccak, а для любой попытки реализации некоего сферического хэша в реальном мире.


Смутно припоминаю ролик на youtube с объяснением работы DH. Там показывалось, кажется, что возведение в степень в группе даёт практически случайные числа на циферблате, т.е. непредсказуемые. Грубо говоря, у нас есть(?) какой-то доказанный источник «случайности» в матконструкции, на который можно опереться. Есть ли что-то подобное для криптопримитивов в целом (шифров и хэшей)?

Это, примерно как для вас кто-то бы сказал на уровне "а электроны в атоме — это такие шарики на картинках". В DH и число не вполне случайное /comment62987 — утечки битов через вычисления символов Якоби и опять же дискретный логарифм ищется быстрее брутфорса методом Полларда (также как делается факторизация RSA), это лишь вычислительная псевдослучайность в любом случае. Использовать именно такие фундаментальные матпроблемы в симметричных алгоритмах пытались. Давно известен потоковый шифр и криптостойкий ГПСЧ BBS. Перед конкурсом SHA-3 был предложен VSH — Very Smooth Hash. Кроме непрактичности его ещё и поломали, обойдя все нижележащие "трудные математические проблемы" и на конкурс он не попал, но теоретические исследования в этой области продолжаются.


Проблемы этих алгоритмов помимо непрактичности из-за сильной тормознутости и прочей ресурсоёмкости ещё и в неполноте симуляции RO. Они не просто имеют зазор стойкости, как симметричные, они симулируют только какие-то отдельные качества RO, но вообще не симулируют другие (или заведомо очень плохо — другой уровень неполноты) и из них не склеить протокол напрямую без промежуточных хэширований/шифрований обычными симметричными алгоритмами. Тогда, спрашивается, зачем они нужны на замену традиционной симметрики ценой такой дикой негибкости, непрактичности, переусложнения, сложности создания протоколов? Т.е. они тянут за собой все недостатки асимметричных алгоритмов, которые традиционно сглаживают симметричными. А здесь выверт наоборот. Пока интересный только с точки зрения теории.


сразу возникает вопрос, насколько близко можно приблизиться к идеалу, т.е. известны ли абсолютные теоретические границы. Я имею в виду не столько идеальность в формальном её определении через RO, сколько идеальность в «общечеловеческом» смысле.

Почти сколь угодно близко к 2127.99999…9 … 2255.99999…9, но для идеализированных (а не идеальных моделей, т.е. которые неуязвимы, а только имеют допуски на неидеальность). Но это на уровне сравнения полуидеальности с RO, а не в «общечеловеческом» смысле, который имеет многоуровневую абстрактность.


Поскольку идеальную PRP в готовом виде создать невозможно, то используется идеальная
s/идеальная/неидеальная/(?)

Тут надо градации вводить. Идеально стойкая, или идеализированная с заведомо известным недостатком стойкости, в которой точно померян уровень дефектности. Таких тоже не бывает, они тоже в каком-то смысле идеальные. Надо поднимать терминологию из работ, но там даже на общие формулировке накладываются разные контексты.


Т.е. — финальный шифр, как идеальная модель ICM или Key Depended PRP. Или раундовая функция, которая идеально-сферична, просто имеет строго померянное отклонение от идеальности. Поэтому можно на основе примитивного теорвера в красивой обёртке с оракулами считать раунды.


Есть идеальнок PRF в качестве ключевого расписания.
идеальная? Не бывает идеальных PRP, но бывают идеальные PRF?

Ни того, ни другого не бывает.


Опять же, правильно указываете на некорректность и непроработанность формулировок. Есть (на уровне формулировок, представлений) совсем идеальная, как RO. А есть "реально неотличимая от идеальной" с фиксированным допуском на нестойкость ε. И это ещё тоже далёкая от реальности модель.


Т.е. взлом обычно происходит не за счёт выяснения новых свойств хорошо изученных конструкций, а за счёт узнавания нового о том, что было малоизученно (трудная проблема)? Грубо говоря, «чем меньше запутывания, тем лучше» и «стойкость хорошо изученных конструкций можно доказать строго, не аппелируя к какому-то незнанию, сложным проблемам и их неизученности (пример — одноразовый блокнот), поэтому надо использовать преимущественно их — в них сюрпризы практически исключены и внезапный взлом нереален, т.к. их стойкость — математическая (опирается на формально доказанные теоремы)». Так получается?

Теперь у вас самого слегка взаимоисключающие параграфы путанно, это кажущаяся парадоксальность, пока не переформулировано яснее. Взлом может произойти и за счёт:


1. "Выяснения новых свойств хорошо изученных конструкций". Значит, плохо изучили, неаккуратно сконструировали.
2. И "за счёт узнавания нового о том, что было малоизученно (трудная проблема)". Но на этом пункте хотя бы можно строить доказательство: если всё кроме этой проблемы ясно, а она трудная и её никто не знает, как решать, то давайте всю трудность сведём к ней.


«стойкость хорошо изученных конструкций можно доказать строго, не аппелируя к какому-то незнанию, сложным проблемам и их неизученности (пример — одноразовый блокнот), поэтому надо использовать преимущественно их — в них сюрпризы практически исключены и внезапный взлом нереален, т.к. их стойкость — математическая (опирается на формально доказанные теоремы)». Так получается?

Строго доказанных вообще нет. Кроме одноразового блокнота и его аналогов. Есть общепризнанные трудные математические проблемы и есть их суррогаты (инженерные конструкции), например "S-блок с такими-то свойствами ведёт себя так-то. В рамках наших знаний он неидеален с известной погрешностью, значит посчитав наши знания о нём (на данный момент, с поправками на будущее, с перестраховками) полными и исчерпывающими, на основе их можно скомбинировать S-блоки, подключи и линейные функции для построения раундовой функции стойкостью λ, из которых создать криптоалгоритм с допуском на неидеальность ε".


Подводя некоторый итог.


Есть разные уровни абстракции идеальности. Самый верхний: случайный оракул (RO) и идеальный блочный шифр (ICM) или PRF/PRP. Они абсолютно идеальны.


Уровнем ниже. Ближе к реальности: неидеальные, но идеализированные конструкции с допуском на неидеальность. Как весь алгоритм, так и его составные части (раундовые функции).


Ещё ниже: особенности конкретных допусков для конкретных реализаций. Алгебраическая сложность, дифференциальная, линейная и пр.: каждая задаёт свой допуск в рамках более конкретной модели.


Может ещё уровень глубже есть. И взлом (атаки) могут быть из-за ошибок в конструировании на любом из уровней. На самых верхних уровнях проще всего исключить ошибки, сделать максимально полное покрытие от возможных атак. Незнание загоняется на самый нижний уровень, где неприятные сюрпризы считаются наименее вероятными до какой-то фундаментальной смены парадигмы.


Т.е. это и уровни идеализации и уровни исключения незнания, сведения его к минимуму, минимизации.


P.S. Теперь понимаю, насколько наивной была попытка поместить понимание фундаментальных основ в FAQ.

— SATtva (23/04/2013 14:40)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Кстати, на одном из недавних воркшопов поступили вообще интересно: слайды выложили на сайт, но страницу с ними закрыли паролем, дав его только тем, кто участвовал в конференции. Надо бы скачать и слить на wikileaks^W в паблик, если там есть что-то действительно интересное.

А вдруг они раздают персонализированные копии файлов в целях traitor tracing?
На страницу: 1, 2, 3, 4, 5, 6, 7 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3