М. Е. Масленников - MCSSHA. Семейство алгоритмов хеширования

MCSSHA
Семейство алгоритмов
хеширования
Основано на использовании
неавтономного регулярного регистра
сдвига над Z/256

Автор: Масленников М.Е., начальник отдела разработки
ПО предприятия НТЦ «Система»
Последнее обновление: 20 марта 2014 г.

ВВЕДЕНИЕ
• Любой алгоритм хеширования из семейства MCSSHA является
итерактивной однонаправленной
хеш-функцией,
результатом
выполнения которой является дайджест произвольного сообщения,
состоящего из набора байт. Хеш функция позволяет проверять
целостность сообщения, поскольку любое изменение в сообщении
приводит к изменению его дайджеста, причем с очень высокой
вероятностью два различных сообщения будут иметь различные
дайджесты, отличающиеся друг от друга как случайные и
равновероятные величины. Это свойство позволяет использовать хешфункцию в системах электронной подписи, в системах выработки и
проверки различных идентификационных кодов, для выработки
случайных чисел и в других подобных задачах.

КРИПТОГРАФИЧЕСКАЯ СХЕМА
•

Криптосхема MCSSHA, основанная на неавтономном регулярном регистре
сдвига (SR) над Z/256, приведена ниже.

где N – длина регистра (в байтах);
π – подстановка из симметрической группы S256;
x1, x2, … xL – входная последовательность в байтах, т.е. из Z/256.
Элементами SR являются байты, т.е. элементы из Z/256,
Состоянием SR (SR state) является вектор (yi,yi+1,…,yi+N-1), в котором любая координата yi,yi+1, …, yi+N-1 является
байтом, т.е. элементом из Z/256.
Если (yi,yi+1, …, yi+N-1) - SR state перед i-ым шагом, то после i-го шага SR state будет
(yi+1,yi+2, …, yi+N ),
где

yi+N = π(yi – yi+1 – yi+N-4 + yi+N-1) + xi

История разработки MCSSHA
•

•

Первый алгоритм из семейства MCSSHA – MCSSHA-3 был разработан в 2008
году для проводимого американским NIST международного открытого
конкурса SHA-3. В ходе этого конкурса независимыми экспертами JeanPhilippe Aumasson (Швейцария) и Mar´ıa Naya-Plasencia (Франция) были
найдены некоторые несоответствия MCSSHA-3 требованиям, предъявляемым
NIST. Автором были проанализированы причины этих несоответствий и
предложена модернизация алгоритма MCSSHA-3 – алгоритм MCSSHA-4. Через
некоторое время те же эксперты нашли уже в MCSSHA-4 отклонение от
требований NIST, и автором были предложены две модернизации: MCSSHA-5
и MCSSHA-6.
Во всех методах, применяемых экспертами при атаках на хеш-функции
семейства MCSSHA, использовался в том или ином виде «парадокс дней
рождения», требующий значительного объема памяти. Вопрос о реальном
нахождении возможных коллизий не рассматривался.

История разработки MCSSHA
• Алгоритмы хеширования MCSSHA-7 и MCSSHA-8 были разработаны в
2013 и в 2014 гг. после завершения конкурса на создание нового
стандарта хеширования SHA-3. Был учтен опыт предыдущих ошибок,
допущенных в MCSSHA-3 – MCSSHA-6 и, при сохранении высокой
скорости работы и простоты реализации, найдены кардинальные
методы защиты от атак, которым они подвергались при проведении
криптоанализа независимыми международными экспертами.
• При построении и анализе алгоритмов хеширования MCSSHA-7 и 8
автор руководствовался теми же требованиями NIST, которые
предъявлялись для участников конкурса SHA-3 за одним важным
исключением: в MCSSHA-7 и 8 нет требования ограничиться
значениями длины дайджеста в 224, 256, 384 или 512 бит, т.е. 28, 32,
48 или 64 байта соответственно. Принцип построения MCSSHA-7 и 8
позволяет вычислять дайджест для любого целого значения длины в
байтах от 4 до 64.

Этапы MCSSHA
• Работа любого алгоритма типа MCSSHA осуществляется в три
этапа: preprocessing, pre-hash computation и final hash
computation. На каждом этапе изменяются состояния SR.
Длины SR на различных этапах также могут быть различными.
Preprocessing: устанавливается начальное состояние SR, не
зависящее от хешируемого сообщения.
The pre-hash computation: выработка pre-final SR-state из
начального SR state и хешируемого сообщения.
The final hash computation: выработка окончательной хешфункции - message digest – из pre-final SR-state. Байты
хешируемого сообщения на вход не подаются

Параметры регистра сдвига
• Пусть N – длина SR в байтах. Параметрами SR являются:
– Состояние SR - N байт: (y0,y1, …,yN-1) ;
– Точки съема SR – 4 значения от 0 до N-1: (p1,p2,p3,p4) ;
– Подстановка SR – группа из 256 байт в которой все величины
различные. Взаимно-однозначное преобразование π для байт
0,1,…,255 будем обозначать π(y) – замена байта y по подстановке
π.
– Состояние и точки съема SR меняются при каждом шаге работы
алгоритма. Подстановка π остается неизменной.

Шаг --">