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]. Криптоаналіз, проведений Гансом Доббертіном, показав, що даний алгоритм не є безпечним в плані наявності колізій, що пізніше було підтверджено знайденими уразливостями^[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.]).

Алгоритм[ред. | ред. код]

Для довільного вхідного повідомлення геш-функція генерує 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 біта. Причому, довжина вихідного повідомлення додається у вигляді двох 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}$):

р Константи[ред. | ред. код]

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

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

Крипостійкість[ред. | ред. код]

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

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

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

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

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

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

Приклади[ред. | ред. код]

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

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

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

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]

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