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 битовой длины ${\displaystyle 0\leq b<2^{n/2}}$. На выходе хотим получить n битный хеш x (n почти той же битовой длины, что и M).

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

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

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

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

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

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

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

Пример кода

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

private final BigInteger compress(BigInteger X, BigInteger H) {
    BigInteger XX = BigInteger.value0f(0);
    BigInteger rem;
    for (int j = k - 4; j >= 0; j -= 4) {
        XX = XX.shiftLeft(4).or(FEFTEEN);
        rem = block.shiftRight(j).mod(SIXSTEEN);
        XX = XX.shiftLeft(4).or(rem);
    }
    return H.xor(XX).or(E).pow(2).mod(N).mod(TWO_POW_N).xor(H);
}

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

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

MASH-2

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

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

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

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

^[3]

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

Примечания

1. A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, c.352
2. Implementation and parallel cryptanalysis of MASH hash function family Marek Gradzki 2011
3. Метод каскадного формирования МАС-кодов с использованием модулярных преобразований Король.О.Г., Парцхуль Л.Т., Евсеев С.П.

Ссылки

• 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.