Crab — это блочный шифр, разработанный Бартом Калиски и Мэттом Робшоу из лаборатории RSA на первом семинаре FSE в 1993. Crab был разработан, чтобы продемонстрировать, как идеи хеш-функций могут быть использованы для создания быстрого шифрования. Алгоритм шифрования очень похож на MD5.
Общие сведения
Crab использует блок из 1024 байтов. Поскольку Crab представлен больше для исследовательских целей, то окончательные алгоритмы генерации ключей не представлены. Авторы предлагают метод, который может превратить 80-битный ключ в три необходимых подключа, хотя алгоритм может легко принимать ключи переменной длины.
Crab использует два набора длинных подключей:
- Перестановка чисел от 0 до 255: P 0 , P 1 , . . . , P 255 {displaystyle P_{0},P_{1},...,P_{255}}
- Массив длиной 2048, состоящий из 32-битных чисел: S 0 , S 1 , . . . , S 2047 {displaystyle S_{0},S_{1},...,S_{2047}}
Эти подключи должны быть вычислены перед шифрованием и дешифрованием.
Crab был предложен как новая тестовая идея, а не как рабочий алгоритм. Он использует многие из тех же методов, что и MD5. Бихам утверждает, что такой размер блока (1024 байта) упрощает алгоритм криптоанализа. С другой стороны, Crab может эффективно использовать ключи длиной и больше 80 бит. В таком случае «алгоритм криптоанализа не упрощается».
Алгоритм
Для шифрования 1024-байтного блока X X :
1. Разбить X X на 256 32-битных подблока: X 0 , X 1 , . . . , X 255 {displaystyle X_{0},X_{1},...,X_{255}} 2. Переставить подблоки X i X_{i} согласно P i P_{i} 3. f o r r = 0 t o 3 {displaystyle for~r=~0~to~3} f o r g = 0 t o 63 {displaystyle for~g=~0~to~63} 4. A = X ( 4 g ) <<< 2 r {displaystyle qquad A~=X_{(4g)<<<2r}} 5. B = X ( 4 g + 1 ) <<< 2 r {displaystyle qquad B~=X_{(4g+1)<<<2r}} 6. C = X ( 4 g + 2 ) <<< 2 r {displaystyle qquad C~=X_{(4g+2)<<<2r}} 7. D = X ( 4 g + 3 ) <<< 2 r {displaystyle qquad D~=X_{(4g+3)<<<2r}} 8. f o r s = 0 t o 7 {displaystyle qquad for~s~=~0~to~7} 9. A = A ⊕ F r ( B , C , D , S 512 r + 8 g + s ) {displaystyle qquad qquad A~=Aoplus F_{r}(B,C,D,S_{512r+8g+s})} 10. T E M P = D {displaystyle qquad qquad TEMP=D} 11. D = C {displaystyle qquad qquad D=C} 12. C = B {displaystyle qquad qquad C=B} 13. B = A <<< 5 {displaystyle qquad qquad B=A<<<5} 14. A = T E M P {displaystyle qquad qquad A=TEMP} 15. X ( 4 g ) <<< 2 r = A {displaystyle X_{(4g)<<<2r}=A} 16. X ( 4 g + 1 ) <<< 2 r = B {displaystyle X_{(4g+1)<<<2r}=B} 17. X ( 4 g + 2 ) <<< 2 r = C {displaystyle X_{(4g+2)<<<2r}=C} 18. X ( 4 g + 3 ) <<< 2 r = D {displaystyle X_{(4g+3)<<<2r}=D} 19. Переставить X 0 , X 1 , . . . , X 255 {displaystyle X_{0},X_{1},...,X_{255}} для формирования зашифрованного текстаX <<< b {displaystyle X<<<b} обозначает левое вращение X {displaystyle X} на b {displaystyle b} бит.
Функции F r {displaystyle F_{r}} применяются 8 раз при обработке каждой из 64 независимых групп в каждой итерации, они используют булевы функции f r {displaystyle f_{r}} , который зависят от итерации. В остальном F r {displaystyle F_{r}} одинаковы и могут быть представлены следующим образом:
F r ( B , C , D , S ) = ( B + f r ( B , C , D ) + S ) {displaystyle F_{r}(B,C,D,S)=(B~+~f_{r}(B,C,D)+S)}
Функции f r {displaystyle f_{r}} совпадают с функциями из MD5:
f 0 ( B , C , D ) = ( B ∧ C ) ∨ ( ¬ B ∧ D ) {displaystyle operatorname {f_{0}} (B,C,D)=(Bwedge C)vee ( eg Bwedge D)} , f 1 ( B , C , D ) = ( B ∧ D ) ∨ ( ¬ D ∧ C ) {displaystyle operatorname {f_{1}} (B,C,D)=(Bwedge D)vee ( eg Dwedge C)} , f 2 ( B , C , D ) = B ⊕ C ⊕ D {displaystyle operatorname {f_{2}} (B,C,D)=Boplus Coplus D} , f 3 ( B , C , D ) = B ⊕ ( ¬ C ∨ D ) {displaystyle operatorname {f_{3}} (B,C,D)=Boplus ( eg {C}vee D)} , где ⊕ , ∧ , ∨ , ¬ oplus ,wedge ,vee , eg побитовые логические операции XOR, AND, OR и NOT соответственно, все операции по модулю 2 32 {displaystyle 2^{32}} .Дешифрование происходит по обратному алгоритму.
Генерация подключей
Генерация подключей — это задача, которая может быть решена различными способами. Начальная перестановка P P может быть сгенерирована с использованием ключа K K вариациями методов, представленных в Knuth; один вариант того, как массив перестановок P P может быть сгенерирован из 80-битного ключа K K , представлен ниже.
1. Инициализировать K 0 , K 1 , . . . , K 9 {displaystyle K_{0},K_{1},...,K_{9}} первыми 10-ю битами K K 2. f o r i = 10 t o 255 {displaystyle for~i=~10~to~255} 3. K i = K i − 2 ⊕ K i − 6 ⊕ K i − 7 ⊕ K i − 10 {displaystyle qquad K_{i}=K_{i-2}oplus K_{i-6}oplus K_{i-7}oplus K_{i-10}} 4. f o r i = 0 t o 255 , P i = i {displaystyle for~i=~0~to~255,~P_{i}=i} 5. m = 0 m=0 6. f o r j = 0 t o i {displaystyle for~j~=~0~to~i} 7. f o r i = 256 t o 1 s t e p − 1 {displaystyle qquad for~i=~256~to~1~step~-1} 8. m = ( K 256 − i + K 257 − i ) m o d i {displaystyle qquad qquad m=(K_{256-i}+K_{257-i})mod~i} 9. K 257 − i = K 257 − i <<< 3 {displaystyle qquad qquad K_{257-i}=K_{257-i}<<<3} 10. Переставить P m {displaystyle P_{m}} и P i − 1 {displaystyle P_{i-1}}Массив S {displaystyle S} из 2048 32-битных слов может быть сгенерирован так же, из того же 80-битного ключа или из другого ключа. Авторы предупреждают, что эти детали должны «рассматриваться как мотивационные; вполне могут быть альтернативные схемы, которые являются более эффективными и предлагают улучшенную безопасность»
Особенности алгоритма
В начале первой итерации слова открытого текста перемещаются в 64 группы из четырёх в псевдослучайном порядке с использованием перестановки P P . В каждой группе слова обрабатываются таким образом, что все четыре слова в конце итерации зависят от каждого входного слова и некоторой ключевой зависимости. В последующих итерациях мы связываем группы вместе, используя метод, полученный из используемых при расчете дискретного преобразования Фурье методов.
В первой итерации первая группа использует слова X 0 , X 1 , X 2 {displaystyle X_{0},X_{1},X_{2}} и X 3 {displaystyle X_{3}} . Во второй итерации первая группа принимает модифицированные слова X 0 , X 4 , X 8 {displaystyle X_{0},X_{4},X_{8}} и X 12 {displaystyle X_{12}} . Первая группа третьей итерации принимает модифицированные X 0 , X 16 , X 32 {displaystyle X_{0},X_{16},X_{32}} и X 48 {displaystyle X_{48}} , а в последней итерации используется недавно модифицированный X 0 , X 64 , X 128 {displaystyle X_{0},X_{64},X_{128}} и X 192 {displaystyle X_{192}} .
Это обобщено на другие группы, и в конце четвёртой итерации получается полный диффузионный эффект, при котором каждое выходное слово зависит от каждого из 256 текстовых слов ввода. Этот эффект легко достигается за счет использования переменной вращения бит, используемой для индексации перестановочных текстовых слов. Его можно обобщить следующим образом, где r = 0 , . . . , 3 {displaystyle r=0,...,3} обозначает итератор:
A = X ( 4 g ) <<< 2 r , B = X ( 4 g + 1 ) <<< 2 r , C = X ( 4 g + 2 ) <<< 2 r , D = X ( 4 g + 3 ) <<< 2 r . {displaystyle 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 {displaystyle X_{i}} легко оптимизируется. Время инициализации перестановок P P и слова X i {displaystyle X_{i}} являются фиксированными накладными расходами и зависят от используемых методов. Эти накладные расходы становятся менее значимыми, чем больше сообщение. Возможно, количество ключевых зависимых слов X i {displaystyle X_{i}} может быть уменьшено без ущерба для безопасности, что сократит время, необходимое для предварительного вычисления ключевого зависимого материала.
Каждая итерация фактически представляет собой 64 приложения 1 2 {displaystyle {1 over 2}} итерации хеширования MD5 (каждая итерация в MD5 имеет 16 шагов). Интересно, что слова буфера в хеш-функции заменяются открытым текстом и его модификациями в блочном шифре, в то время как сообщение в хеш-функции становится ключевым элементом в блочном шифре.
В блочном шифре есть 4 итерации, как в MD5, и поэтому 256 × 32 {displaystyle 256 imes 32} бита зашифрованы с использованием эквивалента 64 × 1 2 {displaystyle 64 imes {1 over 2}} MD5 хэшей из 512 бит. Это дает приблизительную оценку скорости шифрования около 500 Кбайт/с, что вдвое меньше скорости MD5.
Обработка каждой из 64 групп в каждой итерации независима. Это дает прекрасную возможность для распараллеливания алгоритма, что сразу же даст повышение скорости.
Безопасность
Рассмотрим перевернутый 26-й бит (0x04000000) одного из 256 текстовых слов. Этот конкретный бит часто затрагивает только три слова в первой итерации. При следующих трех итерациях число затронутых слов будет увеличиваться в 4 раза, что приведет к 3 × 4 × 4 × 4 = 192 {displaystyle 3 imes 4 imes 4 imes 4=192} затронутым словам, оставив 64 слова нетронутыми. Это происходит с экспериментальной вероятностью в 0.096 = 2 − 3.4 {displaystyle 0.096=2^{-3.4}} . Это немедленно приводит к тому, что для различающей атаки (англ. Distinguishing attacks) нужно не больше дюжины выбранных блоков открытого текста.
Анализ атаки с восстановлением ключа (англ. Key-recovery attack) немного сложнее из-за отрывочного характера описания генерации ключа. Если предположить, что ключ может быть эффективно восстановлен из перестановки P P , авторы считают, что для атаки с восстановлением ключа не потребуется более 2 16 2^{16} выбранных блоков открытого текста и пренебрежительных вычислительных усилий.