Interested Article - RIPEMD-128

RIPEMD-128 ( англ. RACE Integrity Primitives Evaluation Message Digest) — криптографическая хеш-функция , разработанная , и Бартом Пренелем в 1996 году .

История

RIPEMD представляет собой несколько хеш-функций , относящихся к семейству MD-SHA. Первой из них была RIPEMD-0, рекомендованная в 1992 году консорциумом для Оценки примитивов целостности RACE ( англ. RACE Integrity Primitives Evaluation, RIPE) в качестве улучшенной версии алгоритма MD4 . Криптоанализ , проведённый , показал, что данный алгоритм не является безопасным в плане наличия коллизий , что позже было подтверждено найденными уязвимостями . RIPEMD-128 (совместно с 160-битной версией, RIPEMD-160 ) была представлена как замена оригинальной RIPEMD, которая тоже была 128-битной. Были разработаны и другие версии алгоритма, с большей длиной хеша: RIPEMD-256 и RIPEMD-320 (соответственно 256- и 320-битные).

Другой причиной перехода к алгоритмам, выдающим результат с большим количеством бит, было стремительное развитие вычислительной техники (согласно закону Мура ). Имеющиеся в то время алгоритмы с каждым годом становились всё более и более уязвимыми для коллизионных атак путём полного перебора . Тем не менее, RIPEMD-128 нашла своё применение в некоторых банковских приложениях . В 2004 году была стандартизирована (от 2 февраля 2017 на Wayback Machine ).

Алгоритм

Для произвольного входного сообщения хеш-функция генерирует 128-разрядное хеш-значение — дайджест сообщения . Алгоритм основан на алгоритме хеширования MD4 . Хеширование MD4 состоит из 48 операций, содержащих применение нелинейных булевых функций , сгруппированных в 3 раунда по 16 операций. В алгоритме RIPEMD-128 увеличено число раундов до 4. Кроме того, используются другие булевы функции и значения констант . В алгоритме параллельно выполняются две линии (потока), которые условно разделяют на Левую и Правую.

Алгоритм состоит из нескольких основных шагов:

1. Добавление недостающих битов

Алгоритм оперирует с блоками данных длиной 512 бит, входное сообщение предварительно приводится к требуемому размеру. Для начала, вне зависимости от начальной длины сообщения, к нему добавляется один бит, равный 1. Далее к нему добавляются биты, равные 0, до тех пор, пока длина получаемой последовательности не станет равной 448 бит по модулю 512. В результате расширения, до длины в 512 бит модифицированному сообщению недостаёт ровно 64 бит. На этом шаге к нему может быть добавлено от 1 до 512 бит.

2. Добавление длины сообщения

На следующем шаге к 448-битному полученному сообщению добавляется длина исходного сообщения (до применения первого шага) в 64-битном представлении. В случае, если исходная длина сообщения превышает 2 ⁶⁴ бит, то от её битовой длины используется только младшие 64 бита. Причём, длина исходного сообщения добавляется в виде двух 32-битных слов: первым добавляются младшие 32 бита, затем старшие. После этого этапа длина модифицированного сообщения становится равной 512 битам. Его также можно представить в виде 16 32-битных слов.

3. Определение функций и констант

a. Порядок слов в сообщении

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

Определим функцию перестановки $\rho$ $\rho$ :

$i$ $i$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\rho (i)$ $\rho (i)$	7	14	13	1	10	6	15	3	12	0	9	5	2	14	11	8

А также функцию перестановки $\pi$ $\pi$ :

$\pi (i)=9i+5(mod16)$ $\pi (i)=9i+5(mod16)$

В каждом раунде порядок определяется следующим образом:

Линия	Раунд 1	Раунд 2	Раунд 3	Раунд 4
Левая	$i$ $i$	$\rho$ $\rho$	$\rho ^{2}$ $\rho ^{2}$	$\rho ^{3}$ $\rho ^{3}$
Правая	$\pi$ $\pi$	$\pi \rho$ $\pi \rho$	$\pi \rho ^{2}$ $\pi \rho ^{2}$	$\pi \rho ^{3}$ $\pi \rho ^{3}$

б. Булевы функции

В каждом раунде для каждой линии применяются определённые булевы функции.

Определим нелинейные побитовые булевы функции:

$f_{1}(x,y,z)=x\oplus y\oplus z$ $f_{1}(x,y,z)=x\oplus y\oplus z$

$f_{2}(x,y,z)=(x\land y)\lor (\neg x\land z)$ $f_{2}(x,y,z)=(x\land y)\lor (\neg x\land z)$

$f_{3}(x,y,z)=(x\lor \neg y)\oplus z$ $f_{3}(x,y,z)=(x\lor \neg y)\oplus z$

$f_{4}(x,y,z)=(x\land z)\lor (y\land \neg z)$ $f_{4}(x,y,z)=(x\land z)\lor (y\land \neg z)$

В каждом раунде в зависимости от линии будут применяться:

Линия	Раунд 1	Раунд 2	Раунд 3	Раунд 4
Левая	$f_{1}$ $f_1$	$f_{2}$ $f_{2}$	$f_{3}$ $f_3$	$f_{4}$ $f_{4}$
Правая	$f_{4}$ $f_{4}$	$f_{3}$ $f_3$	$f_{2}$ $f_{2}$	$f_{1}$ $f_1$

в. Сдвиги

Для обеих линий применяются следующие сдвиги ( $X$ $X$ ):

Раунд	X ₀	X ₁	X ₂	X ₃	X ₄	X ₅	X ₆	X ₇	X ₈	X ₉	X ₁₀	X ₁₁	X ₁₂	X ₁₃	X ₁₄	X ₁₅
1	11	14	15	12	5	8	7	9	11	13	14	15	6	7	9	8
2	12	13	11	15	6	9	9	7	12	15	11	13	7	8	7	7
3	13	15	14	11	7	7	6	8	13	14	13	12	5	5	6	9
4	14	11	12	14	8	6	5	5	15	12	15	14	9	9	8	6

г. Константы

В качестве констант ( $K$ $K$ ), применяемых в алгоритме, используются целые части следующих вещественных чисел:

Линия	Раунд 1	Раунд 2	Раунд 3	Раунд 4
Левая	$0$ $0$	$2^{30}{\sqrt {2}}$ $2^{30}{\sqrt {2}}$	$2^{30}{\sqrt {3}}$ $2^{30}{\sqrt {3}}$	$2^{30}{\sqrt {5}}$ $2^{30}{\sqrt {5}}$
Правая	$2^{30}{\sqrt[{3}]{2}}$ $2^{30}{\sqrt[{3}]{2}}$	$2^{30}{\sqrt[{3}]{3}}$ $2^{30}{\sqrt[{3}]{3}}$	$2^{30}{\sqrt[{3}]{5}}$ $2^{30}{\sqrt[{3}]{5}}$	$0$ $0$

4. Выполнение хеширования

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

На каждом шаге для каждой из линий выполняется следующая операция:

$A:=(A+f(B,C,D)+X+K)^{<<s}$ $A:=(A+f(B,C,D)+X+K)^{<<s}$

где $^{<<s}$ $^{<<s}$ обозначает циклический сдвиг на $s$ $s$ позиций.

Скорость работы

В таблице для сравнения приведены скорости выполнения MD-подобных функций. Тестовые программы были написаны на языке ассемблера и Си , с использованием оптимизаций для тестовой машины:

Алгоритм	Мбит/сек — asm	Мбит/сек — С	Относительная производительность
RIPEMD-128	77.6	35.6	1.00
RIPEMD-160	45.3	19.3	0.58
SHA-1	54.9	21.2	0.71
MD5	136.2	59.7	1.76
MD4	190.6	81.4	2.46

Независимое исследование, проведённое позднее, показало довольно схожие результаты. В замере была использована Си++ библиотека Crypto++ :

Алгоритм	Мбит/сек	Циклов на байт	Относительная производительность
RIPEMD-128	153	11.4	1.00
RIPEMD-160	106	16.5	0.69
RIPEMD-256	158	11.1	1.03
RIPEMD-320	110	15.9	0.72
SHA-1	153	11.4	1.00
MD5	255	6.8	1.67

Криптостойкость

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

Алгоритм RIPEMD-128, как и другие алгоритмы семейства RIPEMD , включая оригинальный первый, считаются устойчивыми к атаке нахождения прообраза. Для RIPEMD-128 вычислительная сложность нахождения первого прообраза составляет 2 ¹²⁸ , что совпадает с максимальным для её битовой длины значением — отыскание требует полного перебора :

Алгоритм	Сложность нахождения прообраза	Лучшая атака (раунды)
RIPEMD (original)	2 ¹²⁸	35 из 48
RIPEMD-128	2 ¹²⁸	35 из 64
RIPEMD-160	2 ¹⁶⁰	31 из 80

Для сокращённого варианта RIPEMD-128 существуют алгоритмы нахождения первого прообраза, требующие меньшей сложности:

Раунды	Сложность отыскания	Источник
33	2 ^124,5	Статья
35	2 ¹²¹	Статья
36	2 ^126,5	Статья

Оригинальная RIPEMD не была безопасной с точки зрения коллизий. О коллизии стало известно в 2004 году , в 2005 году вышла соответствующая статья, посвящённая криптоанализу алгоритма . Так как любая криптографическая хеш-функция по определению уязвима для атаки «дней рождения» , то сложность подбора не может превышать 2 ^N/2 для N-битной хеш-функции. Однако, 128-битная RIPEMD может быть «сломана» за время 2 ¹⁸ , что гораздо меньше соответствующего ей значения 2 ⁶⁴ .

Полная RIPEMD-128 теоретически может быть «сломана». Коллизионная атака имеет сложность порядка 2 ^61.57 (против необходимой 2 ⁶⁴ ). В то время как сокращённый вариант подвержен более успешным атакам:

Цель	Раунды	Сложность отыскания	Источник
Функция сжатия	48	2 ⁴⁰	Статья
Функция сжатия	60	2 ^57.57	Статья
Функция сжатия	63	2 ^59.91	Статья
Функция сжатия	Полная (64)	2 ^61.57	Статья
Функция хеширования	38	2 ¹⁴	Статья

128-битный выход функции, который не казался достаточно защищённым в ближайшей перспективе , как раз и послужил поводом для перехода к RIPEMD-160 . Для неё известны лишь коллизионные атаки на сокращённый вариант (48 из 80 раундов, 2 ⁵¹ времени) .

Примеры

RIPEMD128("") = "cdf26213a150dc3ecb610f18f6b38b46" RIPEMD128("a") = "86be7afa339d0fc7cfc785e72f578d33" RIPEMD128("abc") = "c14a12199c66e4ba84636b0f69144c77"

Примеры, демонстрирующие лавинный эффект :

RIPEMD128("aaa100") = "5b250e8d7ee4fd67f35c3d193c6648c4" RIPEMD128("aaa101") = "e607de9b0ca4fe01be84f87b83d8b5a3"

Ссылки

от 14 декабря 2005 на Wayback Machine (описание, исходные коды)
от 18 октября 2016 на Wayback Machine

Примечания

↑ Franck Landelle, Thomas Peyrin. . — Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 2013. 25 августа 2016 года.
↑ Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. . — Dept. of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai, China, 2004. 20 декабря 2004 года.
↑ Hans Dobbertin, Antoon Bosselaers, Bart Preneel. . — 1996. 18 октября 2016 года.
Bart Preneel, Hans Dobbertin, Antoon Bosselaers. . — 1997. 9 августа 2017 года.
Wei Dai. (неопр.) . Дата обращения: 22 января 2017. 2 июля 2017 года.
↑ Chiaki Ohtahara, Yu Sasaki, Takeshi Shimoyama. . — 2011. 12 октября 2017 года.
↑ Florian Mendel, Tomislav Nad, Martin Schläffer. . — 2012. 9 октября 2017 года.
Lei Wang, Yu Sasaki, Wataru Komatsubara, Kazuo Ohta, Kazuo Sakiyama. . — 2011. 19 февраля 2017 года.
Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu. . — 2005. 3 марта 2019 года.
Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen. . — 2006. 18 июля 2020 года.