Семестр Лекция 9 Компьютерная криптография

Обеспечение целостности

Определение см. ранее.

Имитостойкость – способность передаваемой информации противостоять активным атакам со стороны противника.

Обобщенный алгоритм работы систем обеспечения целостности информации

· К сообщению M добавляется проверочная комбинация S, называемая кодом аутентификации сообщения или имитовставкой

· По каналу связи передается или записывается на диск пара С=(M,S).

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

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

h_k(M) = S.

Требования к коду аутентификации:

· Невозможность вычисления значения h_k(M) = S. Для заданного сообщения M без знания ключа k; (невозможность фабрикации)

· Невозможность подбора для заданного сообщения M с известным значением h_k(M) = S другого сообщения M₁ с известным значением h_k(M₁) = S₁ без знания ключа k. (невозможность модификации)

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

Применение хэш-функций в криптографии:

· Построение систем контроля целостности данных при их передаче или хранении;

· Аутентификация источника данных.

Одношаговые сжимающие функции

Y=f(x₁,x₂), где x и y – двоичные векторы длины m и n соответственно, причем n – длина свертки.

Рисунок1

Правило применения:

Для получения значения h(M) сообщение M сначала разбивается на блоки длины m (при этом если длина сообщения не кратна m, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M₁,M₂,…,M_N применяют следующую последовательную процедуру вычисления свертки:

H₀ = v

H_i = f(M_i,H_i-1), i=1…N

h(M) = H_N

v-некоторый фиксированный начальный вектор

Хэш-функции бывают:

1) Ключевыми: свертка зависит от сообщения и тайного ключа

2) Бесключевыми: свертка зависит только от сообщения

Ключевые хэш-функции:

Основные требования к ключевым хэш-функциям:

· Невозможность фабрикации – высокая сложность подбора сообщения с правильным значением свертки;

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

В криптографии невозможность=высокая сложность.

Ключевые хэш-функции могут строится:

1. На алгоритмах блочного шифрования

Одношаговая сжимающая функция имеет вид:

F_f(x,H) = Ek(x mod 2 H)

Где Ek – алгоритм блочного шифрования

Алгоритм вычисления свертки имеет следующий вид:

H0=0

Hi=Ek(Mi mod 2 Hi-1), i = 1,…N,

Hk(M) = H_N

2. На основе бесключевых хэш-функций.

В этом случае ключ или его части добавляются как минимум и в начало, и в конец сообщения.

Основные требования к бесключевым хэш-функциям:

· Однонаправленность т.е. по свертке нельзя получить исходное сообщение

· Устойчивость к коллизиям (коллизия-это совпадение хэшей от разных сообщений).

· Устойчивость к нахождению второго прообраза.

Бесключевые хэш-функции могут строится:

1) На основе алгоритмов блочного шифрования. (хэш-функция никак сообщение не шифрует).

Одношаговая сжимающая функция будет иметь вид;

f(x,H) = E_H(x) mod 2 x или

f(x,H) =E_x(H)mod 2 Р

а правило применения в соответствии с первоначально-записанным правилом применения хэш-функции.

2) На основе специально разработанных алгоритмов.

Пример: алгоритм MD-5

1. Добавление незначащих битов

К сворачиваемому сообщению добавляется код 10..0. Число нулей определяется из условия: остаток деления длины дополненного сообщения на 512 должен быть равным 448.

2. Добавление длины сообщения. Длина исходного сообщения, до первого этапа, представляется в виде 64-разрядного числа.

3. Инициализация MD буфера. В четыре 32-рарядных слова заносятся специальные константы, названные разработчиками магическими.

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

5. Вывод результата. Содержимое буфера выдается как результат свертки длиной 128 бит.

Атаки на хэш-функции делятся на 3 типа:

1) Анализ алгоритмов шифрования и поиск в них слабых мест, например, так называемых «мертвых точек», когда содержимое блока не меняется;

2) Анализ закономерностей текста;

3) Перебор возможных вариантов сообщений или их частей до коллизии хэшей (часто применяется для взлома паролей).

Вероятность успеха атаки методом генерации сообщений:
P (дописать формула)

Где n – длина свертки

e – основание натурального логарфима

r₁ – количество генерируемых поддельных сообщений и их сверток

r₂- количество перехваченных сообщений и их сверток.

Радужные таблицы

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

Формирование радужной таблицы:

1) В первый столбец строки радужной таблицы записывается ещё неиспользованная парольная комбинация

2) Вычисляется свертка от этого пароля

3) Важным компонентом радужной таблицы является функция рекурсии, которая преобразует свертку в перебираемое множество символов

4) Шаги 2-3 выполняются число раз, соответствующее глубине радужной таблицы.

5) Последняя свертка заносится во второй столбец строки радужной таблицы.

Использование радужной таблицы

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

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

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

 

Семестр

---

Дата добавления: 2018-08-06; просмотров: 282; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!