Crab (шифр)

Crab — блочный шифр, разработанный Бартом Калиски и Мэттом Робшоу из лаборатории RSA на первом семинаре FSE в 1993. Crab был разработан, чтобы продемонстрировать, как идеи хеш-функций могут быть использованы для создания быстрого шифрования. Алгоритм шифрования очень похож на MD5.

Crab
Создатель	Барт Калиски и Мэтт Робшоу
Создан	1993 год
Опубликован	1993 год
Размер ключа	80 бит
Размер блока	8192 бит
Тип	Криптографическая хеш-функция

Общие сведения

Crab использует блок из 1024 байтов. Поскольку Crab представлен больше для исследовательских целей, то окончательные алгоритмы генерации ключей не представлены. Авторы предлагают метод, который может превратить 80-битный ключ в три необходимых подключа, хотя алгоритм может легко принимать ключи переменной длины.

Crab использует два набора длинных подключей:

• Перестановка чисел от 0 до 255: $P_{0},P_{1},...,P_{255}$
• Массив длиной 2048, состоящий из 32-битных чисел: $S_{0},S_{1},...,S_{2047}$

Эти подключи должны быть вычислены перед шифрованием и дешифрованием.

Crab был предложен как новая тестовая идея, а не как рабочий алгоритм. Он использует многие из тех же методов, что и MD5. Бихам утверждает, что такой размер блока (1024 байта) упрощает алгоритм криптоанализа. С другой стороны, Crab может эффективно использовать ключи длиной и больше 80 бит. В таком случае «алгоритм криптоанализа не упрощается».

Алгоритм

Для шифрования 1024-байтного блока $X$:

1. Разбить $X$ на 256 32-битных подблока: $X_{0},X_{1},...,X_{255}$
2. Переставить подблоки $X_{i}$ согласно $P_{i}$
3. $for~r=~0~to~3$
   $for~g=~0~to~63$
4. $\qquad A~=X_{(4g)<<<2r}$
5. $\qquad B~=X_{(4g+1)<<<2r}$
6. $\qquad C~=X_{(4g+2)<<<2r}$
7. $\qquad D~=X_{(4g+3)<<<2r}$
8. $\qquad for~s~=~0~to~7$
9.  $\qquad \qquad A~=A\oplus F_{r}(B,C,D,S_{512r+8g+s})$
10. $\qquad \qquad TEMP=D$
11. $\qquad \qquad D=C$
12. $\qquad \qquad C=B$
13. $\qquad \qquad B=A<<<5$
14. $\qquad \qquad A=TEMP$    
15.   $X_{(4g)<<<2r}=A$
16.   $X_{(4g+1)<<<2r}=B$
17.   $X_{(4g+2)<<<2r}=C$
18.   $X_{(4g+3)<<<2r}=D$
19. Переставить $X_{0},X_{1},...,X_{255}$ для формирования зашифрованного текста

$X<<<b$ обозначает левое вращение $X$ на $b$ бит.

Функции $F_{r}$ применяются 8 раз при обработке каждой из 64 независимых групп в каждой итерации, они используют булевы функции $f_{r}$, который зависят от итерации. В остальном $F_{r}$ одинаковы и могут быть представлены следующим образом:

$F_{r}(B,C,D,S)=(B~+~f_{r}(B,C,D)+S)$

Функции $f_{r}$ совпадают с функциями из MD5:

$\operatorname {f_{0}} (B,C,D)=(B\wedge C)\vee (\neg B\wedge D)$,

$\operatorname {f_{1}} (B,C,D)=(B\wedge D)\vee (\neg D\wedge C)$,

$\operatorname {f_{2}} (B,C,D)=B\oplus C\oplus D$,

$\operatorname {f_{3}} (B,C,D)=B\oplus (\neg {C}\vee D)$,

где $\oplus ,\wedge ,\vee ,\neg$ побитовые логические операции XOR, AND, OR и NOT соответственно, все операции по модулю $2^{32}$.

Дешифрование происходит по обратному алгоритму.

Генерация подключей

Генерация подключей — это задача, которая может быть решена различными способами. Начальная перестановка $P$ может быть сгенерирована с использованием ключа $K$ вариациями методов, представленных в Knuth; один вариант того, как массив перестановок $P$ может быть сгенерирован из 80-битного ключа $K$, представлен ниже.

1. Инициализировать $K_{0},K_{1},...,K_{9}$ первыми 10-ю битами $K$
2. $for~i=~10~to~255$
3. $\qquad K_{i}=K_{i-2}\oplus K_{i-6}\oplus K_{i-7}\oplus K_{i-10}$
4. $for~i=~0~to~255,~P_{i}=i$
5. $m=0$
6. $for~j~=~0~to~i$
7.$\qquad for~i=~256~to~1~step~-1$
8.$\qquad \qquad m=(K_{256-i}+K_{257-i})mod~i$
9.$\qquad \qquad K_{257-i}=K_{257-i}<<<3$
10.      Переставить $P_{m}$ и $P_{i-1}$

Массив $S$ из 2048 32-битных слов может быть сгенерирован так же, из того же 80-битного ключа или из другого ключа. Авторы предупреждают, что эти детали должны «рассматриваться как мотивационные; вполне могут быть альтернативные схемы, которые являются более эффективными и предлагают улучшенную безопасность»

Особенности алгоритма

В начале первой итерации слова открытого текста перемещаются в 64 группы из четырёх в псевдослучайном порядке с использованием перестановки $P$. В каждой группе слова обрабатываются таким образом, что все четыре слова в конце итерации зависят от каждого входного слова и некоторой ключевой зависимости. В последующих итерациях мы связываем группы вместе, используя метод, полученный из используемых при расчете дискретного преобразования Фурье методов.

В первой итерации первая группа использует слова $X_{0},X_{1},X_{2}$ и $X_{3}$. Во второй итерации первая группа принимает модифицированные слова $X_{0},X_{4},X_{8}$ и $X_{12}$. Первая группа третьей итерации принимает модифицированные $X_{0},X_{16},X_{32}$ и $X_{48}$, а в последней итерации используется недавно модифицированный $X_{0},X_{64},X_{128}$ и $X_{192}$.

Это обобщено на другие группы, и в конце четвёртой итерации получается полный диффузионный эффект, при котором каждое выходное слово зависит от каждого из 256 текстовых слов ввода. Этот эффект легко достигается за счет использования переменной вращения бит, используемой для индексации перестановочных текстовых слов. Его можно обобщить следующим образом, где $r=0,...,3$ обозначает итератор:

$$A~=X_{(4g)<<<2r},B~=X_{(4g+1)<<<2r},C~=X_{(4g+2)<<<2r},D~=X_{(4g+3)<<<2r}.$$

Четыре итерации являются достаточными и минимально необходимыми в этой конструкции, для обеспечения полного перемешивания 256 слов открытого текста в результирующем зашифрованном тексте. Предварительные эмпирические испытания показывают, что с использованием этой сети с помощью предлагаемых функций получается очень хороший лавинный эффект. Альтернативные подходы включают использование трех итераций с 64 словами открытого текста или двумя итерациями с 16 словами открытого текста, каждый из которых будет предлагать все большее улучшение скорости шифрования. Однако авторы считают, что менее четырёх итераций могут привести к риску в области безопасности.

Оценка эффективности

В программной реализации каждая итерация состоит из обработки 64 групп, где для обработки требуется восемь шагов. Каждый шаг требует от 6 до 8 операций, поэтому реализация может выполняться очень быстро. Индексирование $X_{i}$ легко оптимизируется. Время инициализации перестановок $P$ и слова $X_{i}$ являются фиксированными накладными расходами и зависят от используемых методов. Эти накладные расходы становятся менее значимыми, чем больше сообщение. Возможно, количество ключевых зависимых слов $X_{i}$ может быть уменьшено без ущерба для безопасности, что сократит время, необходимое для предварительного вычисления ключевого зависимого материала.

Каждая итерация фактически представляет собой 64 приложения ${1 \over 2}$ итерации хеширования MD5 (каждая итерация в MD5 имеет 16 шагов). Интересно, что слова буфера в хеш-функции заменяются открытым текстом и его модификациями в блочном шифре, в то время как сообщение в хеш-функции становится ключевым элементом в блочном шифре.

В блочном шифре есть 4 итерации, как в MD5, и поэтому $256\times 32$ бита зашифрованы с использованием эквивалента $64\times {1 \over 2}$ MD5 хэшей из 512 бит. Это дает приблизительную оценку скорости шифрования около 500 Кбайт/с, что вдвое меньше скорости MD5.

Обработка каждой из 64 групп в каждой итерации независима. Это дает прекрасную возможность для распараллеливания алгоритма, что сразу же даст повышение скорости.

Безопасность

Рассмотрим перевернутый 26-й бит (0x04000000) одного из 256 текстовых слов. Этот конкретный бит часто затрагивает только три слова в первой итерации. При следующих трех итерациях число затронутых слов будет увеличиваться в 4 раза, что приведет к $3\times 4\times 4\times 4=192$ затронутым словам, оставив 64 слова нетронутыми. Это происходит с экспериментальной вероятностью в $0.096=2^{-3.4}$. Это немедленно приводит к тому, что для различающей атаки (англ. Distinguishing attacks) нужно не больше дюжины выбранных блоков открытого текста.

Анализ атаки с восстановлением ключа (англ. Key-recovery attack) немного сложнее из-за отрывочного характера описания генерации ключа. Если предположить, что ключ может быть эффективно восстановлен из перестановки $P$, авторы считают, что для атаки с восстановлением ключа не потребуется более $2^{16}$ выбранных блоков открытого текста и пренебрежительных вычислительных усилий.

Ссылки

• Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth), John Wiley & Sons, Inc. Архивная копия от 27 ноября 2020 на Wayback Machine
• Fast Block Cipher Proposal, Burton S. Kaliski Jr. and M.J.B. Robshaw Архивная копия от 17 сентября 2017 на Wayback Machine