Построение систем аутентификации с гарантированной вероятностью навязывания.

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

 

Утверждение. Если для аутентификации используются функции, выбираемые равновероятно из строго универсального класса, то вероятность успешного выполнения оптимальной атаки подстановки будет равна, где b – длина аутентификатора.

 

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

По ключу k₀ этот пользователь вырабатывает аутентификатор

Обозначим через H’ множество всех ключей из H, которые переводят заданное M в такой аутентификатор E_S.

Пусть злоумышленник хочет сформировать ложное сообщение M’, которое законный пользователь аутентифицировал бы как правильное.

Тогда он должен создать ложный аутентификатор. Однако он не знает ключа k₀, которым воспользовался бы для проверки законный пользователь. Вся информация, которую имеет злоумышленник при известных ему M и E_S (даже при его неограниченном вычислительном ресурсе), – это множество ключей H’.

 

Таким образом, оптимальная стратегия злоумышленника состоит в том, чтобы случайно (наугад) выбрать ключ k₀ из множества H’. Тем не менее ему не обязательно в точности угадать истинный ключ k₀, а достаточно лишь угадать один из ключей, принадлежащих H’, которые дают отображение:

Обозначим множество таких ключей через H’’. Согласно свойству а) строго универсального класса, количество ключей из H’ равно в точности, а по свойству б) количество ключей из H’’ будет в точности равно

 

Тогда вероятность того, что злоумышленник, зная множество, угадает один из элементов множества H’’, т. е. что навязывание ложного сообщения окажется успешным, может быть записана так:

 

Сравним полученный результат с нижней границей для вероятности необнаруженной подстановки:

 

Так как в схеме, эта граница достигается приb=n и для этого частного случая схемааутентификации на основе использования универсальных хеш-функций оказывается совершенной.

 

Приведенная выше схема аутентификации имеет, однако, два существенных недостатка:

- длина ключа достаточно велика (она всегда в 2 раза превышает длину сообщения!);

- схема совершенна лишь при длине аутентификатора, равной длине сообщения.

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

при увеличении числа аутентифицированных сообщений.

Определение. Хеш-функцией называется преобразование, отображающее множество всех двоичных последовательностей X длины n во множество двоичных последовательностей Y длины b, гдеb<n

Символически это преобразование можно записать так: