Crab (шифр)

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

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

Общие сведения[править | править код]

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

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

  • Перестановка чисел от 0 до 255:
  • Массив длиной 2048, состоящий из 32-битных чисел:

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

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

Алгоритм[править | править код]

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

1. Разбить  на 256 32-битных подблока: 
2. Переставить подблоки  согласно 
3. 
   
4. 
5. 
6. 
7. 
8. 
9.  
10. 
11. 
12. 
13. 
14.     
15.   
16.   
17.   
18.   
19. Переставить  для формирования зашифрованного текста

обозначает левое вращение на бит.

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

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

,
,
,
,
где побитовые логические операции XOR, AND, OR и NOT соответственно, все операции по модулю .

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

Генерация подключей[править | править код]

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

1. Инициализировать  первыми 10-ю битами 
2. 
3. 
4. 
5. 
6. 
7.
8.
9.
10.      Переставить  и 

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

Особенности алгоритма[2][править | править код]

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

В первой итерации первая группа использует слова и . Во второй итерации первая группа принимает модифицированные слова и . Первая группа третьей итерации принимает модифицированные и , а в последней итерации используется недавно модифицированный и .

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

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

Оценка эффективности[править | править код]

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

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

В блочном шифре есть 4 итерации, как в MD5, и поэтому бита зашифрованы с использованием эквивалента MD5 хэшей из 512 бит. Это дает приблизительную оценку скорости шифрования около 500 Кбайт/с, что вдвое меньше скорости MD5.

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

Безопасность[4][править | править код]

Рассмотрим перевернутый 26-й бит (0x04000000) одного из 256 текстовых слов. Этот конкретный бит часто затрагивает только три слова в первой итерации. При следующих трех итерациях число затронутых слов будет увеличиваться в 4 раза, что приведет к затронутым словам, оставив 64 слова нетронутыми. Это происходит с экспериментальной вероятностью в . Это немедленно приводит к тому, что для различающей атаки (англ. Distinguishing attacks) нужно не больше дюжины выбранных блоков открытого текста.

Анализ атаки с восстановлением ключа (англ. Key-recovery attack) немного сложнее из-за отрывочного характера описания генерации ключа. Если предположить, что ключ может быть эффективно восстановлен из перестановки , авторы считают[4], что для атаки с восстановлением ключа не потребуется более выбранных блоков открытого текста и пренебрежительных вычислительных усилий.

Примечания[править | править код]

  1. 1 2 3 4 5 Bruce Schneier. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth). — John Wiley & Sons, Inc..
  2. 1 2 3 4 Burton S. Kaliski Jr. and M.J.B. Robshaw. Fast Block Cipher Proposal // RSA Laboratories.
  3. D.E. Knuth. The Art of Computer Programming.. — Volume 2, 2nd edition. — Addison-Wesley, Reading, Mass., 1981.
  4. 1 2 Markku-Juhani O. Saarinen. Cryptanalysis of Block Ciphers Based on SHA-1 and MD5 // Helsinki University of Technology Laboratory for Theoretical Computer Science P.O. Box 5400, FIN-02015 HUT, Finland.

Ссылки[править | править код]