Cartman

Cartman

Cartman
Создатель:	Мясников Александр
Создан:	2008 г.
Опубликован:	2008 г.
Размер ключа:	128 x L ≥ 2 бит
Размер блока:	128 бит
Число раундов:	(kw/64)²
Тип:	собственный (модифицированная сеть Фейстеля)

Cartman — в криптографии симметричный блочный криптоалгоритм, опубликованный в 2008 году в виде нескольких модификаций. В исходном варианте алгоритма используется 512-битный ключ и 128-битный (16-байтный) блок. Все операции — подстановки, перестановки, сложения по модулю 2, смещения и деления по модулю выполняются с 32-разрядными числами, что предполагает реализацию алгоритма на 32-разрядных платформах.

Последней редакцией первой версии алгоритма является его модификация 1.2mK с переменной длиной ключа и исправленным механизмом его выборки. Алгоритмы данного семейства основаны на трансформации фиксированного блока длиной 128 бит (16 байт или четыре 32-разрядных числа), длина ключа в последних модификациях алгоритма переменна и кратна 128 битам, то есть 128 x L бит, где рекомендуемое значение L — число от 4 до 16.

Алгоритм

Все модификации имеют структуру сбалансированной сети Фейстеля, однако за один полный раунд взаимозависимо трансформируют все четыре подблока и выполняют их перестановку. В частности, в версиях шифра от 1K и выше в зависимости от генерированной константы выборки операции производится сложение по модулю 2, либо сложение по модулю 2³² двух 32-разрядных элементов второй половины блока с двумя элементами первой половины, трансформированными выбранными элементами ключа. Число раундов зависимо от длины ключа, равняясь (KW/64)², что для 512-битного ключа будет составлять 64.

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

Как и большинство классических симметричных блочных шифров, Cartman имеет схожие процедуры шифрования и расшифрования. Другими словами, процедура восстановления открытого текста является обратной по отношению к шифрованию, выборка ключа производится так же в обратном порядке.

В процессе трансформации открытого текста производится рассеивание, изменение произвольного байта открытого текста приведут к измению всех 16 байт шифротекста, а при использовании механизмов обратной связи — режимов сцепления блоков (к примеру, CBC) затронет весь шифротекст. Именно по этой причине крайне не рекомендуется реализация шифра в режиме простой замены — ECB.

Выполнение операций циклического сдвига (ROR/ROL) накладывает определённые ограничения в скорости работы алгоритмов, что наиболее критично для больших ключей и соответственно большого числа раундов. Скорость выполнения операции шифрования референтной реализацией алгоритма Cartman 1.1mK c 512-битным ключом составляет около 7,5 МБайт/с, с 1024-битным — в среднем 2 МБайт/с на системах с процессором AMD Athlon 64 X2 3600. Шифр с 256-битным ключом будет иметь всего 16-раундов и соответственно высокую скорость выполнения — около 30 МБайт/с.

Шифр Cartman 1.2mK призван устранить недостатки и возможные уязвимости алгоритма в редакции 1.1mK. В частности, изменено ключевое расписание, введена дополнительная трансформация некоторых элементов на основе запросов к четырём таблицам подстановки, изменены константы сдвигов и некоторые операции. Скорость выполнения — около четырёх Мбайт/с с ключом 512 бит.

Cartman II

Существует также альтернативный вариант шифра 1.1mK, имеющий наименование Cartman-II. Данный шифр для дополнительной трансформации блока реализует таблицу подстановок — матрицу 8x8 из 256-ти восьмиразрядных элементов.

На данном этапе каждый из четырёх 32-разрядных элементов блока разбивается на четыре 8-битных элемента, каждый из которых, в свою очередь, заменяется элементом одной из 64-х таблиц замен, выбранной в зависимости для текущих индексов выборки ключа. Использование S-Box на каждом раунде теоретически обеспечивает более высокий уровень рассеивания чем аналогичный шифр без таблиц подстановок и усложняет нахождение зависимостей между открытым и зашифрованным текстом.

Длина ключа данного шифра может составлять 256, 384 или 512 бит, в данных конфигурациях алгоритм имеет 16, 36 и 64 раунда соответственно.

Как развитие данного шифра существует модификация с использованием пермутации, зависимой от данных (DDP) — шифр Cartman-2DDP. Усиленный вариант данного шифра имеет две дополнительные таблицы индексов циклического сдвига, генерированные на основе подключей и именуется Cartman-2DDP1. Его модификация — версия Cartman-2DDP2 имеет дополнительные генерированные на основе ключа индексы выборки константы циклического сдвига для каждого раунда.

Алгоритм в редакции Cartman-2DDP3 для достижения максимального рассеивания и затруднения криптоанализа использует дополнительное расписание таблиц подстановки — две генерируемые на основе ключа таблицы выборки размером в число раундов и используемые для выборки индивидуальной таблицы перестановки для 32-разрядного элемента блока. Созданный на его основе шифр Cartman-2DDP4 при сложении элементов блока использует дополнительную модификацию слагаемого 32-разрядного элемента.

Алгоритм Cartman-2DDP5 использует дополнительную процедуру расширения ключа на основе счётчика и таблицы подстановки.

Модификация данного шифра Cartman-2KW использует 512-битный ключ, 256 бит из которого используются модифицированным Cartman-2DDP3 c 16 полными раундами, вторые 256 бит — механизмом ключевого забеливания, что позволяет в несколько раз увеличить производительность алгоритма — на ПК с процессором AMD Athlon 64 X2 3600 скорость шифрования составляет около 9,8 МБайт/с.

Экспериментальный шифр Cartman-2X реализован на базе алгоритма Cartman-2DDP3 и использует элементы ГПСЧ TrashCart для генерации зависимых от ключа таблиц подстановки.

Уникальным для всего семейства Cartman шифром является вариант алгоритма Cartman-2DDP4 с изменённой структурой раундов. Алгоритм Cartman-2F не имеет фиксированного механизма трансформации блока, поскольку операция трансформации каждого из четырёх 32-разрядных элементов каждого раунда является случайной и зависима только от секретного ключа. Таким образом, для 384-битного ключа (полный размер ключа составит 512 бит, поскольку 128 бит используются для генерации таблицы операций) в 36 полных раундах будут использованы в общей сложности 288 различных операций.

Алгоритм Cartman-2H является вариантом шифра Cartman-2F с расширенным набором возможных операций и изменённой таблицей подстановок.

Блочные шифры Cartman-2L, Cartman-2I и Cartman-2K являются вариантом шифра Cartman-2H с расширенным набором возможных операций и допустимых вариаций функций трансформации элементов блока.

Блочный шифр Cartman-2M основан на несколько других принципах, не использует обратимой таблицы подстановок, применяет ключевое забеливание (сложением по модулю 2³² перед первым раундом и сложением по модулю 2 после последнего), сдвиги унифицированы, выполняются после перестановок. Длина ключа по умолчанию равна 256 бит основного шифра + 128 бит трансформации (384 бит).

Блочный шифр Cartman-2N основан на шифре версии 2.M и имеет несколько изменённое ключевое расписание.

Блочный шифр Cartman-2O основан на шифре версии 2.M и имеет, вероятно, наиболее продуманное ключевое расписание. Дельта, в отличие от редакции 2.N не используется, таблицы подстановки используются для расширения ключа до subkeysize * subkeysize * 4 элементов (для 256-битного ключа 64 32-х разрядных подключа, для 384-битного — 144 подключа). Скорость выполнения при 256-битном ключе составляет в среднем 7 Мбайт/с.

Cartman-2P реализован на базе шифра Cartman-2N, но использует таблицы подстановки для расширения ключа. Ключевое расписание, таким образом, напоминает алгоритм Cartman-2O.

Технология применения зависимых от ключа операций используется также в шифре FROG. Такие принципы основаны на идее, согласно которой операции, характер и последовательность которых не известна криптоаналитику и секретна (зависима от ключа) значительно затрудняет криптоанализ.

Шифры семейства Cartman не патентованы и могут быть использованы без каких-либо лицензионных, патентных и иных ограничений в коммерческих и некоммерческих целях.

GTEA

Алгоритм GTEA (англ. Green TEA) объединяет в себе некоторые идеи шифра TEA и алгоритмов Cartman. Шифр имеет 128 битный блок, использует по умолчанию 512-битный ключ и 32 полных цикла. Один полный цикл включает трансформацию четырёх равных 32-разрядных элементов блока.

Процедура расширения ключа проста — по умолчанию используются 128 таблиц подстановок и 32-разрядный счётчик. Ключ расширяется до 128-ми (R x 4) 32-разрядных подключей. Использование независимых подключей для каждого раунда обосновывает теоретическую устойчивость ко скользящим атакам (англ. slide attack).

Алгоритм имеет довольно высокую скорость — свыше 15 МБайт/с на тестируемом ПК при 32-х полных циклах. При этом, возможно использования ключа длиной от 256 до 4096 бит, что благодаря структуре шифра не сказывается на производительности. Напротив, безопасность шифра теоретически повышается при использовании больших ключей, поскольку на основе последних генерируются подключи раундов. Алгоритм имеет довольно гибкую структуру — возможно использование произвольного числа полных циклов (16 ≤ R ≤ 128) и таблиц подстановки (от 4 до 256).

Структура раунда крайне проста и представляет собой модификацию Сети Фейстеля, хотя лишь частично соответствует ее принципам. Шифр отличает использование таблиц подстановки, операций зависимого от данных циклического сдвига, предварительное и последующее ключевое забеливание.^[1]

Модификации алгоритма

Существует ряд модификаций алгоритма, имеющих отличия в сложности структуры и скоростных характеристиках. Таблицы подстановки используются лишь в редакции Cartman-II и выше.

Устойчивость

На данный момент алгоритм не подвергался детальным исследованиям криптоаналитиков.

Ссылки

• Домашняя страница блочного шифра Cartman
• Исходные тексты алгоритма Cartman 1.2mK на языке C
• Исходные тексты алгоритма Cartman-2DDP5 на языке C
• Исходные тексты алгоритма Cartman-2P на языке C
• Исходные тексты алгоритма GTEA на языке C
• Плагин для Total Commander, реализующий шифры семейства Cartman
• Программа DarkCrypt GUI, реализующая шифры Cartman

Примечания

1. ↑ Описание и анализ алгоритма GTEA