MCSSHA. Семейство алгоритмов хеширования [М. Е. Масленников] (pdf) читать постранично

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 меняются при каждом шаге работы
алгоритма. Подстановка π остается неизменной.

Шаг регистра сдвига
•

Шаг регистра сдвига (SR step) – это преобразование состояния регистра (SR
state) и точек съема (SR points) за один шаг работы.
Пусть:
Y=(y0,y1, …,yN-1) – SR state перед шагом;
P=(p1,p2,p3,p4) – SR points перед шагом
p – изменяемая позиция: p= (p4+1)(mod N);
x – входной байт для шага.
Тогда SR state F1(Y,P,x) и SR points F2(P) после шага будут следующими:
F1(Y,P,x) = (y0,y1, …,yp-1,z,yp+1,...,yN-1)
F1(Y,P,x) = (z,y1,y2, …,yN-1)
F1(Y,P,x) = (y0,y1, …,yN-2,z)

0 < p < N-1
p=0
p = N-1

где
z = π(yp1 – yp2 – yp3 + yp4) + x
F2(P) = ((p1+1)(mod N), (p2+1)(mod N), (p3+1)(mod N), (p4+1)(mod N))

Логарифмическая подстановка π
•

Для