REDOC
REDOC — симметричный блочный криптоалгоритм, разработанный Майклом Вудом в 1990 году для компании Cryptech и получивший наименование REDOC II. Все операции — подстановки, перестановки, XOR выполняются с байтами что позволяет его эффективно реализовать программно. Алгоритм использует зависимые от ключа и исходного открытого текста наборы таблиц (S-блоков), используя меняющиеся табличные функции. Алгоритм отличает использование масок, т.е. чисел, получаемых из ключевой таблицы. Маски используются для выбора таблиц конкретной функции конкретного раунда. При этом используется как значение маски, так и значение данных[1].
| REDOC II | |
|---|---|
| Создатель | Майкл Вуд |
| Создан | 1990 г. |
| Опубликован | 1990 г. |
| Размер ключа | от 70 до 17 920 бит,эффективный: 70 бит |
| Размер блока | 70 бит |
| Число раундов | 10 |
| Тип | собственный |
| REDOC III | |
|---|---|
| Создатель | Майкл Вуд |
| Размер ключа | Переменный, до 2560 байт (20480 бит) |
| Размер блока | 80 бит |
| Число раундов | 10 |
| Тип | собственный |
Алгоритм
REDOC-II представляет собой десятираундовую криптосистему (но высказано предположение, что 1- или двухраундовая версия является безопасной)[2]. Каждый раунд в оригинальной версии REDOC II предусматривает набор манипуляций с 10 байтовым блоком. Семь битов из каждого байта используются для значений данных, и восьмой бит — бит четности.
Однако, так как используются для шифрования только первые 7 бит из каждого байта, алфавитное пространство для каждого байта от 0 до 127. И все операции выполняются по модулю 128[3].
Длина ключа в оригинальной версии REDOC II составляет 10 байт. Эффективный размер ключа составляет 70 бит. Следует уточнить, что REDOC II может поддерживать длину ключа в диапазоне от 70 до 17 920 бит[3].
Каждый раунд состоит из шести фаз:
- Фаза переменной перестановки,
- Первая фаза переменного ключа XOR,
- Вторая фаза переменного ключа XOR,
- Фаза переменного анклава,
- Первая фаза переменной подстановки,
- Вторая фаза переменной подстановки.
Во время каждой фазы данные обрабатываются с помощью таблиц[4].
Виды таблиц
1) 16 предопределенных подстановочных таблиц, которые используются в фазах переменной подстановки. (Фиксированы)
| Пример таблицы подстановок | |||||||
|---|---|---|---|---|---|---|---|
| Original | = | Sub 0 | Sub 1 | Sub 4 | Sub 10 | Sub 14 | Sub15 |
| Value | |||||||
| 0 | = | 90 | 47 | 25 | 66 | 73 | 0 |
| 1 | = | 46 | 89 | 51 | 13 | 36 | 52 |
| 2 | = | 66 | 87 | 103 | 31 | 107 | 44 |
| 3 | = | 21 | 20 | 116 | 7 | 43 | 83 |
| … | = | ||||||
| 126 | = | 24 | 14 | 105 | 114 | 77 | 6 |
| 127 | = | 122 | 62 | 11 | 63 | 49 | 79 |
2) 128 предопределенных таблиц перестановок, используемые фазами переменной перестановки. (Фиксированы)
| Пример таблицы перестановок | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Original | = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Перестановка 1 | = | 1 | 6 | 7 | 9 | 10 | 2 | 5 | 8 | 3 | 4 |
| Перестановка 2 | = | 10 | 4 | 8 | 3 | 1 | 7 | 2 | 9 | 5 | 6 |
| Перестановка 3 | = | 1 | 6 | 4 | 9 | 8 | 5 | 10 | 2 | 3 | 7 |
| … | = | ||||||||||
| Перестановка 86 | = | 9 | 7 | 2 | 6 | 5 | 8 | 3 | 10 | 1 | 4 |
| Перестановка 87 | = | 5 | 3 | 8 | 1 | 9 | 7 | 10 | 2 | 4 | 6 |
| … | = | ||||||||||
| Перестановка 126 | = | 9 | 8 | 3 | 7 | 1 | 10 | 5 | 6 | 2 | 4 |
| Перестановка 127 | = | 7 | 8 | 5 | 10 | 9 | 3 | 4 | 2 | 1 | 6 |
3) 128 предопределенных таблиц анклава, используемые фазами переменного анклава. (Фиксированы)
| Пример таблицы анклава | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| a | b | c | d | ||||||||||||
| Entry 0: | 5 | 2 | 3 | 3 | 5 | 2 | 5 | 4 | 2 | 5 | 4 | 2 | |||
| 4 | 3 | 1 | 1 | 3 | 5 | 4 | 3 | 1 | 2 | 5 | 1 | ||||
| 2 | 5 | 4 | 2 | 4 | 1 | 1 | 5 | 3 | 1 | 3 | 5 | ||||
| 1 | 4 | 5 | 4 | 1 | 4 | 3 | 2 | 5 | 3 | 2 | 4 | ||||
| 3 | 1 | 2 | 4 | 2 | 3 | 2 | 1 | 4 | 4 | 1 | 3 | ||||
| Entry 1: | 3 | 1 | 2 | 3 | 2 | 5 | 4 | 2 | 1 | 4 | 2 | 3 | |||
| 4 | 3 | 1 | 5 | 1 | 4 | 3 | 4 | 5 | 5 | 3 | 1 | ||||
| 2 | 5 | 4 | 2 | 4 | 3 | 5 | 1 | 4 | 2 | 1 | 5 | ||||
| 5 | 2 | 3 | 4 | 3 | 1 | 1 | 3 | 2 | 3 | 5 | 4 | ||||
| 1 | 4 | 5 | 1 | 5 | 2 | 2 | 5 | 3 | 1 | 4 | 2 | ||||
| … | |||||||||||||||
| Entry 31: | 2 | 4 | 1 | 2 | 4 | 3 | 1 | 5 | 3 | 4 | 1 | 5 | |||
| 3 | 5 | 4 | 4 | 1 | 2 | 2 | 4 | 1 | 3 | 5 | 2 | ||||
| 5 | 1 | 3 | 3 | 5 | 4 | 4 | 3 | 2 | 1 | 4 | 3 | ||||
| 1 | 2 | 5 | 5 | 2 | 1 | 5 | 2 | 4 | 2 | 3 | 4 | ||||
| 4 | 3 | 2 | 1 | 3 | 5 | 3 | 1 | 5 | 5 | 2 | 1 | ||||
4) Кроме того, 128 десятибайтных таблиц ключей и девять таблиц масок вычисляются для каждого ключа с помощью алгоритма обработки ключа. (Вычислимые, создаются при инициализации шифрования)[3][4]
| Пример таблицы ключей | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Ключ 0 | = | 0 | 34 | 5 | 63 | 9 | 73 | 74 | 107 | 109 | 33 |
| Ключ 1 | = | 10 | 62 | 48 | 85 | 32 | 101 | 8 | 0 | 63 | 56 |
| Ключ 2 | = | 26 | 59 | 75 | 97 | 33 | 80 | 8 | 6 | 73 | 26 |
| … | = | ||||||||||
| Ключ 107 | = | 36 | 123 | 45 | 10 | 55 | 59 | 109 | 45 | 98 | 24 |
| … | = | ||||||||||
| Ключ 118 | = | 95 | 25 | 48 | 47 | 1 | 20 | 117 | 55 | 19 | 67 |
| … | = | ||||||||||
| Ключ 126 | = | 62 | 110 | 70 | 27 | 124 | 31 | 119 | 97 | 9 | 2 |
| Ключ 127 | = | 11 | 54 | 25 | 87 | 107 | 73 | 4 | 118 | 62 | 34 |
| Пример таблицы масок | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Маска 1 | = | 48 | 2 | 121 | 18 | 60 | 105 | 33 | 50 | 11 | 60 |
| Маска 2 | = | 26 | 78 | 24 | 72 | 69 | 13 | 77 | 43 | 9 | 99 |
| Маска 3 | = | 64 | 113 | 72 | 61 | 37 | 13 | 49 | 71 | 24 | 60 |
| Маска 4 | = | 104 | 62 | 69 | 87 | 18 | 31 | 102 | 101 | 32 | 125 |
Описание фаз
Фазы переменной перестановки
В каждой фазе переменной перестановки складываются все десять байт данных(по модулю 128), и результат подвергается операции XOR с конкретным байтом из таблицы масок. Полученное значение — это номер таблицы перестановок. Все байты данных заменяются выбранной перестановкой[4].
Фазы переменного ключа XOR
Выбирается байт из данных и соответствующий байт из таблицы масок, между которыми осуществляется операция XOR. Полученное значение — номер таблицы ключей. (Стоит напомнить, что для шифрования используется 7 бит из каждого байта. Поэтому полученный номер таблицы ключей лежит в диапазоне от 0 до 127). Все байты данных, исключая выбранный, подвергаются операции XOR с соответствующими байтами из таблицы ключей с полученным номером.
Такая операция совершается для всех байтов из данных.[4]
Фазы переменной подстановки
Выбирается байт из данных и соответствующий байт из таблицы масок, между которыми осуществляется операция XOR. Полученное значение, взятое по модулю 16 — номер таблицы подстановок. Все байты, за исключением выбранного, заменяются значениями из таблицы подстановок с полученным номером.
Такая операция совершается для всех байтов из данных[4].
Фазы переменного анклава
Предопределенная таблица анклава имеет пять строк и 3 столбца. Каждая запись содержит число от 1 до 5. Существует 2 свойства, которым таблица анклава должна удовлетворять:
- каждый столбец должен быть перестановкой чисел 1—5;
- каждая строка должна содержать 3 различных значения[4].
Связано это с тем, что обработка таблицы происходит построчно и следующим образом: Каждое число в таблице анклава означает позицию байта. Три байта, которые указаны с помощью одной строки таблицы, суммируются (по модулю 128). Байт, указанный в первом столбце, заменяется полученной суммой.[3]
Каждая фаза переменного анклава использует 4 таблицы анклава следующим образом:
- Разделяет блоки на два под-блока по 5 байт каждый. Под-блоки называют левой и правой половинами.
- XOR между двумя байтами из левой половины и двумя байтами из таблицы масок. Получившиеся 2 байта — это указатели двух таблиц анклава.
- Обработка левой половины первой таблицей анклава указанной с помощью полученного байта.
- Обработка полученной левой половины второй таблицей анклава указанной с помощью полученного байта.
- XOR между левой и правой половинами.
- XOR между двумя байтами в полученной правой половине и двумя байтами из таблицы масок. Полученные два байта — указатели двух таблиц анклава.
- Обработка полученной правой половины первой таблицей анклава указанной полученным байтом.
- Обработка полученной правой половины второй таблицей анклава указанной полученным байтом.
- XOR правой и левой половин.
- Конкатенация левой половины с полученным значением предыдущего шага[5].
Алгоритм расширения ключа и генерация масок
В оригинальной версии REDOC-II заполнение таблицы ключей и таблицы масок происходит с помощью ключа K длиной в 70 бит.
Алгоритм заполнения таблицы ключей.
Алгоритм заполнения таблицы ключей выглядит следующим образом:
- Первые пять байт ключа суммируются по модулю 128. Результат - номер таблицы перестановок.
- Оставшиеся пять значений ключа суммируются по модулю 16. Результат - номер таблицы подстановок.
- Исходный ключ подвергается подстановке-перестановке,используя таблицы подстановок-перестановок,номера которых были получены ранее. Результат - обработанный ключ K'.
- Байты ключа K' с третьего по седьмой суммируются по модулю 32. Результат - номер таблицы анклава.
- Ключ K' обрабатывается по Фазе переменного анклава.Результат - ключ Ki.
- Ключ Ki записывается в соответствующую ячейку таблицы ключей (в случае исходного ключа это первая или же нулевая ячейка).
- Алгоритм повторяется для ключа Ki до тех пор,пока таблица ключей не будет заполнена.
Итого формируется 128 подключей.
Алгоритм заполнения таблицы масок.
Алгоритм заполнения таблицы масок выглядит следующий образом:
- Первые байты первых 32-х ключей (K0...K31) суммируются по модулю 128. Результат - первый байт маски M1.
- Второй байт маски M0 - сумма вторых байт первых 32-х ключей по модулю 128. Соответственно,третий байт маски M1 - сумма третьих байт первых 32-х ключей,четвёртый байт - сумма четвертых байт первых 32-х ключей и т.д
- После заполнения маски M1 для следующей маски используются следующие 32 ключа таблицы масок,для которых выполняются точно такие же операции.
Итого формируется 4 маски.
Надежность
Наиболее эффективным способом вскрытия ключа считается грубая сила, для достижения цели потребуется 2160 операций. Практически единственным эффективным криптоанализом было вскрытие одного из раундов алгоритма Томасом Кузиком, но расширить вскрытие на дальнейшие раунды не удалось. С помощью 2300 открытых текстов был проведен криптоанализ одного из раундов Шамиром и Бихамом, после 4 раундов были получены 3 значения маски, однако успехов как таковых это не принесло и на данный момент алгоритм считается криптостойким[1].
REDOC III
Существует также значительно упрощенная версия алгоритма — REDOC III, созданный Майклом Вудом. Используется 80-битный блок, длина ключа переменна, может достигать 20480 битов. Перестановки и подстановки исключены, все операции над блоком и ключом основаны лишь на применении XOR, за счет чего значительно увеличена скорость шифрования в ущерб стойкости к дифференциальному криптоанализу. Основой алгоритма являются генерированные на основе секретного ключа 256 10-байтовых ключей, и полученные на основе XOR 128 10-байтовых ключей два 10-байтовых блока маски. Для успешного восстановления обеих масок алгоритма REDOC III требуется 223 открытых текстов. Этот алгоритм несложен и быстр. На 33 мегагерцовом процессоре 80386 он шифрует данные со скоростью 2.75 Мбит/с[1]. Криптографическая система REDOC II способна шифровать 800 кбит/с при тактовой частоте 20 Мгц.[6]
Алгоритм REDOC II и его упрощенная версия запатентованы в США[1].
Примечания
- Шнайер, Б., 2002, Раздел 13.5.
- M.J.B. Robshaw, 1995, с. 36.
- Cusick, Wood, 1991, p. 547.
- Biham, Shamir, 1992, p. 19.
- Biham, Shamir, 1992, p. 20.
- Cusick, Wood, 1991, p. 546.
Литература
- Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C.. — М.: Триумф, 2002. — 816 с. — ISBN 5-89392-055-4.
- Cusick T. W., Wood M. C. The Redoc II Cryptosystem (англ.) // Advances in Cryptology — CRYPTO ’90: 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes, S. A. Vanstone — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Berlin Heidelberg, 1991. — P. 546—563. — (Lecture Notes in Computer Science; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-38424-3_38
- Biham E., Shamir A. Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer (англ.) // Advances in Cryptology — CRYPTO’91: 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 1991, Proceedings / J. Feigenbaum — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Science+Business Media, 1992. — P. 156—171. — 484 p. — (Lecture Notes in Computer Science; Vol. 576) — ISBN 978-3-540-55188-1 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-46766-1
- M.J.B. Robshaw. Block Ciphers. RSA Laboratories Technical Report TR-601 // 2-е изд. — 1995. — 1 августа.
- Ken Shirriff, Differential Cryptanalysis of REDOC-III, (PS)