Перегляд вихідного коду сторінки RIPEMD-128

{{Infobox encryption method
| name           = RIPEMD-128
| image          = 
| caption        = 
<!-- General -->
| designers      = [[Барт Пренель]]
| publish date   = 1996
| series         = [[RIPEMD-256]] і [[RIPEMD-320]]
| derived from   = 
| derived to     = 
| related to     = 
| certification  = 
<!-- Detail -->
| digest size    = 128 біт
| structure      = [[геш-функція]]
| rounds         = 4
| cryptanalysis  = 
}}

'''RIPEMD-128''' ({{lang-en|RACE Integrity Primitives Evaluation Message Digest}})&nbsp;— [[криптографічна геш-функція]], розроблена [[Ганс Доббертін|Гансом Доббертіном]], [[Антон Боселаерс| Антоном Боселаерсом]] і [[Барт Пренель | Бартом Пренелем]] у 1996 році.

== Історія ==
[[RIPEMD]] має кілька [[геш-функція|геш-функцій]], що відносяться до сімейства MD-SHA. Першою з них була RIPEMD-0, рекомендована в 1992 році консорціумом для Оцінки примітивів цілісності RACE ({{lang-en|RACE Integrity Primitives Evaluation, RIPE}}) в якості поліпшеної версії алгоритму [[MD4]]<ref name = "Cryptanalysis of Full RIPEMD-128"/>. [[Криптоаналіз]], проведений Гансом Доббертіном, показав, що даний алгоритм не є безпечним в плані наявності [[Колізія хеш-функції | колізій]], що пізніше було підтверджено знайденими уразливостями<ref name="Cryptanalysis of Full RIPEMD-128"/>. RIPEMD-128 (спільно з 160-бітної версією, [[RIPEMD-160]]) була представлена як заміна оригінальної RIPEMD, яка теж була 128-бітною. Були розроблені й інші версії алгоритму, з більшою довжиною хешу: [[RIPEMD-256]] і [[RIPEMD-320]] (відповідно 256 і 320-бітові).

Іншою причиною переходу до алгоритмів, що видають результат із великою кількістю біт, був стрімкий розвиток обчислювальної техніки, (згідно [[Закон Мура | закону Мура]]). Наявні в той час алгоритми з кожним роком ставали все більш і більш уразливими до колізійних атак шляхом [[Повний перебір # Атака методом «грубої сили» | повного перебору]]. Проте, RIPEMD-128 знайшов своє застосування в деяких банківських додатках<ref name="Cryptanalysis of Full RIPEMD-128"/>. У 2004 році була стандартизована ([http://www.iso.org/iso/catalogue_detail.htm?csnumber=39876 ISO / IEC 10118-3: 2004] {{Webarchive|url=https://web.archive.org/web/20170202085319/http://www.iso.org/iso/catalogue_detail.htm?csnumber=39876 |date=2 лютого 2017 }}).

== Алгоритм ==
[[Файл: ripemd128.png | thumb | RIPEMD-128: Схематичне представлення одного циклу алгоритму]]

Для довільного вхідного повідомлення геш-функція генерує 128-розрядне геш-значення&nbsp;— [[Геш-сума | дайджест повідомлення]]. Алгоритм заснований на алгоритмі хешування [[MD4]]. Гешування MD4<ref name="Cryptanalysis of Full RIPEMD-128">{{Cite web |url=https://eprint.iacr.org/2013/607.pdf |title=Cryptanalysis of Full RIPEMD-128 |accessdate=14 квітня 2018 |archive-date=25 серпня 2016 |archive-url=https://web.archive.org/web/20160825192005/http://eprint.iacr.org/2013/607.pdf }}</ref> складається з 48 операцій, що містять застосування нелінійних [[Булева функція | булевих функцій]], згрупованих в 3 [[Раунд (криптографія) | раунди]] по 16 операцій. В алгоритмі RIPEMD-128 збільшено число раундів до 4. Крім того, використовуються інші булеві функції і значення констант<ref name="Cryptanalysis of Full RIPEMD-128"/>. В алгоритмі паралельно виконуються дві лінії (потоку), які умовно поділяють на Ліву і Праву.

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

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

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

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

==== a. Порядок слів у повідомленні ====
Для визначення порядку 32-бітних слів в повідомленні в кожному раунді використовуються різні комбінації функцій [[Перестановка | перестановок]].

Визначимо функцію перестановки <math>\rho</math>:
{|class = "wikitable"
 |-
  ! <math>i</math>
  | 0
  | 1
  | 2
  | 3
  | 4
  | 5
  | 6
  | 7
  | 8
  | 9
  | 10
  | 11
  | 12
  | 13
  | 14
  | 15
 |-
  ! <math>\rho(i)</math>
  | 7
  | 14
  | 13
  | 1
  | 10
  | 6
  | 15
  | 3
  | 12
  | 0
  | 9
  | 5
  | 2
  | 14
  | 11
  | 8
 |}
А також функцію перестановки <math>\pi</math>:

<math>\pi(i) = 9i + 5 (mod 16)</math>

В кажному раунді порядок визначається наступним чином:
{|class = "wikitable"
 |-
  ! Лінія
  ! Раунд 1
  ! Раунд 2
  ! Раунд 3
  ! Раунд 4
 |-
  ! Ліва
  | <math>i</math>
  | <math>\rho</math>
  | <math>\rho^2</math>
  | <math>\rho^3</math>
 |-
  ! Права
  | <math>\pi</math>
  | <math>\pi\rho</math>
  | <math>\pi\rho^2</math>
  | <math>\pi\rho^3</math>
|}

==== б. Булеві функції ====
У кожному раунді для кожної лінії застосовуються певні булеві функції.

Визначимо нелінійні побітові булеві функції:

<math>f_1(x, y, z) = x \oplus y \oplus z</math>

<math>f_2(x, y, z) = (x \land y) \lor (\neg x \land z)</math>

<math>f_3(x, y, z) = (x \lor \neg y) \oplus z</math>

<math>f_4(x, y, z) = (x \land z) \lor (y \land \neg z)</math>

У кожному раунді в залежності від лінії будуть застосовуватися:
{|class = "wikitable"
 |-
  ! Лінія
  ! Раунд 1
  ! Раунд 2
  ! Раунд 3
  ! Раунд 4
 |-
  ! Ліва
  | <math>f_1</math>
  | <math>f_2</math>
  | <math>f_3</math>
  | <math>f_4</math>
 |-
  ! Права
  | <math>f_4</math>
  | <math>f_3</math>
  | <math>f_2</math>
  | <math>f_1</math>
|}

==== б. Булеві функції ====
У кожному раунді для кожної лінії застосовуються певні булеві функції.

Визначимо нелінійні побітові булеві функції:

<math>f_1(x, y, z) = x \oplus y \oplus z</math>

<math>f_2(x, y, z) = (x \land y) \lor (\neg x \land z)</math>

<math>f_3(x, y, z) = (x \lor \neg y) \oplus z</math>

<math>f_4(x, y, z) = (x \land z) \lor (y \land \neg z)</math>

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

{|class = "wikitable"
 |-
  ! Лінія
  ! Раунд 1
  ! Раунд 2
  ! Раунд 3
  ! Раунд 4
 |-
  ! Ліва
  | <math>f_1</math>
  | <math>f_2</math>
  | <math>f_3</math>
  | <math>f_4</math>
 |-
  ! Права
  | <math>f_4</math>
  | <math>f_3</math>
  | <math>f_2</math>
  | <math>f_1</math>
|}

==== в. Зрушення ====
Для обох ліній застосовуються такі зрушення (<math> X </math>):
{|class = "wikitable"
 |-
  ! Раунд
  ! X<sub>0</sub>
  ! X<sub>1</sub>
  ! X<sub>2</sub>
  ! X<sub>3</sub>
  ! X<sub>4</sub>
  ! X<sub>5</sub>
  ! X<sub>6</sub>
  ! X<sub>7</sub>
  ! X<sub>8</sub>
  ! X<sub>9</sub>
  ! X<sub>10</sub>
  ! X<sub>11</sub>
  ! X<sub>12</sub>
  ! X<sub>13</sub>
  ! X<sub>14</sub>
  ! X<sub>15</sub>
 |-
  ! 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
|}

==== р Константи ====
В якості констант (<math> K </math>), що застосовуються в алгоритмі, використовуються цілі частини наступних дійсних чисел:

{|class = "wikitable"
 |-
  ! Лінія
  ! Раунд 1
  ! Раунд 2
  ! Раунд 3
  ! Раунд 4
 |-
  ! Ліва
  | <math>0</math>
  | <math>2^{30}\sqrt{2}</math>
  | <math>2^{30}\sqrt{3}</math>
  | <math>2^{30}\sqrt{5}</math>
 |-
  ! Права
  | <math>2^{30}\sqrt[3]{2}</math>
  | <math>2^{30}\sqrt[3]{3}</math>
  | <math>2^{30}\sqrt[3]{5}</math>
  | <math>0</math>
|}

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

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

== Швидкість роботи ==
У таблиці для порівняння наведені швидкості виконання MD-подібних функцій. Тестові програми були написані на [[Мова асемблера | мові асемблера]] і [[Сі (мова програмування) | Сі]], з використанням оптимізацій для тестової машини:<ref name="Functio RIPEMD-160">{{Cite web |url=https://www.esat.kuleuven.be/cosic/publications/article-317.pdf |title=The Cryptographic Hash Functio RIPEMD-160 |accessdate=14 квітня 2018 |archive-date=9 серпня 2017 |archive-url=https://web.archive.org/web/20170809170700/https://www.esat.kuleuven.be/cosic/publications/article-317.pdf }}</ref>
{|class = "wikitable"
 |-
  ! Алгоритм
  ! Мбит/сек — [[Мова асемблера | asm]]
  ! Мбит/сек — [[C (мова програмування) | С]]
  !Відносна продуктивність
 |-
  | 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
|}

Незалежне дослідження, проведене пізніше, показало досить схожі результати. У вимірі була використана [[C++|Сі ++]] бібліотека<ref>{{Cite web |url=https://www.cryptopp.com/benchmarks.html |title=Crypto++ 6.0.0 Benchmarks |accessdate=14 квітня 2018 |archive-date=2 липня 2017 |archive-url=https://web.archive.org/web/20170702105931/https://www.cryptopp.com/benchmarks.html }} {{Webarchive|url=https://web.archive.org/web/20170702105931/https://www.cryptopp.com/benchmarks.html |date=2017-07-02 }}</ref>.
{|class = "wikitable"
 |-
  ! Алгоритм
  ! Мбіт/сек
  ! Циклів на байт
  ! Відносна продуктинівсть
 |-
  | 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
|}

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

Алгоритм RIPEMD-128, як і інші алгоритми сімейства [[RIPEMD]], включаючи оригінальний перший, вважається стійким до атаки знаходження прообразу. Для RIPEMD-128 [[обчислювальна складність]] знаходження першого прообразу становить 2 <sup> 128 </sup>, що збігається з максимальним для її бітової довжини значенням&nbsp;— пошук вимагає [[Повний перебір | повного перебору]]<ref name = "Cryptanalysis of Full RIPEMD-128"/>.
{|class = "wikitable"
 |-
  ! Алгоритм
  ! Складність пошуку праобраза
  ! Найкраща атака (раунди)
 |-
  | RIPEMD (original)
  | 2<sup>128</sup>
  | 35 из 48
 |-
  | RIPEMD-128
  | 2<sup>128</sup>
  | 35 из 64
 |-
  | RIPEMD-160
  | 2<sup>160</sup>
  | 31 из 80
|}
Для скороченого варіанту RIPEMD-128 існують алгоритми знаходження першого праобразу, що вимагають меншої складності:<ref name="Function RIPEMD-128">{{Cite web |url=https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=62247 |title=Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128 |accessdate=14 квітня 2018 |archive-date=9 жовтня 2017 |archive-url=https://web.archive.org/web/20171009144403/https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=62247 }}</ref>
{|class = "wikitable"
 |-
  ! Раунди
  ! Складність пошуку
  ! Джерело
 |-
  | 33
  | 2<sup>124,5</sup>
  | Стаття<ref name="Function RIPEMD-128"/>
 |-
  | 35
  | 2<sup>121</sup>
  | Стаття<ref name="Function RIPEMD-128"/>
 |-
  | 36
  | 2<sup>126,5</sup>
  | Стаття<ref name="Function RIPEMD-128"/>
|}

Оригінальна RIPEMD не була безпечною з точки зору колізій. Про колізії стало відомо в 2004 році<ref name="MD4-Family">{{Cite web |url=http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DaumMagnus/diss.pdf |title=Cryptanalysis of Hash Functions of the MD4-Family |accessdate=14 квітня 2018 |archive-date=3 березня 2019 |archive-url=https://web.archive.org/web/20190303050859/http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DaumMagnus/diss.pdf }}</ref>, в 2005 році вийшла відповідна стаття, присвячена [[Криптоаналіз|криптоаналізу]] алгоритму<ref name="MD4-Family"/>. Так як будь-яка криптографічна хеш-функція за визначенням вразлива до [[Парадокс днів народження | атаки «днів народження»]], то складність підбору не може перевищувати 2 <sup> N / 2 </sup> для N-бітної геш-функції. Однак, 128-бітна RIPEMD може бути «зламана» за час 2 <sup> 18 </sup>, що набагато менше відповідного їй значення 2 <sup> 64 </sup>.

Повна RIPEMD-128 теоретично може бути «зламана». Колізійна атака має складність порядку 2 <sup> 61.57 </sup> (проти необхідної 2 <sup> 64 </sup>). У той час як скорочений варіант схильний до більш успішних атак:
{|class = "wikitable"
 |-
  ! Ціль
  ! Раунди
  ! Складність пошуку
  ! Джерело
 |-
  | [[Одностороння функція стиснення|Функція стиснення]]
  | 48
  | 2<sup>40</sup>
  | Стаття<ref name = "Cryptanalysis of Full RIPEMD-128"/>
 |-
  | [[Одностороння функція стиснення|Функція стиснення]]
  | 60
  | 2<sup>57.57</sup>
  | Статья<ref name = "Cryptanalysis of Full RIPEMD-128"/>
 |-
  | [[Одностороння функція стиснення|Функція стиснення]]
  | 63
  | 2<sup>59.91</sup>
  | Стаття<ref name = "Cryptanalysis of Full RIPEMD-128"/>
 |-
  | [[Одностороння функція стиснення|Функція стиснення]]
  | Полная (64)
  | 2<sup>61.57</sup>
  | Стаття<ref name = "Cryptanalysis of Full RIPEMD-128"/>
 |-
  | Функція гешування
  | 38
  | 2<sup>14</sup>
  | Стаття<ref name = "Cryptanalysis of Full RIPEMD-128"/>
|}

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

== Приклади ==
 RIPEMD128("") = "cdf26213a150dc3ecb610f18f6b38b46"
 RIPEMD128("a") = "86be7afa339d0fc7cfc785e72f578d33"
 RIPEMD128("abc") = "c14a12199c66e4ba84636b0f69144c77"
Приклади, які демонструють [[Лавиновий ефект]]:
 RIPEMD128("aaa10'''0'''") = "5b250e8d7ee4fd67f35c3d193c6648c4"
 RIPEMD128("aaa10'''1'''") = "e607de9b0ca4fe01be84f87b83d8b5a3"

== Примітки ==
{{reflist}}

== Посилання ==
* [https://eprint.iacr.org/2013/607.pdf Cryptanalysis of Full RIPEMD-128] {{Webarchive|url=https://web.archive.org/web/20160825192005/http://eprint.iacr.org/2013/607.pdf |date=25 серпня 2016 }}
* [https://www.esat.kuleuven.be/cosic/publications/article-317.pdf The Cryptographic Hash Functio RIPEMD-160] {{Webarchive|url=https://web.archive.org/web/20170809170700/https://www.esat.kuleuven.be/cosic/publications/article-317.pdf |date=9 серпня 2017 }}
* [https://www.cryptopp.com/benchmarks.html Crypto++ 6.0.0 Benchmarks] {{Webarchive|url=https://web.archive.org/web/20170702105931/https://www.cryptopp.com/benchmarks.html |date=2 липня 2017 }}
* [https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=62247 Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128] {{Webarchive|url=https://web.archive.org/web/20171009144403/https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=62247 |date=9 жовтня 2017 }}
* [http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DaumMagnus/diss.pdf Cryptanalysis of Hash Functions of the MD4-Family] {{Webarchive|url=https://web.archive.org/web/20190303050859/http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/DaumMagnus/diss.pdf |date=3 березня 2019 }}

{{Геш-функції та коди аутентифікації повідомлення}}