Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Основи криптографії. Тема 3. Асиметричні криптосистеми. Носов В.В.
Лекція 9. Геш-функції і техніка аутентифікації
Навчальні питання
1. Геш-функції та коди аутентифікації повідомлень 2
2. Безумовно безпечні коди аутентифікації 3
Час – 2 год.
Література.
Вступ
Ранее мы упомянули конфиденциальность (секретность) как основную причину использования криптосистем. Однако, для огромного большинства задач секретность данных не является основной проблемой.
Не меньшую роль в информационных процессах играют задачи обеспечения аутентификации (установление подлинности) и целостности данных. Например, при получении файлов данных, сообщений по электронной почте и т.п. Нарушение конфиденциальности может привести к меньшему ущербу, чем нарушение целостности или аутентичности.
При изучении возможных схем аутентификации нужно определить следующие особенности:
Первые две особенности аутентификации приводят к полностью отличным друг от друга областям исследований.
Темой лекции являются схемы аутентификации, обладающие безусловной безопасностью (или абсолютной стойкостью). Это означает, что даже при неограниченных вычислительных возможностях противник не может взломать систему, т.е. осуществить имперсонацию.
Такие схемы обычно называют кодами аутентификации, а один их частный подкласс называют А-кодами.
Вычислительно безопасные системы базируются на некоторых математических допущениях наподобие (практической) невозможности факторизовать большие числа или брать дискретные логарифмы. Эти системы носят название схем цифровых подписей и уже обсуждались нами ранее.
В случае, когда файл — очень длинный и его конфиденциальность несущественна, имеется весьма общая техника присоединения к нему доказательства аутентичности или целостности:
Этот "хвост" должен доказывать, что сообщение на самом деле пришло от предполагаемого отправителя и что его содержание не было изменено.
Стандартный путь осуществления этого — хэшировать2 файл криптографически безопасным способом в короткую последовательность и вычислить подпись на этом хэш-значении. Подпись хэш-значения добавляется к исходному файлу. Если реализация схемы аутентификации работает медленно (как в случае схем цифровой подписи), такой двух-шаговый подход оказывается очень практичным.
Во многих приложениях хэш-функции используют секретный ключ, разделяемый отправителем и получателем. Такие системы, называемые по-английски MAC (от Message Authentication Code), не обладают безусловной безопасностью, потому что кто-нибудь, имеющий неограниченные вычислительные ресурсы, может в принципе перебрать все ключи.
Хэш-функции и MAC'и являются предметом этой лекции.
Здесь мы исключим формальное описание различных типов хэш-кодов. Для наших целей достаточно общего понимания этих кодов и их свойств.
Функция хэширования (хэш-функция или хэш-код) — это отображение из множества 𝒜* всех последовательностей символов из алфавита 𝒜 в , где — некоторое фиксированное натуральное число. Таким образом, каждая последовательность (произвольной длины) над 𝒜 отображается в последовательность длины над 𝒜. В типичных приложениях , а принимает значение между 64 и 256.
Так как обычно желательна очень быстрая реализация хэш-функции, мы также требуем, чтобы хэш-значения для любых последовательностей над 𝒜 вычислялись легко.
Чтобы сделать хэш-функцию криптографически безопасной, обычно требуют выполнения одного или более из следующих условий.
H1. Хэш-функция — односторонняя функция, т.е. почти для всех выходов вычислительно невозможно найти вход такой, что ).
Н2. Хэш-функция слабо сопротивляется коллизиям. Это означает, что для заданного значения вычислительно невозможно найти второе значение , , такое, что .
Н3. Хэш-функция сильно сопротивляется коллизиям. Это означает, что вычислительно невозможно найти пару значений , такую, что .
Н2 означает, что если хэш-значение ) на файле защищено цифровой подписью, то последний нельзя заменить другим файлом с тем же хэш-значением — просто потому, что такой невозможно найти.
Условие Н3 еще сильнее: оно дает возможность убедить арбитра, что система была скомпрометирована.
Пример 13.1
Рассмотрим, и . При хэшировании последовательности просто берется . Это хэш-значепие зависит от всех символов в и легко вычисляется, но не выполняется ни одно из условий Н1-Н3.
Пример 13.2
Снова рассмотрим, и . Для хэширования последовательности вычисляется . Если — большое составное число, то условие Н1 выполняется, поскольку вычисление квадратных корней по модулю такого целого считается невозможным.
С помощью функций Mod и Length пакета "Mathematica" эта хэш-функция легко вычисляется.
h[inputfile_List,nn_Integer]:=
Mod[()2,nn]
n=989;
in={189,632,900,722,349};
h[in,n]
|| 955
Условия H1 и Н3 не выполняются, так как имеет то же хэш-значение, что и . Кроме того, хэш-значение сохраняется, когда одна из координат увеличивается, а другая уменьшается на одно и то же число.
alternative = Mod[-in, n]
h[alternative, n]
|| {800, 357, 89, 267, 640}
|| 955
Даже когда хэш-функция удовлетворяет условиям Н1-Н3, остается возможность перехватить передачу и заменить это другим файлом ). По этой причине иногда желательно ввести секретный ключ, разделяемый отправителем и получателем. При этом хэш-функция обретает название код аутентификации сообщений (MAC) и является отображением из в , где — пространство ключей, в точности, как в традиционных криптосистемах.
Пример 13.3
Пусть и . Через обозначим результат DES-шифрования блока и длины относительно ключа . Допустим, что Алиса и Боб разделяют ключ .
Рассмотрим теперь бинарный файл длины , который Алиса намерена переслать Бобу. Сначала Алиса добавляет достаточное число нулей, чтобы длина файла стала кратной . Пусть L — эта новая длина. Для вычисления хэш-значения на Алиса выполняет следующий алгоритм.
Алгоритм 13.1 (использование DES в качестве МАC)
input двоичная цепочка , где ;
initialize ;
for i = 0 to do
;
output хэш-значение .
Получатель повторяет приведенные выше вычисления для проверки того, что файл не был изменен и что он на самом деле был послан Алисой.
Конечно, в этом примере вместо DES можно было бы использовать любой другой блочный шифр.
Можно также использовать блочный шифр в качестве безключевой хэш-функции. С этой целью ключ делается публичным параметром.
При использовании блочного шифра для целей аутентификации неявно предполагается, что при фиксированном ключе шифр работает как случайная перестановка символов входной цепочки. Надеются также, что блочный шифр криптографически безопасен. Далее рассмотрим коды аутентификации, которые не базируются ни на каком математическом допущении.
Имеется много различных стандартов для хэш-функций.
Основные понятия и границы
Никакая схема аутентификации не может дать абсолютной гарантии, что полученное сообщение пришло от ожидаемого пользователя, скажем, Алисы. Например, всегда имеется небольшая вероятность того, что сгенерированная (случайно или нет) последовательность могла быть создана Алисой, хотя фактически это не так. Тогда вторая сторона может счесть эту последовательность подлинным документом Алисы.
Отсюда следует, что необходимо определить и уметь вычислять вероятность подмены. Однако при таких вычислениях имеется существенное различие между предполагаемой вычислительной безопасностью тех или иных проблем (как это было в криптосистемах с публичными ключами) и отсутствием вовсе каких-либо предположений такого вида (безусловная безопасность или абсолютная стойкость). Последнюю ситуацию рассмотрим далее.
Предположим, что Алиса и Боб доверяют друг другу и имеют общий секретный ключ. В действительности это предположение не является необходимым, но тогда должно быть введено понятие доверенной третьей стороны (типа арбитра). Начнем с простого примера.
Пример 13.4
Алиса хочет послать Бобу единственный бит информации (да или нет) с помощью слова длины 2. Алисе и Бобу доступны 4 возможных ключа, причем, они используют матрицу из таблицы 13.1.
Таблица 13.1. Код аутентификации для двух сообщений.
|
ключ/код |
00 |
01 |
10 |
11 |
|
1 |
0 |
1 |
||
|
2 |
1 |
0 |
||
|
3 |
0 |
1 |
||
|
4 |
1 |
0 |
Например, относительно третьего ключа сообщение будет послано как слово . Вероятность того, что кто-то другой может имперсонифицировать Алису (выдать себя за неё), равна , поскольку относительно общего секретного ключа Алисы и Боба только два из четырех слов могут быть действительно переданы.
Противник Ева, при попытке подменить переданное сообщение иным сообщением, знает, что могут быть использованы только два ключа или , но не знает, который именно. Поэтому вероятность успешной подмены также равна .
Например, если Ева перехватывает , то она знает, что было послано либо сообщение (относительно ключа ), либо сообщение (относительно ключа ). В первом случае она должна передать , а во втором, — , значит, ее успех имеет вероятность .
Эта схема обеспечивает и секретность, потому что любое переданное слово может порождаться как сообщением, , так и сообщением (оба события имеют вероятность 1/2).
Общее определение кода аутентификации таково (здесь мы отклоняемся от стандартных обозначений из теории кодов аутентификации, чтобы избежать смешения со стандартными обозначениями из теории кодов, исправляющих ошибки):
Определение 13.1
Код аутентификации — это тройка вместе с отображением , таким, что для всех и всех
(13.1)
Множество называется множеством сообщений, множеством ключей, множеством кодовых слов.
Код аутентификации можно описать таблицей , в которой строки индексированы ключами из , столбцы — кодовыми словами из , а в клетке с индексами стоит либо такое , что (если оно существует; тогда в силу (13.1) оно единственно), либо стоит прочерк, если такого нет. Эту таблицу мы будем называть матрицей аутентификации данного кода.
В примере 13.4 , и . Матрица аутентификации этого кода задана в табл. 13.1.
Условие (13.1) означает, что инъективно для каждого ключа .
Когда Боб получает кодовое слово от Алисы, он принимает как подписанную версию сообщения , где однозначно определено равенством . Здесь — ключ, уже согласованный Алисой и Бобом. Чтобы система была практичной, должно быть легко обратимым для каждого ключа . С этой целью структуру (и ) часто значительно упрощают.
Определение 13.2
А-код — это тройка вместе с отображением . При данном ключе сообщение передается в виде , где называется аутентификатором сообщения .
Беря и , мы видим, что А-код — это частный случай кода аутентификации.
Хороший код аутентификации строится таким образом, чтобы подложные слова равномерно распределялись над , тогда как подмножество слов, ожидаемых легитимным получателем, знающим общий ключ , было лишь небольшой частью этого множества.
Поэтому при создании кода аутентификации цель состоит в том, чтобы не только Боб, но и арбитр мог проверить аутентичность правильно созданного (в случае А-кода проверяется, что , а в случае произвольного кода аутентификации проверяется, что лежит в образе отображения ), но имперсонатор, который не знает ключа, имел бы лишь малую вероятность получить допустимое слово . Атака имперсонатора называется атакой имперсонации (имитации).
Вышесказанное должно оставаться верным и в случае, когда противник хочет подменить подлинное кодовое слово (полученное с правильным ключом) другим словом , которое представляет иное сообщение.
Этот вид атаки называют атакой подмены. Заметим, что в этом случае противнику доступна некоторая информация о ключе. Не будем обсуждать системы, в которых один и тот же ключ может безопасно использоваться легитимными сторонами более одного раза.
В последующих определениях будем предполагать, что как ключи, так и сообщения выбираются случайно из множеств и, соответственно, с равномерным распределением вероятностей.
Допустим, что Алиса и Боб используют некий общий код аутентификации. Чтобы максимизировать вероятность успешной имперсонации, противник не может сделать ничего лучшего, нежели выбрать и послать кодовое слово , которое имеет наибольшую вероятность быть принятым легитимным получателем. В этом случае кодовое слово с должно лежать в образе отображений для максимального числа ключей .
Говоря иными словами, в матрице аутентификации ищется столбец, содержащий максимальное число непрочерков [т.е. минимальное число прочерков]. Тогда посылается индекс с этого столбца.
Определение 13.3
Вероятность — это максимальная вероятность успешной атаки имперсонации, т.е.
. (13.2)
В примере 13.4 каждое кодовое слово является образом какого-то сообщения относительно ровно двух из четырех ключей (в каждом столбце из 4 клеток — 2 непрочерка). Поэтому .
В случае атаки подмены перехватывается кодовое слово . Это сужает множество ключей, которые могли быть использованы отправителем и получателем, до множества . Тогда наилучшая атака для противника — искать среди кодовых слов, допустимых для данных ключей, слово, которое встречается наиболее часто.
Говоря иными словами, в матрице аутентификации данного кода отыскивается столбец с перехваченным индексом и из матрицы удаляются все строки, содержащие прочерк в этом столбце (это строки, индексированные ключами, которые не могли быть использованы). Удаляется также столбец с индексом . Среди оставшихся столбцов ищется столбец с наибольшим количеством непрочерков. Индекс этого столбца и будет подменой для . Если для примера 13.4, перехвачен код 10, тогда таблица 13.1 примет вид
|
ключ/код |
00 |
01 |
11 |
|
2 |
1 |
||
|
4 |
0 |
Среди оставшихся столбцов два столбца с наибольшим количеством непрочерков, тогда подменой для будет или .
Определение 13.4
Вероятность — это максимальная вероятность успешной атаки подмены, т.е.
. (13.3)
В примере 13.4 каждое кодовое слово является образом какого-то сообщения относительно ровно двух из четырех ключей. Для каждого из этих двух ключей различные возможные сообщения отображаются в различные кодовые слова. Поэтому .
Максимальная из двух вероятностей (13.2) и (13.3) часто называется вероятностью успешного обмана (deception). Она дается формулой
. (13.4)
Поскольку функция аутентификации инъективна для каждого , ровно кодовых слов должны быть аутентичны для любого данного ключа. Другими словами, каждая строка матрицы аутентификации кода аутентификации содержит ровно непрочерков. Из того, что имеет строк и столбцов, следует, что среднее число непрочерков на столбец из равно .
|
ключ/код |
00 |
01 |
10 |
11 |
|
|
1 |
0 |
1 |
|||
|
2 |
1 |
0 |
|||
|
3 |
0 |
1 |
|||
|
4 |
1 |
0 |
Таким образом, максимальная доля непрочерков на столбец не меньше . Это доказывает следующую теорему.
Теорема 13.2
Максимальная вероятность успешной имперсонации в схеме аутентификации для кода удовлетворяет неравенству .
Аналогично предыдущему, в случае атаки подмены сужение матрицы аутентификации на строки, которые в столбце с индексом , где — перехваченное кодовое слово, содержат не-прочерки, состоит из строк. После удаления столбца с индексом новое сужение имеет столбцов и непрочерков в каждой строке.
Таким образом, среднее значение относительной частоты непрочерков в последнем сужении равно . Это дает следующую границу.
Теорема 13.3
Максимальная вероятность успешной подмены в схеме аутентификации для удовлетворяет неравенству
Даже если сообщения и ключи распределены неравномерно на пространствах сообщений и ключей соответственно, то все еще можно вывести нижние границы для , и .
Теорема 13.4
Пусть и — случайные переменные, определенные на , и соответственно, связанные отображением , удовлетворяющим (13.1). Далее, пусть и обозначают функцию условной энтропии и, соответственно, функцию взаимной информации. Тогда
(13.5)
(13.6)
(13.7)
Граница в неравенстве (13.7) называется границей квадратного корня. Коды аутентификации, достигающие этой границы, называют совершенными.
Теорема 13.5
Необходимым условием совершенности кода аутентификации служит неравенство
Висновки
Контрольні питання
Задачі
2 От английского hash в смысле "мешанина, путаница".