Введение
Блок-шифры
В криптографии Хуфу и Хафре — это два блок-шифра, разработанные Ральфом Мерклем в 1989 году, когда он работал в Исследовательском центре Xerox в Пало-Альто. Вместе с Snefru, криптографической хеш-функцией, эти шифры были названы в честь египетских фараонов Хуфу, Хафре и Снеферу. В рамках добровольной программы Xerox предоставила шифры Хуфу и Хафре в Агентство национальной безопасности США (NSA) до публикации. NSA попросила Xerox не публиковать алгоритмы, ссылаясь на соображения национальной безопасности. Xerox, крупный подрядчик правительства США, выполнила эту просьбу. Однако рецензент передал копию Джону Гилмору, который опубликовал её в новостной группе sci.crypt. По-видимому, это было сделано против воли Меркла. Описание программы было впоследствии опубликовано на конференции CRYPTO 1990 года (Merkle, 1990). Шифры Хуфу и Хафре были запатентованы Xerox; патент был выдан 26 марта 1991 года.
Хуфу
Khufu – это 64-битный блочный шифр, который, в отличие от большинства, использует ключи размером 512 бит; обычно блочные шифры имеют гораздо меньшие ключи, редко превышающие 256 бит. Большая часть ключевого материала используется для построения S-блоков шифра. Из-за значительного времени, необходимого для подготовки ключа, Khufu не очень подходит для ситуаций, в которых обрабатывается множество небольших сообщений. Он лучше подходит для пакетного шифрования больших объемов данных. Khufu – это шифр Фейстеля с 16 раундами по умолчанию (допускаются и другие кратные восьми, от 8 до 64). Каждый набор из восьми раундов называется октетом; в каждом октете используется свой S-блок. В каждом раунде наименее значимый байт половины блока передается в S-блок размером 8×32 бита. Выходные данные S-блока затем объединяются (с использованием XOR) с другой 32-битной половиной. Левая половина циклически сдвигается, чтобы новый байт занял нужную позицию, после чего половины меняются местами. В начале и конце алгоритма дополнительный ключевой материал складывается по XOR с блоком (отбеливание ключа). Помимо этого, весь ключ содержится в S-блоках. Существует дифференциальная атака на 16 раундов Khufu, которая позволяет восстановить секретный ключ. Для этого требуется 243 выбранных открытых текста и имеет временную сложность 243 (Gilbert и Chauvaud, 1994). Для простого различения шифра от случайного требуется 232 открытых текста и соответствующая сложность. Бумеранговая атака (Wagner, 1999) может быть использована в адаптивном сценарии «выбранный открытый текст / выбранный шифротекст» с 218 запросами и аналогичной временной сложностью. Khufu также уязвим для атаки на основе невозможных дифференциалов, которая может взломать до 18 раундов шифра (Biham и др., 1999). Schneier и Kelsey (1996) классифицируют Khafre и Khufu как «даже неполные, неоднородные, целевые, тяжелые, несбалансированные сети Фейстеля».
Хафре
Khafre похож на Khufu, но использует стандартный набор S-блоков и не вычисляет их на основе ключа. (Вместо этого они генерируются из RAND-таблиц, используемых как источник "случайных" чисел). Преимущество заключается в том, что Khafre может очень быстро шифровать небольшие объемы данных — он обладает хорошей скоростью смены ключей. Однако Khafre, вероятно, требует большего числа раундов для достижения сопоставимого уровня безопасности с Khufu, что замедляет его при шифровании больших объемов данных. Khafre использует ключ, размер которого кратен 64 битам. Поскольку S-блоки не зависят от ключа, Khafre выполняет операцию XOR с подключами каждые восемь раундов. Дифференциальный криптоанализ эффективен против Khafre: 16 раундов можно взломать, используя 1500 выбранных открытых текстов или 238 известных открытых текстов. Аналогично, 24 раунда можно атаковать, используя 253 выбранных открытых текста или 259 известных открытых текстов.