Целостность сообщения и установление подлинности сообщения

Разбить на страницы

Показывать лекцию целиком

1.1. Целостность сообщения

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

Документ и отпечатки пальцев

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

Сообщение и дайджест сообщения

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

(рис 1.1) Сообщение и дайджест

Различия

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

Дайджест сообщения должен быть защищен от изменения.

Проверка целостности

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

(рис 1.2) Проверка целостности

Криптографические критерии хэш-функции

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

(рис 1.3) Критерии криптографической функции

Устойчивость прообраза

Криптографическая функция должна быть устойчива к прообразу. Если дана хэш-функция h и y = h(M), то для Евы должно быть экстремально трудно найти сообщение, такое, что y = h(M'). рис. 1.4 иллюстрирует эту идею.

(рис 1.4) Прообраз

Если хэш-функция - неустойчивый прообраз, Ева может перехватить дайджест h(M), создать сообщение M' и затем передать M' Бобу вместо исходного М.

Атака прообраза

Дано: y = h (M) Найти: такое М', что y = h (M').

Пример 1.1

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

Решение

Не можем. Метод сжатия без потерь создает сжатое сообщение, которое должно быть обратимо. Вы можете обработать сжатое сообщение, чтобы получить первоначальный текст.

Пример 1.2

Можем ли мы использовать функцию контрольной суммы как криптографическую хэш-функцию?

Решение

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

Устойчивость ко второму прообразу

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

(рис 1.5) Второй прообраз

Ева перехватывает (имеет доступ к) сообщение М и его дайджест h(M). Она создает другое сообщение М.' М., но h (M) = h(M'). Ева передает М.' и h (M') Бобу. Ева подделала сообщение.

Атака второго прообраза

Дана Атака: М и h (M) Найти: такое M' = М, что h (M) = h (M').

Устойчивость к коллизиям

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

(рис 1.6) Устойчивость к коллизиям

1.2. Случайная модель Oracle

Случайная модель Oracle была предложена в 1993 г. Белларом (Bellare) и Роджеем (Rogaway). Это идеальная математическая модель для хэш-функции. Функция, которая основана на этой модели, обладает следующими свойствами.

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

Когда передается сообщение, для которого существует дайджест, oracle просто вставляет дайджест в запись.

Дайджест для нового сообщения должен быть выбран независимо от всех предыдущих дайджестов. Это подразумевает, что модель Oracle не может использовать формулу или алгоритм для вычисления дайджеста.

Пример 1.3

Возьмем модель Oracle с таблицей и правильной монетой. Таблица имеет два столбца. Левый столбец - сообщения, дайджесты которых были выработаны. Второй столбец перечисляет дайджесты, созданные для этих сообщений. Примем, что дайджест - всегда 16 битов независимо от размера сообщения. табл. 1.1 показывает пример такой таблицы, в которой сообщение и дайджест сообщения приведены в шестнадцатеричном исчислении. Модель Oracle уже создала три дайджеста.

Таблица Oracle после создания первых трех дайджестов
Сообщение	Дайджест сообщения
`4523AB1352CDEF45126`	`13AB`
`723BAE38F2AB3457AC`	`02CA`
`AB45CD1048765412AAAB6662BE`	`A38B`

Теперь предположим, что возникают два события:

а. Поступает сообщение AB1234CDS765BDAD для вычисления дайджеста. Oracle проверяет свою таблицу. Этого сообщения нет в таблице, так что сотрудник, использующий Oracle, подбрасывает в воздух свою монету 16 раз. Предположим, что результат - ООРОООРРОРООРРРО, в котором буква О представляет " Орел ", буква Р представляет " Решка ". Oracle интерпретирует О как 1 бит и Р как бит 0 и выдает 1101 1100101 10001 в двоичном коде либо DCB1 в шестнадцатеричном, как дайджест сообщения для этого сообщения, и складывает сообщение и дайджест в таблице (табл. 1.2).

Таблица Oracle после создания четвертого дайджеста
Сообщение	Дайджест сообщения
`4523AB1352CDEF45126`	`13AB`
`723BAE38F2AB3457AC`	`02CA`
`AB1234CD8765BDAD`	`DCB1`
`AB45CD1048765412AAAB6662BE`	`A38B`

б. Сообщение 4523AB 1352CDEF45126 дается для вычисления дайджеста. Oracle проверяет свою таблицу и находит, что есть дайджест для этого сообщения в таблице (первая строка). Oracle просто выдает соответствующий дайджест ( 13AB ).

Пример 1.4

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

Например, вообразим, что Oracle использует формулу h (M) = М mod n. Теперь предположим, что Oracle уже выдал h (М1) и h (М₂). Если новое сообщение представлено как М₃ = M₁ + М₂ , Oracle не должен вычислить h (М₃). Новый дайджест - только [h (M₁) + h (M₂)] mod n, поскольку:

(M₃) = (M₁ + M₂) mod n = M₁ mod n + M₂ mod n = [h(M₁) + h(M₂)] mod n

Это нарушает третье требование: каждый дайджест должен быть выбран беспорядочно на основе сообщения, данного Oracle.

Принцип голубиных ящиков

Первое понятие, с которым мы должны быть знакомы для того, чтобы понять анализ случайной Модели Oracle, - принцип голубиных ящиков: если n ящиков заняты n + 1 голубями, то по крайней мере один ящик занят двумя голубями. Обобщенная версия принципа голубиных ящиков: если ящиков n заняты kn +1 голубями, то по крайней мере один ящик занят k + 1 голубем.

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

Пример 1.5

Предположим, что сообщения в хэш-функции длиной 6 битов, дайджесты только длиной 4 бита. Тогда возможное число дайджестов (ящики) - от 2⁴ = 16 и возможное число сообщений (голуби) - 2⁶ = 64. Это означает n = 16 и kn + 1 = 64, так что k больше, чем 3. Это говорит о том, что по крайней мере один дайджест соответствует четырем ( k + 1 ) сообщениям.

Проблемы дня рождения

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

(рис 1.7) Четыре проблемы дня рождения

Описание проблем

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

Проблема 1. Каково минимальное число k студентов в классной комнате, такое, что с некоторой вероятностью по крайней мере один студент имеет заранее заданный день рождения? Эта проблема может быть обобщена следующим образом. Мы имеем однородно распределенную случайную переменную с N возможными значениями (между 0 и N - 1 ). Каково минимальное число экземпляров, таких, что с некоторой вероятностью по крайней мере один экземпляр равен заранее заданному значению?

Проблема 2. Каково минимальное число k студентов в классной комнате, такое, что с некоторой вероятностью по крайней мере один студент имеет тот же самый день рождения, как и студент, выбранный профессором? Эта проблема может быть обобщена следующим образом. Мы имеем однородно распределенную случайную переменную с N возможными значениями (между 0 и N - 1 ) Какое минимальное число экземпляров, k, таких, что с некоторой вероятностью по крайней мере один экземпляр является равным выбранному?

Проблема 3. Каково минимальное число k студентов в классной комнате, такое, что с заданной вероятностью по крайней мере два студента имеют тот же самый день рождения? Эта проблема может быть обобщена следующим образом. Мы имеем однородно распределенную случайную переменную с N возможными значениями (между 0 и N - 1 ). Каково минимальное число экземпляров k, таких, что с некоторой вероятностью по крайней мере два экземпляра равны?

Проблема 4. Мы имеем два класса, каждый с k студентами. Каково минимальное значение A, такое, чтобы по крайней мере один студент из первой классной комнаты с некоторой вероятностью имел тот же самый день рождения, что и студент из второй классной комнаты? Эта проблема может быть обобщена следующим образом. Мы имеем однородно распределенную случайную переменную N со значениями (между 0 и N - 1 ). Мы генерируем два множества случайных значений, каждое величиной k. Каково минимальное число k, такое, что с некоторой вероятностью по крайней мере один экземпляр первого множества равен одному образцу во втором множестве?

Результаты решений

Для заинтересованных читателей решения этих проблем даются в приложении E. Результаты приведены в табл. 1.3.

Результаты решений четырех проблем дней рождения
Проблема	Вероятность	Общее значение для `k`	Значение `k` при `P = 1/2`	Число студентов ( `N=365` )
1	`P =l - e^-k/N`	`k = ln[1/(1-P) xN`	`k = 0,69 x N`	`253`
2	`P =l - e^-(k-1)N`	`k = ln[1/(1-P) xN + 1`	`k = 0,69 x N`	`254`
3	`P= 1 - e^k(k-1)/2N`	`k = {2 ln [1/1-P]}^1/2 xN^1/2`	`k= 1,18 xN^1/2`	`23`
4	`P =1- e^{- k^2/2N}`	`k = {ln [1/1-P]}^1/2 x N^1/2`	`k=0,83 x N^1/2`	`16`

Затемненное значение, 23, является решением классического парадокса дня рождения; если есть 23 студента в классной комнате, то с некоторой вероятностью (с P > 1/2 ) два студента имеют одинаковый день рождения (игнорируя год их рождения).

Сравнение проблем

Значение k в проблемах 1 или 2 пропорционально N ; значение k в проблемах 3 или 4 является пропорциональным N^1/2. Как мы увидим коротко, первые две проблемы связаны с атаками прообраза и второго прообраза; третья и четвертая проблемы связаны с атакой коллизии. Сравнение показывает, что намного более трудно начать атаку прообраза или атаку второго прообраза, чем атаку коллизии. рис. 1.8 дает граф P при различных k. Для первой и второй проблем показан один граф (значения вероятностей - очень близки). Графы для второй и третьей проблем отличаются сильнее.

(рис 1.8) Граф четырех проблем дня рождения

Атаки случайной модели Oracle

Чтобы лучше понимать характер хэш-функций и важность случайной модели Oracle, рассмотрим, как Ева может атаковать хэш-функцию, созданную Oracle. Предположим, что хэш-функция создает дайджесты n битов. Тогда дайджест можно представить как случайную переменную, однородно распределенную между 0 и N - 1, в которой N = 2ⁿ.Другими словами, есть возможные 2ⁿ значений для дайджеста; каждый раз Oracle случайно выбирает одно из этих значений для сообщения. Обратите внимание: это не означает, что выбор является исчерпывающим. Некоторые значения могут никогда не выбираться, но некоторые могут быть выбраны несколько раз. Мы принимаем, что алгоритм хэш-функции общедоступен и Ева знает размер дайджеста n.

Атака прообраза

Ева перехватила дайджест D = h (M) ; она хочет найти любое сообщение М', такое, что D = h (М'). Ева может создать список k сообщений и выполнить алгоритм 1.1.

Алгоритм может найти сообщение, для которого D является дайджестом, или может потерпеть неудачу. Какова вероятность успеха этого алгоритма? Очевидно, это зависит от размера списка, k, выбранного Евой. Чтобы найти вероятность, мы используем первую проблему дня рождения. Дайджест, созданный в соответствии с программой, определяет результаты случайной переменной. Вероятность успеха - P == 1 - e^-k/N.

Алгоритм 1.1 Атака на прообраз

Preimage_Attack (D)
{
for (i =1 to k)
{
создать (M[i])
T <- h(M [i ])  // T - временный дайджест

if (T = D) return M[i]
}
return failure
{

Какой должен быть размер k, если Ева должна достигнуть успеха по крайней мере в 50 процентах случаев? Мы показали это значение в табл. 1.3. Для первой проблемы дня рождения: $$k \approx 0,69 \times N$$, или $$k \approx 0,69 \times 2^{n}$$. Другими словами, чтобы Ева добилась своего более чем в 50 процентах случаев, она должна создать список дайджеста, который пропорционален 2ⁿ.

Сложность атаки прообраза пропорциональна 2ⁿ.

Пример 1.6

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

Решение

Число дайджестов, которые будут созданы, - $$k \approx 0,69 x 2^{n} = 0,69 \times 2^{64}$$. Это большое значение. Даже если Ева сможет генерировать 2³⁰ (почти один миллиард) сообщений в секунду, требуется 0,69 x 2³⁴ секунды или больше чем 500 лет. Это означает, что дайджест сообщения размером 64 бита является безопасным относительно атаки прообраза, но, как мы увидим далее, он не защищен от атаки коллизии.

Атака второго прообраза

Ева перехватила дайджест D = h (M) и соответствующее сообщение М.; она хочет найти другое сообщение M', такое, чтобы h(M') = D. Ева может создать список из k - 1 сообщения и выполнить Алгоритм 1.2.

Алгоритм 1.2. Атака второго прообраза

Second_Preimage_Attack (D, M)
{
for (i = 1 to k - 1)
{
создать (M[i]
T <-  h (M[i])
If (T = D) return  M[i]  // T - временный дайджест
}
return failure
}

Алгоритм может найти второе сообщение, для которого D является также дайджестом, или может потерпеть неудачу. Какова вероятность успеха этого алгоритма? Очевидно, это зависит от размера списка, k, выбранного Евой. Чтобы найти вероятность положительного исхода алгоритма, мы используем вторую проблему дня рождения. Дайджест, созданный в соответствии с программой, определяет выходное значение случайной переменной. Вероятность успеха - P = 1 -e^1-(k-1)/N. Какой должен быть размер k, если Ева хочет достичь успеха по крайней мере в 50 процентах случаев? Мы уже указали это значение в табл. 1.3 для второй проблемы дня рождения: $$k \approx 0,69 \times N + 1$$ или $$k \approx 0,69 \times 2^{n}$$. Другими словами, чтобы Ева добилась своего более чем в 50 процентах случаев, она должна создать список дайджеста, который пропорционален 2ⁿ.

Сложность атаки второго прообраза пропорциональна 2ⁿ.

Атака коллизии

Ева должна найти два сообщения, М. и М.', такие, что h (M) = h (М.'). Она может создать список сообщений и выполнить алгоритм 1.3.

Алгоритм 1.3. Атака коллизии

Collision_Attack
{
for (i = 1 to k)
{
создать (M[i])
D[i] <- h (M[i])    // D[i] - список создаваемых дайджестов
for (j = 1  to i - 1)
{
if (D[i] = D[j] return (M[i] и  M[j] )  
}
}
return failure
}

Алгоритм может найти два сообщения с одним и тем же дайджестом. Какова вероятность успеха этого алгоритма? Очевидно, это зависит от размера списка, k, выбранного Евой. Чтобы найти вероятность этого события, мы используем третью проблему дня рождения. Дайджест, созданный в соответствии с программой, определяет выходное значение случайной переменной. Вероятность успеха - P = 1 - e^1-(k-1)/2N. Какой должен быть размер k, если Ева хочет достичь успеха по крайней мере в 50 процентах случаев? Мы уже указали это значение в табл. 1.3 для третьей проблемы дня рождения: $$k \approx 1,18 \times N^{1/2}$$, или $$k \approx 1,18 \times 2^{n/2}$$. Другими словами, чтобы Ева добилась своего более чем в 50 процентах случаев, она должна создать список дайджеста, который пропорционален 2^n/2.

Сложность атаки коллизии пропорциональна 2^n/2.

Пример 1.7

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

Решение

Число дайджестов, которые будут созданы, $$k \approx 1,18 \times 2^{n/2.} \approx 1,18 \times 2^{32}$$. Если Ева может проверить 2²⁰ (почти один миллион) сообщений в секунду, потребуется 1,18 x 2¹² секунд, или меньше чем два часа. Это означает, что дайджест сообщения размера 64 бита небезопасен относительно атаки коллизии.

Дополнительная атака коллизии

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

Второе сообщение может также создать множество сообщений. Если обозначить первоначальное сообщение М, а фиктивное сообщение - М', Ева создает k различных вариантов М (M1, M2 ,... , Mk) и k различных вариантов М' (M'1, M'2 ,... , M'k). Затем Ева использует алгоритм 1.4 для того, чтобы начать атаку.

Алгоритм 1.4. Дополнительная атака коллизии

Alternate_Collision _Attack (M[k], M'[k])
{
for (i = 1 to k)
{
D[i] <- h ([M[i])
D'[i] <- h [M'[i])
if (D[i] = D'[j] return (M[i], M'[j])
}
return failure
]

Какова вероятность успеха этого алгоритма? Очевидно, это зависит размера списка k, выбранного Евой. Чтобы найти вероятность, мы используем четвертую проблему дня рождения. Два списка дайджеста, созданные в соответствии с программой, определяют два выходных значения случайной Вероятность успеха равна $$P \approx 1- e^{-k^2/2N}$$. Какой должен быть размер k, если Ева хочет достичь успеха по крайней мере в 50 процентах случаев? Мы уже указали это значение в таблице для четвертой проблемы дня рождения: $$k \approx 0.83 \times N^{1/2}$$ или $$k \approx 0.83 \times 2^{n/2}$$. Другими словами, чтобы Ева добилась своего более чем в 50 процентах случаев, она должна создать список дайджеста, который пропорционален 2^n/2.

Сложность дополнительной атаки коллизии пропорциональна 2^n/2.

Итоги атак

Таблица 1.4 показывает уровень сложности для каждой атаки, если дайджест имеет длину n бит.

Уровни сложности для каждого типа атаки
Атака	Значение при `P =1/2`	Порядок верхнего предела
Прообраз	$$k \approx 0.69 \times 2^{2n+1}$$	`2ⁿ`
Второй прообраз	$$k \approx 0.69 \times 2^{2n+1}$$	`2ⁿ`
Коллизия	$$k \approx 1,18 \times 2^{n/2}$$	`2^n/2`.
Дополнительная коллизия	$$k \approx 0.83 \times 2^{n/2}$$	`2^n/2`

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

Пример 1.8

Первоначально хэш-функции с дайджестом на 64 бита, как полагали, были стойкими к атакам коллизии. Но с увеличением скорости обработки сегодня все обнаружили, что эти хэш-функции больше не безопасны. Ева нуждается только в 2^64/2 = 2³² испытаний, чтобы начать атаку с вероятностью 1/2 или больше. Предположим, что она может выполнить 2²⁰ (один миллион) испытаний в секунду. Она может провести атаку за 2³² / 2²⁰ = 2¹² секунд (почти час!).

Пример 1.9

MD5 (см. лекцию 2), который был одной из стандартных хэш-функций в течение долгого времени, создает дайджесты в 128 битов. Чтобы провести атаку коллизии, противник должен провести 2⁶⁴(2^128/2) испытаний алгоритма коллизии. Даже если противник может выполнить 2³⁰ (больше чем один миллиард) испытаний в секунду, требуется 2³⁴ секунды (больше чем 500 лет), чтобы провести атаку. Этот тип атаки базируется на случайной модели Oracle. Было доказано, что MD5 может быть атакован за менее чем 2⁶⁴ испытаний - из-за структуры алгоритма.

Пример 1.10

SHA-1 (см. лекцию 2), стандартная хэш-функция, разработанная NIST, создает дайджесты в 160 битов. Чтобы провести атаку коллизии, противник должен исполнить 2^160/2 = 2⁸⁰ испытания в алгоритме коллизии. Даже если противник может выполнить 2³⁰ (больше чем один миллиард) испытаний в секунду, требуется 2⁵⁰ секунд (больше чем десять тысяч лет), чтобы начать атаку. Однако исследователи обнаружили некоторые особенности функции, которые позволяют провести атаку на эту хэш-функцию за меньшее время, чем вычисленное выше.

Пример 1.11

Новая хэш-функция, которая, вероятно, станет NIST-стандартом, - SHA-512 (см. лекцию 2) имеет дайджест на 512 битов. Эта функция явно стойкая к атакам коллизии, основанным на случайной модели Oracle. Требуется от 2^512/2 до 2²⁵⁶ испытаний, чтобы найти коллизию с вероятностью 1/2.

Атаки структуры

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

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

1.3. Уcтановление подлинности сообщения

Дайджест сообщения гарантирует целостность сообщения - то есть что сообщение не было изменено. Дайджест сообщения, однако, не подтверждает подлинность передачи сообщения. Когда Алиса передает сообщение Бобу, Боб должен знать, что это сообщение точно прибыло от Алисы. Для того, чтобы обеспечивать установление подлинности сообщения, Алиса должна предоставить доказательство, что это сообщение послала именно она, а не самозванец. Дайджест сообщения не может обеспечить такое доказательство. Дайджест, созданный криптографической хэш-функцией, обычно называется кодом обнаружения модификации (Modification Detection Code - MDC ), - код может обнаружить любое изменение в сообщении. Кроме этого, мы нуждаемся аутентификации сообщения (установление подлинности происхождения данных) - в коде установления подлинности сообщения (Message Authentication Code - MAC ).

Код обнаружения модификации

Код обнаружения модификации ( MDC ) - дайджест сообщения, который может доказать целостность сообщения и подтвердить, что сообщение не было изменено. Если Алиса должна передать сообщение Бобу и хочет быть уверена, что сообщение не будет изменено во время передачи, она может создать дайджест, MDC -сообщение и послать сообщение и MDC Бобу. Боб может создать новый MDC из сообщения и сравнить полученный MDC и новый MDC. Если они одинаковые, значит, сообщение не был изменено. рис. 1.9 иллюстрирует идею.

(рис 1.9) Код обнаружения модификации

Рис. 1.9 показывает, что сообщение может быть передано через ненадежный канал. Ева может читать или даже изменять сообщение. MDC, однако, должен быть передан через безопасный канал, - такой канал называют безопасный (safe), он не позволяет изменений.

Если сообщение и MDC передаются через ненадежный канал, Ева может перехватить сообщение, изменить его, создать новый MDC из сообщения и передать их Бобу. Боб никогда не узнает, что сообщение пришло от Евы. Обратите внимание, что термин безопасный может означать сторону, которой доверяют. Термин канал может означать отрезок времени прохождения сигнала. Например, если Алиса создает MDC своего завещания и вносит его с поверенным нотариусом, который сохраняет блокированное сообщение до ее смерти, - она использовала безопасный канал.

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

Код установления подлинности сообщения (Message Authentication Code - MAC)

Чтобы гарантировать целостность сообщения, подлинность первоначального сообщения и то, что создатель сообщения - Алиса, а не кто-то другой, мы должны изменить код обнаружения модификации ( MDC ) на код установления подлинности сообщения (Message Authentication Code - MAC). Отличие между MDC и MAC в том, что второй включает секретность между Алисой и Бобом, например секретный ключ, которым Ева не обладает. рис. 1.10 иллюстрирует идею.

(рис 1.10) Код установления подлинности сообщения

Алиса использует хэш-функцию, чтобы создать MAC по объединению (конкатенации) ключа и сообщения - h (K|M). Она передает сообщение и MAC Бобу по ненадежному каналу. Боб отделяет сообщение от MAC и затем делает новый MAC из объединения сообщения и ключа засекречивания. Затем Боб сравнивает недавно созданный MAC с полученным. Если оба эти MAC совпадают, то сообщение подлинное и не было изменено противником.

Обратите внимание, что в этом случае нет необходимости использовать два канала. И сообщение, и MAC можно передать по одному, хотя бы и самому ненадежному каналу. Ева может видеть сообщение, но она не может создать новое сообщение, чтобы подделать исходное, потому что Ева не обладает ключом засекречивания между Алисой и Бобом. Она неспособна создать такой же MAC, как это сделала Алиса.

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

Безопасность MAC

Предположим, что Ева перехватила сообщение М и дайджест h (K|M). Как Ева может подделать сообщение, не зная ключа засекречивания? Есть три возможных случая.

Если размер ключа позволяет полный перебор, Ева может перебрать все возможные ключи в начале сообщения и сделать дайджест ( K|M ), чтобы найти, что этот дайджест равняется перехваченному. Она уже знает ключ и может успешно заменить сообщение подделанным сообщением по своему выбору.

Размер ключа в MAC является обычно очень большим, но Ева может использовать другой инструмент - атаку прообраза, рассмотренную в алгоритме 1.1. Она использует алгоритм, пока не находит X, такой, что h (X) равен MAC, который она перехватила. Теперь она может найти ключ и успешно заменить сообщение подделанным. Поскольку размер ключа обычно очень большой, для полного перебора Ева может только атаковать MAC, который использует алгоритм прообраза.

Получая некоторые пары сообщений и их MAC, Ева может управлять ими, чтобы придумать новое сообщение и его MAC.

Безопасность MAC зависит от безопасности основного хэш-алгоритма.

Вложенный MAC

Чтобы улучшить безопасность MAC, был разработан вложенный MAC (nested MAC), в котором хэширование делается в два шага. На первом шаге ключ конкатенируется (последовательно объединяется) с сообщением и хэшируется, чтобы создать промежуточный дайджест. На втором шаге ключ конкатенируется с промежуточным дайджестом, чтобы создать конечный дайджест. рис. 1.11 иллюстрирует общую идею.

(рис 1.11) Вложенный MAC

Код аутентификации сообщения, основанный на хэшировании (HMAC)

Национальный институт стандартов США (NIST) разработал стандарт (FIPS 198) для вложенного MAC, который часто называют HMAC (HASH-BASED MESSAGE AUTHENTICATION CODE ) (его надо отличать от CMAC, который будет рассмотрен в следующем разделе). Реализация HMAC намного более сложна, чем упрощенный вложенный MAC, показанный на рис. 1.11. Есть дополнительные особенности, такие как заполнение. рис. 1.12 показывает детали. При реализации HMAC мы проходим следующие шаги:

(рис 1.12) Детали HMAC

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

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

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

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

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

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

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

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

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

CMAC

Национальный институт стандартов и технологии США (NIST) разработал стандарт (FIPS113), названный Алгоритмом установления подлинности данных или кодом аутентификации сообщения, основанный на шифровании базового сообщения - CMAC (Сipher based Message, Authentication Code) или CBCMAC. Метод подобен режиму сцепления блоков шифрованного текста (CBC - Cipher Block Chaining), рассмотренному в лекции 8 для шифрования симметричными ключами. рис. 1.13 иллюстрирует идею.

(рис 1.13) CMAC

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

Сообщение разделено на N блоков, каждый длины m бит. Размер CMAC - n бит. Если последний блок - не m бит, он дополняется единичным битом ( 1 ), сопровождаемым достаточным количеством нулей (0), чтобы сделать его m -битовым. Первый блок сообщения зашифрован симметричным ключом, чтобы создать m -разрядный блок зашифрованных данных. Этот блок складывается (ИСКЛЮЧАЮЩЕЕ ИЛИ) со следующим блоком, а результат зашифровывается снова, чтобы создать новый m- битовый блок. Процесс продолжается, пока не будет зашифрован последний блок сообщения. CMAC - это n крайних левых бит последнего блока. В дополнение к симметрическому ключу, K, CMAC также использует другой ключ, k, который применяется только на последнем шаге. Этот ключ получен с помощью алгоритма шифрования исходного текста, дополненного m нулевыми битами, и использованием шифро-ключа, K. Результат затем умножен на x, если нет никакого дополнения, или на x², если дополнение есть. Умножение проводится в GF(2^m) с неприводимым полиномом степени m, выбранным в соответствии с используемым конкретным протоколом.

Обратите внимание, что эта процедура отличается от CBC (см. лекцию 8), метода, который используется для получения конфиденциальности. В упомянутом ранее методе выход каждого шифрования передают как зашифрованный текст и в то же самое время складывают (ИСКЛЮЧАЮЩЕЕ ИЛИ) со следующим блоком исходного текста. Здесь же промежуточные зашифрованные блоки не передаются как зашифрованный текст; они только используются для сложения со следующим блоком.

1.4. Рекомендованная литература

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

Книги

Книги [Sti06], [Sta06], [Sch99], [Mao04], [KPS02], [PHS03L] и [MOV97] дают хороший обзор криптографических хэш-функций.

Сайты

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

http://en.wikipedia.org/wiki/Preimage_attack

http://en.wikipedia.org/wiki/Collision_attack#In_cryptography

http://en.wikipedia.org/wiki/Pigeonhole __ principle

csrc.nist.gov/ispab/2005-12/B_Burr-Dec2005-ISPAB.pdf

http://en.wikipedia.org/wiki/Message_authentication_code

http://en.wikipedia.org/wiki/HMAC

csrc.nist.gov/pLiblicationVnps/npsl98/fips-198a.pdf

http://www.faqs.org/rfcs rfc2104.html

http://en.wikipedia.org/wiki/Birthday_paradox

1.5. Итоги

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

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

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

Случайная модель Oracle, которая была введена в 1993 г. Белларом и Роджеем, является идеальной математической моделью для хэш-функции.

Принцип голубиных ящиков устанавливает, что если n ящиков заняты n + 1 голубем, то по крайней мере один ящик занят двумя голубями. Обобщенная версия принципа голубиных ящиков: если n ящики заняты kn + 1 голубем, по крайней мере один ящик занят k + 1 голубем.

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

Код обнаружения модификации (MDC) - дайджест сообщения, который может доказать целостность сообщения: что сообщение не было изменено. Чтобы доказать целостность сообщения и установить подлинность происхождения данных, мы должны заменить код обнаружения модификации (MDC) на код установления подлинности сообщения (MAC). Различие между MDC и MAC в том, что MAC включает в себя безопасность передачи между передатчиком и приемником.

Национальный Институт Стандартов и Технологии США (NIST) выработал стандарт (FIPS 198) для вложенного MAC, который часто называется кодом аутентификации сообщения, основанным на хэшировании - HMAC (хэшированный MAC ). NIST также определил другой стандарт (FIPS 113), названный CMAC, или CBCMAC.

1.6. Набор для практики

Обзорные вопросы

Покажите различия между целостностью сообщения и установлением подлинности сообщения

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

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

Определите третий критерий для криптографической хэш-функции.

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

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

Определите проблемы четырех дней рождения, рассмотренные в этой лекции.

Испробуйте каждый метод дня рождения с одной проблемой из атак хэш-функции.

Покажите различия между MDC и MAC.

Покажите различия между HMAC и CMAC.

Упражнения

В случайной модели Oracle: почему Oracle должен делать запись дайджеста, созданного для сообщения, и присваивать тот же самый дайджест одинаковым сообщениям?

Объяснить, почему секретный/открытый ключи не могут использоваться в создании MAC.

Игнорируя месяц рождения, сколько попыток в среднем необходимо, чтобы найти человека с такой же датой рождения, как ваша? Примите, что все месяцы имеют 30 дней.

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

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

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

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

однородно распределены в течение дней недели,

в течение дней месяца, в течение каждого месяца года,

в течение 365 дней года.

Предположим также, что год состоит точно из 365 дней и каждый месяц - точно из 30 дней.

Какова вероятность, что два из членов семьи имеют один и тот же день рождения?

Какова вероятность, что ни один из них не имеет совпадающего дня рождения?

Какова вероятность, что двое из членов семьи рождены в одном и том же месяце? вероятность того, что ни один из них не был рожден в одном и том же месяце?

Какова вероятность, что кто-то из членов семейства рожден в первый день одного из месяцев?

Какова вероятность, что у трех из членов семейства дни рождения приходятся на один и тот же день недели?

Какова вероятность совпадения дней рождения в двух классах, одного с k студентами и другого с l студентами?

В классе из 100 студентов какова вероятность, что два или больше студента имеют паспорта с одними и теми же последними четырьмя цифрами?

Есть 100 студентов в группе, и профессор разбивает ( A, B, C, D, E ) по результатам теста. Покажите, что по крайней мере одна группа будет содержать не менее 20 студентов.

Требует ли принцип голубиных ящиков случайного распределения голубей по ящикам?

Предположим, что Ева решила найти прообраз по алгоритму 1.1. Какое число раз в среднем Ева должна повторить алгоритм?

Предположим, что Ева решила найти коллизию по Алгоритму 1.3. Какое число раз, в среднем, Ева должна повторить алгоритм?

Предположим, что мы имеем очень простой дайджест сообщения. Наш дайджест сообщения (нереальный) - только одно число между 0 и 25. Дайджест первоначально установлен на 0. Криптографическая хэш-функция складывает текущее значение дайджеста со значением текущего символа (между 0 и 25). Сложение проводится по модулю 26. Идея показана на рис 1.14(рис 1.14)

Попробуем увеличить сложность предыдущего упражнения. Возьмем значение текущего символа, заменим его другим числом и затем сложим с предыдущим значением из дайджеста по модулю 100. Дайджест первоначально устанавливается на 0. рис. 1.1 показывает идею. Каково значение дайджеста для сообщения " (рис 1.15)

Используя модульную арифметику, найдите дайджест сообщения. рис 1.16(рис 1.16)

Пусть длина дайджеста сообщения равна n битам.

Выберите в качестве модуля простое n - битовое число p.

Представьте сообщение как двоичное число и дополните сообщение с нулями (0), чтобы оно было кратно m битам.

Разбейте дополненное сообщение на N блоков, каждый по m бит. Обозначим каждый i -тый блок X_i.

Выберите начальный дайджест N битов, H₀.

Повторите N раз следующие действия:

H_i  = (H_i-1 + X_i)2 mod p

Дайджест будет равен H_N.

Какое значение будет иметь дайджест, если сообщение - " HELLO "? Почему этот дайджест не безопасен?

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

Пусть длина дайджеста сообщения равна N бит.

Выберите два простых числа, p и q. Вычислите M = pq.

Представьте сообщение как двоичное число и дополните сообщение нулями, так чтобы сделать его число битов кратным N/2. N выбран как число, кратное 16, меньшее, чем число битов в M.

Разделите дополненное сообщение на m блоков, каждый по N/2 битов. Обозначим каждый блок X_i.

Прибавьте длину сообщения по модулю N/2 как двоичное число к сообщению. Это создаст сообщение длиной m+1 блоков по N/2 битов.

Расширьте сообщение, чтобы получить m + 1 блок, каждый по N битов, как показано ниже.

Разделите блоки X₁ до X_m на группы по 4 бита. Вставьте 1111 перед каждой группой.

Разделите блок X_m+1 на группы по 4 бита. Вставьте 1010 перед каждой группой.

Назовем расширенные блоки Y₁, Y₂..., Y_m+1.

Выберите начальный дайджест N битов, H₀.

Выберите константу K из N битов.

Повторите m+1 раз следующие действия ( T_i и G_i - промежуточные значения). Символ || обозначает конкатенацию.

T_i = ((H_i+1, + Y_i,) || K)²⁵⁷ mod M.    
G_i = H_i mod 2^N 
H_i = H_i+1 +G_i;

Дайджест равен H_m+1.

Напишите алгоритм в псевдокоде для решения первой проблемы дня рождения (в общей форме).

Напишите алгоритм в псевдокоде для решения второй проблемы дня рождения (в общей форме).

Напишите алгоритм в псевдокоде для решения третьей проблемы дня рождения (в общей форме).

Напишите алгоритм в псевдокоде для решения четвертой проблемы дня рождения (в общей форме).

Напишите алгоритм в псевдокоде для HMAC.

Напишите алгоритм в псевдокоде для CMAC.

Страницы:

1.1. Целостность сообщения

Документ и отпечатки пальцев

Сообщение и дайджест сообщения

(рис 1.1) Сообщение и дайджест

Различия

Дайджест сообщения должен быть защищен от изменения.

Проверка целостности

(рис 1.2) Проверка целостности

Криптографические критерии хэш-функции

(рис 1.3) Критерии криптографической функции

Устойчивость прообраза

(рис 1.4) Прообраз

Атака прообраза

Дано: y = h (M) Найти: такое М', что y = h (M').

Пример 1.1

Решение

Пример 1.2

Можем ли мы использовать функцию контрольной суммы как криптографическую хэш-функцию?

Решение

Устойчивость ко второму прообразу

(рис 1.5) Второй прообраз

Атака второго прообраза

Дана Атака: М и h (M) Найти: такое M' = М, что h (M) = h (M').

Устойчивость к коллизиям

(рис 1.6) Устойчивость к коллизиям

1.2. Случайная модель Oracle

Когда передается сообщение, для которого существует дайджест, oracle просто вставляет дайджест в запись.

Пример 1.3

Таблица Oracle после создания первых трех дайджестов
Сообщение	Дайджест сообщения
`4523AB1352CDEF45126`	`13AB`
`723BAE38F2AB3457AC`	`02CA`
`AB45CD1048765412AAAB6662BE`	`A38B`

Теперь предположим, что возникают два события:

Таблица Oracle после создания четвертого дайджеста
Сообщение	Дайджест сообщения
`4523AB1352CDEF45126`	`13AB`
`723BAE38F2AB3457AC`	`02CA`
`AB1234CD8765BDAD`	`DCB1`
`AB45CD1048765412AAAB6662BE`	`A38B`

Пример 1.4

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

(M₃) = (M₁ + M₂) mod n = M₁ mod n + M₂ mod n = [h(M₁) + h(M₂)] mod n

Принцип голубиных ящиков

Пример 1.5

Проблемы дня рождения

(рис 1.7) Четыре проблемы дня рождения

Описание проблем

Результаты решений

Для заинтересованных читателей решения этих проблем даются в приложении E. Результаты приведены в табл. 1.3.

Результаты решений четырех проблем дней рождения
Проблема	Вероятность	Общее значение для `k`	Значение `k` при `P = 1/2`	Число студентов ( `N=365` )
1	`P =l - e^-k/N`	`k = ln[1/(1-P) xN`	`k = 0,69 x N`	`253`
2	`P =l - e^-(k-1)N`	`k = ln[1/(1-P) xN + 1`	`k = 0,69 x N`	`254`
3	`P= 1 - e^k(k-1)/2N`	`k = {2 ln [1/1-P]}^1/2 xN^1/2`	`k= 1,18 xN^1/2`	`23`
4	`P =1- e^{- k^2/2N}`	`k = {ln [1/1-P]}^1/2 x N^1/2`	`k=0,83 x N^1/2`	`16`

Сравнение проблем

(рис 1.8) Граф четырех проблем дня рождения

Атаки случайной модели Oracle

Атака прообраза

Алгоритм 1.1 Атака на прообраз

Preimage_Attack (D)
{
for (i =1 to k)
{
создать (M[i])
T <- h(M [i ])  // T - временный дайджест

if (T = D) return M[i]
}
return failure
{

Сложность атаки прообраза пропорциональна 2ⁿ.

Пример 1.6

Решение

Атака второго прообраза

Алгоритм 1.2. Атака второго прообраза

Second_Preimage_Attack (D, M)
{
for (i = 1 to k - 1)
{
создать (M[i]
T <-  h (M[i])
If (T = D) return  M[i]  // T - временный дайджест
}
return failure
}

Сложность атаки второго прообраза пропорциональна 2ⁿ.

Атака коллизии

Алгоритм 1.3. Атака коллизии

Collision_Attack
{
for (i = 1 to k)
{
создать (M[i])
D[i] <- h (M[i])    // D[i] - список создаваемых дайджестов
for (j = 1  to i - 1)
{
if (D[i] = D[j] return (M[i] и  M[j] )  
}
}
return failure
}

Сложность атаки коллизии пропорциональна 2^n/2.

Пример 1.7

Решение

Дополнительная атака коллизии

Алгоритм 1.4. Дополнительная атака коллизии

Alternate_Collision _Attack (M[k], M'[k])
{
for (i = 1 to k)
{
D[i] <- h ([M[i])
D'[i] <- h [M'[i])
if (D[i] = D'[j] return (M[i], M'[j])
}
return failure
]

Сложность дополнительной атаки коллизии пропорциональна 2^n/2.

Итоги атак

Таблица 1.4 показывает уровень сложности для каждой атаки, если дайджест имеет длину n бит.

Уровни сложности для каждого типа атаки
Атака	Значение при `P =1/2`	Порядок верхнего предела
Прообраз	$$k \approx 0.69 \times 2^{2n+1}$$	`2ⁿ`
Второй прообраз	$$k \approx 0.69 \times 2^{2n+1}$$	`2ⁿ`
Коллизия	$$k \approx 1,18 \times 2^{n/2}$$	`2^n/2`.
Дополнительная коллизия	$$k \approx 0.83 \times 2^{n/2}$$	`2^n/2`