Whirlpool (хеш-функция)

Материал из testwiki
Перейти к навигации Перейти к поиску

Шаблон:Значения

Шаблон:Карточка хеш-функции Whirlpool — криптографическая хеш-функция, разработанная Винсентом Рэйменом и Шаблон:Iw. Опубликована в ноябре 2000 года. Хеширует входное сообщение с длиной до 2256 битов. Выходное значение хеш-функции Whirlpool, называемое хешем, составляет 512 битов.

История

Название

Галактика Водоворот (M51), в честь которой названа хеш-функция.

Хеш-функция Whirlpool названа в честь Галактики Водоворот (M51) в созвездии Гончие Псы — первой галактики с наблюдаемой спиральной структурой.

Модификации

С момента создания в 2000 году Whirlpool дважды модифицировалась.

Первая версия, Whirlpool-0, представлена как кандидат в проекте NESSIE (Шаблон:Lang-en, новые европейские проекты по цифровой подписи, целостности и шифрованию).

Модификация Whirlpool-0, названная Whirlpool-T, в 2003 году добавлена в перечень рекомендованных к использованию криптографических функций NESSIE. Изменения касались блока подстановки (S-box) Whirlpool: в первой версии структура S-box не была описана, и он генерировался произвольно, что создавало определённые проблемы при аппаратной реализации Whirlpool. В версии Whirlpool-T S-box «приобрёл» чёткую структуру.

Дефект в диффузных матрицах Whirlpool-T, обнаруженный Шаблон:Iw и Шаблон:Iw[1], впоследствии исправлен, и конечная (третья) версия, названная для краткости просто Whirlpool, принята ISO в стандарте ISO/IEC 10118-3:2004 в 2004 году.

Описание

Основная версия — хеш-функции — третья; в отличие от первой версии, S-box определён, а диффузная матрица заменена на новую после доклада Сирая и Сибутани[1].

Whirlpool состоит из повторного применения функции сжатия, основой которой является специальный 512-битный блочный шифр W с 512-битным ключом.

В алгоритме используются операции в поле Галуа  GF(28) по модулю неприводимого многочлена  p8(x)=x8+x4+x3+x2+1.

Многочлены для краткости записываются в шестнадцатеричном представлении. Например, запись  11Dx означает  p8(x).

Для обозначения композиции последовательности функций fm,fm+1,...,fn1,fn,mn используется символ mr=n:
mr=nfrfnfn1fm+1fm.
  • Mm×n[GF(28)] — множество матриц m×n над  GF(28).
cir(a0,a1,...,am1)[a0a1am1am1a0am2a1a2a0],
или просто  cir(a0,a1,...,am1)=ccij=a(ji)modm,0i,jm1.

Формат данных

Whirlpool построен на специальном блочном шифре W, который работает с 512-битными данными.

В преобразованиях промежуточный результат вычисления хеша называется хеш-состоянием или просто состоянием. При вычислениях состояние обычно представляется матрицей состояния. Для Whirlpool это матрица в M8×8[GF(28)]. Следовательно, 512-битные блоки данных должны быть преобразованы в этот формат перед дальнейшими вычислениями. Это достигается введением функции  μ:

μ:GF(28)64M8×8[GF(28)],μ(a)=bbij=a8i+j,0i,j7.

Проще говоря, заполнение матрицы состояния данными происходит построчно. При этом каждый байт матрицы представляет собой соответствующий многочлен в  GF(28).

Преобразования

Нелинейное преобразование γ (S-box)

Функция γ:M8×8[GF(28)]M8×8[GF(28)] состоит из параллельного применения блока подстановки (S-box) S:GF(28)GF(28),xS[x] ко всем байтам матрицы состояния:

γ(a)=bbij=S[aij],0i,j7.

Блок подстановки описывается следующей таблицей замен:

Таблица 1. Блок подстановки
00x 01x 02x 03x 04x 05x 06x 07x 08x 09x 0Ax 0Bx 0cx 0dx 0Ex 0Fx

00x

18x 23x c6x E8x 87x B8x 01x 4Fx 36x A6x d2x F5x 79x 6Fx 91x 52x

10x

60x Bcx 9Bx 8Ex A3x 0cx 7Bx 35x 1dx E0x d7x c2x 2Ex 4Bx FEx 57x

20x

15x 77x 37x E5x 9Fx F0x 4Ax dAx 58x c9x 29x 0Ax B1x A0x 6Bx 85x

30x

Bdx 5dx 10x F4x cBx 3Ex 05x 67x E4x 27x 41x 8Bx A7x 7dx 95x d8x

40x

FBx EEx 7cx 66x ddx 17x 47x 9Ex cAx 2dx BFx 07x Adx 5Ax 83x 33x

50x

63x 02x AAx 71x c8x 19x 49x d9x F2x E3x 5Bx 88x 9Ax 26x 32x B0x

60x

E9x 0Fx d5x 80x BEx cdx 34x 48x FFx 7Ax 90x 5Fx 20x 68x 1Ax AEx

70x

B4x 54x 93x 22x 64x F1x 73x 12x 40x 08x c3x Ecx dBx A1x 8dx 3dx

80x

97x 00x cFx 2Bx 76x 82x d6x 1Bx B5x AFx 6Ax 50x 45x F3x 30x EFx

90x

3Fx 55x A2x EAx 65x BAx 2Fx c0x dEx 1cx Fdx 4dx 92x 75x 06x 8Ax

A0x

B2x E6x 0Ex 1Fx 62x d4x A8x 96x F9x c5x 25x 59x 84x 72x 39x 4cx

B0x

5Ex 78x 38x 8cx d1x A5x E2x 61x B3x 21x 9cx 1Ex 43x c7x Fcx 04x

c0x

51x 99x 6dx 0dx FAx dFx 7Ex 24x 3Bx ABx cEx 11x 8Fx 4Ex B7x EBx

d0x

3cx 81x 94x F7x B9x 13x 2cx d3x E7x 6Ex c4x 03x 56x 44x 7Fx A9x

E0x

2Ax BBx c1x 53x dcx 0Bx 9dx 6cx 31x 74x F6x 46x Acx 89x 14x E1x

F0x

16x 3Ax 69x 09x 70x B6x d0x Edx ccx 42x 98x A4x 28x 5cx F8x 86x

Циклическая перестановка π

Перестановка π:M8×8[GF(28)]M8×8[GF(28)] циклически сдвигает каждый столбец матрицы состояния так, что столбец j сдвигается вниз на j позиций:

π(a)=bbij=a(ij)mod8,j,0i,j7.

Задача данного преобразования — перемешать байты строк матрицы состояния между собой.

Линейная диффузия θ

Линейная диффузия θ:M8×8[GF(28)]M8×8[GF(28)] — это линейное преобразование, матрицей которого является Шаблон:Iw  C=cir(01x,01x,04x,01x,08x,05x,02x,09x), то есть:


C=cir(01x,01x,04x,01x,08x,05x,02x,09x)=[01x01x04x01x08x05x02x09x09x01x01x04x01x08x05x02x02x09x01x01x04x01x08x05x05x02x09x01x01x04x01x08x08x05x02x09x01x01x04x01x01x08x05x02x09x01x01x04x04x01x08x05x02x09x01x01x01x04x01x08x05x02x09x01x],
так что
θ(a)=bb=aC.

Другими словами, матрица состояния умножается справа на матрицу  C. Напомним, что операции сложения и умножения элементов матриц производятся в  GF(28).

Шаблон:Iw — это такая матрица над конечным полем  K, что если взять её в качестве матрицы линейного преобразования  f(x)=(MDS)x из пространства  Kn в пространство  Km, то любые два вектора из пространства  Kn+m вида  (x,f(x)) будут иметь как минимум  m+1 различий в компонентах. То есть набор векторов вида  (x,f(x)) образует код, обладающий свойством максимальной разнесённости (Шаблон:Lang-en). Таким кодом является, например, код Рида-Соломона.

В Whirlpool свойство максимальной разнесённости MDS-матрицы означает, что общее количество меняющихся байт вектора  x и вектора  f(x)=(MDS)x не меньше  8+1=9. Другими словами, любое изменение только одного байта  x приводит к изменению всех 8 байтов  f(x). В этом и состоит задача линейной Шаблон:Iw.

Как уже упоминалось выше, MDS-матрица в последней (третьей) версии Whirlpool была изменена благодаря статье Шаблон:Не переведено и Шаблон:Не переведено[1]. Они проанализировали MDS-матрицу второй версии Whirlpool и указали на возможность повышения устойчивости Whirlpool к дифференциальному криптоанализу. Также они предложили 224 кандидата на место новой MDS-матрицы. Из этого списка авторы Whirlpool выбрали вариант, наиболее легко реализуемый в аппаратном обеспечении.

Добавление ключа σ[k]

Функция добавления ключа σ[k]:M8×8[GF(28)]M8×8[GF(28)] представляет собой побитовое сложение (XOR) матриц состояния  a и ключа kM8×8[GF(28)]:

σ[k](a)=bbi,j=ai,jki,j,0i,j7.

Константы раунда cr

В каждом раунде  r,r>0 используется матрица констант crM8×8[GF(28)], такая, что:

c0jrS[8(r1)+j],0j7,
cijr0,1i7,0j7.

Отсюда видно, что первая строка матрицы cr является результатом применения блока подстановки S к байтовым числам [8(r1)+j],0j7.

Остальные 7 строк — нулевые.

Функция раунда ρ[k]

Для каждого раунда  r функция раунда — это составное преобразование ρ[k]:M8×8[GF(28)]M8×8[GF(28)], параметром k которого является матрица ключа kM8×8[GF(28)]. Описывается функция раунда следующим образом:

ρ[k]σ[k]θπγ.

Расширение ключа

Для каждого раунда  r,0rR необходим 512-битный ключ шифрования. Для решения данной проблемы во многих алгоритмах вводится так называемая процедура расширения ключа. В Whirlpool расширение ключа реализуется следующим образом:

 K0=K,
 Kr=ρ[cr](Kr1),r>0.

Таким образом, из известного ключа K производится необходимая последовательность K0,...,KR ключей для каждого раунда блочного шифра W.

Блочный шифр W

Специальный 512-битный блочный шифр W[K]:M8×8[GF(28)]M8×8[GF(28)] в качестве параметра использует 512-битный ключ K и выполняет следующую последовательность преобразований:

W[K]=(1r=Rρ[Kr])σ[K0],

где ключи K0,...,KR порождены описанной выше процедурой расширения ключа. В хеш-функции Whirlpool число раундов R=10.

Дополнение входного сообщения

Whirlpool, как и любая другая хеш-функция, должна осуществлять хеширование сообщения произвольной длины. Поскольку внутренний блок шифрования W работает с 512-битными входными сообщениями, то исходное сообщение необходимо разбить на блоки по 512 бит. При этом последний блок, который содержит конец сообщения, может оказаться неполным.

Для решения данной задачи Whirlpool использует алгоритм Меркла — Дамгора дополнения входного сообщения. Результатом дополнения сообщения M является сообщение M, длина которого кратна 512. Пусть L — длина исходного сообщения. Тогда M получается в несколько шагов:

  1. К концу сообщения M приписать бит «1».
  2. Приписать x битов «0» так, чтобы длина полученной строки L+1+x была кратна 256 нечетное число раз.
  3. Наконец, приписать 256-битное представление числа L.

Дополненное сообщение M записывается в виде

M=ML100xL256

и разбивается на 512-битные блоки для дальнейшей обработки.

Функция сжатия

Функция сжатия Whirlpool

В Whirlpool применяется схема хеширования Шаблон:Не переведено.

 t блоков mi,1it дополненного сообщения M последовательно шифруются блочным шифром W:


 ηi=μ(mi),
 H0=μ(IV),
Hi=W[Hi1](ηi)Hi1ηi,1it,

где IV (Шаблон:Lang-en, Шаблон:Не переведено) — 512-битная строка, заполненная «0».

Вычисление хеша

Дайджестом для сообщения M является выходное значение Ht функции сжатия, преобразованное обратно в 512-битную строку:

Whirlpool(M)μ1(Ht).

Криптостойкость

Хеш-функция H считается криптографически стойкой, если она удовлетворяет трём основным требованиям, на которых основано большинство применений хеш-функций в криптографии: необратимость, стойкость к коллизиям первого рода и стойкость к коллизиям второго рода.

Пусть hn — произвольная n-битная подстрока 512-битного хеша Whirlpool. Авторы Whirlpool утверждают, что созданная ими хеш-функция удовлетворяет следующим требованиям криптостойкости:

  • Генерация коллизии требует порядка 2n/2 вычислений хеша WHIRLPOOL (стойкость к коллизиям второго рода).
  • Для заданной hn поиск такого сообщения M, что H(M)=hn, потребует порядка 2n вычислений хеша WHIRLPOOL (необратимость).
  • Для заданного сообщения M обнаружение другого сообщения N, для которого H(N)=H(M), потребует порядка 2n вычислений хеша WHIRLPOOL (стойкость к коллизиям первого рода).
  • Невозможно обнаружить систематические корреляции между любой линейной комбинацией входных бит и любой линейной комбинацией бит хеша или предсказать, какие биты хеша изменят своё значение при изменении определённых входных бит (стойкость к линейному криптоанализу и дифференциальному криптоанализу).

К данному заявлению авторы Whirlpool добавили примечание:

Эти утверждения вытекают из значительного запаса прочности относительно всех известных атак. Тем не менее, мы понимаем, что невозможно сделать не спекулятивные утверждения о неизвестных вещах.

Криптоанализ

На сегодняшний день WHIRLPOOL устойчива ко всем видам криптоанализа. На протяжении 8 лет существования Whirlpool не было зарегистрировано ни одной атаки на неё.

Однако в 2009 году был опубликован новый способ атаки на хеш-функции — The Rebound Attack[2][3]. Первыми «подопытными» новой атаки стали хеш-функции Whirlpool и Grøstl. Результаты проведённого криптоанализа приведены в таблице.

Таблица 2. Результаты криптоанализа хеш-функций Whirlpool и Grøstl по методу The Rebound Attack[2][3]
Хеш-функция Число раундов Сложность Требуемый объём памяти Тип коллизии
Whirlpool 4.5/10 2120 216 коллизия
5.5/10 2120 216 полусвободная коллизия
7.5/10 2128 216 полусвободная почти коллизия
Grøstl-256 6/10 2120 270 полусвободная коллизия

Авторы исследования использовали следующие понятия и термины:

Типы коллизий:

  • коллизия:
    •  IV — фиксирован
    • f(Mt,IV)=f(Mt,IV),MtMt
  • почти коллизия:
    •  IV — фиксирован
    • fMt=f(Mt,IV),fMt=f(Mt,IV),MtMt
    • небольшое число бит хешей fMt и fMt различны
  • полусвободная коллизия:
    • f(Mt,Ht1)=f(Mt,Ht1),MtMt
  • свободная коллизия:
    • f(Mt,Ht1)=f(Mt,Ht1),MtMt1,HtHt1


Как видно из таблицы, сгенерировать коллизию для 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

Примечания

Шаблон:Примечания

Ссылки

Стандарты

Программные реализации

Аппаратные реализации

Шаблон:Хеш-алгоритмы