Whirlpool (хеш-функция): различия между версиями
[отпатрулированная версия] | [непроверенная версия] |
м добавлена ссылка на архивную копию в шаблон {{cite web}} содержащий мёртвую ссылку |
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.9.5 |
||
(не показано 39 промежуточных версий 24 участников) | |||
Строка 1: | Строка 1: | ||
{{значения|Whirlpool (значения)}} |
{{значения|Whirlpool (значения)}} |
||
{{Карточка хеш |
{{Карточка хеш-функции |
||
|название = |
|название = Whirlpool |
||
|изображение = |
|изображение = Miyaguchi-Preneel.PNG |
||
|разработчики = |
|разработчики = [[Рэймен, Винсент|Винсент Рэймен]],<br> {{iw|Баррето, Пауло|Пауло Баррето|en|Paulo S. L. M. Barreto}} |
||
|впервые опубликован = |
|впервые опубликован = ноябрь 2000 |
||
|стандарты = |
|стандарты = NESSIE Portfolio ([[2003]]), ISO/IEC 10118-3:2004 ([[2004]]) |
||
|размер хеша = 512 бит |
|размер хеша = 512 бит |
||
|число раундов = 10 |
|число раундов = 10 |
||
|тип = [[хеш-функция]] |
|тип = [[хеш-функция]] |
||
}} |
}} |
||
'''Whirlpool''' — [[Криптографические хеш-функции|криптографическая хеш-функция]], разработанная |
'''Whirlpool''' — [[Криптографические хеш-функции|криптографическая хеш-функция]], разработанная [[Винсент Рэймен|Винсентом Рэйменом]] и {{iw|Баррето, Пауло|Пауло Баррето|en|Paulo S. L. M. Barreto}}. Опубликована в ноябре [[2000 год]]а. [[Хеширование|Хеширует]] входное [[сообщение]] с длиной до <math>2^{256}</math> битов. Выходное значение [[хеш-функция|хеш-функции]] Whirlpool, называемое [[Хеш-сумма|хешем]], составляет 512 битов. |
||
== История == |
== История == |
||
Строка 20: | Строка 20: | ||
=== Модификации === |
=== Модификации === |
||
С момента создания в [[2000 год]]у Whirlpool дважды |
С момента создания в [[2000 год]]у Whirlpool дважды модифицировалась. |
||
Первая версия, |
Первая версия, Whirlpool-0, представлена как кандидат в проекте [[NESSIE]] ({{lang-en|New European Schemes for Signatures, Integrity and Encryption}}, новые европейские проекты по [[Электронная подпись|цифровой подписи]], целостности и шифрованию). |
||
Модификация |
Модификация Whirlpool-0, названная Whirlpool-T, в [[2003 год]]у добавлена в перечень рекомендованных к использованию криптографических функций NESSIE. Изменения касались блока подстановки ([[S-box]]) Whirlpool: в первой версии структура S-box не была описана, и он генерировался произвольно, что создавало определённые проблемы при аппаратной реализации Whirlpool. В версии Whirlpool-T S-box «приобрёл» чёткую структуру. |
||
Дефект в диффузных матрицах |
Дефект в диффузных матрицах Whirlpool-T, обнаруженный {{iw|Сирай, Тайдзо|Тайдзо Сираем|en|Taizo Shirai}} и {{iw|Сибутани, Кёдзи|Кёдзи Сибутани|en|Kyoji Shibutani}}<ref name=Shirai&Shibutani>{{статья |
||
|заглавие=On the diffusion matrix employed in the Whirlpool hashing function |
|||
{{cite web |
|||
|ссылка=https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/whirlpool-20030311.pdf |
|||
|accessdate=2019-06-25 |
|||
| title = On the diffusion matrix employed in the Whirlpool hashing function |
|||
|язык=en |
|||
| description = NESSIE public report |
|||
|тип=journal |
|||
| author = [[Taizo Shirai]], [[Kyoji Shibutani]] |
|||
|автор=Kyoji, Shibutani; Shirai, Taizo |
|||
| year = 2003 |
|||
|число=11 |
|||
| accessdate = 16 ноября 2009 |
|||
|месяц=3 |
|||
| lang = en |
|||
|год=2003 |
|||
| archiveurl = http://www.webcitation.org/65p0SPRnR |
|||
|archivedate=2021-10-03 |
|||
|archiveurl=https://web.archive.org/web/20211003064715/https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/whirlpool-20030311.pdf |
|||
}} |
|||
</ref>, |
}}</ref>, впоследствии исправлен, и конечная (третья) версия, названная для краткости просто Whirlpool, принята [[ISO]] в стандарте ISO/IEC 10118-3:2004 в 2004 году. |
||
== Описание == |
== Описание == |
||
Основная версия — хеш-функции — третья; в отличие от первой версии, [[S-box]] определён, а диффузная матрица заменена на новую после доклада Сирая и Сибутани<ref name=Shirai&Shibutani/>. |
|||
Whirlpool состоит из повторного применения [[Односторонняя функция сжатия|функции сжатия]], основой которой является специальный 512-битный [[блочный шифр]] <math>W</math> с 512-битным ключом. |
|||
=== Введение === |
|||
В данной статье описывается последняя(третья) версия Whirlpool. В отличие от первой версии {{Не переведено|:en:S-box | S-box}} определен, а диффузная матрица заменена на новую после доклада {{Не переведено|:en:Taizo Shirai|Taizo Shirai}} и {{Не переведено|:en:Kyoji Shibutani|Kyoji Shibutani}}<ref name=Shirai&Shibutani/>. |
|||
Whirlpool состоит из повторного применения {{Не переведено|:en:One-way compression function|функции сжатия}}, основой которой является специальный 512-битный [[блочный шифр]] <math>W</math> с 512-битным ключом. |
|||
=== Используемые обозначения и операции === |
|||
В алгоритме используются операции в [[Конечное поле|поле Галуа]] <math>\ GF(2^8)</math> по модулю [[Неприводимый многочлен|неприводимого многочлена]] <math>\ p_8(x) = x^8 + x^4 + x^3 + x^2 + 1</math>. |
В алгоритме используются операции в [[Конечное поле|поле Галуа]] <math>\ GF(2^8)</math> по модулю [[Неприводимый многочлен|неприводимого многочлена]] <math>\ p_8(x) = x^8 + x^4 + x^3 + x^2 + 1</math>. |
||
Строка 53: | Строка 49: | ||
Многочлены для краткости записываются в шестнадцатеричном представлении. Например, запись <math>\ 11D_x</math> означает <math>\ p_8(x)</math>. |
Многочлены для краткости записываются в шестнадцатеричном представлении. Например, запись <math>\ 11D_x</math> означает <math>\ p_8(x)</math>. |
||
* Символом <math>\circ</math> обозначается {{iw|оператор композиции||en|Composition operator}}. Выражение <math>f \circ g</math> означает [[Композиция функций|композицию функций]] <math>\ g</math> и <math>\ f</math>. |
|||
* Символом <math>\circ</math> обозначается {{Не переведено|:en:Composition operator | оператор композиции}}. Выражение <math>f \circ g</math> означает [[Композиция функций|композицию функций]] <math>\ g</math> и <math>\ f</math>. |
|||
: Для обозначения композиции последовательности функций <math>f_m, f_{m+1},...,f_{n-1}, f_n, m \leq n</math> используется символ <math>\bigcirc_m^{r=n}</math>: |
: Для обозначения композиции последовательности функций <math>f_m, f_{m+1},...,f_{n-1}, f_n, m \leq n</math> используется символ <math>\bigcirc_m^{r=n}</math>: |
||
: <math>\bigcirc_m^{r=n} f_r \equiv f_n \circ f_{n-1} \circ \dots \circ f_{m+1} \circ f_m.</math> |
: <math>\bigcirc_m^{r=n} f_r \equiv f_n \circ f_{n-1} \circ \dots \circ f_{m+1} \circ f_m.</math> |
||
* <math>M_{m \times n}[GF(2^8)]</math> — множество матриц <math>m \times n</math> над <math>\ GF(2^8).</math> |
* <math>M_{m \times n}[GF(2^8)]</math> — множество матриц <math>m \times n</math> над <math>\ GF(2^8).</math> |
||
* <math>\ cir(a_0, a_1, . . . , a_{m-1})</math> — [[Циркулянт|циркулянтная матрица]] <math>m \times m</math>, первая строка которой состоит из элементов <math>\ a_0, a_1, . . . , a_{m-1},</math> то есть: |
|||
* <math>\ cir(a_0, a_1, . . . , a_{m-1})</math> — {{Не переведено|:en:Circulant matrix|циркулянтная матрица}} <math>m \times m</math>, первая строка которой состоит из элементов <math>\ a_0, a_1, . . . , a_{m-1},</math> то есть: |
|||
: <math> |
: <math> |
||
Строка 78: | Строка 71: | ||
=== Формат данных === |
=== Формат данных === |
||
Whirlpool построен на специальном [[блочный шифр|блочном шифре]] <math>W</math>, который работает с 512-битными данными. |
|||
В преобразованиях промежуточный результат вычисления [[Хеш-сумма|хеша]] называется ''хеш-состоянием'' или просто ''состоянием''. При вычислениях ''состояние'' обычно представляется ''матрицей состояния''. Для Whirlpool это матрица в <math>M_{8 \times 8}[GF(2^8)]</math>. Следовательно, 512-битные блоки данных должны быть преобразованы в этот формат перед дальнейшими вычислениями. Это достигается введением функции <math>\ \mu</math>: |
|||
Как уже говорилось выше, Whirlpool построена на специальном [[блочный шифр|блочном шифре]] <math>W</math>, который работает с 512-битными данными. |
|||
В преобразованиях промежуточный результат вычисления [[Хеш|хеша]] называется ''хеш-состоянием'' или просто ''состоянием''. При вычислениях ''состояние'' обычно представляется ''матрицей состояния''. Для Whirlpool это матрица в <math>M_{8 \times 8}[GF(2^8)]</math>. Следовательно, 512-битные блоки данных должны быть преобразованы в этот формат перед дальнейшими вычислениями. Это достигается введением функции <math>\ \mu</math>: |
|||
: <math>\mu: GF(2^8)^{64} \to M_{8 \times 8}[GF(2^8)], \qquad \mu(a) = b \Leftrightarrow b_{ij} = a_{8i+j}, 0 \leq i,j \leq 7. </math> |
: <math>\mu: GF(2^8)^{64} \to M_{8 \times 8}[GF(2^8)], \qquad \mu(a) = b \Leftrightarrow b_{ij} = a_{8i+j}, 0 \leq i,j \leq 7. </math> |
||
Строка 89: | Строка 81: | ||
==== Нелинейное преобразование <math>\gamma</math> (S-box) ==== |
==== Нелинейное преобразование <math>\gamma</math> (S-box) ==== |
||
Функция <math>\gamma: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> состоит из параллельного применения блока подстановки ([[S-box]]) <math>S: GF(2^8) \to GF(2^8), x \to S[x]</math> ко всем байтам матрицы состояния: |
|||
Функция <math>\gamma: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> состоит из параллельного применения блока подстановки ({{Не переведено|:en:S-box | S-box}}) <math>S: GF(2^8) \to GF(2^8), x \to S[x]</math> ко всем байтам матрицы состояния: |
|||
: <math>\gamma(a)=b \Leftrightarrow b_{ij} = S[a_{ij}], 0 \leq i,j \leq 7. </math> |
: <math>\gamma(a)=b \Leftrightarrow b_{ij} = S[a_{ij}], 0 \leq i,j \leq 7. </math> |
||
Строка 167: | Строка 158: | ||
==== Циклическая перестановка <math>\pi</math> ==== |
==== Циклическая перестановка <math>\pi</math> ==== |
||
Перестановка <math>\pi: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> циклически сдвигает каждый столбец матрицы состояния так, что столбец <math>j</math> сдвигается вниз на <math>j</math> позиций: |
Перестановка <math>\pi: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> циклически сдвигает каждый столбец матрицы состояния так, что столбец <math>j</math> сдвигается вниз на <math>j</math> позиций: |
||
Строка 175: | Строка 165: | ||
==== Линейная диффузия <math>\theta</math> ==== |
==== Линейная диффузия <math>\theta</math> ==== |
||
Линейная диффузия <math>\theta: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> — это линейное преобразование, матрицей которого является {{iw|MDS-матрица||en|MDS matrix}} <math>\ C = cir(01_x, 01_x, 04_x, 01_x, 08_x, 05_x, 02_x, 09_x)</math>, то есть: |
|||
Линейная диффузия <math>\theta: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> — это линейное преобразование, матрицей которого является {{Не переведено|:en:MDS matrix | MDS матрица}} <math>\ C = cir(01_x, 01_x, 04_x, 01_x, 08_x, 05_x, 02_x, 09_x)</math>, то есть: |
|||
Строка 199: | Строка 188: | ||
Другими словами, матрица состояния умножается справа на матрицу <math>\ C</math>. Напомним, что операции сложения и умножения элементов матриц производятся в <math>\ GF(2^8)</math>. |
Другими словами, матрица состояния умножается справа на матрицу <math>\ C</math>. Напомним, что операции сложения и умножения элементов матриц производятся в <math>\ GF(2^8)</math>. |
||
{{iw|MDS-матрица||en|MDS matrix}} — это такая матрица над [[Конечное поле|конечным полем]] <math>\ K</math>, что если взять её в качестве матрицы [[Линейное преобразование|линейного преобразования]] <math>\ f(x)=(MDS)x</math> из пространства <math>\ K^n</math> в пространство <math>\ K^m</math>, то любые два вектора из пространства <math>\ K^{n+m}</math> вида <math>\ (x, f(x))</math> будут иметь как минимум <math>\ m+1</math> различий в компонентах. То есть набор векторов вида <math>\ (x, f(x))</math> образует код, обладающий свойством максимальной разнесённости ({{lang-en|Maximum Distance Separable code}}). Таким кодом является, например, [[код Рида-Соломона]]. |
|||
В Whirlpool свойство максимальной разнесённости MDS-матрицы означает, что общее количество меняющихся байт вектора <math>\ x</math> и вектора <math>\ f(x)=(MDS)x</math> не меньше <math>\ 8+1=9</math>. Другими словами, любое изменение только одного байта <math>\ x</math> приводит к изменению всех 8 байтов <math>\ f(x)</math>. В этом и состоит задача линейной {{iw|Confusion and diffusion|диффузии|en|Confusion and diffusion}}. |
|||
{{Не переведено|:en:MDS matrix | MDS матрица}} — это такая матрица над [[Конечное поле|конечным полем]] <math>\ K</math>, что если взять её в качестве матрицы [[Линейное преобразование|линейного преобразования]] <math>\ f(x)=(MDS)x</math> из пространства <math>\ K^n</math> в пространство <math>\ K^m</math>, то любые два вектора из пространства <math>\ K^{n+m}</math> вида <math>\ (x, f(x))</math> будут иметь как минимум <math>\ m+1</math> различий в компонентах. То есть набор векторов вида <math>\ (x, f(x))</math> образует код, обладающий свойством максимальной разнесённости ({{lang-en|Maximum Distance Separable code}}). Таким кодом является, например, [[код Рида-Соломона]]. |
|||
Как уже упоминалось выше, MDS-матрица в последней (третьей) версии Whirlpool была изменена благодаря статье {{Не переведено|Taizo Shirai||en|Taizo Shirai}} и {{Не переведено|Kyoji Shibutani||en|Kyoji Shibutani}}<ref name=Shirai&Shibutani/>. Они проанализировали MDS-матрицу второй версии Whirlpool и указали на возможность повышения устойчивости Whirlpool к [[Дифференциальный криптоанализ|дифференциальному криптоанализу]]. Также они предложили 224 кандидата на место новой MDS-матрицы. Из этого списка авторы Whirlpool выбрали вариант, наиболее легко реализуемый в аппаратном обеспечении. |
|||
В Whirlpool свойство максимальной разнесённости {{Не переведено|:en:MDS matrix | MDS матрицы}} означает, что общее количество меняющихся байт вектора <math>\ x</math> и вектора <math>\ f(x)=(MDS)x</math> не меньше <math>\ 8+1=9</math>. Другими словами, любое изменение только одного байта <math>\ x</math> приводит к изменению всех 8 байтов <math>\ f(x)</math>. В этом и состоит задача линейной {{Не переведено|:en:Diffusion (cryptography) | диффузии}}. |
|||
Как уже упоминалось выше, {{Не переведено|:en:MDS matrix | MDS матрица}} в последней (третьей) версии Whirlpool была изменена благодаря статье {{Не переведено|:en:Taizo Shirai|Taizo Shirai}} и {{Не переведено|:en:Kyoji Shibutani|Kyoji Shibutani}}<ref name=Shirai&Shibutani/>. Они проанализировали {{Не переведено|:en:MDS matrix | MDS матрицу}} второй версии Whirlpool и указали на возможность повышения устойчивости Whirlpool к [[Дифференциальный криптоанализ|дифференциальному криптоанализу]]. Также они предложили 224 кандидата на место новой {{Не переведено|:en:MDS matrix | MDS матрицы}}. Из этого списка авторы Whirlpool выбрали вариант, наиболее легко реализуемый в аппаратном обеспечении. |
|||
==== Добавление ключа <math>\sigma[k]</math> ==== |
==== Добавление ключа <math>\sigma[k]</math> ==== |
||
Функция добавления ключа <math>\sigma[k]: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> представляет собой побитовое сложение ([[XOR]]) матриц состояния <math>\ a</math> и ключа <math> k \in M_{8 \times 8}[GF(2^8)]</math>: |
Функция добавления ключа <math>\sigma[k]: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> представляет собой побитовое сложение ([[XOR]]) матриц состояния <math>\ a</math> и ключа <math> k \in M_{8 \times 8}[GF(2^8)]</math>: |
||
Строка 214: | Строка 200: | ||
==== Константы раунда <math>c^r</math> ==== |
==== Константы раунда <math>c^r</math> ==== |
||
В каждом раунде <math>\ r, r > 0</math> используется матрица констант <math>c^r \in M_{8 \times 8}[GF(2^8)]</math>, такая, что: |
|||
В каждом раунде <math>\ r, r > 0</math> используется матрица констант <math>c^r \in M_{8 \times 8}[GF(2^8)]</math> такая, что: |
|||
: <math>c_{0j}^r \equiv S[8(r-1)+j], \qquad 0 \leq j \leq 7,</math> |
: <math>c_{0j}^r \equiv S[8(r-1)+j], \qquad 0 \leq j \leq 7,</math> |
||
Строка 225: | Строка 210: | ||
==== Функция раунда <math>\rho[k]</math> ==== |
==== Функция раунда <math>\rho[k]</math> ==== |
||
Для каждого раунда <math>\ r</math> ''функция раунда'' — это составное преобразование <math>\rho[k]: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math>, параметром <math>k</math> которого является матрица ключа <math> k \in M_{8 \times 8}[GF(2^8)]</math>. Описывается ''функция раунда'' следующим образом: |
Для каждого раунда <math>\ r</math> ''функция раунда'' — это составное преобразование <math>\rho[k]: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math>, параметром <math>k</math> которого является матрица ключа <math> k \in M_{8 \times 8}[GF(2^8)]</math>. Описывается ''функция раунда'' следующим образом: |
||
Строка 231: | Строка 215: | ||
=== Расширение ключа === |
=== Расширение ключа === |
||
Для каждого раунда <math>\ r, 0 \leq r \leq R</math> необходим 512-битный [[Ключ (криптография)|ключ шифрования]]. Для решения данной проблемы во многих алгоритмах вводится так называемая процедура ''расширения ключа''. В Whirlpool ''расширение ключа'' реализуется следующим образом: |
|||
Для каждого раунда <math>\ r, 0 \leq r \leq R</math> необходим 512-битный [[Ключ (криптография)|ключ шифрования]]. Для решения данной проблемы во многих алгоритмах вводится так называемая процедура ''расширения ключа''. В Whirlpool ''расширение ключа'' реализуется следующим образом: |
|||
: <math>\ K^0 = K,</math> |
: <math>\ K^0 = K,</math> |
||
: <math>\ K^r = \rho[c^r](K^{r-1}), r > 0.</math> |
: <math>\ K^r = \rho[c^r](K^{r-1}), r > 0.</math> |
||
Таким образом, из известного ключа <math>K</math> производится необходимая последовательность <math>K^0,...,K^R</math> ключей для каждого раунда |
Таким образом, из известного ключа <math>K</math> производится необходимая последовательность <math>K^0,...,K^R</math> ключей для каждого раунда [[блочный шифр|блочного шифра]] <math>W</math>. |
||
=== Блочный шифр <math>W</math> === |
=== Блочный шифр <math>W</math> === |
||
Специальный 512-битный [[блочный шифр]] <math>W[K]: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> в качестве параметра использует 512-битный ключ <math>K</math> и выполняет следующую последовательность преобразований: |
Специальный 512-битный [[блочный шифр]] <math>W[K]: M_{8 \times 8}[GF(2^8)] \to M_{8 \times 8}[GF(2^8)]</math> в качестве параметра использует 512-битный ключ <math>K</math> и выполняет следующую последовательность преобразований: |
||
Строка 246: | Строка 228: | ||
где ключи <math>K^0,...,K^R</math> порождены описанной выше процедурой ''расширения ключа''. |
где ключи <math>K^0,...,K^R</math> порождены описанной выше процедурой ''расширения ключа''. |
||
В |
В [[хеш-функция|хеш-функции]] Whirlpool число раундов <math>R=10</math>. |
||
=== Дополнение входного сообщения === |
=== Дополнение входного сообщения === |
||
Whirlpool, как и любая другая [[хеш-функция]], должна осуществлять [[хеширование]] сообщения произвольной длины. Поскольку внутренний блок шифрования <math>W</math> работает с 512-битными входными сообщениями, то исходное сообщение необходимо разбить на блоки по 512 бит. При этом последний блок, который содержит конец сообщения, может оказаться неполным. |
|||
Для решения данной задачи Whirlpool использует [[Структура Меркла — Дамгора|алгоритм Меркла — Дамгора]] дополнения входного сообщения. Результатом дополнения сообщения <math>M</math> является сообщение <math>M'</math>, длина которого кратна 512. Пусть <math>L</math> — длина исходного сообщения. Тогда <math>M'</math> получается в несколько шагов: |
|||
Whirlpool, как и любая другая [[хеш-функция]], должна осуществлять [[хеширование]] сообщения произвольной длины. Поскольку внутренний блок шифрования <math>W</math> работает с 512-битными входными сообщениями, то исходное сообщение необходимо разбить на блоки по 512 бит. При этом последний блок, который содержит конец сообщения, может оказаться не полным. |
|||
Для решения данной задачи Whirlpool использует алгоритм {{Не переведено|:en:Merkle–Damgård construction | Меркле-Дамгаарда}} дополнения входного сообщения. Результатом дополнения сообщения <math>M</math> является сообщение <math>M'</math>, длина которого кратна 512. Пусть <math>L</math> — длина исходного сообщения. Тогда <math>M'</math> получается в несколько шагов: |
|||
# К концу сообщения <math>M</math> приписать бит «1». |
# К концу сообщения <math>M</math> приписать бит «1». |
||
# Приписать <math>x</math> битов «0» так, чтобы длина полученной строки <math>L+1+x</math> была кратна <math>256</math> нечетное число раз. |
# Приписать <math>x</math> битов «0» так, чтобы длина полученной строки <math>L+1+x</math> была кратна <math>256</math> нечетное число раз. |
||
Строка 264: | Строка 245: | ||
=== Функция сжатия === |
=== Функция сжатия === |
||
[[Файл:Miyaguchi-Preneel.PNG|thumbnail|300px| '''Функция сжатия Whirlpool''']] |
[[Файл:Miyaguchi-Preneel.PNG|thumbnail|300px| '''Функция сжатия Whirlpool''']] |
||
В Whirlpool применяется схема хеширования {{Не переведено| |
В Whirlpool применяется схема хеширования {{Не переведено|Miyaguchi-Preneel||en|Miyaguchi-Preneel}}. |
||
<math>\ t</math> блоков <math>m_i, 1 \leq i \leq t</math> дополненного сообщения <math>M'</math> последовательно шифруются |
<math>\ t</math> блоков <math>m_i, 1 \leq i \leq t</math> дополненного сообщения <math>M'</math> последовательно шифруются [[блочный шифр|блочным шифром]] <math>W</math>: |
||
Строка 276: | Строка 256: | ||
: <math>H_i = W[H_{i-1}](\eta_i)\oplus H_{i-1}\oplus \eta_i, 1 \leq i \leq t,</math> |
: <math>H_i = W[H_{i-1}](\eta_i)\oplus H_{i-1}\oplus \eta_i, 1 \leq i \leq t,</math> |
||
где <math>IV</math> ({{lang-en|initialization vector}}, {{Не переведено| |
где <math>IV</math> ({{lang-en|initialization vector}}, {{Не переведено|вектор инициализации||en|initialization vector}}) — 512-битная строка, заполненная «0». |
||
=== Вычисление хеша === |
=== Вычисление хеша === |
||
Дайджестом для сообщения <math>M</math> является выходное значение <math>H_t</math> функции сжатия, преобразованное обратно в 512-битную строку: |
Дайджестом для сообщения <math>M</math> является выходное значение <math>H_t</math> функции сжатия, преобразованное обратно в 512-битную строку: |
||
Строка 287: | Строка 266: | ||
[[Хеш-функция]] <math>H</math> считается [[криптографическая стойкость|криптографически стойкой]], если она удовлетворяет трём основным требованиям, на которых основано большинство применений [[Хеш-функция|хеш-функций]] в [[Криптография|криптографии]]: ''необратимость'', стойкость к ''[[коллизия хеш-функции|коллизиям]] первого рода'' и стойкость к ''[[коллизия хеш-функции|коллизиям]] второго рода''. |
[[Хеш-функция]] <math>H</math> считается [[криптографическая стойкость|криптографически стойкой]], если она удовлетворяет трём основным требованиям, на которых основано большинство применений [[Хеш-функция|хеш-функций]] в [[Криптография|криптографии]]: ''необратимость'', стойкость к ''[[коллизия хеш-функции|коллизиям]] первого рода'' и стойкость к ''[[коллизия хеш-функции|коллизиям]] второго рода''. |
||
Пусть <math>h_n</math> — произвольная <math>n</math>-битная подстрока 512-битного [[Хеш|хеша]] Whirlpool. Авторы Whirlpool утверждают, что созданная ими [[хеш-функция]] удовлетворяет следующим требованиям [[криптографическая стойкость|криптостойкости]]: |
Пусть <math>h_n</math> — произвольная <math>n</math>-битная подстрока 512-битного [[Хеш-сумма|хеша]] Whirlpool. Авторы Whirlpool утверждают, что созданная ими [[хеш-функция]] удовлетворяет следующим требованиям [[криптографическая стойкость|криптостойкости]]: |
||
* Генерация [[коллизия хеш-функции|коллизии]] требует порядка <math>2^{n/2}</math> вычислений [[хеш]] |
* Генерация [[коллизия хеш-функции|коллизии]] требует порядка <math>2^{n/2}</math> вычислений [[хеш-сумма|хеша]] WHIRLPOOL (стойкость к ''[[коллизия хеш-функции|коллизиям]] второго рода''). |
||
* Для заданной <math>h_n</math> поиск такого сообщения <math>M</math>, что <math>H(M)=h_n</math>, потребует порядка <math>2^{n}</math> вычислений [[хеш]] |
* Для заданной <math>h_n</math> поиск такого сообщения <math>M</math>, что <math>H(M)=h_n</math>, потребует порядка <math>2^{n}</math> вычислений [[хеш-сумма|хеша]] WHIRLPOOL (''необратимость''). |
||
* Для заданного сообщения <math>M</math> обнаружение другого сообщения <math>N</math>, для которого <math>H(N)=H(M)</math>, потребует порядка <math>2^{n}</math> вычислений [[хеш]] |
* Для заданного сообщения <math>M</math> обнаружение другого сообщения <math>N</math>, для которого <math>H(N)=H(M)</math>, потребует порядка <math>2^{n}</math> вычислений [[хеш-сумма|хеша]] WHIRLPOOL (стойкость к ''[[коллизия хеш-функции|коллизиям]] первого рода''). |
||
* Невозможно обнаружить систематические корреляции между любой линейной комбинацией входных бит и любой линейной комбинацией бит [[Хеш|хеша]] или предсказать, какие биты |
* Невозможно обнаружить систематические корреляции между любой линейной комбинацией входных бит и любой линейной комбинацией бит [[Хеш-сумма|хеша]] или предсказать, какие биты хеша изменят своё значение при изменении определённых входных бит (стойкость к [[Линейный криптоанализ|линейному криптоанализу]] и [[Дифференциальный криптоанализ|дифференциальному криптоанализу]]). |
||
К данному заявлению авторы Whirlpool добавили примечание: |
К данному заявлению авторы Whirlpool добавили примечание: |
||
<blockquote> |
<blockquote> |
||
Эти утверждения вытекают из значительного запаса прочности относительно всех известных атак. Тем не менее мы понимаем, что невозможно сделать не спекулятивные утверждения о неизвестных вещах. |
Эти утверждения вытекают из значительного запаса прочности относительно всех известных атак. Тем не менее, мы понимаем, что невозможно сделать не спекулятивные утверждения о неизвестных вещах. |
||
</blockquote> |
</blockquote> |
||
=== Криптоанализ === |
=== Криптоанализ === |
||
На сегодняшний день WHIRLPOOL устойчива ко всем видам [[криптоанализ]]а. На протяжении 8 лет существования Whirlpool не было зарегистрировано ни одной атаки на неё. |
На сегодняшний день WHIRLPOOL устойчива ко всем видам [[криптоанализ]]а. На протяжении 8 лет существования Whirlpool не было зарегистрировано ни одной атаки на неё. |
||
Однако |
Однако в 2009 году был опубликован новый способ атаки на [[хеш-функция|хеш-функции]] — ''[[Rebound attack|The Rebound Attack]]''<ref name=RApresentation>{{cite web |
||
<ref name=RApresentation> |
|||
{{cite web |
|||
| url = https://www.cosic.esat.kuleuven.be/fse2009/slides/2402_1150_Schlaeffer.pdf |
| url = https://www.cosic.esat.kuleuven.be/fse2009/slides/2402_1150_Schlaeffer.pdf |
||
| title = The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl |
| title = The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl |
||
| |
| date = 2009-02-24 |
||
| author = Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. |
| author = Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. |
||
| accessdate = |
| accessdate = 2019-06-25 |
||
| lang = en |
| lang = en |
||
| description = презентация нового способа криптоанализа и его применения для криптоанализа хеш-функций Whirlpool и |
| description = презентация нового способа криптоанализа и его применения для криптоанализа хеш-функций Whirlpool и [[Grøstl]] |
||
| archive-date = 2011-09-28 |
|||
}} |
|||
| archive-url = https://web.archive.org/web/20110928092455/https://www.cosic.esat.kuleuven.be/fse2009/slides/2402_1150_Schlaeffer.pdf |
|||
</ref> |
|||
| deadlink = no |
|||
<ref name=RAarticle> |
|||
{{cite web |
}}</ref><ref name=RAarticle>{{cite web |
||
| url = |
| url = https://link.springer.com/chapter/10.1007%2F978-3-642-03317-9_16 |
||
| title = The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl |
| title = The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl |
||
| |
| date = 2009 |
||
| author = Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. |
| author = Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. |
||
| accessdate = |
| accessdate = 2019-06-25 |
||
| lang = en |
| lang = en |
||
| description = статья о новом способе криптоанализа и его применении для криптоанализа хеш-функций Whirlpool и |
| description = статья о новом способе криптоанализа и его применении для криптоанализа хеш-функций Whirlpool и [[Grøstl]] |
||
| archive-date = 2018-11-18 |
|||
}} |
|||
| archive-url = https://web.archive.org/web/20181118124105/https://link.springer.com/chapter/10.1007/978-3-642-03317-9_16 |
|||
</ref>. |
|||
| deadlink = no |
|||
Первыми «подопытными» новой атаки стали [[хеш-функция|хеш-функции]] Whirlpool и {{Не переведено|:en:Grøstl | Grøstl}}. Результаты проведённого [[криптоанализ]]а приведены в таблице. |
|||
}}</ref>. |
|||
Первыми «подопытными» новой атаки стали [[хеш-функция|хеш-функции]] Whirlpool и [[Grøstl]]. Результаты проведённого [[криптоанализ]]а приведены в таблице. |
|||
{| border="1" class="standard" align="center" |
{| border="1" class="standard" align="center" |
||
|+ Таблица 2. Результаты [[криптоанализ]]а |
|+ Таблица 2. Результаты [[криптоанализ]]а [[хеш-функция|хеш-функций]] Whirlpool и [[Grøstl]] по методу [[Rebound attack|The Rebound Attack]]<ref name=RApresentation/><ref name=RAarticle/> |
||
![[Хеш-функция]] |
![[Хеш-функция]] |
||
!Число раундов |
!Число раундов |
||
Строка 349: | Строка 327: | ||
Авторы исследования использовали следующие понятия и термины: |
Авторы исследования использовали следующие понятия и термины: |
||
* <math>\ IV</math> — {{Не переведено| |
* <math>\ IV</math> — {{Не переведено|вектор инициализации||en|initialization vector}} |
||
* <math>\ M</math> — сообщение, подлежащее [[хеширование|хешированию]] |
* <math>\ M</math> — сообщение, подлежащее [[хеширование|хешированию]] |
||
* <math>\ h(M,IV)</math> — [[хеш-функция]] |
* <math>\ h(M,IV)</math> — [[хеш-функция]] |
||
Строка 359: | Строка 337: | ||
** <math>\ IV</math> — фиксирован |
** <math>\ IV</math> — фиксирован |
||
** <math>f(M_t, IV) = f(M_t', IV), M_t \neq M_t'</math> |
** <math>f(M_t, IV) = f(M_t', IV), M_t \neq M_t'</math> |
||
* ''почти коллизия'': |
* ''почти коллизия'': |
||
** <math>\ IV</math> — фиксирован |
** <math>\ IV</math> — фиксирован |
||
** <math>f_{M_t} = f(M_t, IV), f_{M_t'} = f(M_t', IV), M_t \neq M_t'</math> |
** <math>f_{M_t} = f(M_t, IV), f_{M_t'} = f(M_t', IV), M_t \neq M_t'</math> |
||
** небольшое число бит |
** небольшое число бит [[Хеш-сумма|хешей]] <math>f_{M_t}</math> и <math>f_{M_t'}</math> различны |
||
* ''полусвободная коллизия'': |
* ''полусвободная коллизия'': |
||
** <math>f(M_t, H_{t-1}) = f(M_t', H_{t-1}), M_t \neq M_t'</math> |
** <math>f(M_t, H_{t-1}) = f(M_t', H_{t-1}), M_t \neq M_t'</math> |
||
* ''свободная коллизия'': |
* ''свободная коллизия'': |
||
** <math>f(M_t, H_{t-1}) = f(M_t', H_{t-1}'), M_t \neq M_{t-1}', H_t \neq H_{t-1}'</math> |
** <math>f(M_t, H_{t-1}) = f(M_t', H_{t-1}'), M_t \neq M_{t-1}', H_t \neq H_{t-1}'</math> |
||
Как видно из таблицы, сгенерировать коллизию для Whirlpool удалось лишь для её «урезанного» варианта в 4.5 раунда. К тому же |
Как видно из таблицы, сгенерировать коллизию для Whirlpool удалось лишь для её «урезанного» варианта в 4.5 раунда. К тому же сложность необходимых вычислений довольно высока. |
||
== Применение == |
== Применение == |
||
Whirlpool — свободно распространяемая [[хеш-функция]]. Поэтому она находит широкое применение в [[Открытое программное обеспечение|открытом программном обеспечении]]. Здесь перечислены некоторые примеры использования Whirlpool: |
Whirlpool — свободно распространяемая [[хеш-функция]]. Поэтому она находит широкое применение в [[Открытое программное обеспечение|открытом программном обеспечении]]. Здесь перечислены некоторые примеры использования Whirlpool: |
||
* [[Jacksum]] — свободно распространяемая утилита для вычисления [[Контрольная сумма|контрольных сумм]] |
* [[Jacksum]] — свободно распространяемая утилита для вычисления [[Контрольная сумма|контрольных сумм]] |
||
* [[Crypto++]] — свободно распространяемая C++ библиотека классов криптографических примитивов |
* [[Crypto++]] — свободно распространяемая C++ библиотека классов криптографических примитивов |
||
* [[TrueCrypt]] — бесплатная программа для шифрования «на лету» |
|||
* [[ |
* [[FreeOTFE]] — свободная бесплатная программа с [[Открытое программное обеспечение|открытым кодом]], предназначенная для [[шифрование|шифрования]] «на лету». |
||
* [[DarkCrypt]] — свободно распространяемая крипто- и стеганографическая утилита в виде плагина для [[Total Commander]] |
|||
* [[FreeOTFE]] — это свободная бесплатная программа с [[Open source|открытым кодом]], предназначенная для [[шифрование|шифрования]] «на лету». Выпускается для [[операционная система|операционных систем]] [[Windows]] и [[Windows Mobile]] (FreeOTFE4PDA) |
|||
* [[DarkCrypt]] — свободно распространяемая крипто- и стеганографическая утилита в виде плагина для [[Total Commander]] |
|||
=== Примеры хешей === |
=== Примеры хешей === |
||
Для удобства 512 бит (64 байта) |
Для удобства 512 бит (64 байта) хеша Whirlpool часто представляются в виде 128-значного шестнадцатеричного числа. |
||
Как говорилось выше, алгоритм потерпел два изменения с момента выпуска в 2000 году. |
Как говорилось выше, алгоритм потерпел два изменения с момента выпуска в 2000 году. |
||
Ниже приведены примеры |
Ниже приведены примеры хешей, вычисленных по [[ASCII]] тексту [[панграмма|панграммы]] [[The quick brown fox jumps over the lazy dog]] для всех трех версий Whirlpool: |
||
Whirlpool-0("The quick brown fox jumps over the lazy dog") = |
Whirlpool-0("The quick brown fox jumps over the lazy dog") = |
||
Строка 406: | Строка 376: | ||
D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35 |
D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35 |
||
Даже небольшое изменение исходного текста сообщения (в данном случае подменяется одна буква: символ «d» заменяется на символ «e») приводит к полному изменению [[Хеш|хеша]]: |
Даже небольшое изменение исходного текста сообщения (в данном случае подменяется одна буква: символ «d» заменяется на символ «e») приводит к полному изменению [[Хеш-сумма|хеша]]: |
||
Whirlpool-0("The quick brown fox jumps over the lazy eog") = |
Whirlpool-0("The quick brown fox jumps over the lazy eog") = |
||
228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A |
228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A |
||
Строка 419: | Строка 389: | ||
0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C |
0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C |
||
Добавление символов в строку, конкатенация строк и другие изменения также влияют на результат. |
Добавление символов в строку, [[конкатенация]] строк и другие изменения также влияют на результат. |
||
Примеры [[Хеш|хешей]] для «нулевой» строки: |
Примеры [[Хеш-сумма|хешей]] для «нулевой» строки: |
||
Whirlpool-0("") = |
Whirlpool-0("") = |
||
B3E1AB6EAF640A34F784593F2074416ACCD3B8E62C620175FCA0997B1BA23473 |
B3E1AB6EAF640A34F784593F2074416ACCD3B8E62C620175FCA0997B1BA23473 |
||
Строка 442: | Строка 412: | ||
|- |
|- |
||
| [[PHP]] 5.0 |
| [[PHP]] 5.0 |
||
| valign="top" | |
| valign="top" | <pre>echo hash( 'whirlpool', 'test' );</pre> |
||
| valign="top" | |
| valign="top" | |
||
<pre>b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f |
<pre>b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f |
||
8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6</pre> |
8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6</pre> |
||
|- |
|- |
||
| [[Ruby]] |
| [[Ruby]] |
||
| valign="top" | |
| valign="top" | <pre>puts Whirlpool.calc_hex('test')</pre> |
||
| valign="top" | |
| valign="top" | |
||
<pre>b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f |
<pre>b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f |
||
8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6</pre> |
8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6</pre> |
||
Строка 458: | Строка 428: | ||
== Ссылки == |
== Ссылки == |
||
* {{cite web |
* {{cite web |
||
| |
|url = http://www.larc.usp.br/~pbarreto/WhirlpoolPage.html |
||
| |
|title = Whirlpool homepage |
||
| |
|accessdate = 2019-06-25 |
||
| |
|lang = en |
||
| |
|description = главная страница Whirlpool |
||
| |
|archiveurl = https://web.archive.org/web/20171129084214/http://www.larc.usp.br/~pbarreto/WhirlpoolPage.html |
||
| |
|archivedate = 2017-11-29 |
||
}} |
|||
* {{cite web |
|||
| url = http://hash.online-convert.com/whirlpool-generator |
|||
| title = Calculate a Whirlpool hash |
|||
| accessdate = 16 ноября 2009 |
|||
| lang = en |
|||
| description = он-лайн вычисление хешей Whirlpool |
|||
| archiveurl = http://www.webcitation.org/65p0UDGco |
|||
| archivedate = 2012-02-29 |
|||
}} |
}} |
||
=== Стандарты === |
=== Стандарты === |
||
* {{cite web |
* {{cite web |
||
| |
|url = https://www.iso.org/standard/39876.html |
||
| |
|title = The ISO/IEC 10118-3:2004 standard |
||
| |
|accessdate = 2019-06-25 |
||
| |
|lang = en |
||
| |
|description = стандарт ISO/IEC 10118-3:2004 |
||
| |
|archiveurl = |
||
| |
|archivedate = |
||
}} |
}} |
||
* {{cite web |
* {{cite web |
||
|url = https://www.cosic.esat.kuleuven.be/nessie/ |
|||
|title = NESSIE |
|||
|accessdate = 2019-06-25 |
|||
|lang = en |
|||
|description = {{lang-en|New European Schemes for Signatures, Integrity and Encryption}}, новые европейские проекты по цифровой подписи, целостности и шифрованию |
|||
|archiveurl = |
|||
|archiveurl=http://www.webcitation.org/65p0W5Ozj|archivedate=2012-02-29}} |
|||
|archivedate = |
|||
}} |
|||
* {{cite web |
* {{cite web |
||
| url = https://www.cosic.esat.kuleuven.be/nessie/deliverables/decision-final.pdf |
| url = https://www.cosic.esat.kuleuven.be/nessie/deliverables/decision-final.pdf |
||
| title = Portfolio of recommended cryptographic primitives |
| title = Portfolio of recommended cryptographic primitives |
||
| accessdate = |
| accessdate = 2019-06-25 |
||
| lang = en |
| lang = en |
||
| description = перечень рекомендованных к использованию криптографических функций NESSIE |
| description = перечень рекомендованных к использованию криптографических функций NESSIE |
||
Строка 505: | Строка 467: | ||
=== Программные реализации === |
=== Программные реализации === |
||
* {{cite web |
* {{cite web |
||
| |
|url = http://www.jonelo.de/java/jacksum/index.html |
||
| |
|title = A Java implementation of all three revisions of Whirlpool |
||
| |
|accessdate = 2009-11-15 |
||
| |
|lang = en |
||
| |
|description = реализация всех трех модификаций Whirlpool на языке программирования [[Java]] |
||
| |
|archiveurl = https://www.webcitation.org/65p0WZQa4?url=http://www.jonelo.de/java/jacksum/index.html |
||
| |
|archivedate = 2012-02-29 |
||
}} |
}} |
||
* {{cite web |
* {{cite web |
||
| |
|url = http://www.karljapetre.com/whirlpool/ |
||
| |
|title = A Matlab Implementation of the Whirlpool Hashing Function |
||
| |
|accessdate = 2009-11-15 |
||
| |
|lang = en |
||
| |
|description = реализация Whirlpool в пакете [[Matlab]] |
||
| |
|archiveurl = https://www.webcitation.org/65p0XVMV7?url=http://www.karljapetre.com/whirlpool/ |
||
| |
|archivedate = 2012-02-29 |
||
}} |
}} |
||
* {{cite web |
* {{cite web |
||
| url = |
| url = https://metacpan.org/module/Digest::Whirlpool |
||
| title = Perl Whirlpool module at CPAN |
| title = Perl Whirlpool module at CPAN |
||
| accessdate = 15 ноября 2009 |
|||
| lang = en |
| lang = en |
||
| description = модуль Whirlpool на языке [[Perl]] в [[CPAN]] |
| description = модуль Whirlpool на языке [[Perl]] в [[CPAN]] |
||
| deadlink = 404 |
|||
| archiveurl = http://web.archive.org/20071210185636/search.cpan.org/~avar/Digest-Whirlpool-1.0.6/ |
|||
| archivedate = 2007-12-10 |
|||
}} |
}} |
||
* {{cite web |
* {{cite web |
||
| |
|url = http://raa.ruby-lang.org/project/whirlpool/ |
||
| |
|title = Ruby Whirlpool library |
||
| |
|accessdate = 2009-11-15 |
||
| |
|lang = en |
||
| |
|description = библиотека [[Ruby]] с реализацией Whirlpool |
||
| |
|archiveurl = https://www.webcitation.org/65p0XxjKK?url=http://raa.ruby-lang.org/project/whirlpool/ |
||
| |
|archivedate = 2012-02-29 |
||
}} |
}} |
||
=== Аппаратные реализации === |
=== Аппаратные реализации === |
||
* {{cite web |
* {{cite web |
||
| |
|url = http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1277864 |
||
| |
|title = Efficient architecture and hardware implementation of the Whirlpool hash function |
||
| |
|accessdate = 2009-11-18 |
||
| |
|lang = en |
||
| |
|description = Эффективная аппаратная реализация Whirlpool. Статья ''IEEE Transactions on Consumer Electronics'' |
||
| |
|archiveurl = https://www.webcitation.org/65p0YWH5h?url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true |
||
| |
|archivedate = 2012-02-29 |
||
}} |
}} |
||
* {{cite web |
* {{cite web |
||
| |
|url = http://www.sersc.org/journals/IJAST/vol7/3.pdf |
||
| |
|title = High-Speed Parallel Architecture of the Whirlpool Hash Function |
||
| |
|accessdate = 2009-11-18 |
||
| |
|lang = en |
||
| |
|description = Высокоскоростная параллельная архитектура Whirlpool. Статья журнала ''International Journal of Advanced Science and Technology'', выпуск 7, Июнь, 2009 |
||
| |
|archiveurl = https://www.webcitation.org/65p0ZFFyq?url=http://www.sersc.org/journals/IJAST/vol7/3.pdf |
||
| |
|archivedate = 2012-02-29 |
||
}} |
}} |
||
{{Хеш-алгоритмы}} |
{{Хеш-алгоритмы}} |
||
{{Стандарты ISO}} |
|||
[[Категория:Криптографические хеш-функции]] |
Текущая версия от 01:12, 17 июня 2023
Whirlpool | |
---|---|
Разработчики |
Винсент Рэймен, Пауло Баррето[англ.] |
Впервые опубликован | ноябрь 2000 |
Стандарты | NESSIE Portfolio (2003), ISO/IEC 10118-3:2004 (2004) |
Размер хеша | 512 бит |
Число раундов | 10 |
Тип | хеш-функция |
Whirlpool — криптографическая хеш-функция, разработанная Винсентом Рэйменом и Пауло Баррето[англ.]. Опубликована в ноябре 2000 года. Хеширует входное сообщение с длиной до битов. Выходное значение хеш-функции Whirlpool, называемое хешем, составляет 512 битов.
История
[править | править код]Название
[править | править код]Хеш-функция Whirlpool названа в честь Галактики Водоворот (M51) в созвездии Гончие Псы — первой галактики с наблюдаемой спиральной структурой.
Модификации
[править | править код]С момента создания в 2000 году Whirlpool дважды модифицировалась.
Первая версия, Whirlpool-0, представлена как кандидат в проекте NESSIE (англ. New European Schemes for Signatures, Integrity and Encryption, новые европейские проекты по цифровой подписи, целостности и шифрованию).
Модификация Whirlpool-0, названная Whirlpool-T, в 2003 году добавлена в перечень рекомендованных к использованию криптографических функций NESSIE. Изменения касались блока подстановки (S-box) Whirlpool: в первой версии структура S-box не была описана, и он генерировался произвольно, что создавало определённые проблемы при аппаратной реализации Whirlpool. В версии Whirlpool-T S-box «приобрёл» чёткую структуру.
Дефект в диффузных матрицах Whirlpool-T, обнаруженный Тайдзо Сираем[англ.] и Кёдзи Сибутани[англ.][1], впоследствии исправлен, и конечная (третья) версия, названная для краткости просто Whirlpool, принята ISO в стандарте ISO/IEC 10118-3:2004 в 2004 году.
Описание
[править | править код]Основная версия — хеш-функции — третья; в отличие от первой версии, S-box определён, а диффузная матрица заменена на новую после доклада Сирая и Сибутани[1].
Whirlpool состоит из повторного применения функции сжатия, основой которой является специальный 512-битный блочный шифр с 512-битным ключом.
В алгоритме используются операции в поле Галуа по модулю неприводимого многочлена .
Многочлены для краткости записываются в шестнадцатеричном представлении. Например, запись означает .
- Символом обозначается оператор композиции[англ.]. Выражение означает композицию функций и .
- Для обозначения композиции последовательности функций используется символ :
- — множество матриц над
- — циркулянтная матрица , первая строка которой состоит из элементов то есть:
- или просто
Формат данных
[править | править код]Whirlpool построен на специальном блочном шифре , который работает с 512-битными данными.
В преобразованиях промежуточный результат вычисления хеша называется хеш-состоянием или просто состоянием. При вычислениях состояние обычно представляется матрицей состояния. Для Whirlpool это матрица в . Следовательно, 512-битные блоки данных должны быть преобразованы в этот формат перед дальнейшими вычислениями. Это достигается введением функции :
Проще говоря, заполнение матрицы состояния данными происходит построчно. При этом каждый байт матрицы представляет собой соответствующий многочлен в .
Преобразования
[править | править код]Нелинейное преобразование (S-box)
[править | править код]Функция состоит из параллельного применения блока подстановки (S-box) ко всем байтам матрицы состояния:
Блок подстановки описывается следующей таблицей замен:
|
||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
||||||||||||||||
|
Циклическая перестановка
[править | править код]Перестановка циклически сдвигает каждый столбец матрицы состояния так, что столбец сдвигается вниз на позиций:
Задача данного преобразования — перемешать байты строк матрицы состояния между собой.
Линейная диффузия
[править | править код]Линейная диффузия — это линейное преобразование, матрицей которого является MDS-матрица[англ.] , то есть:
- так что
Другими словами, матрица состояния умножается справа на матрицу . Напомним, что операции сложения и умножения элементов матриц производятся в .
MDS-матрица[англ.] — это такая матрица над конечным полем , что если взять её в качестве матрицы линейного преобразования из пространства в пространство , то любые два вектора из пространства вида будут иметь как минимум различий в компонентах. То есть набор векторов вида образует код, обладающий свойством максимальной разнесённости (англ. Maximum Distance Separable code). Таким кодом является, например, код Рида-Соломона.
В Whirlpool свойство максимальной разнесённости MDS-матрицы означает, что общее количество меняющихся байт вектора и вектора не меньше . Другими словами, любое изменение только одного байта приводит к изменению всех 8 байтов . В этом и состоит задача линейной диффузии[англ.].
Как уже упоминалось выше, MDS-матрица в последней (третьей) версии Whirlpool была изменена благодаря статье Taizo Shirai[англ.] и Kyoji Shibutani[англ.][1]. Они проанализировали MDS-матрицу второй версии Whirlpool и указали на возможность повышения устойчивости Whirlpool к дифференциальному криптоанализу. Также они предложили 224 кандидата на место новой MDS-матрицы. Из этого списка авторы Whirlpool выбрали вариант, наиболее легко реализуемый в аппаратном обеспечении.
Добавление ключа
[править | править код]Функция добавления ключа представляет собой побитовое сложение (XOR) матриц состояния и ключа :
Константы раунда
[править | править код]В каждом раунде используется матрица констант , такая, что:
Отсюда видно, что первая строка матрицы является результатом применения блока подстановки к байтовым числам .
Остальные 7 строк — нулевые.
Функция раунда
[править | править код]Для каждого раунда функция раунда — это составное преобразование , параметром которого является матрица ключа . Описывается функция раунда следующим образом:
Расширение ключа
[править | править код]Для каждого раунда необходим 512-битный ключ шифрования. Для решения данной проблемы во многих алгоритмах вводится так называемая процедура расширения ключа. В Whirlpool расширение ключа реализуется следующим образом:
Таким образом, из известного ключа производится необходимая последовательность ключей для каждого раунда блочного шифра .
Блочный шифр
[править | править код]Специальный 512-битный блочный шифр в качестве параметра использует 512-битный ключ и выполняет следующую последовательность преобразований:
где ключи порождены описанной выше процедурой расширения ключа. В хеш-функции Whirlpool число раундов .
Дополнение входного сообщения
[править | править код]Whirlpool, как и любая другая хеш-функция, должна осуществлять хеширование сообщения произвольной длины. Поскольку внутренний блок шифрования работает с 512-битными входными сообщениями, то исходное сообщение необходимо разбить на блоки по 512 бит. При этом последний блок, который содержит конец сообщения, может оказаться неполным.
Для решения данной задачи Whirlpool использует алгоритм Меркла — Дамгора дополнения входного сообщения. Результатом дополнения сообщения является сообщение , длина которого кратна 512. Пусть — длина исходного сообщения. Тогда получается в несколько шагов:
- К концу сообщения приписать бит «1».
- Приписать битов «0» так, чтобы длина полученной строки была кратна нечетное число раз.
- Наконец, приписать 256-битное представление числа .
Дополненное сообщение записывается в виде
и разбивается на 512-битные блоки для дальнейшей обработки.
Функция сжатия
[править | править код]В Whirlpool применяется схема хеширования Miyaguchi-Preneel[англ.].
блоков дополненного сообщения последовательно шифруются блочным шифром :
где (англ. initialization vector, вектор инициализации[англ.]) — 512-битная строка, заполненная «0».
Вычисление хеша
[править | править код]Дайджестом для сообщения является выходное значение функции сжатия, преобразованное обратно в 512-битную строку:
Криптостойкость
[править | править код]Хеш-функция считается криптографически стойкой, если она удовлетворяет трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии: необратимость, стойкость к коллизиям первого рода и стойкость к коллизиям второго рода.
Пусть — произвольная -битная подстрока 512-битного хеша Whirlpool. Авторы Whirlpool утверждают, что созданная ими хеш-функция удовлетворяет следующим требованиям криптостойкости:
- Генерация коллизии требует порядка вычислений хеша WHIRLPOOL (стойкость к коллизиям второго рода).
- Для заданной поиск такого сообщения , что , потребует порядка вычислений хеша WHIRLPOOL (необратимость).
- Для заданного сообщения обнаружение другого сообщения , для которого , потребует порядка вычислений хеша WHIRLPOOL (стойкость к коллизиям первого рода).
- Невозможно обнаружить систематические корреляции между любой линейной комбинацией входных бит и любой линейной комбинацией бит хеша или предсказать, какие биты хеша изменят своё значение при изменении определённых входных бит (стойкость к линейному криптоанализу и дифференциальному криптоанализу).
К данному заявлению авторы Whirlpool добавили примечание:
Эти утверждения вытекают из значительного запаса прочности относительно всех известных атак. Тем не менее, мы понимаем, что невозможно сделать не спекулятивные утверждения о неизвестных вещах.
Криптоанализ
[править | править код]На сегодняшний день WHIRLPOOL устойчива ко всем видам криптоанализа. На протяжении 8 лет существования Whirlpool не было зарегистрировано ни одной атаки на неё.
Однако в 2009 году был опубликован новый способ атаки на хеш-функции — The Rebound Attack[2][3]. Первыми «подопытными» новой атаки стали хеш-функции Whirlpool и Grøstl. Результаты проведённого криптоанализа приведены в таблице.
Хеш-функция | Число раундов | Сложность | Требуемый объём памяти | Тип коллизии |
---|---|---|---|---|
Whirlpool | коллизия | |||
полусвободная коллизия | ||||
полусвободная почти коллизия | ||||
Grøstl-256 | полусвободная коллизия |
Авторы исследования использовали следующие понятия и термины:
- — вектор инициализации[англ.]
- — сообщение, подлежащее хешированию
- — хеш-функция
- функция сжатия
Типы коллизий:
- коллизия:
- — фиксирован
- почти коллизия:
- — фиксирован
- небольшое число бит хешей и различны
- полусвободная коллизия:
- свободная коллизия:
Как видно из таблицы, сгенерировать коллизию для Whirlpool удалось лишь для её «урезанного» варианта в 4.5 раунда. К тому же сложность необходимых вычислений довольно высока.
Применение
[править | править код]Whirlpool — свободно распространяемая хеш-функция. Поэтому она находит широкое применение в открытом программном обеспечении. Здесь перечислены некоторые примеры использования Whirlpool:
- Jacksum — свободно распространяемая утилита для вычисления контрольных сумм
- Crypto++ — свободно распространяемая C++ библиотека классов криптографических примитивов
- TrueCrypt — бесплатная программа для шифрования «на лету»
- FreeOTFE — свободная бесплатная программа с открытым кодом, предназначенная для шифрования «на лету».
- DarkCrypt — свободно распространяемая крипто- и стеганографическая утилита в виде плагина для Total Commander
Примеры хешей
[править | править код]Для удобства 512 бит (64 байта) хеша Whirlpool часто представляются в виде 128-значного шестнадцатеричного числа.
Как говорилось выше, алгоритм потерпел два изменения с момента выпуска в 2000 году. Ниже приведены примеры хешей, вычисленных по ASCII тексту панграммы The quick brown fox jumps over the lazy dog для всех трех версий Whirlpool:
Whirlpool-0("The quick brown fox jumps over the lazy dog") = 4F8F5CB531E3D49A61CF417CD133792CCFA501FD8DA53EE368FED20E5FE0248C 3A0B64F98A6533CEE1DA614C3A8DDEC791FF05FEE6D971D57C1348320F4EB42D
Whirlpool-T("The quick brown fox jumps over the lazy dog") = 3CCF8252D8BBB258460D9AA999C06EE38E67CB546CFFCF48E91F700F6FC7C183 AC8CC3D3096DD30A35B01F4620A1E3A20D79CD5168544D9E1B7CDF49970E87F1
Whirlpool("The quick brown fox jumps over the lazy dog") = B97DE512E91E3828B40D2B0FDCE9CEB3C4A71F9BEA8D88E75C4FA854DF36725F D2B52EB6544EDCACD6F8BEDDFEA403CB55AE31F03AD62A5EF54E42EE82C3FB35
Даже небольшое изменение исходного текста сообщения (в данном случае подменяется одна буква: символ «d» заменяется на символ «e») приводит к полному изменению хеша:
Whirlpool-0("The quick brown fox jumps over the lazy eog") = 228FBF76B2A93469D4B25929836A12B7D7F2A0803E43DABA0C7FC38BC11C8F2A 9416BBCF8AB8392EB2AB7BCB565A64AC50C26179164B26084A253CAF2E012676
Whirlpool-T("The quick brown fox jumps over the lazy eog") = C8C15D2A0E0DE6E6885E8A7D9B8A9139746DA299AD50158F5FA9EECDDEF744F9 1B8B83C617080D77CB4247B1E964C2959C507AB2DB0F1F3BF3E3B299CA00CAE3 Whirlpool("The quick brown fox jumps over the lazy eog") = C27BA124205F72E6847F3E19834F925CC666D0974167AF915BB462420ED40CC5 0900D85A1F923219D832357750492D5C143011A76988344C2635E69D06F2D38C
Добавление символов в строку, конкатенация строк и другие изменения также влияют на результат.
Примеры хешей для «нулевой» строки:
Whirlpool-0("") = B3E1AB6EAF640A34F784593F2074416ACCD3B8E62C620175FCA0997B1BA23473 39AA0D79E754C308209EA36811DFA40C1C32F1A2B9004725D987D3635165D3C8
Whirlpool-T("") = 470F0409ABAA446E49667D4EBE12A14387CEDBD10DD17B8243CAD550A089DC0F EEA7AA40F6C2AAAB71C6EBD076E43C7CFCA0AD32567897DCB5969861049A0F5A
Whirlpool("") = 19FA61D75522A4669B44E39C1D2E1726C530232130D407F89AFEE0964997F7A7 3E83BE698B288FEBCF88E3E03C4F0757EA8964E59B63D93708B138CC42A66EB3
Примеры в программировании
[править | править код]Среда исполнения | Код | Результат |
---|---|---|
PHP 5.0 | echo hash( 'whirlpool', 'test' ); |
b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6 |
Ruby | puts Whirlpool.calc_hex('test') |
b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6 |
Примечания
[править | править код]- ↑ 1 2 3 Kyoji, Shibutani; Shirai, Taizo. On the diffusion matrix employed in the Whirlpool hashing function (англ.) : journal. — 2003. — 11 March. Архивировано 3 октября 2021 года.
- ↑ 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl (англ.) (24 февраля 2009). — презентация нового способа криптоанализа и его применения для криптоанализа хеш-функций Whirlpool и Grøstl. Дата обращения: 25 июня 2019. Архивировано 28 сентября 2011 года.
- ↑ 1 2 Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl (англ.) (2009). — статья о новом способе криптоанализа и его применении для криптоанализа хеш-функций Whirlpool и Grøstl. Дата обращения: 25 июня 2019. Архивировано 18 ноября 2018 года.
Ссылки
[править | править код]- Whirlpool homepage (англ.). — главная страница Whirlpool. Дата обращения: 25 июня 2019. Архивировано 29 ноября 2017 года.
Стандарты
[править | править код]- The ISO/IEC 10118-3:2004 standard (англ.). — стандарт ISO/IEC 10118-3:2004. Дата обращения: 25 июня 2019.
- NESSIE (англ.). — англ. New European Schemes for Signatures, Integrity and Encryption, новые европейские проекты по цифровой подписи, целостности и шифрованию. Дата обращения: 25 июня 2019.
- Portfolio of recommended cryptographic primitives (англ.). — перечень рекомендованных к использованию криптографических функций NESSIE. Дата обращения: 25 июня 2019.
Программные реализации
[править | править код]- A Java implementation of all three revisions of Whirlpool (англ.). — реализация всех трех модификаций Whirlpool на языке программирования Java. Дата обращения: 15 ноября 2009. Архивировано 29 февраля 2012 года.
- A Matlab Implementation of the Whirlpool Hashing Function (англ.). — реализация Whirlpool в пакете Matlab. Дата обращения: 15 ноября 2009. Архивировано 29 февраля 2012 года.
- Perl Whirlpool module at CPAN (англ.). — модуль Whirlpool на языке Perl в CPAN.
- Ruby Whirlpool library (англ.). — библиотека Ruby с реализацией Whirlpool. Дата обращения: 15 ноября 2009. Архивировано 29 февраля 2012 года.
Аппаратные реализации
[править | править код]- Efficient architecture and hardware implementation of the Whirlpool hash function (англ.). — Эффективная аппаратная реализация Whirlpool. Статья IEEE Transactions on Consumer Electronics. Дата обращения: 18 ноября 2009. Архивировано 29 февраля 2012 года.
- High-Speed Parallel Architecture of the Whirlpool Hash Function (англ.). — Высокоскоростная параллельная архитектура Whirlpool. Статья журнала International Journal of Advanced Science and Technology, выпуск 7, Июнь, 2009. Дата обращения: 18 ноября 2009. Архивировано 29 февраля 2012 года.