Khafre — вторая (вместе с Khufu) из криптосистем, предложенных Ральфом Мерклом (Ralf Merkle). (Khufu (Хуфу) и Khafre (Хафра) — имена египетских фараонов). По конструкции этот алгоритм похож на Khufu, но спроектирован для приложений, не использующих предварительных вычислений. S-блоки не зависят от ключа, вместо этого Khafre использует фиксированные S-блоки. Блок шифрования подвергается операции XOR с ключом не только перед первым этапом и после последнего, но и после каждых 8 этапов шифрования.

Меркл предположил, что с Khafree должны использоваться 64- или 128-битовые ключи, и что для Khafre потребуется больше этапов, чем для Khufu. Это, наряду с тем, что каждый этап Khafre сложнее этапа Khufu, делает Khafre более медленным. Зато для Khafre не нужны никакие предварительные расчёты, что позволяет быстрее шифровать небольшие порции данных.

В 1990 году Бихам и Шамир применили свой метод дифференциального анализа против Khafre. Им удалось взломать 16-этапный Khafre с помощью вскрытия с выбранным открытым текстом после 1500 различных шифрований. На их персональном компьютере это заняло около часа. Преобразование этого вскрытия во вскрытие с известным открытым текстом потребует около 238 шифрований. Khafre с 24 этапами может быть взломан с помощью вскрытия с выбранным открытым текстом за 253 шифрования, а с помощью вскрытия с известным открытым текстом — за 259 шифрований.

История

В 1990 году Меркл предложил два алгоритма — Khufu и Khafre. В основе их проектирования лежали следующие принципы:

1. 56-битовый размер ключа DES слишком мал. Так как стоимость увеличения размера ключа пренебрежимо мала (компьютерная память недорога и доступна), он должен быть увеличен.
2. Интенсивное использование перестановок в DES хотя и удобно для аппаратных реализаций, чрезвычайно затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перестановки табличным образом. Просмотр таблицы может обеспечить те же характеристики «рассеяния», что и собственно перестановки, и может сделать реализацию намного более гибкой.
3. S-блоки DES, всего 64 4-битовых элемента, слишком малы. Теперь, с увеличением памяти, должны увеличиться и S-блоки. Более того, все восемь S-блоков в DES используются одновременно. Хотя это и удобно для аппаратуры, для программной реализации это кажется ненужным ограничением. Должны быть реализованы больший размер S-блоков и последовательное (а не параллельное) их использование.
4. Широко признано, что начальная и заключительная перестановки криптографически бессмысленны, поэтому они должны быть устранены.
5. Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. При данном условии нет смысла усложнять эти вычисления.
6. В отличие от DES, критерии проектирования S-блоков должны быть общедоступны.

К этому перечню Меркл, возможно, теперь добавил бы «устойчивость к дифференциальному и линейному криптоанализу», ведь в то время эти способы вскрытия не были известны.