MASH-1

MASH-1 (Modular Arithmetic Secure Hash)— этохеш-функция,используемая в криптографии, основанная намодульной арифметике.Главные преимущества этой функции - возможность повторного использования существующего программного или аппаратного обеспечения и масштабируемость. Из недостатков: не очень высокая скорость, обусловленная скоростьюRSA-шифрования, которая на 2-3 порядка ниже скорости блочно-симметричных шифров, и история неудачных предложений функций, основанных на модульной арифметике.

История

MASH-1 и MASH-2 после долгой проработки и множества неудачных предложений вошли в стандарт ISO/IEC 10118-4 [1] в 1998 году. К данному моменту нет опубликованных результатов проблем в безопасности этих хеш-функций.

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

Описание алгоритма

MASH-1 предполагает использование модуля M, аналогичного модулю из RSA. Битовая длина M оказывает прямое влияние на безопасность. M должно быть сложно факторизовать и безопасность держится на сложности выделения корней по модулю. Также битовая длина M определяет размер блока обрабатываемых данных и размер хеш-результата.

На вход алгоритма получаем x битовой длины$0\leq b<2^{n/2}$.На выходе хотим получить n битный хеш x (n почти той же битовой длины, что и M).

1)$M=pq$m = битовая длина M, p и q - засекреченные простые числа, выбранные так, чтобы факторизация M была трудной. Пусть битовая длина n будет наибольшим множителем 16, меньшим чем m (т.е.$n=16n'<m$).$H_{0}=0$определим как IV и n-битная целочисленная константа A = 0xf0...0. "$\vee$"- обозначение дляпобитового ИЛИ,$\oplus$- обозначение дляпобитового исключающего ИЛИ.

2)Разбиваем сообщения с помощьюструктуры Меркла — Дамгора.Заполняем x 0-битами, если это необходимо чтобы получить строку битовой длины$t*n/2$для наименьшего возможного$t\geq 1$.Поделим дополненный текст на блоки по$n/2$бита -$x_{1},x_{2},...x_{t}$и добавим последний блок$x_{t+1}$,в котором лежит b, выраженная$n/2$битами.

3)Расширим каждый$x_{i}$до n-битного блока$y_{i}$.Для этого поделим его в 4 битные полубайты и вставим 4 бита один за другим, за исключением$y_{t+1}$,где вставленный полубайт 1010, а не 1111

4)Теперь обработаем функцию сжатия. Для$1\leq i\leq t+1$,сопоставим 2 n-битных входа ($H_{i-1},y_{i}$) одному n-битному входу следующим образом:

$H_{i}\gets ((((H_{i-1}\oplus y_{i})\vee A)^{2}modM)\dashv n)\oplus H_{i-1}$

Здесь "$\dashv$"обозначает сохранение правых n бит m-битного результата слева от него.

5) Нужный нам хеш лежит в n-битном блоке$H_{t+1}$

Пример кода

Пример реализации алгоритма наJavaс использованием класса BigInteger для работы сдлинной арифметикой:

privatefinalBigIntegercompress(BigIntegerX,BigIntegerH){
BigIntegerXX=BigInteger.value0f(0);
BigIntegerrem;
for(intj=k-4;j>=0;j-=4){
XX=XX.shiftLeft(4).or(FEFTEEN);
rem=block.shiftRight(j).mod(SIXSTEEN);
XX=XX.shiftLeft(4).or(rem);
}
returnH.xor(XX).or(E).pow(2).mod(N).mod(TWO_POW_N).xor(H);
}

Чтобы сделать этот код более эффективным можно добавить следующие оптимизации:

• Работать с векторами фиксированной длины
• Работать с беззнаковыми числами
• Модульное возведение в степень только для степень 2 или 257(в случае MASH-2)
• Модульное вычитание только для чётных модулей

MASH-2

MASH-2 отличается от MASH-1 только другим значением экспоненты. В MASH-1 используется$e=2$,в то время как в MASH-2 используется$e=2^{8}+1$.

• Пример сравнения MASH-1 и MASH-2:

Результаты сравнительного анализа

Хеш-функция	Применяемые преобразования	Скорость обработки данных	Модель безопасности
MASH-1	Модулярное возведение в квадрат	$10^{5}..10^{6}$бит/с	Доказуемая безопасность
MASH-2	Модулярное возведение в степень$e=2^{8}+1=257$	$10^{4}..10^{5}$бит/с	Доказуемая безопасность

• Для очень высокой безопасности рекомендуется выбирать MASH-2, а не MASH-1, где могут быть нежелательные статистические зависимости

Ссылки

• Smashing MASH-1, Vladimir Antipkin
• A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography,ISBN 0-8493-8523-7
• Метод каскадного формирования МАС-кодов с использованием модулярных преобразований Король.О.Г., Парцхуль Л.Т., Евсеев С.П.
• Implementation and parallel cryptanalysis of MASH hash function family Marek Gradzki 2011
• P. van Oorschot and M. Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology, 12(1):1-28, 1999.
• D. Bishop, Introduction to Cryptography with Java Applets, 2003.
• ISO/IEC 10118. Information technology{security. Part 4: Hash-functions using modular arithmetic, 1998.
• H.C.A. van Tilborg, Encyclopedia of Cryptography and Security, Springer-Verlag New York, Inc., Secaucus, NJ, 2005.
• J. Bloch, E ective Java: Programming Language Guide, Addison Wesley, 2001.