Шифра Поспешное пудинг ( ГПЦ ) является переменным размером блока блочного шифра разработанный Ричард Шреппел , который был неудачным кандидатом в конкурсе для выбора US Advanced Encryption Standard (AES). Он имеет ряд необычных свойств для блочного шифра: его размер входного блока и длина ключа являются переменными, и он включает дополнительный входной параметр, называемый «приправа», для использования в качестве вторичного, несекретного ключа. Шифр Hasty Pudding был единственным кандидатом на AES, разработанным исключительно криптографами США. [1] [2]
Общий | |
---|---|
Дизайнеров | Ричард Шрёппель |
Впервые опубликовано | Июнь 1998 г. |
Детали шифра | |
Ключевые размеры | Переменная |
Размеры блоков | Переменная |
Шифр Hasty Pudding находится в открытом доступе . [3]
Шифр
Шифр Hasty Pudding состоит из 5 различных суб-шифров: [4]
HPC-Tiny | 0–35 бит |
HPC-Short | 36–64 бит |
HPC-средний | 65-128 бит |
HPC-Long | 129–512 бит |
HPC-расширенный | 513+ бит |
Все алгоритмы шифрования Hasty Pudding внутренне используют 64-битные слова. Шифр предназначен для работы на 64-битных машинах , которые могут легко выполнять простые операции с 64-битными словами.
Ключевое расширение
Шифр Hasty Pudding может принимать ключ из любого количества битов для любого из пяти подшифров. Сам шифр использует таблицу ключей из 16 384 бит (256 64-битных слов). Чтобы получить таблицу ключей из ключа, функция расширения ключа использует следующий алгоритм: [4]
- Первые три слова, KX [0], KX [1], KX [2], устанавливаются на основе констант, субшифра и длины ключа. KX [1] вычисляется с умножением; другие задействованные операции - это сложение и битовый сдвиг.
- Каждое последующее слово KX [ i ] определяется из трех предыдущих слов с помощью эффективной рекурсивной формулы.
- Биты ключа подвергаются операции XOR с битами таблицы ключей, начиная с KX [0], пока не будут использованы все биты ключа. (Для ключей длиннее 8192 бит используется более сложная процедура.)
- Сделано несколько проходов по ключевому столу. Каждый раз к каждому слову ключевой таблицы последовательно применяется «функция перемешивания». Функция перемешивания использует восемь внутренних переменных и использует 14 логических битовых операций, 5 битовых сдвигов и 14 сложений / вычитаний. Каждое использование функции перемешивания изменяет одно слово в ключевой таблице на основе его предыдущего значения, значений некоторых других слов и внутренних переменных функции перемешивания. (По умолчанию - 3 прохода.)
Шифрование и дешифрование
Каждая из подшифр использует свой алгоритм, но между ними есть определенные сходства. Для определения зашифрованного текста используются три входа: открытый текст (в нескольких 64-битных словах плюс один «фрагмент»), специя (восемь 64-битных слов со значением по умолчанию 0) и таблица ключей. Операции внутри шифра состоят из перемешивания , при котором внутренние переменные различными способами комбинируются со значениями из ключевой таблицы и специи через равные промежутки времени. HPC-Short дополнительно использует две фиксированные перестановки, а HPC-Tiny состоит из множества специальных поддиапазонов.
Расшифровка включает в себя отмену шагов шифрования один за другим. Многие операции легко отменяются (например, s 0 = s 0 + s 1 отменяется путем вычисления s 0 = s 0 - s 1). Другие операции сложнее отменить. Некоторые из задействованных идей включают:
- Операция типа x = x ( x >> 17) отменяется двухэтапным процессом: (1) x = x ( x >> 17), за которым следует (2) x = x ( х >> 34).
- Шифр использует зависимый от значения поиск в ключевой таблице. Их можно отменить, поскольку поиск зависит только от последних 8 бит переменной, а когда возникает необходимость найти значение из таблицы ключей при расшифровке, последние 8 бит значения в определенной более ранней точке в вычисления предсказуемы, даже если все эти операции невозможно отменить без значения ключевой таблицы. Например, если поиск k основан на последних 8 битах x , тогда, когда мы хотим отменить такой шаг, как x = x ( k << 8), мы можем найти k , заметив, что последние 8 бит x не изменились этой операцией.
Шифр Hasty Pudding также может использоваться для шифрования значений в диапазоне, которые не переводятся в строки с целым числом бит; например, он может зашифровать число от 0 до N, производя другое число от 0 до N . Это достигается за счет использования наименьшего субшифра, который может обрабатывать ввод как битовой строки, и многократного применения его ко входу как битовой строки, пока результат не окажется в правильном диапазоне. [4]
Представление
Шроппель утверждал, что шифр Hasty Pudding был самым быстрым кандидатом на AES на 64-битной архитектуре; [5] Schroeppel утверждал, что он был в два раза быстрее своего ближайшего конкурента, DFC , и в три раза быстрее, чем другие кандидаты, и что его производительность на 32-битной машине была адекватной. [5] Комментарии других не подтверждают эту точку зрения; например, анализ Шнайера и др. поставил шифр Hasty Pudding на 4-е место (376 циклов) на 64-битной машине, хотя для Rijndael и Twofish производительность была только оценочной. [6] На 32-битном Pentium шифрование Hasty Pudding было оценено Schneier et al. при 1600 тактовых циклах, 10-е место среди 15 кандидатов. [6] Шнайер и др. И Шроеппель отметили, что скорость шифрования будет значительно снижена на 32-битной машине из-за интенсивного использования 64-битных операций, особенно битовых сдвигов. [3] [6]
Настройка ключа шифра Hasty Pudding была оценена как относительно медленная; 120000 циклов на Pentium. [6]
Шифр подвергался критике за его работу на смарт-картах . В частности, в некоторых комментариях указывается на сложность хранения более 2 КБ ОЗУ для ключевой таблицы. [7]
Дальнейшая работа
Результаты атаки на шифр Hasty Pudding относительно немногочисленны. В начале процесса AES Дэвид Вагнер заметил, что относительно большие классы ключей Hasty Pudding эквивалентны в том смысле, что они приводят к одной и той же таблице ключей. [8] Это было расширено на от D'Halluin и др., Который отметил , что для 128-битных ключей, примерно 2 120 клавиши слабые клавиши , каждая из которых 2 30 эквивалентных ключей каждый. [9] В ответ на эту атаку Шроппель изменил алгоритм расширения ключа, включив в него один дополнительный шаг. [4]
Несмотря на относительное отсутствие криптоанализа, шифр Hasty Pudding подвергался критике за его сложную для понимания конструкцию и отсутствие обоснования результатов исследований. [8] [10] Шрёппель предложил бутылку шампанского Dom Pérignon лучшему докладу о прогрессе в шифровании Hasty Pudding. [3] Второй раунд рассмотрения для AES не проводился. [11]
Шифр Hasty Pudding считается первым настраиваемым блочным шифром . [12]
Рекомендации
- ↑ Эли Бихам , Заметка о сравнении кандидатов AES , апрель 1999 г., общественный комментарий к AES.
- ^ Сьюзан Ландау , Безопасность связи для XXI века: расширенный стандарт шифрования , Уведомления AMS, т. 47, номер 4, 2000 г.
- ^ a b c Рич Шроппель и Хилари Орман, Обзор шифра Hasty Pudding , июль 1998 г.
- ^ a b c d Schroeppel, Rich (июнь 1998 г.), Hasty Pudding Cipher Specification (пересмотренное издание мая 1999 г.), заархивировано из оригинала 17 июля 2011 г. , извлечено 10 июня 2009 г.
- ^ a b Rich Schroeppel, The Hasty Pudding Cipher: One Year Later , дата обращения 9.01.2008.
- ^ a b c d Брюс Шнайер , Джон Келси , Дуг Уайтинг , Дэвид Вагнер , Крис Холл и Нильс Фергюсон , Сравнение производительности представлений AES , Вторая конференция кандидатов AES, 1999.
- ^ Emanoil Daneliuc, Общественный комментарий о кандидатах AES , февраль 1999.
- ^ а б Дэвид Вагнер, Эквивалентные ключи для высокопроизводительных вычислений , доклад на 2-й конференции AES, Рим , март 1999 г.
- ^ Карл D'Halluin, Герт Bijnens, Барт Preneel , и Винсент Рэймен , Эквивалентные Ключи КВД , Успехи в криптографии - Труды ASIACRYPT 1999, 1999.
- ^ Оливье Baudron, Генри Гилберт , Луи Granboulan, Helena Handschuh , Антуан Жу , Фонг Нгуен , Фабрис Нойан, Дэвид Pointcheval , Томас Pornin, Гийом Попард, Жак Стерн и Серж Воденей , Отчет о Кандидатов AES , второй AES Conference, март 1999 .
- ^ Джеймс Нечватал, Элейн Баркер, Лоуренс Бэшем, Уильям Берр, Моррис Дворкин, Джеймс Фоти и Эдвард Робак, Отчет о разработке усовершенствованного стандарта шифрования (AES) ,официальный выпуск NIST , 2 октября 2000 г.
- ^ Моисей Лиск, Ривест и Дэвид Вагнер , оттиск и блочные шифры , в Достижения вкриптологии - Труды CRYPTO '02, 2002.
Смотрите также
- Шифрование с сохранением формата