Шифр Хэсти Пудинга
| Общий | |
|---|---|
| Дизайнеры | Ричард Шреппель |
| Впервые опубликовано | июнь 1998 г. |
| Деталь шифрования | |
| Размеры ключей | Переменная |
| Размеры блоков | Переменная |
Шифр Hasty Pudding ( HPC с переменным размером блока, ) — блочный шифр разработанный Ричардом Шреппелем , который был неудачным кандидатом в конкурсе на выбор американского стандарта расширенного шифрования (AES). Он обладает рядом необычных свойств для блочного шифра: размер входного блока и длина ключа являются переменными, а также включает дополнительный входной параметр, называемый «приправой», для использования в качестве вторичного, несекретного ключа. Шифр Hasty Pudding был единственным кандидатом на AES, разработанным исключительно криптографами США. [ 1 ] [ 2 ]
Шифр Hasty Pudding находится в открытом доступе . [ 3 ]
Шифр
[ редактировать ]Шифр Hasty Pudding состоит из 5 различных подшифров: [ 4 ]
| HPC-Tiny | 0–35 бит |
|---|---|
| HPC-короткий | 36–64 бита |
| HPC-Средний | 65-128 бит |
| HPC-длинный | 129–512 бит |
| HPC-расширенный | 513+ бит |
Все алгоритмы шифрования Hasty Pudding внутренне используют 64-битные слова. Шифр предназначен для работы на 64-битных машинах , которые могут легко выполнять простые операции с 64-битными словами.
Ключевое расширение
[ редактировать ]Шифр Хэсти Пудинг может использовать ключ любого числа бит для любого из пяти субшифров. Сам шифр использует ключевую таблицу длиной 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 ⊕ ( 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 ] Шреппель утверждал, что он в два раза быстрее своего ближайшего конкурента, 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 ] Это было развито Д'Халлуином и др., которые отметили, что для 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 г.
- ^ Перейти обратно: а б с Рич Шреппель и Хилари Орман, Обзор быстрого шифра пудинга , июль 1998 г.
- ^ Перейти обратно: а б с д Шреппель, Рич (июнь 1998 г.), Спецификация шифра Hasty Pudding Cipher (пересмотренное издание от мая 1999 г.), заархивировано из оригинала 17 июля 2011 г. , получено 10 июня 2009 г.
- ^ Перейти обратно: а б Рич Шреппель, Поспешный шифр пудинга: год спустя , по состоянию на 01.09.2008 г.
- ^ Перейти обратно: а б с д Брюс Шнайер , Джон Келси , Дуг Уайтинг , Дэвид Вагнер , Крис Холл и Нильс Фергюсон , Сравнение производительности материалов AES , Вторая конференция кандидатов AES, 1999 г.
- ↑ Эманойл Данелюк, Общественное обсуждение кандидатов AES , февраль 1999 г.
- ^ Перейти обратно: а б Дэвид Вагнер, «Эквивалентные ключи для HPC» , доклад на 2-й конференции AES, Рим , март 1999 г.
- ^ Карл Д'Халлуин, Герт Бийненс, Барт Пренил и Винсент Раймен , Эквивалентные ключи HPC , Достижения в криптологии - Труды ASIACRYPT 1999, 1999.
- ↑ Оливье Бодрон, Анри Жильбер , Луи Гранбулан, Хелена Хандшу , Антуан Жу , Фонг Нгуен , Фабрис Нойан, Дэвид Пойнтчеваль , Томас Порнен, Гийом Пупар, Жак Штерн и Серж Водене , Отчет о кандидатах AES , Вторая конференция AES, март 1999 г. .
- ↑ Джеймс Нечватал, Элейн Баркер, Лоуренс Бэшем, Уильям Берр, Моррис Дворкин, Джеймс Фоти и Эдвард Робак, Отчет о разработке расширенного стандарта шифрования (AES) , официальный выпуск NIST , 2 октября 2000 г.
- ^ Моисей Лисков, Рональд Ривест и Дэвид Вагнер , Настраиваемые блочные шифры , в книге «Достижения в криптологии — материалы CRYPTO '02», 2002.
