Рейтинг:9

Есть ли преимущество у блочного шифра, который не является эффективно обратимым?

флаг mk

Классическое определение PRP включает эффективную обратимость.

Учитывая, что многие современные режимы шифрования (на основе CTR, например, GCM) используют только прямое направление блочного шифра, кажется, что часть определения эффективной обратимости на самом деле не нужна для практических целей.

Даст ли нам что-нибудь такое расслабление? т. е. существуют ли практические конструкции PRP, которые эффективно вычисляются в прямом направлении, но не в обратном направлении? И какие из них более эффективны в прямом направлении, чем современные блочные шифры с эквивалентной безопасностью?

fgrieu avatar
флаг ng
Заголовок и основная часть вопроса требуют разных вещей. В этом [связанном вопросе] (https://crypto.stackexchange.com/q/14338/555) я задал вопрос заголовка. Это сложно, и среди того, что предлагается, нет ничего очень быстрого в прямом направлении. Что касается вопроса в теле (который я прочитал как: можем ли мы сделать более быстрые блочные шифры, не требуя, чтобы они были эффективно обратимы): обратите внимание, что AES в программном обеспечении заметно быстрее в прямом направлении, и ускорение является преднамеренным. Но обратное по-прежнему эффективно обратимо.
eddydee123 avatar
флаг mk
Я исправил заголовок (чтобы комментарий Франсуа имел смысл, оригинал был «Блочный шифр, который не является эффективно обратимым?»)
Рейтинг:9
флаг ru

Я бы сказал, что для многих криптографов аргумент идет еще дальше. Учитывая, что режимы потоковой передачи блочного шифра предпочтительнее для массового шифрования, нужна ли вообще обратимость? Если следовать этой линейной аргументации, можно понять, почему наблюдается возрождение популярности потоковых шифров, и ChaCha20 является очевидным примером. Хотя ChaCha20 производит 512-битный вывод из 512-битного состояния и обновляет состояние с помощью простого счетчика (во многом похожего на режимы CTR и GCM), этот процесс (мы полагаем) необратим. Верно также и то, что ChaCha20 — очень эффективная конструкция (при условии, что аппаратное обеспечение поддерживает эффективное добавление 32-битных слов).

Обратите внимание, что для многих реализаций AES функция раунда расшифровки менее эффективна, чем функция раунда шифрования, поскольку инвертирует MixCol процесс более связан с вычислениями.

Gilles 'SO- stop being evil' avatar
флаг cn
«Функция раунда дешифрования менее эффективна, чем функция раунда дешифрования» Я думаю, что вторым *дешифрованием* должно быть *шифрование*? Это действительно распространено? В наивной реализации MixCol довольно симметричен.
Daniel S avatar
флаг ru
Спасибо за исправление; Я сейчас отредактировал. Если люди не используют реализации T-таблиц, наиболее распространенным подходом является умножение соответствующей матрицы, а [обратная матрица] (https://en.wikipedia.org/wiki/Rijndael_MixColumns#InverseMixColumns) имеет более неудобные записи, чем ` Матрица MixCol`, где все элементы равны 1, $x$ или $1+x$.
Рейтинг:6
флаг in

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

Нам нужен режим работы для блочных шифров, и мы покинули CBC из-за множества атак, которые произошли, несмотря на то, что он защищен Ind-CPA.В настоящее время все шифры TLS 1.3 внутренне используют безопасный режим CTR Ind-CPA (наборы шифров TLS 1.3 — это нечто большее, все они представляют собой режимы шифрования с проверкой подлинности и данными с проверкой подлинности).

Даст ли нам что-нибудь такое расслабление?

Это дает нам много возможностей. Нам не нужно ограничиваться PRP в режиме CTR - он уже был разработан для Псевдослучайные функции (ПРФ); Режим CTR не нуждается в обратной функции. С PRF мы можем использовать широкий спектр функций, которым не нужны обратные функции (есть $2^n!$ PRP и $(2^n)^{2^n}$ PRF для n-битных блочных шифров. Даже мы можем взять хеш-функцию и преобразовать ее в шифрование CTR, как в Сальса. Мы также можем разработать ключевой график практически без затрат.

Использование PRP в режиме CTR может привести к распознаватель длинных сообщений и мы можем устранить это, используя PRF. Если мы используем PRP в режиме CTR, нам нужно ограничить количество блоков шифрования из-за леммы о переключении PRP-PRF.

Режим CTR также не требует заполнения, поэтому они невосприимчивы к атакам оракула заполнения.

ChaCha20 и Salsa20 являются хорошо известными примерами, которые имеют нулевую стоимость расписания ключей, дизайн ARX с дружественным процессором. Они имеют встроенный режим CTR и очень быстры в программном обеспечении.

Рейтинг:5
флаг in

Действительно, PRF лучше подходит для различных режимов, таких как CTR, чем PRP.Проблема в том, что мы не знаем, как построить хорошие PRF, кроме как из PRP.

  1. Один из способов состоит в том, чтобы просто представить, что наша PRP является PRF: и это верно, пока не выдается определенное количество данных (граница дня рождения, см. лемму о переключении PRP/PRF).

  2. Другим часто используемым способом является вычисление PRP/перестановки и добавление ввода к выводу. Это не улучшает привязку ко дню рождения, но этот трюк делает функцию необратимой, что имеет решающее значение в некоторых случаях (например, в ChaCha, упомянутом @Daniel S). Он также используется в хеш-функциях в стиле Меркла-Дамгарда для построения функции сжатия (Дэвиса-Мейера).

  3. Добавление/объединение двух перестановок является хорошим PRF, но это дорого.

  4. Достаточное усечение вывода также является хорошим PRF, но опять же дорого.

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

poncho avatar
флаг my
Обратите внимание, что криптография на основе губки эффективно использует опцию «усечения вывода» (не выводя «емкость»)
fgrieu avatar
флаг ng
_"PRF подходит лучше, чем PRP"_ отклоняется от вопроса в его текущей формулировке, которая недвусмысленно требует эффективно вычисляемой _перестановки_ и того, что мы получаем, когда удаляем ограничение, заключающееся в том, что обратная перестановка эффективно вычислима. На примере AES вполне вероятно, что мы немного выиграем. Я согласен, что мы выиграем больше, если отбросим требование о том, что функция является перестановкой, и что с достаточно большим размером блока мы можем обойтись без этого на практике. Но я все еще нахожу интерес к этому вопросу.

Ответить или комментировать

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