RIPEMD-128

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \pi (i)=9i+5(mod16)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Страница хеш-функций семейства RIPEMD Архивная копия от 14 декабря 2005 на Wayback Machine (описание, исходные коды)
• Основная статья разработчиков Архивная копия от 18 октября 2016 на Wayback Machine