Ключевые хэш-функции. Основные требования и примеры построения. Атаки на хеш-функции. (1 семестр 9 лекция)
Хэш-функции – это функции, предназначенные для «сжатия» произвольного сообщения или набора данных, записанного, как правило, в двоичном алфавите, в некоторую битовую комбинацию фиксированной длины, называемую сверткой или хэшем. (необходимо знать)
Применение хэш-функций в криптографии:
· Построение систем контроля целостности данных при их передаче или хранении;
· Аутентификация источника данных.
Одношаговые сжимающие функции
Y=f(x1,x2), где x и y – двоичные векторы длины m и n соответственно, причем n – длина свертки.
Правило применения:
Для получения значения h(M) сообщение M сначала разбивается на блоки длины m (при этом если длина сообщения не кратна m, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1,M2,…,MN применяют следующую последовательную процедуру вычисления свертки:
H0 = v
Hi = f(Mi,Hi-1), i=1…N
h(M) = HN
v-некоторый фиксированный начальный вектор
Хэш-функции бывают:
3) Ключевыми: свертка зависит от сообщения и тайного ключа
4) Бесключевыми: свертка зависит только от сообщения
Основные требования к ключевым хэш-функциям:
· Невозможность фабрикации – высокая сложность подбора сообщения с правильным значением свертки;
· Невозможность модификации – высокая сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.
В криптографии невозможность=высокая сложность.
|
|
|
Ключевые хэш-функции могут строится:
3. На алгоритмах блочного шифрования
Одношаговая сжимающая функция имеет вид:
Ff(x,H) = Ek(x mod 2 H)
Где Ek – алгоритм блочного шифрования
Алгоритм вычисления свертки имеет следующий вид:
H0=0
Hi=Ek(Mi mod 2 Hi-1), i = 1,…N,
Hk(M) = HN
4. На основе бесключевых хэш-функций.
В этом случае ключ или его части добавляются как минимум и в начало, и в конец сообщения.
Атаки на хэш-функции делятся на 3 типа:
4) Анализ алгоритмов шифрования и поиск в них слабых мест, например, так называемых «мертвых точек», когда содержимое блока не меняется;
5) Анализ закономерностей текста;
6) Перебор возможных вариантов сообщений или их частей до коллизии хэшей (часто применяется для взлома паролей).
Вероятность успеха атаки методом генерации сообщений:
Где n – длина свертки
e – основание натурального логарфима
r1 – количество генерируемых поддельных сообщений и их сверток
r2- количество перехваченных сообщений и их сверток.
Бесключевые хэш-функции. Основные требования и примеры построения. Атаки на хэш-функции. Хэш-функция MD5. (1 семестр 9 лекция)
Хэш-функции – это функции, предназначенные для «сжатия» произвольного сообщения или набора данных, записанного, как правило, в двоичном алфавите, в некоторую битовую комбинацию фиксированной длины, называемую сверткой или хэшем. (необходимо знать)
|
|
|
Применение хэш-функций в криптографии:
· Построение систем контроля целостности данных при их передаче или хранении;
· Аутентификация источника данных.
Одношаговые сжимающие функции
Y=f(x1,x2), где x и y – двоичные векторы длины m и n соответственно, причем n – длина свертки.
Правило применения:
Для получения значения h(M) сообщение M сначала разбивается на блоки длины m (при этом если длина сообщения не кратна m, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1,M2,…,MN применяют следующую последовательную процедуру вычисления свертки:
H0 = v
Hi = f(Mi,Hi-1), i=1…N
h(M) = HN
v-некоторый фиксированный начальный вектор
Хэш-функции бывают:
1)Ключевыми: свертка зависит от сообщения и тайного ключа
2)Бесключевыми: свертка зависит только от сообщения
Основные требования к бесключевым хэш-функциям:
· Однонаправленность т.е. по свертке нельзя получить исходное сообщение
· Устойчивость к коллизиям (коллизия-это совпадение хэшей от разных сообщений).
· Устойчивость к нахождению второго прообраза.
|
|
|
Бесключевые хэш-функции могут строится:
3) На основе алгоритмов блочного шифрования. (хэш-функция никак сообщение не шифрует).
Одношаговая сжимающая функция будет иметь вид;
f(x,H) = EH(x) mod 2 x или
f(x,H) =Ex(H)mod 2 Р
а правило применения в соответствии с первоначально-записанным правилом применения хэш-функции.
4) На основе специально разработанных алгоритмов.
Атаки на хэш-функции делятся на 3 типа:
1) Анализ алгоритмов шифрования и поиск в них слабых мест, например, так называемых «мертвых точек», когда содержимое блока не меняется;
2) Анализ закономерностей текста;
3) Перебор возможных вариантов сообщений или их частей до коллизии хэшей (часто применяется для взлома паролей).
Вероятность успеха атаки методом генерации сообщений:
Где n – длина свертки
e – основание натурального логарфима
r1 – количество генерируемых поддельных сообщений и их сверток
r2- количество перехваченных сообщений и их сверток.
Пример: алгоритм MD-5
6. Добавление незначащих битов
К сворачиваемому сообщению добавляется код 10..0. Число нулей определяется из условия: остаток деления длины дополненного сообщения на 512 должен быть равным 448.
7. Добавление длины сообщения. Длина исходного сообщения, до первого этапа, представляется в виде 64-разрядного числа.
|
|
|
8. Инициализация MD буфера. В четыре 32-рарядных слова заносятся специальные константы, названные разработчиками магическими.
9. Обработка сообщения. Инициализируются 4 функции, каждая из которых преобразует три 32-битных слова в одно. Каждый 512-разрядный блок сообщения поочередно обрабатывается всеми функциями вместе со словами из буфера. Новые значения добавляются к предыдущим значениям, хранящимся в буфере, и алгоритм переходит к обработке следующего 512-разрядного блока.
10. Вывод результата. Содержимое буфера выдается как результат свертки длиной 128 бит.
Дата добавления: 2018-08-06; просмотров: 1844; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!