Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУ ВПО «Северо-Кавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций

КУРСОВАЯ РАБОТА

НА ТЕМУ:

Исследование работы алгоритма хеширования Whirlpool

Автор дипломного проекта

Шевченко Ростислав Сергеевич

ГруппаБАС-081

Руководитель работы Р. А. Воронкин

Ставрополь, 2011

СОДЕРЖАНИЕ

Введение

1. Диагностический анализ работы алгоритма хеширования Whirlpool

1.1 История Whirlpool

1.2 Описание Whirlpool

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

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

1.5 Применение Whirlpool

2. Реализация алгоритма хеширования Whirlpool

Заключение

Список использованных источников

Приложение

ВВЕДЕНИЕ

Хеширование (иногда хэширование, англ. hashing) - преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения (англ. message digest).

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

Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.

Криптографической хеш-функцией называется всякая хеш-функция, являющаяся криптостойкой, то есть, удовлетворяющая ряду требований специфичных для криптографических приложений.

Требования специфичные для криптографических приложений:

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

1. Необратимость или стойкость к восстановлению прообраза: для заданного значения хеш-функции m должно быть вычислительно невозможно найти блок данных X, для которого H(X) = m.

2. Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого H(N) = H(M).

3. Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений , имеющих одинаковый хеш.

Данные требования не являются независимыми:

1. Обратимая функция нестойка к коллизиям первого и второго рода.

2. Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

Следует отметить, что не доказано существование необратимых хеш-функций, для которых вычисление какого-либо прообраза заданного значения хеш-функции теоретически невозможно. Обычно нахождение обратного значения является лишь вычислительно сложной задачей.

Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n битов в среднем за примерно вычислений хеш-функции. Поэтому n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к .

Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект). В частности, значение хеша не должно давать утечки информации даже об отдельных битах аргумента. Это требование является залогом криптостойкости алгоритмов хеширования пользовательских паролей для получения ключей.

1. ДИАГНОСТИЧЕСКИЙ АНАЛИЗ РАБОТЫ АЛГОРИТМА ХЕШИРОВАНИЯ WHIRLPOOL

Whirlpool - криптографическая хеш-функция, разработанная Vincent Rijmen и Paulo S. L. M. Barreto. Впервые опубликована в ноябре 2000 года. Осуществляет хеширование входного сообщения с длиной до 2²⁵⁶ бит. Выходное значение хеш-функции Whirlpool, называемое хешем, составляет 512 бит.

1.1 История Whirlpool

Хеш-функция 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, обнаруженный Taizo Shirai и Kyoji Shibutani , был впоследствии исправлен, и конечная (третья) версия, названная для краткости просто WHIRLPOOL, была принята ISO (англ. International Organization for Standardization, международная организация по стандартизации) в стандарте ISO/IEC 10118-3:2004 в 2004 году.

1.2 Описание Whirlpool

В отличие от первой версии, в последней (третьей) S-box определен, а диффузная матрица заменена на новую после доклада Taizo Shirai и Kyoji Shibutani.

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

В алгоритме используются операции в поле Галуа по модулю неприводимого многочлена

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

- Символом _ обозначается оператор композиции. Выражение _ означает композицию функций и .

Для обозначения композиции последовательности функций используется символ :

____ (1)

-  -- множество матриц над .

-  -- циркулянтная матрица , первая строка которой состоит из элементов , то есть:

, (2)

или просто

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

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

. (3)

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

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

Функция состоит из параллельного применения блока подстановки (S-box) ко всем байтам матрицы состояния:

(4)

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

Таблица 1.1. Блок подстановки

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

00x

01x

02x

03x

04x

05x

06x

07x

08x

09x

0Ax

0Bx

0cx

0dx

0Ex

0Fx

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Перестановка циклически сдвигает каждый столбец матрицы состояния так, что столбец j сдвигается вниз на j позиций:

. (5)

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

Линейная диффузия - это линейное преобразование, матрицей которого является MDS матрица , то есть:

так что

(6)

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

MDS матрица - это такая матрица над конечным полем K, что если взять её в качестве матрицы линейного преобразования из пространства в пространство , то любые два вектора из пространства вида будут иметь как минимум различий в компонентах. То есть набор векторов вида образует код, обладающий свойством максимальной разнесённости (англ. Maximum Distance Separable code). Таким кодом является, например, код Рида-Соломона. В Whirlpool свойство максимальной разнесённости MDS матрицы означает, что общее количество меняющихся байт вектора и вектора не меньше . Другими словами, любое изменение только одного байта приводит к изменению всех 8 байтов . В этом и состоит задача линейной диффузии.

Как уже упоминалось выше, MDS матрица в последней (третьей) версии Whirlpool была изменена благодаря статье Taizo Shirai и Kyoji Shibutani. Они проанализировали MDS матрицу второй версии Whirlpool и указали на возможность повышения устойчивости Whirlpool к дифференциальному криптоанализу. Также они предложили 224 кандидата на место новой MDS матрицы. Из этого списка авторы Whirlpool выбрали вариант, наиболее легко реализуемый в аппаратном обеспечении.

Функция добавления ключа представляет собой побитовое сложение (XOR) матриц состояния и ключа :

? (7)

В каждом раунде используется матрица констант такая, что:

(8)

(9)

Отсюда видно, что первая строка матрицы c^r является результатом применения блока подстановки S к байтовым числам .

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

Для каждого раунда функция раунда - это составное преобразование , параметром k которого является матрица ключа . Описывается функция раунда следующим образом:

___ (10)

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

 (11)

(12)

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

Специальный 512-битный блочный шифр в качестве параметра использует 512-битный ключ K и выполняет следующую последовательность преобразований:

_ (13)

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

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

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

1. К концу сообщения приписать бит «1».

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

3. Наконец, приписать 256-битное представление числа L.

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

(14)

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

В Whirlpool применяется схема хеширования Miyaguchi-Preneel  блоков дополненного сообщения последовательно шифруются блочным шифром W:

(15)

(16)

Е?Е??????????????????????????7?

где IV (англ. initialization vector, вектор инициализации) - 512-битная строка, заполненная "0".

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

(18)

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

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

Пусть h_n - произвольная n-битная подстрока 512-битного хеша Whirlpool.

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

1. Генерация коллизии требует порядка 2^{n / 2} вычислений хеша WHIRLPOOL (стойкость к коллизиям второго рода).

2. Для заданной h_n поиск такого сообщения M, что H(M) = h_n, потребует порядка 2ⁿ вычислений хеша WHIRLPOOL (необратимость).

3. Для заданного сообщения M обнаружение другого сообщения N, для которого H(N) = H(M), потребует порядка 2ⁿ вычислений хеша WHIRLPOOL (стойкость к коллизиям первого рода).

4. Невозможно обнаружить систематические корреляции между любой линейной комбинацией входных бит и любой линейной комбинацией бит хеша или предсказать, какие биты хеша изменят свое значение при изменении определенных входных бит (стойкость к линейному криптоанализу и дифференциальному криптоанализу).

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

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

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

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

1.  - вектор инициализации

2.  - сообщение, подлежащее хешированию

3.  - хеш-функция

4. функция сжатия

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

1. коллизия:

1.1. - фиксирован

2. почти коллизия:

2.1. - фиксирован

2.2. небольшое число бит хешей и различны

3. полусвободная коллизия:

4. свободная коллизия:

1.5 Применение Whirlpool

Whirlpool - свободно распространяемая хеш-функция. Поэтому она находит широкое применение в открытом программном обеспечении. Здесь перечислены некоторые примеры использования Whirlpool:

1. Jacksum - свободно распространяемая утилита для вычисления контрольных сумм.

2. Crypto++ - свободно распространяемая C++ библиотека классов криптографических примитивов.

3. TrueCrypt - программа для шифрования «на лету».

4. FreeOTFE - это свободная бесплатная программа с открытым кодом, предназначенная для шифрования «на лету». Выпускается для операционных систем Windows и Windows Mobile (FreeOTFE4PDA).

5. 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

Таблица 1.3. Примеры в программировании

Среда исполнения	Код	Результат
PHP 5.0	echo hash( 'whirlpool', 'test' );	b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6
Ruby	puts Whirlpool.calc_hex('test')	b913d5bbb8e461c2c5961cbe0edcdadfd29f068225ceb37da6defcf89849368f 8c6c2eb6a4c4ac75775d032a0ecfdfe8550573062b653fe92fc7b8fb3b7be8d6

Вывод: Достоинством алгоритма хеширования Whirlpool является то что для него пока не нашли коллизий. Недостатком этого алгоритма является сложность реализации.

2. РЕАЛИЗАЦИЯ АЛГОРИТМА ХЕШИРОВАНИЯ WHIRLPOOL

Также как AES, Whirlpool производит все вычисления в конечных полях. Под «конечным полем» здесь подразумеваются всего лишь операции * (умножить) и + (сложить) определённые хитрым образом над парами целых чисел. Здесь используют следующую идею. Будем считать, что число 0x17=1'0111 это компактная запись многочлена, у которого 1'0111 - коэффициенты: x⁴+x²+x+1.

Для сложения двух чисел их записывают в виде многочленов и складывают коэффициенты при соответствующих степенях, при этом считая, что коэффициенты это биты с двумя значениями и правилами сложения 1+0=1, 1+1=0 и т.д. Вообщем получается, что сложение двух чисел это xor.

Умножение двух чисел берётся по модулю некоторого специально выбранного многочлена, вид которого зависит от разрядности чисел. Whirlpool оперирует полями GF(2⁴) (4-битные числа) и GF(2⁸) (8-битные числа). Для GF(2⁴) авторами Whirlpool было выбрано число 0x13=1'0011=x⁴+x+1. Найдем, например произведение 0xb*0xb=1011*1011: 1011*1011 = (x³+x+1)(x³+x+1) mod(x⁴+x+1)

Вычислять это напрямую долго, однако видно, что это умножение сводится к умножению на простой многочлен x: 1011*1011 = 1011*x³+1011*x+1011 = 1011*10*10*10+1011*10+1011.

Найдём правило умножения p*x. Если p*x не помещается в 4 бита, надо отнять от p*x многочлен 0x13, иначе оставить p*x без изменений.

1011*10 = 1'0110 - 1'0011 = 1'0110 ^ 1'0011 = 101

1011*10*10 = 101*10 = 1010

1011*10*10*10 = 1010*10 = 1'0100 - 1'0011 = 110

Теперь складываем три слагаемых: 1011*10*10*10+1011*10+1011 = 110+101+1011 = 10+1011 = 1001 = 0x9. Получилось, что 0xb*0xb=0x9. Правила умножения в GF(2⁸) такие же, только многочлен другой: 0x11d (в AES используется 0x11b).

Листинг 3.1.

whirlpool.gf4mul = function(a, b)

{

var c = 0

while (b != 0)

{

if (b & 1)

c ^= a

b = b >> 1

a = a << 1

if (a & 0x10)

a ^= 0x13

}

return c

}

whirlpool.gf8mul = function(a, b)

{

var c = 0

while (b != 0)

{

if (b & 1)

c ^= a

b = b >> 1

a = a << 1

if (a & 0x100)

a ^= 0x11d

}

return c

}

Чтобы умножить два числа нужно вызвать одну из этих функций, а чтобы сложить нужно просто применить xor.

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

1. Дописывают в конец бит равный 1.

2. Дописывают в конец нулевые биты так, чтобы длина сообщения получилась кратной 32 байтам, при этом отношение длина/32 должно быть нечётным.

3. Дописывают в конец длину исходного сообщения.

Рассмотрим это на примере строки «habrahabr»:

68 61 62 72 61 68 61 62

72 80 00 00 00 00 00 00

00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 48

Первые 9 байт - ASCII коды букв из строки. Байт 0x80 - это добавленный бит «1». В конце записано число битов в исходном сообщении: 9Ч8=72=0x48. После такого выравнивания сообщение выглядит как несколько 64-байтных блоков.

Алгоритм использует несколько простых вспомогательных функций, таких как E-Box, R-Box, S-Box.

1. R-Box это просто массив из 16-ти 4-битных чисел. Он сгенерирован так, чтобы иметь некоторые особые свойства. Для реализации важно только то, что R-Box нельзя получить алгоритмически, потому что авторы Whirlpool использовали для генерации R-Box функцию random. Вот этот R-Box:

[7, 12, 11, 13, 14, 4, 9, 15, 6, 3, 8, 10, 2, 5, 1, 0]

2. E-Box получается так: E(n)=0xbⁿ, E(0xf)=0. Вычисления ведутся в поле GF(2⁴) - т.е. особое умножение и сложение как xor. Функция Inv-E-Box это E^-1 - функция обратная к E-Box. Фактически E-Box это массив из 16-ти 4-битных чисел.

Листинг 3.2.

whirlpool.ebox = function(i)

{

var mul = whirlpool.gf4mul

var ebox = whirlpool.ebox

switch(i)

{

case 0:return 1

case 0xf:return 0

default:return mul(ebox(i - 1), 0xb)

}

}

whirlpool.invebox = function(i)

{

for (var j = 0; j < 16; j++)

if (whirlpool.ebox(j) == i)

return j

}

3. S-Box принимает аргумент в диапазоне 0x00..0xff и возвращает число в том же диапазоне. Если считать, что b - один байт, а u, v - его верхняя и нижняя 4-битные половины, то S(b) = S(u, v) = (E(E(u) + a), E^-1(E^-1(v) + a)) где a = R(E(u) + E^-1(v)).

Листинг 3.3.

whirlpool.sbox = function(i)

{

var v = i & 0xf

var u = i >> 4

var e = whirlpool.ebox

var ie = whirlpool.invebox

var a = whirlpool.rbox[e(u) ^ ie(v)]

var u = e(e(u) ^ a)

var v = ie(ie(v) ^ a)

return (u << 4) ^ v

}

Whirlpool воспринимает 64-байтный блок как матрицу 8Ч8 - первые 8 байт это первая строка матрицы, следующие 8 байт - вторая строка, и т.д. Алгоритм умеет делать несколько преобразований этой матрицы:

1. rotate вращает k-ый столбец на k байт вниз. Нумерация с нуля. Исходная матрица:

00 01 02 03 04 05 06 07

10 11 12 13 14 15 16 17

20 21 22 23 24 25 26 27

30 31 32 33 34 35 36 37

40 41 42 43 44 45 46 47

50 51 52 53 54 55 56 57

60 61 62 63 64 65 66 67

70 71 72 73 74 75 76 77

Преобразованная матрица:

00 71 62 53 44 35 26 17

10 01 72 63 54 45 36 27

20 11 02 73 64 55 46 37

30 21 12 03 74 65 56 47

40 31 22 13 04 75 66 57

50 41 32 23 14 05 76 67

60 51 42 33 24 15 06 77

70 61 52 43 34 25 16 07

2. diffuse умножает матрицу на матрицу особой структуры построенной за счёт вращения одной строки. Вот пример этой особой матрицы:

00 01 02 03 04 05 06 07

07 00 01 02 03 04 05 06

06 07 00 01 02 03 04 05

05 06 07 00 01 02 03 04

04 05 06 07 00 01 02 03

03 04 05 06 07 00 01 02

02 03 04 05 06 07 00 01

01 02 03 04 05 06 07 00

Видно, что все строки получаются вращением первой строки. Whirlpool использует такую матрицу:

01 01 04 01 08 05 02 09

09 01 01 04 01 08 05 02

02 09 01 01 04 01 08 05

05 02 09 01 01 04 01 08

08 05 02 09 01 01 04 01

01 08 05 02 09 01 01 04

04 01 08 05 02 09 01 01

01 04 01 08 05 02 09 01

diffuse(a) = a*d где d - описанная матрица. Умножение ведётся в поле GF(2⁸).

Листинг 3.4.

whirlpool.diffuserow = [1, 1, 4, 1, 8, 5, 2, 9]

whirlpool.diffuse = function(a)

{

var n = whirlpool.dim

var b = whirlpool.matrix(n, n, 0)

var mul = whirlpool.gf8mul

var row = whirlpool.diffuserow

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

for (var k = 0; k < n; k++)

b[i][j] ^= mul(a[i][k], row[(j - k + n) % n])

return b

}

Whirlpool хранит внутреннее состояние H - матрицу 8Ч8 байт. В самом начале H=0. Когда приходит очередной 64-байтный блок B, Whirlpool его шифрует с помощью H и получает W(H, B), после чего добавляет (операция xor) к своему состоянию полученное значение и исходный блок: H = H + B + W(H, B). Осталось разобраться с шифрованием W. Функция W(H, B) вычисляется по следующей схеме:

Листинг 3.5.

W = H + B

for m = 1..10 do

H = C(m) + diffuse(rotate(sbox(H)))

W = H + diffuse(rotate(sbox(W)))

где C_m это матрица 8Ч8 у которой все элементы нули, кроме первой строчки, которая берётся из S-Box: C_m[0..7] = S-Box[8(m-1)..8m-1]. Преобразования diffuse и rotate уже описаны, в sbox(A) просто применяет к каждому элементу матрицы функцию S-Box.

Выражение A + diffuse(rotate(sbox(B))) удобно записать в виде отдельной функции:

Листинг 3.6.

whirlpool.rfun = function(k, a)

{

a = whirlpool.apply(a)

a = whirlpool.rotate(a)

a = whirlpool.diffuse(a)

a = whirlpool.add(a, k)

return a

}

Вот реализация функции W(H, B):

Листинг 3.7.

whirlpool.cipher = function(key, text)

{

var n = whirlpool.dim

var w = whirlpool.add(key, text)

var rcon = whirlpool.matrix(n, n, 0)

for (var r = 1; r <= whirlpool.rounds; r++)

{

for (var i = 0; i < n; i++)

rcon[0][i] = whirlpool.sbox(n*(r - 1) + i)

key = whirlpool.rfun(rcon, key)

w = whirlpool.rfun(key, w)

}

return w

}

Осталось реализовать схему H = H + B + W(H, B):

Листинг 3.8.

whirlpool.compressor.prototype.push = function(block)

{

var h = this.state

var m = whirlpool.input(block) // преобразовать массив в матрицу 8Ч8

var c = whirlpool.cipher(h, m)

var n = whirlpool.dim

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

h[i][j] ^= c[i][j] ^ m[i][j]

}

После того как обработан последний 64-байтный блок, значение хеша находится в внутреннем состоянии H - матрице 8Ч8. Осталось лишь записать матрицу в виде массива и соединить байты в 64-байтный хеш.

Whirlpool хеш от habrahabr равен

d9d81b7f991a08b89f7cb899f3320564

da5cff67fcb021980862c693caf9d1ef

715f146aff6d92008544095d34451233

ffd83a420f6cdbaff9d5ccdc92407d77

Несколько комментариев к реализации примера. На вход хеш-функции может прийти как строка, так и массив их байтов. Также хочется иметь возможность вычислять хеши от синтетических сообщений - например от миллиона букв 'a'. Из за этой неоднородности входных данных чтение данных сделано трёхслойным:

1. reader преобразует поток байтов в 32-байтные блоки. Он выравнивает сообщение и добавляет биты как сказано в описании Whirlpool.

2. hub преобразует поток 32-байтных блоков в поток 64-байтных блоков.

3. compressor принимает поток 64-байтных блоков и меняет состояние H по алгоритму Whirlpool.

Такая схема, с одной стороны, позволяет вычислять хеш очевидным способом whirlpool.hash('habrahabr'), а с другой стороны позволяет вычислить хеш от синтетического сообщения (для тестирования):

Листинг 3.9.

whirlpool.hash(function() { return 0x61 }, 1000000)

ЗАКЛЮЧЕНИЕ

Результатом написания данной курсовой работы стала программная реализация одного из алгоритмов хеширования, а именно алгоритма хеширования Whirlpool.

Whirlpool хеш больше похож на алгоритм шифрования AES, чем на хеши MD5 и SHA1. Он весьма запутан и реализовать его сложнее чем AES, да и работает он не очень быстро, зато для него пока не нашли коллизий.

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

Однако, в 2009 году был опубликован новый способ атаки на хеш-функции - The Rebound Attack. Первыми «подопытными» новой атаки стали хеш-функции Whirlpool и Grшstl.

Cгенерировать коллизию для Whirlpool удалось лишь для её «урезанного» варианта в 4.5 раунда. К тому же, сложность необходимых вычислений довольно высока.

криптографический преобразование функция

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. Учебное пособие. М., Гелиос АРВ, 2005.

2. Бабаш А.В., Шанкин Г.П. История криптографии. Часть I. М.: Гелиос, 2002.

3. Бабаш А.В., Шанкин Г.П. Криптография. Аспекты защиты. М., Солон-Р, 2002.

4. О. С. Зензин, М. А. Иванов Стандарт криптографической защиты - AES. Конечные поля / Под ред. М. А. Иванова - М.: КУДИЦ-ОБРАЗ, 2002. - 176 с.

5. Нильс Фергюсон, Брюс Шнайер Практическая Криптография. - М., Изд. Вильямс, 2005.

6. Соколов А.В., Шаньгин В.Ф. Защита информации в распределенных корпоративных сетях и системах. - М.: ДМК Пресс, 2002

7. М. Вельшенбах Криптография на Си и С++ в действии. Учебное пособие. - М.: Издательство Триумф, 2004

8. Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект, 2001.

9. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000.

10. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001

ПРИЛОЖЕНИЕ

Листинг 1. Реализация алгоритма хеширования Whirlpool в HTML

<!doctype html>

<html>

<head>

<title>Whirlpool Hash</title>

<meta charset="utf-8">

<script src="whirlpool.js"></script>

<style>

body

{

font-family: lucida console;

font-size: 8pt;

}

div.cell

{

margin: 1em;

border-top: 1pt solid lightgray;

}

div.hint

{

font-family: calibri;

font-weight: bold;

font-size: 1.2em;

padding: 0.5em;

}

span.emptystr

{

color: gray;

}

footer

{

position: fixed;

right: 1em;

bottom: 1em;

color: lightgray;

}

</style>

</head>

<body>

<div>

<input id="input" size="40" onkeydown="computeHash()" onkeyup="computeHash()" onkeypress="computeHash()">

<input type="button" value="Save" onclick="saveHash()">

</div>

<div id="tempHash">

</div>

<div id="data">

</div>

<footer>Whirlpool hash implementation for Habrahabr</footer>

<script>

function $(id)

{

return document.getElementById(id)

}

function hexBytes(bytes)

{

var str = []

var hex = '0123456789abcdef'

for (var i in bytes)

str[i] = hex[bytes[i] >> 4] + hex[bytes[i] & 0xf]

return str

}

function hashStr(bytes)

{

var str = hexBytes(bytes)

var res = []

for (var i = 0; i < str.length; i += 16)

res.push(str.slice(i, i + 16).join(''))

return res.join(' ')

}

function escapeTags(s)

{

var rules = [['\n', ''], ['&', '&amp;'], ['<', '&lt;'], ['>', '&gt;']]

for (var i in rules)

s = s.replace(new RegExp(rules[i][0], 'g'), rules[i][1])

return s

}

function formCell(hint, text)

{

return '<div class="cell">' + '<div class="hint">' +

hint + '</div>' + text + '</div>'

}

function formHashHtml()

{

var hash = hashStr(whirlpool.hash($('input').value))

var hint = escapeTags($('input').value)

if (hint.length == 0)

hint = '<span class="emptystr">empty string</span>'

return formCell(hint, hash)

}

function computeHash()

{

$('tempHash').innerHTML = formHashHtml()

}

function saveHash()

{

$('data').innerHTML = formHashHtml() + $('data').innerHTML

}

$('input').value = 'habrahabr'

computeHash()

</script>

</body>

</html>

Листинг 2 JavaScript хеш-функция

// Whirlpool hash function.

whirlpool = {}

// Computes the Whirlpool hash.

// Examples of use:

//whirlpool.hash('abc')

//whirlpool.hash([0x61, 0x62, 0x63])

//whirlpool.hash(function(i) { return (i*i) & 0xff }, 1000)

// Returns a 64-byte array of bytes.

whirlpool.hash = function(bytes, length)

{

var n = whirlpool.dim

// pipeline: src byte :> reader :> hub :> comp

var comp = new whirlpool.compressor(whirlpool.initvector)

var hub = new whirlpool.hub(n*n, function(a) { comp.push(a) })

var reader = new whirlpool.reader(n*n/2, function(a) { hub.push(a) })

var push = function(b)

{

if (typeof b == 'number' && Math.floor(b) == b && b >= 0 && b <= 255)

{

reader.push(b)

return true

}

}

switch (typeof bytes)

{

case 'object':

for (var i = 0; i < (length || bytes.length); i++)

if (!push(bytes[i]))

return

break

case 'string':

for (var i = 0; i < (length || bytes.length); i++)

if (!push(bytes.charCodeAt(i)))

return

break

case 'function':

for (var i = 0; i < length; i++)

if (!push(bytes(i)))

return

break

default:

return

}

reader.finish()

return whirlpool.output(comp.state)

}

// This function is called automatically.

whirlpool.initialise = function()

{

whirlpool.diffuserow = [1, 1, 4, 1, 8, 5, 2, 9]

whirlpool.rbox = [7, 12, 11, 13, 14, 4, 9, 15, 6, 3, 8, 10, 2, 5, 1, 0]

whirlpool.dim = 8

whirlpool.rounds = 10

whirlpool.initvector = whirlpool.vector(whirlpool.dim*whirlpool.dim, 0)

}

// Algorithm-specific functions.

whirlpool.ebox = function(i)

{

var mul = whirlpool.gf4mul

var ebox = whirlpool.ebox

switch(i)

{

case 0: return 1

case 0xf: return 0

default: return mul(ebox(i - 1), 0xb)

}

}

whirlpool.invebox = function(i)

{

for (var j = 0; j < 16; j++)

if (whirlpool.ebox(j) == i)

return j

}

whirlpool.sbox = function(i)

{

var v = i & 0xf

var u = i >> 4

var e = whirlpool.ebox

var ie = whirlpool.invebox

var a = whirlpool.rbox[e(u) ^ ie(v)]

var u = e(e(u) ^ a)

var v = ie(ie(v) ^ a)

return (u << 4) ^ v

}

whirlpool.input = function(row)

{

var n = whirlpool.sqrt(row.length)

var m = whirlpool.matrix(n, n)

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

m[i][j] = row[i*n + j]

return m

}

whirlpool.output = function(matrix)

{

var n = matrix.length

var row = new Array(n)

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

row[i*n + j] = matrix[i][j]

return row

}

whirlpool.apply = function(a)

{

var n = a.length

var b = whirlpool.matrix(n, n)

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

b[i][j] = whirlpool.sbox(a[i][j])

return b

}

whirlpool.rotate = function(a)

{

var n = a.length

var b = whirlpool.matrix(n, n)

for (var j = 0; j < n; j++)

for (var i = 0; i < n; i++)

b[i][j] = a[(i + n - j) % n][j]

return b

}

whirlpool.diffuse = function(a)

{

var n = whirlpool.dim

var b = whirlpool.matrix(n, n, 0)

var mul= whirlpool.gf8mul

var row = whirlpool.diffuserow

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

for (var k = 0; k < n; k++)

b[i][j] ^= mul(a[i][k], row[(j - k + n) % n])

return b

}

whirlpool.rfun = function(k, a)

{

a = whirlpool.apply(a)

a = whirlpool.rotate(a)

a = whirlpool.diffuse(a)

a = whirlpool.add(a, k)

return a

}

whirlpool.cipher = function(key, text)

{

var n = whirlpool.dim

var w = whirlpool.add(key, text)

var rcon = whirlpool.matrix(n, n, 0)

for (var r = 1; r <= whirlpool.rounds; r++)

{

for (var i = 0; i < n; i++)

rcon[0][i] = whirlpool.sbox(n*(r - 1) + i)

key = whirlpool.rfun(rcon, key)

w = whirlpool.rfun(key, w)

}

return w

}

// Finite fields.

whirlpool.gf4mul = function(a, b)

{

var c = 0

while (b != 0)

{

if (b & 1)

c ^= a

b = b >> 1

a = a << 1

if (a & 0x10)

a ^= 0x13

}

return c

}

whirlpool.gf8mul = function(a, b)

{

var c = 0

while (b != 0)

{

if (b & 1)

c ^= a

b = b >> 1

a = a << 1

if (a & 0x100)

a ^= 0x11d

}

return c

}

// Creates a reader-object that reads bytes and returns chunks of 32 bytes.

whirlpool.reader = function(size, handler)

{

this.pop = handler

this.length = 0

this.chunk = new Array(size)

}

whirlpool.reader.prototype.push = function(byte)

{

var c = this.chunk

var n = this.length % c.length

c[n] = byte

this.length++

if (n + 1 == c.length)

this.pop(c)

}

whirlpool.reader.prototype.finish = function()

{

var len = this.length * 8 // number of bits

var c = this.chunk

this.push(0x80)

while (this.length % c.length != 0 || (this.length / c.length) % 2 == 0)

this.push(0)

for (var i = 0; i < c.length; i++)

{

c[c.length - 1 - i] = len & 0xff

len >>= 8

}

this.pop(c)

}

// Creates a compressor of 32-byte blocks.

whirlpool.compressor = function(initstate)

{

this.state = whirlpool.input(initstate)

}

whirlpool.compressor.prototype.push = function(block)

{

var h = this.state

var m = whirlpool.input(block)

var c = whirlpool.cipher(h, m)

var n = whirlpool.dim

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

h[i][j] ^= c[i][j] ^ m[i][j]

}

// Creates a hub that accepts a sequence of bytes and returns blocks of needed size.

whirlpool.hub = function(size, handler)

{

this.pop = handler

this.cache = new Array(size)

this.length = 0

}

whirlpool.hub.prototype.pushbyte = function(byte)

{

var cache = this.cache

var i = this.length % cache.length

cache[i] = byte

this.length++

if (i + 1 == cache.length)

this.pop(this.cache)

}

whirlpool.hub.prototype.push = function(data)

{

for (var i in data)

this.pushbyte(data[i])

}

// Miscellaneous functions.

whirlpool.matrix = function(rows, cols, init)

{

var m = new Array(rows)

for (var i = 0; i < rows; i++)

m[i] = new Array(cols)

for (var i = 0; i < rows; i++)

for (var j = 0; j < cols; j++)

m[i][j] = init || 0

return m

}

whirlpool.vector = function(n, init)

{

var res = new Array(n)

for (var i = 0; i < n; i++)

res[i] = init || 0

return res

}

whirlpool.sqrt = function(n)

{

for (var i = 0; i < n; i++)

if (i*i == n)

return i

}

whirlpool.add = function(a, b)

{

var n = a.length

var c = whirlpool.matrix(n, n)

for (var i = 0; i < n; i++)

for (var j = 0; j < n; j++)

c[i][j] = a[i][j] ^ b[i][j]

return c

}

// Initialisation.

whirlpool.initialise()

// Optimisations.

whirlpool.cached = function(f)

{

var a = {}

return function(x)

{

if (a[x] !== undefined)

return a[x]

a[x] = f(x)

return a[x]

}

}

whirlpool.sbox = whirlpool.cached(whirlpool.sbox)

Размещено на Allbest.ru