RIPEMD-128

RIPEMD-128

Загальні
Розробники	Барт Пренель
Уперше оприлюднений	1996
Серія	RIPEMD-256 і RIPEMD-320
Деталі
Розмір даджеста	128 біт
Структура	геш-функція
Раундів	4

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

Історія

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

Іншою причиною переходу до алгоритмів, що видають результат із великою кількістю біт, був стрімкий розвиток обчислювальної техніки, (згідно закону Мура). Наявні в той час алгоритми з кожним роком ставали все більш і більш уразливими до колізійних атак шляхом повного перебору. Проте, RIPEMD-128 знайшов своє застосування в деяких банківських додатках[1]. У 2004 році була стандартизована (ISO / IEC 10118-3: 2004 [Архівовано 2 лютого 2017 у Wayback Machine.]).

Алгоритм

RIPEMD-128: Схематичне представлення одного циклу алгоритму

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

Алгоритм складається з декількох основних кроків:

1. Додавання відсутніх бітів

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

2. Додавання довжини повідомлення

На наступному кроці до 448-бітного отриманого повідомлення додається довжина вихідного повідомлення (до застосування першого кроку) в 64-бітному поданні. У разі, якщо вихідна довжина повідомлення перевищує 2 ^64 біт, то від її бітової довжини використовується тільки молодші 64 біта. Причому, довжина вихідного повідомлення додається у вигляді двох 32-бітних слів: першим додаються молодші 32 біта, потім старші. Після цього етапу довжина модифікованого повідомлення стає рівною 512 бітам. Його також можна представити у вигляді 16 32-бітових слів.

3. Визначення функцій і констант

a. Порядок слів у повідомленні

Для визначення порядку 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 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}$):

Раунд	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	X14	X15
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

р Константи

В якості констант (${\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}$

4. Виконання гешування

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

На кожному кроці для кожної з ліній виконується наступна операція: ${\displaystyle A:=(A+f(B,C,D)+X+K)^{<<s}}$ де ${\displaystyle ^{<<s}}$ позначає циклічний зсув на ${\displaystyle s}$ позицій.

Швидкість роботи

У таблиці для порівняння наведені швидкості виконання MD-подібних функцій. Тестові програми були написані на мові асемблера і Сі, з використанням оптимізацій для тестової машини:[2]

Алгоритм	Мбит/сек — 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

Незалежне дослідження, проведене пізніше, показало досить схожі результати. У вимірі була використана Сі ++ бібліотека[3].

Алгоритм	Мбіт/сек	Циклів на байт	Відносна продуктинівсть
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 ^128, що збігається з максимальним для її бітової довжини значенням — пошук вимагає повного перебору[1].

Алгоритм	Складність пошуку праобраза	Найкраща атака (раунди)
RIPEMD (original)	2^128	35 из 48
RIPEMD-128	2^128	35 из 64
RIPEMD-160	2^160	31 из 80

Для скороченого варіанту RIPEMD-128 існують алгоритми знаходження першого праобразу, що вимагають меншої складності:[4]

Раунди	Складність пошуку	Джерело
33	2^124,5	Стаття[4]
35	2^121	Стаття[4]
36	2^126,5	Стаття[4]

Оригінальна RIPEMD не була безпечною з точки зору колізій. Про колізії стало відомо в 2004 році[5], в 2005 році вийшла відповідна стаття, присвячена криптоаналізу алгоритму[5]. Так як будь-яка криптографічна хеш-функція за визначенням вразлива до атаки «днів народження», то складність підбору не може перевищувати 2 ^N / 2 для N-бітної геш-функції. Однак, 128-бітна RIPEMD може бути «зламана» за час 2 ^18, що набагато менше відповідного їй значення 2 ^64.

Повна RIPEMD-128 теоретично може бути «зламана». Колізійна атака має складність порядку 2 ^61.57 (проти необхідної 2 ^64). У той час як скорочений варіант схильний до більш успішних атак:

Ціль	Раунди	Складність пошуку	Джерело
Функція стиснення	48	2^40	Стаття[1]
Функція стиснення	60	2^57.57	Статья[1]
Функція стиснення	63	2^59.91	Стаття[1]
Функція стиснення	Полная (64)	2^61.57	Стаття[1]
Функція гешування	38	2^14	Стаття[1]

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

Приклади

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

Приклади, які демонструють Лавиновий ефект:

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

Примітки

1. Cryptanalysis of Full RIPEMD-128 (PDF). Архів оригіналу (PDF) за 25 серпня 2016. Процитовано 14 квітня 2018.
2. The Cryptographic Hash Functio RIPEMD-160 (PDF). Архів оригіналу (PDF) за 9 серпня 2017. Процитовано 14 квітня 2018.
3. Crypto++ 6.0.0 Benchmarks. Архів оригіналу за 2 липня 2017. Процитовано 14 квітня 2018. [Архівовано 2017-07-02 у Wayback Machine.]
4. Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128. Архів оригіналу за 9 жовтня 2017. Процитовано 14 квітня 2018.
5. Cryptanalysis of Hash Functions of the MD4-Family (PDF). Архів оригіналу (PDF) за 3 березня 2019. Процитовано 14 квітня 2018.

Посилання

• Cryptanalysis of Full RIPEMD-128 [Архівовано 25 серпня 2016 у Wayback Machine.]
• The Cryptographic Hash Functio RIPEMD-160 [Архівовано 9 серпня 2017 у Wayback Machine.]
• Crypto++ 6.0.0 Benchmarks [Архівовано 2 липня 2017 у Wayback Machine.]
• Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128 [Архівовано 9 жовтня 2017 у Wayback Machine.]
• Cryptanalysis of Hash Functions of the MD4-Family [Архівовано 3 березня 2019 у Wayback Machine.]