Курс лекций «Проблемы безопасности в информационных технологиях»



жүктеу 4.51 Mb.
бет13/44
Дата13.09.2017
өлшемі4.51 Mb.
түріКурс лекций
1   ...   9   10   11   12   13   14   15   16   ...   44

Хеш-функции


Хеш-функцией называется односторонняя функция, предназначенная для получения дайджеста, «свёртки» или «отпечатков пальцев» (“fingerprint”) файла, сообщения или некоторого блока данных.

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

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


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

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

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

Хеш-функция, которая удовлетворяет первым двум свойствам, называется простой или слабой хеш-функцией. Если кроме того выполняется третье свойство, то такая функция называется сильной хеш-функцией. Третье свойство защищает против класса атак, известных как атака «дней рождения».

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



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

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

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

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

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

Парадокс «дней рождения»


Парадокс дней рождения – это, на первый взгляд, кажущееся парадоксальным утверждение: вероятность совпадения дней рождения (числа и месяца) хотя бы у двух членов группы из 23 и более человек, превышает 50%. Для 60 и более человек вероятность такого совпадения превышает 99%, хотя 100% она достигает, согласно принципу Дирихле, только когда в группе не менее 367 человек (с учётом високосных лет).

На интуитивном уровне можно осознать, почему в группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока: поскольку рассматривается вероятность совпадения дней рождения у любых двух человек в группе, то эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, то общее число таких пар равно числу сочетаний из 23 по 2, то есть 23 × 22/2 = 253 пары. Глядя на это число, легко понять, что при рассмотрении 253 пар людей вероятность совпадения дней рождения хотя бы у одной пары будет достаточно высокой.

Ключевым моментом здесь является то, что утверждение парадокса дней рождения говорит именно о совпадении дней рождения у каких-либо любых двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим – похожим, на первый взгляд, – случаем, когда из группы выбирается один человек и оценивается вероятность того, что у кого-либо из других членов группы день рождения совпадёт с конкретным днем рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.

Для расчёта вероятности того, что в группе из n человек как минимум у двух человек дни рождения совпадут, примем, что дни рождения распределены равномерно, нет високосных лет, близнецов, рождаемость не зависит от дня недели, времени года и других факторов.



Вначале рассчитаем, какова вероятность (n) того, что в группе из n человек дни рождения всех людей будут различными. Если n > 365, то в силу принципа Дирихле вероятность равна нулю. Если же n 365, то возьмём наугад одного человека из группы и запомним его день рождения. Затем возьмём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна 1 — 1/365. Затем возьмём третьего человека, при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна 1 — 2/365. Рассуждая по аналогии, мы дойдём до последнего человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна 1 — (n — 1)/365. Перемножая все эти вероятности, получаем вероятность того, что все дни рождения в группе будут различными:
= 1·(1 – )·(1 – )···(1 – ) = =
Следовательно, вероятность того, что хотя бы у двух человек из n дни рождения совпадут, равна:
p(n)= 1 – (n)
Значение этой функции превосходит ½ при n = 23 (при этом вероятность совпадения равна примерно 50,7 %). Ниже приведена таблица вероятностей для некоторых значений n:


n

p(n)

10

12 %

20

41 %

30

70 %

50

97 %

100

99,99996 %

200

99,9999999999999999999999999998 %

300

(1 − 7×10−73) × 100 %

350

(1 − 3×10−131) × 100 %

367

100 %

Возможна следующая стратегия атаки, основанной на «парадоксе дней рождения»:




  • Противник создает 2n/2 вариантов сообщения, каждое из которых имеет некоторый определенный смысл. Противник подготавливает такое же количество сообщений, каждое из которых является поддельным и предназначено для замены настоящего сообщения.

  • Два набора сообщений сравниваются в поисках пары сообщений, имеющих одинаковый хеш-код. Вероятность успеха в соответствии с «парадоксом дней рождения» больше, чем ½. Если соответствующая пара не найдена, то создаются дополнительные исходные и поддельные сообщения до тех пор, пока не будет найдена требуемая пара.

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

Таким образом, если используется 64-битный хeш-код, то необходимая сложность вычислений составляет порядка 232.


Хеш-функция MD5


MD5 (англ. Message Digest 5) – 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 году. Предназначен для создания «отпечатков» или дайджестов сообщения произвольной длины и последующей проверки их подлинности. Является улучшенной в плане безопасности версией MD4. Описан в RFC1321.


Рис.23 Схема работы алгоритма MD5
На вход алгоритма поступает поток данных, хеш которого необходимо найти. Длина сообщения может быть любой, в том числе нулевой. Определим длину сообщения как L, целое неотрицательное число. Алгоритм выполняется за пять шагов.

Шаг 1: Выравнивание (добавление недостающих битов). Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина 448 mod 512 или L´ = 512 * N + 448). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Т.е., если длина сообщения составляет ровно 448 битов, оно всё равно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Сначала дописывают единичный бит в конец потока (байт 0x80), затем необходимое число нулевых бит.

Шаг 2: Добавление длины сообщения. В оставшиеся 64 бита дописывается 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записываются младшие 4 байта. Если длина превосходит 264 – 1, то дописываются только младшие 64 бита (т.е. Таким образом, поле содержит длину исходного сообщения по модулю 264). После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.


Рис.24 Структура расширенного сообщения
Шаг 3: Инициализация MD-буфера. Используется 128-битный буфер для хранения промежуточных и окончательных результатов хеш-функции. Буфер представлен как четыре 32-битных регистра (A,B,C,D). Эти регистры инициализируются следующими шестнадцатеричными числами (инициализирующий вектор):
А = 01 23 45 67

В = 89 AB CD EF

С = FE DC BA 98

D = 76 54 32 10


Шаг 4: Вычисление в цикле последовательности 512-битных (16-словных) блоков. Основой алгоритма является модуль, состоящий из четырех циклических обработок, обозначенный как HMD5. Четыре цикла имеют похожую структуру, но каждый цикл использует свою элементарную логическую функцию, обозначаемую fF, fG, fH и fI соответственно.



Рис.25 Обработка 512-битного блока
Каждый цикл принимает в качестве входа текущий 512-битный блок Yq, обрабатывающийся в данный момент и 128-битное значение буфера ABCD, которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. Каждый цикл также использует четвертую часть 64-элементной таблицы T[1...64], построенной на основе функции sin. i-ый элемент T, обозначаемый T[i], имеет значение, равное целой части от 232 * abs (sin (i)), i задано в радианах. Так как abs (sin (i)) является числом между 0 и 1, каждый элемент Т является целым, которое может быть представлено 32 битами. Таблица обеспечивает «случайный» набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения MDq+1 выход четырех циклов складывается по модулю 232 с MDq. Сложение выполняется независимо для каждого из четырех слов в буфере.

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


Рис. 26 Выполнение отдельного шага
Алгебраически отдельный шаг можно представить как:
A ← B + CLSs(A + f(B,C,D) + X[k] + T[i])
где
A, B, C, D - четыре слова буфера; после выполнения каждого отдельного шага происходит циклический сдвиг влево на одно слово.

f – одна из элементарных функций fF, fG, fH, fI.

CLSs - циклический сдвиг влево на s битов 32-битного аргумента.

X[k] – M[q * 16 + k] – k-ое 32-битное слово в q-ом 512-битном блоке сообщения.

T[i] – i-ое 32-битное слово в матрице Т.

+ – сложение по модулю 232.
На каждом из четырех циклов алгоритма используется одна из четырех элементарных логических функций. Каждая элементарная функция получает три 32-битных слова на входе и на выходе создает одно 32-битное слово. Каждая функция является множеством побитовых логических операций, т.е. n-ый бит выхода является функцией от n-ого бита трех входов. Используются следующие элементарные функции:
fF = (BC)(BD)

fG = (BD)(DC)

fH = BCD

fI = C(DB)


Массив из 32-битных слов X [0..15] содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по схеме, показанной на рис.26, 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битных слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т, состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D. На каждом шаге изменяется только одно из четырех слов буфера ABCD. Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

Шаг 5: Результат вычислений, после обработки всех L 512-битных блоков, находится в буфере ABCD, это и есть хеш. Если выводить побайтово, начиная с младшего байта A и закончив старшим байтом D, то мы получим 128-битный MD5-хеш.

Можно суммировать алгоритм MD5 следующим образом:


MD0 = IV – инициализирующий вектор

MDq+1 = MDq + fI[Yq, fH[Yq, fG[Yq, fF[Yq, MDq]]]]

MD = MDL-1
где
IV – начальное значение буфера ABCD, определенное на шаге 3.

Yqq-ый 512-битный блок сообщения.

L – число блоков в сообщении (включая поля дополнения и длины).

MD – окончательное значение дайджеста сообщения.


Алгоритм MD5 происходит от MD4. По сравнению с MD4 в MD5 добавили один раунд (их стало 4 вместо 3), добавили новую константу для того, чтобы свести к минимуму влияние входного сообщения, в каждом раунде на каждом шаге и каждый раз константа разная, она суммируется с результатом F и блоком данных. Изменилась функция fG. Результат каждого шага складывается с результатом предыдущего шага, из-за этого происходит более быстрое изменение результата. Изменился порядок работы с входными словами в раундах 2 и 3.

MD5 обладает хорошим «лавинным эффектом», в примере ниже изменение всего одного входного бита: ASCII символ «5» с кодом 0x3516 = 0001101012 заменяется на символ «4» с кодом 0x3416 = 0001101002 приводит к полному изменению хеша:


MD5("md5") = 1bc29b36f623ba82aaf6724fd3b16718

MD5("md4") = c93d3bf7a7c4afe94b64e30c2ce39f4f


В 1993 году Берт ден Бур (Bert den Boer) и Антон Босселарс (Antoon Bosselaers) показали, что в алгоритме возможны псевдоколлизии, когда разным инициализирующим векторам соответствуют одинаковые дайджесты для входного сообщения.

В 1996 году Ганс Доббертин (Hans Dobbertin) объявил о коллизии в алгоритме и уже в то время было предложено использовать другие алгоритмы хеширования, такие как Whirlpool, SHA-1 или RIPEMD-160.

Из-за небольшого размера хеша в 128 бит, можно рассматривать атаки «дней рождения» (“birthday”). В марте 2004 года был запущен проект MD5CRK с целью обнаружения уязвимостей алгоритма, используя атаки «дней рождения». Проект MD5CRK закончился 17 августа 2004 года, когда Ван Сяоюнь (Wang Xiaoyun), Фэн Дэнго (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) обнаружили уязвимости в алгоритме.

1 марта 2005 года Arjen Lenstra, Xiaoyun Wang и Benne de Weger продемонстрировали построение двух X.509 документов с различными открытыми ключами и одинаковым хешем MD5.

18 марта 2006 года исследователь Властимил Клима (Vlastimil Klima) опубликовал алгоритм, который может найти коллизии за одну минуту на обычном компьютере, метод получил название «туннелирование».

Хеш-функция SHA-1


Secure Hash Algorithm 1 (SHA-1) – алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум 264-1 бит, что равно 2 экзабайтам) алгоритм генерирует 160-битное хеш-значение (дайджест). Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании MD4.


Рис.27 Схема работы алгоритма SHA-1
SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. SHA-1 выполняется за пять шагов, описанных ниже.

Шаг 1: Выравнивание (добавление недостающих битов). Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина 448 mod 512 или L´ = 512 * N + 448). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512. Сначала в конец потока дописывают единичный бит (байт 0x80), затем необходимое число нулевых бит.

Шаг 2: Добавление длины сообщения. В оставшиеся 64 бита дописывается 64-битное представление длины данных (количество бит в сообщении) до выравнивания. После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит * L.

Шаг 3: Инициализация SHA-1 буфера. Используется 160-битный буфер для хранения промежуточных и окончательных результатов хеш-функции. Буфер представлен как пять 32-битных регистров (A,B,C,D,E). Эти регистры инициализируются следующими шестнадцатеричными числами (инициализирующий вектор):
A = 67 45 23 01

B = EF CD AB 89

C = 98 BA DC FE

D = 10 32 54 76

E = C3 D2 E1 F0
Шаг 4: Вычисление в цикле последовательности 512-битных (16-словных) блоков. Основой алгоритма является модуль, состоящий из 80 циклических обработок, обозначенный как HSHA. Все 80 циклических обработок имеют одинаковую структуру.



Рис.28 Обработка 512-битного блока
Каждый цикл получает на входе текущий 512-битный обрабатываемый блок Yq и 160-битное значение буфера ABCDE, и изменяет содержимое этого буфера.

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


0 t 19 Kt = 5A827999

(целая часть числа [230 × 21/2])

20 t 39 Kt = 6ED9EBA1



(целая часть числа [230 × 31/2])

40 t 59 Kt = 8F1BBCDC



(целая часть числа [230 × 51/2])

60 t 79 Kt = CA62C1D6



(целая часть числа [230 × 101/2])
Для получения SHAq+1 выход 80-го цикла складывается со значением SHAq. Сложение по модулю 232 выполняется независимо для каждого из пяти слов в буфере с каждым из соответствующих слов в SHAq.

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





Рис.29 Выполнение отдельного цикла
Алгебраически обработку в каждом отдельном цикле можно представить как:

A, B, C, D, E (CLS5(A) + ft(B,C,D) + E + Wt + Kt), A, CLS30(B), C, D



Где

A, B, C, D, E – пять слов из буфера.

t – номер цикла, 0 t 79.

ft – элементарная логическая функция.

CLSs – циклический левый сдвиг 32-битного аргумента на s битов.

Wt – 32-битное слово, полученное из текущего входного 512-битного блока.

Kt – дополнительная константа.

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


Номер цикла

ft(B,C,D)

0t19

(BC)(BD)

20t39

BCD

40t59

(BC)(BD)(CD)

60t79

BCD

В реальности используется только три функции, т.к. для 0t 19 функция является условием if B then C else D. Для 20t39 и 60t79 создаётся бит чётности (сумма по модулю 2). Для 40t59 функция будет истинной, если два или три аргумента истинны.

32-битные слова Wt получаются из текущего 512-битного блока сообщения следующим образом.




Рис.30 Получение входных значений каждого цикла из очередного блока
Первые 16 значений Wt берутся непосредственно из 16 слов текущего блока. Оставшиеся значения определяются следующим образом:
Wt = Wt-16 Wt-14 Wt-8 Wt-3
В первых 16 циклах вход состоит из 32-битного слова текущего блока. Для оставшихся 64 циклов вход состоит из XOR нескольких слов из блока сообщения.

Шаг 5: Выход. После обработки всех 512-битных блоков выходом L-ой стадии является 160-битный хеш (дайджест) сообщения.

Можно суммировать алгоритм SHA-1 следующим образом:


SHA0 = IV – вектор инициализации

SHAq+1 = Σ32(SHAq, ABCDEq)

SHA = SHAL-1
где
IV - начальное значение буфера ABCDE.

ABCDEq - результат обработки q-того блока сообщения.

L - число блоков в сообщении, включая поля добавления и длины.

Σ32 - сумма по модулю 232, выполняемая отдельно для каждого слова буфера.



SHA - значение дайджеста сообщения.
Оба алгоритма, SHA-1 и MD5, произошли от MD4, поэтому имеют много общего.
Сходства:

  1. Четыре этапа.

  2. Каждое действие прибавляется к ранее полученному результату.

  3. Размер блока обработки равный 512 бит.

  4. Оба алгоритма выполняют сложение по модулю 232, они ориентированы на 32-битную архитектуру.

Различия:

  1. В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе.

  2. В MD5 в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырех групп.

  3. В SHA-1 добавлена пятая переменная.

  4. SHA-1 использует циклический код исправления ошибок.

  5. В MD5 четыре сдвига, используемые на каждом этапе отличаются от значений, используемых на предыдущих этапах. В SHA на каждом этапе используется постоянное значение сдвига.

  6. В MD5 четыре различных элементарных логических функции, в SHA-1 — три.

  7. В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.

  8. Дайджест SHA-1 на 32 бита длиннее, чем дайджест MD5. Если предположить, что оба алгоритма не содержат каких-либо структурированных данных, которые уязвимы для криптоаналитических атак, то SHA-1 является более стойким алгоритмом. Используя brute force атаку, труднее создать произвольное сообщение, имеющее данный дайджест, если требуется порядка 2160 операций, как в случае алгоритма SHA-1, чем порядка 2128 операций, как в случае алгоритма MD5. Используя лобовую атаку, труднее создать два сообщения, имеющие одинаковый дайджест, если требуется порядка 280 как в случае алгоритма SHA-1, чем порядка 264 операций как в случае алгоритма MD5 (атака «дней рождения»).

  9. SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25 % медленнее, чем MD5 на той же аппаратуре.

  10. MD5 использует little-endian схему для интерпретации сообщения как последовательности 32-битных слов, в то время как SHA-1 задействует схему big-endian. Каких-либо преимуществ в этих подходах не существует.

В итоге Брюс Шнайер приходит к следующему выводу: «SHA-1 – это MD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. MD5 – это MD4 с улучшенным битовым хешированием, дополнительным этапом и улучшенным лавинным эффектом».

Хеш-функция SHA-2


SHA-2 (Secure Hash Algorithm Version 2 — безопасный алгоритм хеширования, версия 2) – собирательное название однонаправленных хеш-функций SHA-224, SHA-256, SHA-384 и SHA-512. Хеш-функции предназначены для создания «отпечатков» (“fingerprints”) или «дайджестов» сообщений произвольной битовой длины.


Рис.31 Схема одной итерации алгоритмов SHA-2
Хеш-функции SHA-2 разработаны Агентством национальной безопасности США и опубликованы Национальным институтом стандартов и технологий в федеральном стандарте обработки информации FIPS PUB 180-2 в августе 2002 года. В этот стандарт также вошла хеш-функция SHA-1, разработанная в 1995 году. В феврале 2004 года в FIPS PUB 180-2 была добавлена SHA-224. В октябре 2008 года вышла новая редакция стандарта – FIPS PUB 180-3.

В июле 2006 года появился стандарт RFC 4634 «Безопасные хеш-алгоритмы США (SHA и HMAC-SHA)», описывающий SHA-1 и семейство SHA-2.

Агентство национальной безопасности от лица государства выпустило патент на SHA-2 под лицензией Royalty Free.

Хеш-функции семейства SHA-2 построены на основе структуры Меркла—Дамгарда. Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64-мя или 80-ю итерациями (раундами). На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции.

При работе алгоритмы используют следующие битовые операции:


  • ǁ — конкатенация (объединение),

  • + — сложение,

  • and — побитовое «И»,

  • or — побитовое «ИЛИ»,

  • xor () — исключающее «ИЛИ»,

  • shr (shift right) — логический сдвиг вправо,

  • rotr (rotate right) — циклический сдвиг вправо.

В таблице ниже приведены некоторые технические характеристики различных вариантов SHA:



Алгоритм

Длина сообщения (в битах)

Длина блока (в битах)

Длина слова (в битах)

Длина дайджеста сообщения (в битах)

Безопасность (в битах)

SHA-1

<264

512

32

160

80

SHA-224

<264

512

32

224

112

SHA-256

<264

512

32

256

128

SHA-384

<2128

1024

64

384

192

SHA-512

<2128

1024

64

512

256

SHA-256 использует шесть логических функций, при этом каждая из них выполняется с 32-битными словами, обозначенными как x, y и z. Результатом каждой функции также является 32-битное слово. ROTRn и ROTLn – циклические сдвиги вправо и влево, соответственно, на n разрядов.

Ch(x,y,z) = (xy)(¬xz)

Maj(x,y,z) = (xy)(xz)(yz)

Σ0{256}(x) = ROTR2(x)ROTR13(x)ROTR22(x)

Σ1{256}(x) = ROTR6(x)ROTR11(x)ROTR25(x)

σ0{256}(x) = ROTR7(x)ROTR18(x)SHR3(x)

σ1{256}(x) = ROTR17(x) ROTR19(x)SHR10(x)
SHA-384 и SHA-512 также используют шесть логических функций, каждая из которых выполняется над 64-битными словами, обозначенными как x, y и z. Результатом каждой функции является 64-битное слово.
Ch(x, y, z) = (xy)(¬xz)

Maj(x, y, z) = (xy)(xz)(yz)

Σ0{512}(x) = ROTR28(x)ROTR34(x)ROTR39(x)

Σ1{512}(x) = ROTR14(x)ROTR18(x)ROTR41(x)

σ0{512}(x) = ROTR1(x)ROTR8(x)SHR7(x)

σ1{512}(x) = ROTR19(x)ROTR61(x)SHR6(x)


Предварительная подготовка сообщения, т.е. добавление определенных битов до целого числа блоков и последующее разбиение на блоки выполняется аналогично тому, как это делалось в SHA-1 (конечно, с учетом длины блока каждой хеш-функции). После этого каждое сообщение можно представить в виде последовательности N блоков M(1), M(2),…M(N).

В SHA-256 инициализируются восемь 32-битных переменных, которые послужат промежуточным значением хэш-кода a, b, c, d, e, f, g, h. Основой алгоритма является модуль, состоящий из 64 циклических обработок каждого блока M(i):


T1 = h + Σ1{256}(e) + Ch(e,f,g) + Kt{256} + Wt

T2 = Σ0{256}(a) + Maj(a,b,c)

h = g

g = f


f = e

e = d + T1

d = c

c = b


b = a

a = T1 + T2


где Ki{256}— шестьдесят четыре константы, каждая из которых является первыми 32-мя битами дробной части кубических корней первых 64 простых чисел.

Wt вычисляются из очередного блока сообщения по следующим правилам:


Wt = Mt(i), 0t15

Wt = σ1{256}(Wt-2) + Wt-7 + σ0{256}(Wt-15) + Wt-16,

16t63
i-ое промежуточное значение хэш-кода H(t) вычисляется следующим образом:
H0(i) = a + H0(i-1)

H1(i) = b + H1(i-1)

H2(i) = c + H2(i-1)

H3(i) = d + H3(i-1)

H4(i) = e + H4(i-1)

H5(i) = f + H5(i-1)

H6(i) = g + H6(i-1)

H7(i) = h + H7(i-1)


SHA-224 идентичен SHA-256, за исключением:

  • для инициализации переменных H0—H7 используются другие начальные значения.

  • в итоговом хеше опускается значение H7.

В SHA-512 инициализируются восемь 64-битных переменных, которые послужат промежуточным значением хеш-кода a, b, c, d, e, f, g, h.

Основой алгоритма является модуль, состоящий из 80 циклических обработок каждого блока M(i):
T1 = h + Σ1{512}(e) + Ch(e,f,g) + Kt{512} + Wt

T2 = Σ0{512}(a) + Maj(a,b,c)

h = g

g = f


f = e

e = d + T1

d = c

c = b


b = a

a = T1 + T2


где Ki{512} – восемьдесят 64-битных констант, каждая из которых является первыми 64-мя битами дробной части кубических корней первых восьмидесяти простых чисел.

Wt вычисляются из очередного блока сообщения по следующим правилам:


Wt = Mt(i), 0t15

Wt = σ1{512}(Wt-2) + Wt-7 + σ0{512}(Wt-15) + Wt-16,

16t79
i-ое промежуточное значение хэш-кода H(t) вычисляется следующим образом:
H0(i) = a + H0(i-1)

H1(i) = b + H1(i-1)

H2(i) = c + H2(i-1)

H3(i) = d + H3(i-1)

H4(i) = e + H4(i-1)

H5(i) = f + H5(i-1)

H6(i) = g + H6(i-1)

H7(i) = h + H7(i-1)


SHA-384 идентичен SHA-512, за исключением:

  • для инициализации переменной H0 используются другой начальный хеш-код.

  • 384-битный дайджест получается из левых 384 битов окончательного хэш-кода H(N):

H0(N) ǁ H1(N) ǁ H2(N) ǁ H3(N) ǁ H4(N) ǁ H5(N)


В 2003 году Гилберт и Хандшух провели исследование SHA-2, но не нашли каких-либо уязвимостей. Однако в марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22-х итераций SHA-256 и SHA-512. В сентябре того же года они представили метод конструирования коллизий для усечённых вариантов SHA-2 (21 итерация).

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



  • нахождение коллизий, т. е. разных сообщений с одинаковым хешем.

  • нахождение прообраза, т. е. неизвестного сообщения по его хешу.

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

Ввиду алгоритмической схожести SHA-2 с SHA-1 и наличия у последней потенциальных уязвимостей ведутся поиски улучшенных альтернатив. Новый стандарт будет назван SHA-3, он будет определен конкурсом, проводимым Национальным институтом стандартов и технологий в 2008—2012 гг.



Хеш-функция ГОСТ Р 34.11-94


ГОСТ Р 34.11-94 — российский криптографический стандарт вычисления хеш-функции. Дата опубликования: 23 мая 1994 года. Размер хеша: 265 бит. Размер блока входных данных: 256 бит. Разработчик: ГУБС ФАПСИ и Всероссийский научно-исследовательский институт стандартизации. Структура ГОСТ Р 34.11-94  сильно отличается от MD5, SHA-1,2, которые базируются на MD4.

Сообщение обрабатывается блоками по 256 бит справа налево. Каждый блок сообщения обрабатывается по следующему алгоритму.



  1. Генерация четырех ключей длиной 256 бит каждый.

  2. Шифрование 64-битных значений промежуточного хеш-кода H на ключах Ki(i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.

  3. Перемешивание результата шифрования.

Для генерации ключей используются следующие данные:

  • промежуточное значение хэш-кода H длиной 256 бит;

  • текущий обрабатываемый блок сообщения M длиной 256 бит;

  • параметры - три значения С2, С3 и С4 длиной 256 бит следующего вида: С2 и С4 состоят из одних нулей, а С3 равно

18 08 116 024 116 08 (08 18)2 18 08 (08 18)4 (18 08)4 – где степень означает количество повторений 0 или 1.
Используются две формулы, определяющие перестановку и сдвиг. Перестановка Р битов определяется следующим образом: каждое 256-битное значение рассматривается как последовательность тридцати двух 8-битных значений. Перестановка Р элементов 256-битной последовательности выполняется по формуле y = (x), где x - порядковый номер 8-битного значения в исходной последовательности; y - порядковый номер 8-битного значения в результирующей последовательности.
φ(i + 1 + 4(k - 1)) = 8i + k

i = 0÷3, k = 1÷8

Сдвиг A определяется по формуле

A (x) = (x1x2)ǁ x4ǁ x3ǁ x2

Где


xi – соответствующие 64 бита 256-битного значения x,

ǁ – обозначает конкатенацию.

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

i = 1, U = H, V = M.

W = UV, K1 = Р(W)

Ключи K2, K3, K4 вычисляются последовательно по следующему алгоритму:

U = A(U)Сi,

V = A(A(V)),

W = UV,

Ki = Р(W)

Далее выполняется шифрование 64-битных элементов текущего значения хэш-кода Н с ключами K1, K2, K3 и K4. При этом хэш-код Н рассматривается как последовательность 64-битных значений:

H = h4 ǁ h3 ǁ h2 ǁ h1

Выполняется шифрование алгоритмом ГОСТ 28147:

si = EKi[hi]   i = 1,2,3,4

S = s1 ǁ s2 ǁ s3 ǁ s4

Наконец на заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений. Сдвиг обозначается Ψ и определяется следующим образом:


η16 ǁ η15 ǁ ... ǁ η1 – исходное значение

η1η2η3η4η13η16 ǁ η16 ǁ ... ǁ η2 – результирующее значение




Результирующее значение хеш-кода определяется следующим образом:

Χ(M,H) = ψ61 (Hψ (Mψ12(S)))

где

H – предыдущее значение хеш-кода,



M – текущий обрабатываемый блок,

ψ i – i-ая степень преобразования ψ.


Резюмируя, логику выполнения ГОСТ Р 34.11-94 можно представить следующим образом – входными параметрами алгоритма являются:

  • исходное сообщение М произвольной длины;

  • стартовый вектор хеширования Н, длина которого равна 256 битам;

  • контрольная сумма Σ, начальное значение которой равно нулю и длина равна 256 битам;

  • переменная L, начальное значение которой равно длине сообщения.

Сообщение М делится на блоки длиной 256 бит и обрабатывается справа налево. Очередной блок i обрабатывается следующим образом:




  1. H = Χ(Mi, H)

  2. Σ = Σ ' Mi

  3. L рассматривается как неотрицательное целое число, к этому числу прибавляется 256 и вычисляется остаток от деления получившегося числа на 2256. Результат присваивается L.

Где ' обозначает следующую операцию: Σ и Mi рассматриваются как неотрицательные целые числа длиной 256 бит. Выполняется обычное сложение этих чисел и находится остаток от деления результата сложения на 2256. Этот остаток и является результатом операции.


Самый левый, т.е. самый последний блок М' обрабатывается следующим образом:


  1. Блок добавляется слева нулями так, чтобы его длина стала равна 256 битам.

  2. Вычисляется Σ = Σ ' Mi.

  3. L рассматривается как неотрицательное целое число, к этому числу прибавляется длина исходного сообщения М и находится остаток от деления результата сложения на 2256.

  4. Вычисляется Н = Χ(М', Н).

  5. Вычисляется Н = Χ(L, Н).

  6. Вычисляется Н = Χ(Σ, Н).

Значением функции хеширования является Н.

ЦБ РФ требует использовать ГОСТ Р 34.11-94 для электронной подписи предоставляемых ему документов. Российская компания CryptoPro написала собственный «информационный» RFC4357. Согласно ему реализации ГОСТ Р 34.11-94 должны использовать набор S-блоков разработанный этой компанией. В известной открытой библиотеке OpenSSL начиная с версии 1.0.0 в качестве плагина появилась хеш функция ГОСТ Р 34.11-94 именно с этими параметрами.

Коды аутентификации сообщений – МАС


Имитовставка (MAC, message authentication code — код аутентичности сообщения) — средство обеспечения имитозащиты в протоколах аутентификации сообщений с доверяющими друг другу участниками — специальный набор символов, который добавляется к сообщению и предназначен для обеспечения его целостности и аутентификации источника данных.

MAC обычно применяется для обеспечения целостности и защиты от фальсификации передаваемой информации.

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

Для защиты от фальсификации (имитации) сообщения применяется имитовставка, выработанная с использованием секретного элемента (ключа), известного только отправителю и получателю.

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

Другим способом является выработка имитовставки (MAC) с помощью специализированного алгоритма имитозащиты на основе симметричного алгоритма шифрования.

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

Еще один вариант: использования хеш-функции для получения МАС состоит в том, чтобы определенным образом добавить секретное значение к сообщению, которое подается на вход хеш-функции. Такой алгоритм носит название НМАС (hash-based message authentication code, хеш-код идентификации сообщений), и он описан в RFC 2104.

При разработке алгоритма НМАС преследовались следующие цели:


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

  • Чтобы сохранить первоначальное исполнение хеш-функции без каких нибудь значительных ухудшений

  • Использовать и обрабатывать ключи более простым способом.

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





Рис.32 Эффективная реализация HMAC
Хеш-функция разделяет сообщения на блоки фиксированного размера и применяет к ним функцию сжатия. (MD5 или SHA-1 используют блоки 512 бит). После применения HMAC размер результата не меняется (128 или 160 бит для MD5 и SHA-1).

HMAC определяется следующим образом:


HMACK(m) = h((Kopad)ǁ h((Kipad)ǁ m)), где


  • h — хеш-функция

  • К — секретный ключ, дополненный нулями до размера блока

  • m — сообщение для идентификации

  • ǁ — конкатенация

  • — xor

  • opad — 0x5c5c..5c (длина равна размеру блока)

  • ipad — 0x3636..36 (длина равна размеру блока)

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

HMAC используется в протоколах IPSec (для AH и ESP) и TLS.




Достарыңызбен бөлісу:
1   ...   9   10   11   12   13   14   15   16   ...   44


©kzref.org 2019
әкімшілігінің қараңыз

    Басты бет