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

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

1. Современные хеш-функции

1.1 Эволюция хеш-функций и их криптоанализа

В 1990 году Рон Ривест (один из соавторов алгоритма RSA) изобрел весьма удачную хеш-функцию MD4 [2]. Это послужило началом для разработки серии MD-подобных хеш-функций, а также для усиленного криптоанализа MD4-подобных хеш-функции. Но когда стало ясно, что MD4 все же не очень хороша с точки зрения криптостойкости, Ривест усовершенствовал ее, а в 1992 году создал MD5, как улучшение MD4 [3]. В 1993 году Агентство национальной безопасности США опубликовало собственный вариант хеш-алгоритма, конструктивно весьма похожего на MD5 и получившего название SHA (Secure Hash Algorithm). Однако, в 1995 году АНБ обнаружило в предложенном алгоритме слабости и предложило новый, улучшенный алгоритм хеширования SHA-1, который стал не только национальным стандартом США, но и вообще наиболее популярной в мире хеш-функцией.

К MD-подобным хеш-функциям относятся:

· 256-битная модификация MD4 (Ривест[4]);

· Защищенный Хеш Алгоритм (Secure Hash Algorithm - SHA) разработанный NIST/NSA, позже замещенный на немного исправленный SHA-1 [5];

· HAVAL, который разработали Зенг, Пипрзук и Саберри [6];

· RIPEMD разработанный в рамках Европейского проекта RIPE[7];

· Усиленные версии RIPEMD RIPEMD-160 и RIPEMD-128 (публикации Босселаерса, Пренила и др. [8]).

Защищенность MD4 была широко проанализирована несколькими авторами. В 1993 году, вскоре после создания MD5, Б. ден Боер и А. Басселаерс [9], нашли псевдоколлизию для MD5, которая состояла из одинаковых сообщений но с разными векторами инициализации. Эта атака показала слабости в битах связанных переменных MD5. Х. Добертин [10] представил «коллизию с полусвободным стартом» (semi free-start), которая содержала два различных 512-битных сообщения с определенным вектором инициализации IV₀^/:

a₀=0x12ac2375, b₀=0xfb341042, c₀=0x5f62b97c, d₀=0x4ba763ed.

Несмотря на то, что Х. Добертин не сумел предложил полноценную коллизию для MD5, его атака послужила началом для выявления слабостей на полный MD5. Его работа дала возможность находить специальный дифференциал за одну итерацию. В данной работе предложена новая мощная атака, которая может эффективно находить коллизии MD5. Из атаки Добертина взята идея поиска всевозможных пар сообщений, состоящих из двух блоков, которые порождают коллизию после второго блока, т.е. ищутся пары и такие что:

,

где - векторы инициализации для MD5.

Для нахождения первых блоков требуется около 2³⁹ операций MD5, а для нахождения вторых блоков требуется около 2³² операций MD5. Программная реализация этих атак на IBM P690 находит за 1 час, а нахождение занимает от 15 секунд до 5 минут. Две такие коллизии MD5 были опубликованы в последнем разделе Crypto`04 [11].

Эта атака хорошо применима ко многим другим хеш-функциям, таким как: MD4, HAVAL-128, RIPEMD ([12], [13], [14]). Применительно к MD4 эта атака находит коллизию меньше чем за секунду, а также позволяет находить прообразы для многих сообщений.

В Crypto`04 Эли Бихам и Рафии Чен представили near-коллизию для SHA-0 [15], а также свои последние результаты для SHA-0 и SHA-1 (включая multi-block методику и коллизии на неполный SHA-1). Позже А. Джоукс представил четырехблочную полную коллизию на SHA-0.

Наилучшие атаки были основаны на free-start коллизии, при которой вектор инициализации хеш-функции заменяется на нестандартное значение. В своей работе «How to break MD5 and other hash functions» [16] авторы Xiaoyun Wang и Hongbo Yu предложили новую атаку на MD5, которая позволила находить коллизии за 15-60 минут. Это дифференциальная атака, но не похожая на большинство дифференциальных атак. Она не использует исключающее ИЛИ (XOR) для определения разности, а вместо этого используется модульная целочисленная разность, которую также называют модульная разность [16]. Результаты Xiaoyun Wang 2005 года показали возможность нахождения коллизий на полный алгоритм SHA-1, то есть на 80 шагов, со сложностью меньшей, чем 2⁶⁹ операций хеширования. Применение такой атаки к MD4 позволяет найти коллизию за доли секунды, а сложность при этом составляет 2⁶. Эта атака также применима к другим хеш-функциям, таким как RIPEMD и HAVAL. После введения нового стандарта AES (Advanced Encryption Standard), с тремя длинами ключей (128, 192, и 256 бит), стойкости SHA-1 оказалось недостаточно. В августе 2002 года вышел новый стандарт Secure Hash Standard, описывающий новые версии функций хеширования: SHA-256, SHA-384, SHA-512, объединённые общим названием - семейство SHA-2. Однако переход на SHA-2 - это лишь временная мера, способная заполнить пробел в алгоритмах хеширования только на ближайшие несколько лет [16].

1.2 Парадокс дней рождений

Парадокс дней рождений используется для теоретической оценки вероятности коллизии хеш-функций.

Очевидно, что чем меньше длина хеш-значения, тем чаще будет встречаться коллизия. Может показаться, что возможность в 50% случаев встретить коллизию наступает после генерации половины всех возможных выходов хеш-функции, и для n-битного хеш-значения потребуется 2^n-1 входов. Это не совсем верно. В действительности, необходимо только приблизительно 2^n/2 входов для того, чтобы получить 50 процентную возможность встретить коллизию. Такое явление названо «парадокс дней рождений».

Сколько человек нужно собрать в одной комнате, чтобы получить 50% возможность такого события, что у двух из них совпадут дни рождения? Ответ на этот вопрос следующий: 23 человека (предполагая, что дни рождения у них распределены равномерно). Такой ответ вытекает из того, что при таком количестве людей в комнате можно будет составить 23*(22/2)=253 различных пар людей.

Применительно к стойкости хеш-функций к коллизиям, можно предположить следующее:

Объёмы данных со временем увеличиваются экспоненциально. Объёмы дискового пространства удваиваются каждые 9 месяцев [40]. Предположим, даже, что объёмы памяти удваиваются каждый год. Тогда, с учётом парадокса дней рождений, можем заключить, что длина хеш-значений должна увеличиваться примерно на 2 бита ежегодно. Например, если сейчас достаточна длина хеш 16 бит, то будет не достаточно 32-битового выхода хеш-функций через 16 лет, или даже раньше.

1.3 Постановка задачи исследования

Сегодня задачи анализа уровня безопасности используемых хеш-функций и поиска путей их совершенствования актуальны как в нашей стране, так и за её пределами. На Украине сегодня стандартизирован и используется алгоритм ГОСТ 34.311-94, который был разработан в Российской Федерации. Поэтому, формирование теоретического базиса в области криптографических алгоритмов хеширования и разработка национального стандарта хеширования является актуальной научной задачей. Решению именно этой научной задачи и посвящена данная дипломная работа.

В рамках дипломной работы необходимо выполнить следующие исследования:

· Рассмотреть современные алгоритмы хеширования;

· Оценить применимость и сложность успешной реализации наиболее эффективных криптоаналитических атак против широко распространённых хеш-функций;

· Выполнить сравнительный анализ производительности широко распространённых хеш-функций;

· Программно реализовать атаку аналитического нахождения коллизии для одной из функций хеширования;

· Сформулировать рекомендации по выбору криптографических алгоритмов хеширования для применения в современных системах.

2 Обзор современных хеш-функций

2.1 Общие принципы построения хеш-функций

Проектирование хеш-функции

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

Существует высокая вероятность среди хеш-значений различных сообщений встретить коллизию. Для предотвращения обнаружения коллизии простым вычислением некоторого количества хеш-значений (атака, основанная на парадоксе дней рождений), должно быть достаточно большим. Пока все еще считается достаточным, но новые результаты ван Оршера и Винера [17] показали, что увеличить минимум до (следующий множитель 32), придётся раньше, чем предполагалось.

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

Хеширование с повторным сжатием

Хеш-функции семейства MD соответствуют принципам изложенным Мерклом и Дамгардом [18]. Основная идея заключается в том что хеширования, подобно шифрованию, должно быть блочным. Принцип Меркла-Дамгарда определяет хеш-функцию как n-битные хеш-значения, полученные от сжатия функции . Принято, что функция инициализируется n-битным вектором, принимает входные блоки фиксированной длины , сжимает их, и возвращает n-битный результат (например, MD4 и MD5 , а ). Входное сообщение произвольной длины разбивается на блоки и при необходимости дополняется до размера кратного :

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

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

2.2 Описание MD-подобных хеш-функций

Алгоритм хеширования MD-5

Для удобного описания структуры MD5 сначала опишем итерационный процесс формирования хеш-функции.

В общем виде, хеш-функция представляет собой итеративно повторяющуюся функцию сжатия , которая сжимает l-битный блок сообщения Z в s-битное хеш-значение X, где . Для MD5 l = 512 и s = 128. Метод итерации обычно называют Markle-Damgard мета-метод [19], [20]. Для большого сообщения M, состоящего из набора l-битных блоков, итерационный процесс представляется в виде:

где , а - вектор инициализации хеш-функции.

Опишем функцию сжатия MD5. Каждый 512-битный блок M_i в составном сообщении M делится на 32-битные слова так, что . Алгоритм сжатия для M_i состоит из 4 циклов, каждый цикл содержит 16 шагов. Ниже приведены четыре последовательных шага операций:

где операция «+» означает сложение по модулю 2³²;

t_i+j и s_i+j (j=0,1,2,3) - константы, зависящие от шага;

w_i+j - слово сообщения;

<<<s_i+j - циклический сдвиг влево на s_i+j бит.

Для каждого шага используется свое значение сдвига (Приложение А, Таблица 3).

Для каждого цикла используется определённая нелинейная функция, которая описывается следующим образом:

Где X, Y и Z - 32-битные слова.

Связанные переменные инициализации для MD5 следующие:

a=0x67452301, b=0xefcdab89, c=0x98badcfe, d=0x10325476.

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

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

Отдельные шаги процесса сжатия MD5, как отдельные хеш-функции семейства MD4, основаны на следующих операциях со словами, где слово имеет длину 32-бита:

? поразрядные Булевы операции;

? сложение по модулю 2³²;

? циклические сдвиги.

Эти операции были выбраны, потому что они быстро вычисляются на обычных 32-битных процессорах, и сочетание Булевых функций и сложения предполагает криптографическую стойкость. Знак «+» обозначает сложение по модулю 2³², а «<<s» определяет циклический сдвиг влево на s позиций.

Проиллюстрируем внутреннюю структуру функции сжатия MD5. -битный вход и -битный вектор инициализации IV разбиваются на слова. Процесс сжатия оперирует четырьмя связанными регистрами A, B, C, D, которые инициализируются IV. Алгоритм сжатия состоит из четырех циклов. Каждый цикл состоит из 16 шагов. В каждом цикле слова входа используются в различном порядке, это показано в таблице 2.1.

Таблица 2.1 - Порядок использования входных слов для различных циклов

шаг	цикл 1	шаг	цикл 2	шаг	цикл 3	шаг	цикл 4
1	[0]	17	[1]	33	[5]	49	[0]
2	[1]	18	[6]	34	[8]	50	[7]
3	[2]	19	[11]	35	[11]	51	[14]
4	[3]	20	[0]	36	[14]	52	[5]
5	[4]	21	[5]	37	[1]	53	[12]
6	[5]	22	[10]	38	[4]	54	[3]
7	[6]	23	[15]	39	[7]	55	[10]
8	[7]	24	[4]	40	[10]	56	[1]
9	[8]	25	[9]	41	[13]	57	[8]
10	[9]	26	[14]	42	[0]	58	[15]
11	[10]	27	[3]	43	[3]	59	[6]
12	[11]	28	[8]	44	[6]	60	[13]
13	[12]	29	[13]	45	[9]	61	[4]
14	[13]	30	[2]	46	[12]	62	[11]
15	[14]	31	[7]	47	[15]	63	[2]
16	[15]	32	[12]	48	[2]	64	[9]

На каждом шаге, изменяется один из связанных регистров. В общем виде шаг операция сжатия MD5 выглядит следующим образом:

где - Булева функция зависящая от цикла, К - константа зависящая от шага, и величина сдвига s, также зависит от шага. После четырех циклов, результатом хеширования является сумма по модулю 2³² текущего значения хеш-функции и значений связанных регистров A, B, C, D.

Алгоритм хеширования SHA-1

Secure Hash Algorithm (SHA) (Безопасный Алгоритм Хеширования), был разработан NIST, вместе с NASA, для использования со стандартом цифровой подписи Digital Signature Standard.

SHA разработан таким образом, что вычислительно невозможно восстановление сообщения соответствующего данному образу (дайджесту), или нахождения двух различных сообщений которые выдают одинаковый образ. Любые изменения в исходном сообщении приведут к коренным изменениям в выходных значениях. SHA основывается на принципах схожих с алгоритмом MD5, и является его дальнейшим развитием. SHA генерирует 160 битный хеш, то есть длиннее, чем MD5 (128 бит).

Рассмотрим принцип работы SHA-алгоритма. Сначала сообщение дополняется до длины, кратной 512. Дополнение производится следующим образом: сначала добавляется единица, а потом столько нулей, сколько требуется для того, чтобы при дальнейшем добавлении 64 бит длина делилась на 512. И, наконец, добавляется 64 битное значение длины сообщения до расширения.

Пять 32 битных переменных устанавливаются равными следующим значениям:

A = 67452301h;

B = EFCDAB89h;

C = 98BADCFEh;

D = 10325476h;

E = C3D2E1F0h.

Затем начинается основной цикл алгоритма, который обрабатывает сообщение по 512 бит за раз, и повторяется столько раз, сколько 512 битных блоков содержит сообщение.

Сначала 5 переменных копируются в другие переменные (в a, b, c, d и e соответственно). Основной цикл содержит 4 внутренних цикла, каждый из которых содержит по 20 операторов. Каждый оператор применяет нелинейную функцию к трем из a, b, c, d и e затем сдвигает общий результат на одно двойное слово.

SHA содержит следующие нелинейные функции:

В алгоритме используются 4 константы:

K_t = 5A827999h t=(0..19);

K_t = 6ED9EBA1h t=(20..39);

K_t = 8F1BBCDCh t=(40..59);

K_t = CA62C1D6h t=(60..79);

Блок сообщения преобразуется из 16-ти 32-х битных слов (M₀…M₁₅) в 80-т 32-х битных слов (W₀…W₇₉) используя следующий алгоритм:

W_t = M_t, t=(0..15)

W_t=(W_t-3 W_t-8 W_t-14 W_t-16) <<< l, t=(16..79)

Интересно заметить, что в оригинале SHA не содержал левого сдвига. Изменение было введено для «корректировки технического недочета, который делал стандарт менее безопасным, чем требуется». NSA отказалось изменять алгоритм так как непонятна природа недочета.

Если t номер операции (0…79), W_t представляет t-тый подблок расширенного сообщения и <<<s представляет левый циклический сдвиг на s бит, тогда основной цикл выглядит так:

for (t=0; t<80; t++) {

tmp = (a <<< 5) + f_t(b, c, d) + e + W_t + K_t

e = d

d = c

c = b <<< 30

b = a

a = tmp

}

На рисунке 1 представлен один оператор. Сдвиг переменных производится используя различные переменные в различных позициях.

Рисунок 1 - Один оператор SHA

После выполнения основного цикла содержимое переменных a, b, c, d и e добавляются к A, B, C, D и E соответственно, и алгоритм продолжается со следующим блоком данных. Окончательный результат работы хеш-функции представляет собой конкатенацию A, B, C, D и E.

2.3 Семейство хеш-функций SHA-2

В стандарте SHS [21], определены 5 стандартных хеш-алгоритмов: SHA-1, SHA-224, SHA-256, SHA-384 и SHA-512, которые генерируют дайджест сообщения длины бит соответственно. SHA-1 - фактически, всемирный стандарт. Однако, опережение в развитии компьютерной мощности приводит к необходимости использования более стойких ключей и хеш-алгоритмов. Следовательно, 4 алгоритма претендуют на то, чтобы стать всемирными стандартами в будущем. Эти 4 алгоритма основаны на общих принципах известных как SHA-2.

Алгоритмы SHA-224 и SHA-256 отличаются один от другого всего в двух моментах: алгоритмы используют различные инициализирующие константы, и SHA-224 использует первые 224 бита. Алгоритмы SHA-384 и SHA-512 также отличаются лишь константами инициализации, и длиной дайджеста. Поэтому их обозначают SHA-224/256 и SHA-384/512. Когда будем говорить: «SHA-2 основан на 32 битных (64 битных соотв.) словах» - то под этим следует понимать, что SHA-224/256 основан на 32 битных словах, а SHA-384/512 на 64 битных словах.

SHA алгоритмы содержат 4 фазы:

? дополнение (до длины кратной 512 (1024), в зависимости от алгоритма, причем младшие 64 (128) бит содержат в двоичном представлении число, равное длине исходного сообщения);

? разбиение сообщения на блоки длиной 512 (1024), в зависимости от алгоритма);

? Разворачивание сообщения (Message scheduling);

? Обновление регистра (Register update) в соответствии с количеством входных блоков.

Обновленный регистр, называют аккумулирующим регистром. Message schedule использует уже дополненное и разбитое сообщение для генерации расширенной (развернутой) последовательности входов в аккумулирующий регистр. Расширенная (развернутая) последовательность используется во время обновления регистров.

Наиболее успешные криптоанализы SHA алгоритмов заключаются в поиске дифференциальных коллизий Chabaud-Joux [22, 23, 24, 25, 26]. Заметим, что коллизии для SHA-0 (частично для SHA-1) найдены Джоуксом [25], а коллизии для MD4, MD5, HAVAL-128 и RIPEMD найдены Ванг и др. [26].

SHA-2 состоит из четырех фаз: дополнение, разбиение (parsing), message scheduling и обновление регистра (register update).

Дополнение (padding): предположим, что длина сообщения - бит. Добавляется единица в конец сообщения, за которой следуют нулевых бит. определяется из уравнения:

(или , соответственно). Затем добавляется 64 битный (или 128 битный соответственно) блок, равный числу в двоичном представлении. После этого длина дополненного сообщения кратна 512 (или 1024 соответственно).

Разбиение (parsing): дополненное сообщение делится на 512 (или 1024) - битных блоков, . 512 (или 1024 соответственно) битов входного блока представляется в виде 16-ти 32-х (или 64-х) битных слов. Первые 32 (или 64 соответственно) бита i-го блока сообщения обозначается , вторые 32 (или 64 соответственно) бита i-го блока сообщения обозначается , и так далее до .

Преобразование сообщения (message schedule): применяется к каждому блоку отдельно. Сначала входным словам присваиваются значения слов сообщения . Остальные входные слова (или ) определяются рекуррентно по формуле:

,

где - линейные функции.

Для SHA-224/256 функции принимают и возвращают 32 битные слова и определяются так:

Для SHA-384/512 функции принимают и возвращают 64 битные слова и определяются следующим образом:

Обновление регистров (register update): аккумулирующий регистр содержит 8 слов: Для первого блока сообщения эти слова инициализируются заранее определенными константами. Для остальных блоков сообщения эти слова инициализируются промежуточными хеш-значениями предыдущих блоков сообщения. За инициализацией следует 64 (80) цикла, на каждом из которых применяется функция сжатия к входной последовательности . i-тый цикл функции сжатия модифицирует аккумулирующий регистр используя входное слово и предопределенную константу в качестве входа. Функция сжатия использует сложение по модулю 2³² (2⁶⁴ соответственно) и четыре нелинейных функции: .

SHA-224/256 использует функции, которые принимают и возвращают 32 битные слова и определяются как:



SHA-384/512 использует функции, которые принимают и возвращают 64 битные слова и определяются как:

Функция сжатия изменяет аккумулирующий регистр согласно следующему алгоритму:

хеш функция вероятность коллизия

После того, как все 64 (или 80) входные слова, поступают на вход аккумулирующего регистра, результирующее значения состояния складываются по модулю 2³² (или 2⁶⁴) со значением инициализации. Эти значения составляют новый промежуточный хеш. Для последнего блока сообщения новый промежуточный хеш является дайджестом сообщения. В остальных случаях, алгоритм выполняет обновление регистра используя следующий блок сообщения.

2.4 Выводы

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

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

Алгоритм SHA-1 был разработан агентством национальной безопасности США (NSA) и является дальнейшим развитием алгоритмов хеширования MD2, MD4, MD5. Длина дайджеста алгоритма SHA-1 была выбрана в соответствии с длиной параметра q алгоритма цифровой подписи DSA.

Дальнейшим развитием алгоритма хеширования SHA-1 стало семейство хеш-функций SHA-2, оно включает в себя четыре алгоритма хеширования, называемые SHA-n, где и определяет длину получаемого дайджеста в битах. Алгоритмы SHA-224 и SHA-256 отличаются один от другого всего в двух моментах: алгоритмы используют различные инициализирующие константы, и SHA-224 использует первые 224 бита. Алгоритмы SHA-384 и SHA-512 также отличаются лишь константами инициализации, и длиной дайджеста. Поэтому их обозначают SHA-224/256 и SHA-384/512.

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