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

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

Московский авиационный институт

(Научно-исследовательский университет)

Курсовая работа

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

Тема: Оценка эффективности типовых приложений обеспечения целостности сообщений с помощью MAC и хэш-функций

Выполнил студент

группы 04-422 Каксис Ю.Р.

Проверил Толкачев В.И.

Москва

2013

Общие положения

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

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

Один из способов обеспечения целостности - это вычисление МАС (Message Authentication Code). В данном случае под МАС понимается некоторый аутентификатор, являющийся определенным способом вычисленным блоком данных, с помощью которого можно проверить целостность сообщения.

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

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

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

Получатель вычисляет МАС, используя тот же самый секретный ключ, и сравнивает вычисленное значение с полученным. Если эти значения совпадают, то с большой долей вероятности можно считать, что при пересылке изменения сообщения не произошло.

MAC = CK (M)

Рассмотрим свойства, которыми должна обладать функция МАС. Если длина ключа, используемого при вычислении МАС, равна k, то при условии сильной функции МАС противнику потребуется выполнить 2^k попыток для перебора всех ключей. Если длина значения, создаваемого МАС, равна n, то всего существует 2ⁿ различных значений МАС.

Предположим, что конфиденциальности сообщения нет, т.е. оппонент имеет доступ к открытому сообщению и соответствующему ему значению МАС. Определим усилия, необходимые оппоненту для нахождения ключа МАС. Предположим, что k > n, т.е. длина ключа больше длины МАС. Тогда, зная М₁ и МАС₁ = С_K (M₁), оппонент может вычислить МАС₁ = СK_i (M₁) для всех возможных ключей K_i.

При этом, по крайней мере, для одного из ключей будет получено совпадение MAC_i = MAC₁.

Оппонент вычислит 2^k значений МАС, тогда как при длине МАС n битов существует всего 2ⁿ значений МАС. Мы предположили, что k > n, т.е. 2^k > 2ⁿ.

Таким образом, правильное значение МАС будет получено для нескольких значений ключей. В среднем совпадение будет иметь место для 2^k / 2ⁿ = 2^(k-n) ключей. Поэтому для вычисления единственного ключа оппоненту требуется знать несколько пар сообщений и соответствующий ему МАС.

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

Функция вычисления МАС должна обладать следующими свойствами:

1. Должно быть вычислительно трудно, зная М и С_K (M), найти сообщение М', такое, что С_K(M) = С_K(M').

2. Значения С_K(M) должны быть равномерно распределенными в том смысле, что для любых сообщений М и M' вероятность того, что С_K(M) = С_K(M'), должна быть равна 2^-n, где n - длина значения МАС.

МАС на основе алгоритма симметричного шифрования

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

Хэш-функция

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

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

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

Таким образом, хэш-функции вместе со схемами электронной цифровой подписи предназначены для решения задач обеспечения целостности и достоверности электронных данных. В прикладных компьютерных системах требуется применение так называемых криптографически стойких хэш-функций. Под термином "криптографически стойкая хэш-функция" понимается функция h, которая является односторонней и свободной от коллизий.

Введем следующие обозначения. Хэш-функция h обозначается как h(б) и h(б,в) для одного и двух аргументов соответственно. Хэш-код функции h обозначается как H.

При этом H₀=I обозначает начальное значение (вектор инициализации) хэш-функции. Под обозначением будет пониматься операция сложения по модулю 2 или логическая операция XOR (исключающая ИЛИ). Результат шифрования блока B блочным шифром на ключе k обозначается E_k(B).

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

В качестве шифрующего преобразования в хэш-функции будут использоваться процедуры шифра DES с ключом k. Тогда, чтобы получить хэш-код H программы M при помощи хэш-функции h необходимо выполнить следующую итеративную операцию:

где код программы M разбит на n 64-битных блока. Хэш-кодом данной хэш-функции является значение H=h(M,I)=H_n.

Стойкость (безопасность) хэш-функций.

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

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

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

Например, для криптоанализа хэш-функций, основанных на использовании криптоалгоритма DES, указанная атака может быть проведена следующим образом. Пусть n - мощность области хэш-кодов (для криптоалгоритма DES она равна 2⁶⁴).

Предположим, что есть две программы m₁ и m₂. Первая программа достоверна, а для второй криптоаналитик пытается получить то же самое значение хэш-кода, выдав таким образом программу m₁ за программу m₂ (то есть криптоаналитик пытается получить коллизию). Для этого криптоаналитик подготавливает порядка различных, незначительно отличающихся версий m₁ и m₂ и для каждой из них вычисляет хэш-код. С высокой вероятностью криптоаналитику удается обнаружить пару версий m`<sub>1</sub> и m`₂, имеющих один и тот же хэш-код.

В дальнейшем при использовании данного хэш-кода можно выдать программу m`<sub>2</sub> вместо программы m`₁, содержание которой близко к содержанию программы m₁.

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

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

Рассмотрим примеры построения хэш-функций на основе алгоритмов шифрования. Наряду с примером, приведенным выше, покажем, как строить хэш-функции на основе наиболее известных блочных шифров ГОСТ 28147 - 89, DES и FEAL. В качестве шифрующего преобразования будут использоваться некоторые режимы шифров ГОСТ 28147-89, DES и FEAL с ключом k. Тогда, чтобы получить хэш-код H программы M при помощи хэш-функции h, необходимо выполнить следующую итеративную операцию (например, с использованием алгоритма ГОСТ 28147-89):

Таким образом, хэш-кодом данной хэш-функции является значение H=h(M,I)=H_n. При этом используется режим выработки имитовставки ГОСТ 28147-89, а шифрующее преобразование 64-битных блоков заключается в выполнении 16 циклов алгоритма шифрования в режиме простой замены.

Алгоритм ГОСТ 28147-89 в качестве базового используется в хэш-функции отечественного стандарта на функцию хэширования сообщений ГОСТ Р 34.11-94, являющегося основным практическим инструментом в компьютерных системах, требующих обеспечения достоверности и целостности электронных данных.

Алгоритм DES (в режиме CFB) можно использовать в качестве базового, например, в следующей хэш-функции (с получением хэш-кода H=h(M,I)=H_n):

шифрование компьютерный хэширование

Другие примеры хэш-функций на основе алгоритмов шифрования. N-хэш алгоритм разработан фирмой Nippon Telephone Telegraph в 1990 году. N-хэш алгоритм использует блоки длиной 128 битов, шифрующую функцию, аналогичную функции алгоритма шифрования FEAL, и вырабатывает блок хэш-кода длиной 128 битов.

На вход пошаговой хэш-функции в качестве аргументов поступают очередной блок кода M_i длиной 128 битов и хэш-код H_i-1 предыдущего шага также размером 128 битов. При этом H₀=I, а H_i=E_k(M_i,H_i-1)M_iH_i-1. Хэш-кодом всего кода программы объявляется хэш-код, получаемый в результате преобразования последнего блока текста.

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

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

Еще одной слабостью указанных выше схем хэширования является то, что размер хэш-кода совпадает с размером блока алгоритма шифрования. Чаще всего размер блока недостаточен для того, чтобы схема была стойкой против атаки на основе "парадокса дня рождения". Поэтому были предприняты попытки построения хэш-функций на базе блочного шифра с размером хэш-кода в k раз (как правило, k=2) большим, чем размер блока алгоритма шифрования.

МАС на основе хэш-функции

НМАС

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

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

· возможность использовать без модификаций уже имеющиеся хэш-функции;

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

· сохранение скорости работы алгоритма, близкой к скорости работы соответствующей хэш-функции;

· возможность применения ключей и простота работы с ними.

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

Введем следующие обозначения:

Вводится два вспомогательных значения:

Далее НМАС вычисляется следующим образом:

Детали HMAC

1. Сообщение разделяется на N блоков, каждый по b битов.

2. Ключ засекречивания дополняется слева нулями, чтобы создать ключ длиной b бит. Обратите внимание: рекомендуется, чтобы ключ засекречивания, прежде чем он будет дополнен, был длиною более чем n бит, где n - размер HMAC.

3. Результат шага 2 складывают по модулю два с константой, называемой ipad ( входной блокнот ), чтобы создать блок b бит. Значение ipad - b/8 - состоит из повторяемой последовательности 00110110 (36 в шестнадцатеричном исчислении).

4. Блок результата присоединим спереди к сообщению из N -блоков. В результате получим N + 1 блоков.

5. Результат шага 4 хэшируется, чтобы создать дайджест длиною n -битов. Мы называем этот дайджест промежуточным HMAC.

6. Промежуточный n -битовый HMAC дополняют слева нулями, чтобы создать b -битовый блок.

7. Шаги 2 и 3 повторяются с другой константой opad ( выходной блокнот ). Значение opad - b/8 - состоит из повторяемой последовательности 01011100 ( 5C в шестнадцатеричном исчислении).

8. Блок результата шага 7 присоединим спереди к блоку шага 6.

9. Результат шага 8 хэшируется, тем же самым алгоритмом хэширования, что и в п. 4, чтобы создать конечный n -разрядный HMAC.

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