id: Гость   вход   регистрация
текущее время 09:15 29/03/2024
создать
просмотр
редакции
ссылки

Это старая редакция страницы Библиотека / Статьи / Sponge Encryption за 17/10/2013 14:19.


Перспективные режимы Sponge-шифрования


Конструкция Sponge ранее рассматривалась в обзоре совместно с алгоритмом Keccak, благодаря которому она и получила наибольшую известность. С того моменте Keccak стал победителем конкурса на стандарт хэширования SHA-3. Но как ранее отмечалось, как конструкция Sponge, так и построенный на неё алгоритм Keccak — это не просто хэш, а универсальный симметричный криптопримитив, повзоляющий решать множество разных задач. В данном обзоре мы более подробно рассмотрим возможности Sponge для шифрования.


Вспомним, как устроена конструкция Sponge в общем виде (см. рис. 1).


Стартовый блок b (на схеме разделён на части r и c) состоит из одних нулей. Исходное сообщение M дополняется до нужного размера блока, равного части блока b, т.е. r и разделяется для поблочной обработки. Каждый такой блок сообщения M объединяется с частью r блока b при помощи операции XOR. Между этими объединениями и в заключительной части после них, блоки обрабатываются функцией многораундовой бесключевой перестановки f. Все эти преобразования входят в стадию поглощения (абсорбции) сообщения.


Во второй стадии происходит обратный процесс: стадия отжатия псевдослучайного потока данных, выработанных на основе поглощённого сообщения. Для этого из каждой части блока r выводится блок исходящих данных, между всеми блоками также производится обработка всего внутреннего состояния функцией f, как и в первой стадии. Накопленные блоки формируют исходящие данные Z.


Важно отметить, что в часть c никакие данные напрямую не вводятся и не выводятся из неё. Она только перемешивается с частью r блока b при помощи функции f.


Рис.1 Общий вид конструкции Sponge (34 Кб)
Рис. 1 Общий вид конструкции Sponge.


В простейшем случае M — это любое сообщение, а Z — это его псевдослучайное отображение. Т.е. функция Sponge работает в режиме хэш-функции.


Если перед блоками сообщения ввести блок с секретным ключом K, то получится код аутентификации сообщения (Message Authentication CodeMAC). Полученный с таким ключом проверочный хэш-код иногда кратко называется тэг (Tag), как показано на рис. 2:


Рис. 2 Функция Sponge в режиме MAC (27 Кб)
Рис. 2 Функция Sponge в режиме MAC.


При помощи знания секретного K и тэга можно аутентифицировать сообщение — удостовериться, что его отправил только тот, кто знает K и что сообщение никто не исказил в процессе передачи: иначе вычисленный и присланный вместе с сообщением Tag не сойдутся, а без знания K противник не сможет вычислить корректный Tag.


Можно использовать Sponge и для шифрования. Для этого на вход в стадии сжатия нужно вместо сообщения подать ключ шифрования K, объединённый с вектором инициализации (уникальным несекретным случайным значением N, передаваемым открыто). Тогда в стадии отжатия псевдослучайные данные на выходе с блоков можно рассматривать как гамму потокового шифра и объединять при помощи операции XOR с блоками сообщения M, как показано на рис. 3:


Рис. 3 Шифрование Sponge (29 Кб)
Рис. 3 Шифрование Sponge.


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


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


Как показано на рис.4 для этого достаточно операцией XOR сообщение M объединять с выходом гаммы, а затем снова вводить в функцию Sponge при помощи операции XOR. Все данные будут поблочно зашифрованы, а в конце будет выведен MAC — Tag. Из-за нелинейности функции f повреждение в шифртексте приведёт к изменению внутреннего состояния функции Sponge, что приведёт к искажению всех последующих блоков шифртекста и несовпадению значения Tag.


Рис. 4 Шифрование с аутентификацией Sponge (32 Кб)
Рис. 4 Шифрование с аутентификацией Sponge.


Поскольку при таком подходе стадии (фазы) поглощения и отжатия чередуются поблочно, то каждые две такие фазы образуют дуплекс, а сам такой режим работы функции Sponge назван дуплексным. В общем виде такой режим показан на рис. 5


Рис. 5 Дуплексный режим Sponge (41 Кб)
Рис. 5 Дуплексный режим Sponge.


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


Однако, если вернуться к вопросу аутентифицированного шифрования Sponge, то у него остаётся один практический недостаток: оно может исполняться только последовательно и не может исполняться параллельно. Ранее считалось, что такие параллельные режимы возможны только для блочных шифров (OCB, GCM) или при использовании громоздкого режима древовидного исполнения алгоритма.


Но исследователи Павел Моравецки (Отделение информатики университета коммерции Кельце, Польша) и Йозеф Пиепжик (Кафедра компьютерных наук, Университет Маккуори, Австралия) предложили простой, очевидный и эффективный способ параллельного исполнения аутентифицированного Sponge-шифрования.


Вариант схемы этого режима показан на рис. 6.


Рис. 6 Параллельное шифрование с аутентификацией Sponge (43 Кб)
Рис. 6 Параллельное шифрование с аутентификацией Sponge.



Литература:


"Permutation-based encryption, authentication and authenticated encryption". Joan Daemen, Michaёl Peeters, Gilles Van Assche, Guido Bertoni. DIAC 2012, Stockholm, July 6.


"Duplexing the sponge: single-pass authenticated encryption and other applications". Guido Bertoni, Joan Daemen, Michaлl Peeters, Gilles Van Assche (STMicroelectronics, NXP Semiconductors).


"Parallel authenticated encryption with the duplex construction". Pawel Morawiecki (Section of Informatics, University of Commerce, Kielce, Poland), Josef Pieprzyk (Department of Computing, Macquarie University, Australia).