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.]).
Алгоритм
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Ripemd128.png/220px-Ripemd128.png)
Для довільного вхідного повідомлення геш-функція генерує 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-бітних слів в повідомленні в кожному раунді використовуються різні комбінації функцій перестановок.
Визначимо функцію перестановки :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
7 | 14 | 13 | 1 | 10 | 6 | 15 | 3 | 12 | 0 | 9 | 5 | 2 | 14 | 11 | 8 |
А також функцію перестановки :
В кажному раунді порядок визначається наступним чином:
Лінія | Раунд 1 | Раунд 2 | Раунд 3 | Раунд 4 |
---|---|---|---|---|
Ліва | ||||
Права |
б. Булеві функції
У кожному раунді для кожної лінії застосовуються певні булеві функції.
Визначимо нелінійні побітові булеві функції:
У кожному раунді в залежності від лінії будуть застосовуватися:
Лінія | Раунд 1 | Раунд 2 | Раунд 3 | Раунд 4 |
---|---|---|---|---|
Ліва | ||||
Права |
б. Булеві функції
У кожному раунді для кожної лінії застосовуються певні булеві функції.
Визначимо нелінійні побітові булеві функції:
У кожному раунді в залежності від лінії будуть застосовуватися:
Лінія | Раунд 1 | Раунд 2 | Раунд 3 | Раунд 4 |
---|---|---|---|---|
Ліва | ||||
Права |
в. Зрушення
Для обох ліній застосовуються такі зрушення ():
Раунд | 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 |
р Константи
В якості констант (), що застосовуються в алгоритмі, використовуються цілі частини наступних дійсних чисел:
Лінія | Раунд 1 | Раунд 2 | Раунд 3 | Раунд 4 |
---|---|---|---|---|
Ліва | ||||
Права |
4. Виконання гешування
Після завдання всіх вихідних функцій і констант, приведення повідомлення до необхідного розміру, можна переходити до виконання алгоритму. Виконання алгоритму відбувається двома паралельними шляхами (лініями). Обробка повідомлення відбувається словами по 16 слів у 32 біта.
На кожному кроці для кожної з ліній виконується наступна операція: де позначає циклічний зсув на позицій.
Швидкість роботи
У таблиці для порівняння наведені швидкості виконання 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) | 2128 | 35 из 48 |
RIPEMD-128 | 2128 | 35 из 64 |
RIPEMD-160 | 2160 | 31 из 80 |
Для скороченого варіанту RIPEMD-128 існують алгоритми знаходження першого праобразу, що вимагають меншої складності:[4]
Раунди | Складність пошуку | Джерело |
---|---|---|
33 | 2124,5 | Стаття[4] |
35 | 2121 | Стаття[4] |
36 | 2126,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 | 240 | Стаття[1] |
Функція стиснення | 60 | 257.57 | Статья[1] |
Функція стиснення | 63 | 259.91 | Стаття[1] |
Функція стиснення | Полная (64) | 261.57 | Стаття[1] |
Функція гешування | 38 | 214 | Стаття[1] |
128-бітний вихід функції, яка не здавалась досить захищеною в найближчій перспективі[2], як раз і послужив приводом для переходу до RIPEMD-160. Для неї відомі лише колізійні атаки на скорочений варіант (48 з 80 раундів, 2 51 часу)[2].
Приклади
RIPEMD128("") = "cdf26213a150dc3ecb610f18f6b38b46" RIPEMD128("a") = "86be7afa339d0fc7cfc785e72f578d33" RIPEMD128("abc") = "c14a12199c66e4ba84636b0f69144c77"
Приклади, які демонструють Лавиновий ефект:
RIPEMD128("aaa100") = "5b250e8d7ee4fd67f35c3d193c6648c4" RIPEMD128("aaa101") = "e607de9b0ca4fe01be84f87b83d8b5a3"
Примітки
- ↑ а б в г д е ж и к л м Cryptanalysis of Full RIPEMD-128 (PDF). Архів оригіналу (PDF) за 25 серпня 2016. Процитовано 14 квітня 2018.
- ↑ а б в The Cryptographic Hash Functio RIPEMD-160 (PDF). Архів оригіналу (PDF) за 9 серпня 2017. Процитовано 14 квітня 2018.
- ↑ Crypto++ 6.0.0 Benchmarks. Архів оригіналу за 2 липня 2017. Процитовано 14 квітня 2018.
- ↑ а б в г Collision Attacks on the Reduced Dual-Stream Hash Function RIPEMD-128. Архів оригіналу за 9 жовтня 2017. Процитовано 14 квітня 2018.
- ↑ а б 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.]
- п
- о
- р
розтягування ключів[en]
- HKDF[en]
- KDF1/KDF2
повідомлення
шифрування
- CCM[en]
- ChaCha20-Poly1305[en]
- CWC[en]
- EAX[en]
- GCM
- IAPM[en]
- OCB[en]
некриптографічні[en]
функції
- Adler-32[en]
- CRC
- FNV[en]
- Алгоритм Луна
- Колізійна
- Знаходження першовзору
- «Днів народження»
- Грубою силою
- Райдужна таблиця
- Сторонніми каналами
- Розширення довжини[en]
- Лавиновий ефект
- Колізія геш-функції
- Будова Меркла-Демґарда
- Функція губки
- HAIFA construction[en]
- Hash-based cryptography[en]
- Дерево Меркла
- Автентифікація повідомлень
- Доказ виконаної роботи
- Сіль
- Перець