Блочные шифры семейства Cartman Cartman - симметричный блочный криптоалгоритм. Симметричные шифры — шифры, в которых для зашифрования и расшифрования применяется один и тот же криптографический ключ. Блочный алгоритм обрабатывает информацию блоками определённой длины (в данном случае 128 бит), применяя к блоку ключ в установленном порядке, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект - нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.
Алгоритмы имеют очень простую, прозрачную структуру, вся трансформация основана на операциях сложения, вычитания, сложения по модулю 2, сдвигов и циклических сдвигов. Последней версией алгоритма является модификация 1.2mK с масштабируемой длиной и улучшенной выборкой ключа. Все модификации алгоритма трансформируют блок длиной 128 бит (16 байт), длина ключа в последних модификациях переменна, кратна 128 битам, т.е. 128 x L бит, где рекомендуемое значение L = [4..16]
Семейство шифров Cartman не следует принципам сети Фейстеля, за один раунд взаимосвязанно трансформируя четыре 32-битных составляющих блока и выполняя их перестановку. При этом, в зависимости от константы выборки операции выполняется либо сложение по модулю 2, либо сложение элементов второй половины блока с элементами первой с учетом выбранных элементов ключа
Число раундов зависимо от длины ключа и равно (kw/64)², что для 512-битного ключа составляет 64.
Для устранения линейной уязвимости формируются зависимые от ключа таблицы выборки для каждого из раундов и субраундов, таблицы циклических сдвигов и константы выборки операции. Наличие операций циклического сдвига накладывает определенные ограничения в скорости работы алгоритмов, что наиболее критично для больших ключей и сравнительно большого числа раундов соответственно.
Оценочная скорость выполнения неоптимизированной реализации шифра Cartman 1.1mK с 1024-битным ключом на ПК с процессором AMD Athlon 64 X2 3600 - свыше 2 Мб/с. Вариант с 512-битным ключом имеет оценочную скорость около 7.5 МБайт/с, с 256-битным - примерно 30 МБайт/с.

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

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

В качестве примера использования шифра для реализации генератора псевдослучайных чисел предоставлен ГПСЧ TrashCart. Данный генератор имеет размер внутреннего состояния 128 бит, поэтому, длина цикла ГПСЧ составляет около 2⁶⁴.
Для инициализации ГПСЧ TrashCart используется входной битовый блок размером, равным сумме длины ключа шифра Cartman и длины вектор инициализации шифра, т.е. kw + 128. Как правило, можно использовать процедуру расширения ключа, предложенную в качестве примера и инициализующую шифр 32-разрядным значением seed.

Генератор псевдослучайных чисел TrashCart проходит тесты Diehard, результат которых варьируется в зависимости от метода инициализации. Теоритически, оптимальным будет использование TrashCart с блоком инициализации, полученным как выход хэш-функции. Как и блочный шифр, ГПСЧ имеет лимит на размеры ключа - от 256 до 2048 бит. Минимальный лимит основан на структурных особенностях дизайна, максимальный - на фактическом достижении точки неэффективности. TrashCart версии II основан на использовании альтернативной версии шифра Cartman с использованием таблиц подстановки (S-Box) и поддерживает инициализацию ключом 256, 384 или 512 бит.

Как простейший пример создания хэш фунции на основе блочного шифра Cartman на данной странице размещен образец реализации хэш-функции HashCart-128. Данный алгоритм реализует блочный шифр в режиме CBC, хэш имеет внутреннее состояние размером 128 бит, дополнительно используются пять фиксированных 256-байтных таблиц замен. На выходе хэш-функции генерируется дайджест длиной 128-бит. До 128-битного состояния блок длиной менее 16 байт расширяется с использованием фиксированных 32-разрядных констант. Аналогична и процедура расширения ключа. Данная функция являет собой не более чем пример одного из режимов работы шифра, выполняя свою главную задачу - изменение одного из битов входного блока приведет к изменению всего дайджеста, что позволит проконтроливать, к примеру, целостность хэшированных данных. Как и ГПСЧ, хэш-функция HashCart имеет ряд редакций - на базе шифра Cartman 1.1mK, шифра Cartman-II и выше.

Отдельно следует упомянуть альтернативную разработку на базе блочного шифра Cartman 1.1mK - вариант с использованием таблиц замен. Шифр, названный Cartman-II реализует матрицу из 8x8 256-байтных SBOX с выборкой, зависимой от индексов выборки ключа. Длина ключа шифра лежит в диапазоне 256-512 бит. Развитием шифра Cartman-II является шифр Cartman-2DDP, усиленный вариант с использованием технологии DDP - пермутации, зависимой от данных. Усиленный вариант шифра Cartman-2DDP именуется Cartman-2DDP1 и применяет две дополнительные таблицы циклического сдвига для наиболее эффективного рассеивания. Модифицированный вариант данного шифра с дополнительными индексами выборки констант циклического сдвига именуется Cartman-2DDP2. На основе шифра Cartman-2DDP2 разработана модификация с дополнительным зависимым от ключа расписанием таблиц подстановки для каждого раунда - блочный шифр Cartman-2DDP3. Шифр Cartman-2DDP4 для дополнительной безопасности при сложении элементов блока использует дополнительную модификацию слагаемого 32-разрядного элемента. Алгоритм Cartman-2DDP5 использует дополнительную процедуру расширения ключа на основе счетчика и таблицы подстановки.

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

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

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

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

Блочный шифр 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 подключа). Скорость выполнения данного шифра около 7 МБайт/с при 256 битном ключе.

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

Блочные шифры семейства GTEA

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

Алгоритм KAIRAKAN является вариацией на тему классического Skipjack с 256-битным ключом, 128 битным блоком и увеличенной таблицей подстановки.

Блочный шифр VEMOKWANA объединяет в себе идеи GTEA и элементы IDEA в части умножения по модулю 2³²-1. Допустимые длины ключа - от 256 до 4096 бит, число раундов и размер таблицы подстановки - переменные.

Блочные шифры на основе хэш-функций

Алгоритм KINEBICK основан на использовании элементов обратимой раундовой функции хэш-алгоритмов MD4 и RipeMD-128. Функция расширения ключа комплексная, использует таблицы подстановки, счетчик, зависимую от данных перестановку.

Алгоритм SONJITEGE основан является модификацией алгоритма KINEBICK с более комплексной структурой.

Алгоритм WABASSO основан на 160 раундах функции преобразования хэш-алгоритма RipeMD-160. Функция расширения ключа комплексная, использует таблицы подстановки, счетчик, зависимую от данных перестановку.

Алгоритм Maskenoza основан на 80 раундах функции преобразования корейского хэш-алгоритма HAS-160. Функция расширения ключа комплексная, использует таблицы подстановки, счетчик, зависимую от данных перестановку.

Алгоритм Webino основан на использовании элементов обратимой раундовой функции хэш-алгоритма MD5. Функция расширения ключа комплексная, использует таблицы подстановки, счетчик, зависимую от данных перестановку.

Алгоритм Shebamik основан на реализации 80 раундов обратимой функции хэш-алгоритма SHA1. Функция расширения ключа комплексная, использует таблицы подстановки, счетчик, зависимую от данных перестановку. Схож с алгоритмом SHACAL1, однако имеет более сложную структуру и более комплексное ключевое расписание. Имеет очень хорошие скоростные характеристики.

Алгоритм Daginda основан на реализации 64 раундов функции преобразования хэш-алгоритма SHA2-256. Функция расширения ключа комплексная, использует таблицы подстановки, счетчик, зависимую от данных перестановку. Как и Shebamik, cхож с алгоритмом SHACAL, второй версии, однако имеет более сложную структуру и более комплексное ключевое расписание.

Эксперементальные блочные шифры

Шифр LameCrypt создан в качестве примера плагина для моей криптосистемы DarkCrypt. Алгоритм LameCrypt содержит процедуру расширения ключа, родственную шифру Skipjack, однако более сложную, использующую несколько подэтапов, включая 32-разрядную таблицу замен и подстановку, схожую с аналогичной у отечественного шифра по ГОСТ 28147-89. В результате 512-битный ключ расширяется до 32-х таблиц из 256-ти 32-разрядных элементов. Причем половина ключа, а именно 256 первых бит, применяется непосредственно для генерации подключей, а второя половина - для их трансформации с подстановкой. Процедура шифрования схожа с таковой у TEA, содержит 32 полных цикла. Применяется зависимая от данных выборка ключа.

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

Шифр Simplicity - довольно необычная разработка. Хотя, в процедуре расширения ключа можно найти что-то общее с шифрами Cobra и Blowfish. На основе ключевого материала генерируются 3584 раундовых подключа и таблица выборки длиной 256 x kb, где kb - длина ключа в байтах. Ключевое расписание включает предварительное прешифрование раундовых ключей процедурой зашифрования. Шифрование Simplicity представляет технологию зависимых от данных перестановок, однако здесь имеет место более сложная структура - выборка подключа для подблока осуществляется как в зависимости от ключа, так и в зависимости от всех подблоков. Для препятствования криптоанализу используется технология ключевого забеливания.

Поточные шифры и ГПСЧ

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

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

Шифр по некоторым элементам своей структуры несколько схож с RC4 и VMPC, поскольку в его основе - перестановки и необратимые функции.

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

По-сути используются два взаимотрансформирующих внутренних состояния, каждое длиной 2048 бит.

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

Алгоритм предусматривает использование второго ключевого значения - вектора инициализации длиной до 512 бит. Если вектор инициализации не используется, для генерации MG применяется фиксированная таблица MGBOX, которая может быть как открытым, так и секретным элементом алгоритма. Выполняется зависимая от основного ключа, а точнее - от трансформированных ключом блоков внутреннего состояния, перестановка блока MG. В противном случае выполняется дополнительный цикл ключевого расписания с инициализацией внутренного состояния ключом IV. Режим усиленной (параноидальной) функции ключевого расписания предусматривает дополнительный цикл ключевого расписания после трансформации внутренних состояний ключом IV.

Для усиления алгоритма возможно применение вариации AMPRNG-DROP [N] с генерацией первых N байт потока без их вывода на выход генератора. Оптимальным значением N будет 768.

В качестве альтернативы использования ключа KEY и вектора инициализации IV возможно применение ключевого расписания с расширением ключа длиной SL - строки до бинарного ключа длиной KL. В таком режиме пользовательский ключ длиной SL расширяется до бинарного ключа длиной 512 бит и подается на вход типовой функции ключевого расписания, которая генерирует бинарный ключ длиной KL. При этом первые 768 байт ключевого потока отбрасываются.

Поскольку ГПСЧ является прежде всего генератором псевдо-случайных бит, сфера его применения гораздо шире потокового шифрования. AMPRG может использоваться для замены стандартных функций генерации случайных чисел, может использоваться для генерации случайных паролей, бинарных ключей, внедряться в качестве генератора случайных событий в игровых, прикладных и научных приложениях, где важен большой запас выдываемых значений до т.н. зацикливания ГСЧ и высокая энтропия, максимально близкая к абсолютной величине, равной 8 бит на байт.

Математическим обоснованием качества ГСЧ является его статистическая характеристика.

Генератор псевдослучаных чисел AMPRNG тестировался в качестве генератора потока длиной 2013265920 байт и показал энтропию, равную 8.000000 бит на байт (Arithmetic mean value = 127.4989, Monte Carlo value for Pi = 3.141617429, Serial correlation coefficient = 0.000023, Сhi square distribution = 262.65, базовый набор 15-ти тестов DieHard пройден без недопустимых значений, в пределах нормы)

Каких либо специальных исследований алгоритма не проводилось, на момент написания заметки ГПСЧ не был проанализирован криптосообществом.

Хэш-функции на основе блочных шифров

HashCart-XT - безопасная хэш-функция на основе блочного шифра XTEA-3.Сжимающая функция данного алгоритма основана на функции зашифрования симметричного блочного шифра с ключом 256-бит и блоком 128.

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

Практически все хэш-функции, основанные на блочных шифрах, спроектированы по обобщенной схеме симметричного блочного алгоритма шифрования, типовой схеме безопасного хэширования. Одной из схем является передача в качестве ключа выхода шифратора на предшествующем шаге (H i-1), в качестве блока для зашифрования (M i) - текущего входного блока. На выходе получаем значение H i.

Похожая, но принципиально иная схема используется в HashCart-XT. Прежде всего, размер ключа и размер блока не идентичны. Ключ (длиной 256 бит) в данном случае разбит на два 128-битных подключа, первая половина которого является H i-1, вторая - содержит трансформированное значение счетчиков и контрольных сумм. В данном режиме результат преобразования (сжатия) входного блока зависим от его положения в очереди хэширования, от прошлого входного блока до его сжатия и от истории хэширования.

В каждой функции сжатия используется в качестве подключа 32-битный номер текущего блока, число оставшихся блоков, сумма элементов предшествующего входного блока, контрольная сумма всех предшествующих трансформированных блоков. Данный подключ трансформируется функцией зашифрования с использованием в качестве ключа либо фиксированных значений (и длины сообщения в байтах), либо ключа, заданного пользователем. Первая половина ключа на следующем этапе заменяется трансформированным входным блоком, вторая половина заменяется новой. Поскольку в данной схеме ключ блочного шифра отбрасывается (известны лишь некоторые биты - счетчики ключевого материала второго подключа до его зашифрования), функция сжатия не обратима.

Алгоритм может быть использован совместно с любом блочным шифром с ключом 256 бит и блоком 128 бит. Возможно использование шифров Cartman и GTEA, однаком ввиду сложных процедур инициализации (ключевого расписания), скорость работы алгоритма будет невысокой. Это будет положительным моментом при хэшировании небольших строк и получения хэш-значения паролей, однако препятствует использованию для подсчета хэшей большого объема информации.