О кодах аутентификации на основе ортогональных таблиц

Аннотация

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

Полный текст

Пусть h : K × X → Y - ключевая криптографическая хеш-функция, где X - конечное множество сообщений, K - конечное множество ключей, Y - конечное множество сверток. Напомним, что кодом аутентификации (без сокрытия) называется четверка (X, K, Y, h), для которой Y = k∈K hk (X). Заметим, что потенциальный противник может осуществлять не только пассивные действия относительно передаваемых по каналу связи сообщений, © 2014 Самарский государственный технический университет. Образец для цитирования Р а ц е е в С. М., Ч е р е в а т е н к о О. И. О кодах аутентификации на основе ортогональных таблиц // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2014. № 4 (37). С. 178- 186. doi: 10.14498/vsgtu1309. 178 О кодах аутентификации на основе ортогональных таблиц которые заключаются, например, в подслушивании или перехвате сообщений, но также и активные атаки, заключающиеся в имитации или подмене сообщения. Пусть канал связи готов к работе и на приеме установлены действующие ключи k ∈ K, но в данный момент времени никакого сообщения вида (x, y), где y = hk (x), не передается. Тогда в этом случае противником может быть предпринята попытка имитации сообщения некоторой парой (x, y) ∈ X × Y . Рассмотрим вероятностное пространство (Ω = K, FK , PK ). Зафиксируем (x, y) ∈ X × Y . Обозначим через K(x, y) следующее множество: K(x, y) = {k ∈ K | hk (x) = y}. Под обозначением K(x, y) будем также понимать событие из алгебры событий FK , заключающееся в том, что при случайном выборе ключа k ∈ K будет выполнено равенство hk (x) = y. Тогда событию K(x, y) будут благоприятствовать все элементы из множества K(x, y), и только они. Поэтому P (K(x, y)) = PK (k). k∈K(x,y) Поскольку противник имеет возможность выбора (x, y) ∈ X × Y , его шансы на успех имитации сообщения выражаются такой величиной: Pim = max P (K(x, y)). (x,y)∈X×Y Если же в данный момент передается некоторое сообщение вместе со своей сверткой (x, y) ∈ X × Y , y = hk (x), то противник может заменить его на (x, y) ∈ X × Y , x = x. При этом он будет рассчитывать на то, что на действующем ключе k при проверке будет выполнено равенство y = hk (x). Чем больше вероятность этого события, тем успешнее будет попытка подмены. Пусть «K(x, y) | K(x, y)» - событие, заключающееся в попытке подмены сообщения (x, y) сообщением (x, y). Применяя теорему о произведении вероятностей, получаем P (K(x, y) | K(x, y)) = P (K(x, y) ∩ K(x, y)) . P (K(x, y)) Тогда вероятность успеха подмены сообщения будет вычисляться по следующей формуле: P (K(x, y) | K(x, y)). Psubst = max x,x∈X, y,y∈Y x=x Теорема 1 [1]. Для любого кода аутентификации (X, K, Y, h) справедливы следующие утверждения: (i) Pim 1/|Y |, причем нижняя граница достигается тогда и только тогда, когда для любой пары (x, y) ∈ X × Y выполнено равенство P (K(x, y)) = 1/|Y |; 179 Р а ц е е в С. М., Ч е р е в а т е н к о О. И. (ii) Psubst 1/|Y |, причем нижняя граница достигается тогда и только тогда, когда для любых x, x ∈ X, x = x, y, y ∈ Y выполнено равенство P (K(x, y) | K(x, y)) = 1/|Y |; (iii) Pim и Psubst одновременно достигают нижней границы тогда и только тогда, когда для любых x, x ∈ X, x = x, y, y ∈ Y выполнено равенство P (K(x, y) ∩ K(x, y)) = 1/|Y |2 . Напомним несколько определений. Латинским квадратом s-того порядка над множеством Y = {y1 , . . . , ys } называется таблица размера s × s, заполненная элементами множества Y таким образом, что в каждой строке и в каждом столбце каждый элемент встречается ровно один раз. Две матрицы A = (aij ) и B = (bij ) над множеством Y = {y1 , ..., ys } называются ортогональными, если все упорядоченные пары (aij , bij ) различны. Ортогональной таблицей OA(s, n) над множеством Y = {y1 , . . . , ys } называется матрица размера s2 × n над множеством Y с тем условием, что для любых двух столбцов данной матрицы каждая из пар (yi , yj ) ∈ Y × Y встречается ровно один раз. Существование ортогональной таблицы OA(s, n) над множеством Y эквивалентно существованию n попарно ортогональных квадратных матриц порядка s над множеством Y [2]. Хорошо известно, что если число s является степенью некоторого простого числа, то в этом случае существуют s - 1 попарно ортогональных латинских квадрата, или, что то же самое, s + 1 ортогональных матриц [3]: для этого достаточно рассмотреть многочлены fα (x, y) = αx + y над полем GF (s) при ненулевых α. Большой интерес представляют коды аутентификации со свойством Pim = Psubst = 1/|Y |. Такие коды называются оптимальными. Для описания таких кодов используется понятие ортогональной таблицы. Теорема 2 [1]. Пусть код аутентификации (X, K, Y, h) является оптимальным. Тогда верны следующие утверждения: (i) |K| |Y |2 ; (ii) |K| = |Y |2 тогда и только тогда, когда табличное задание хеш-функции h представляет собой ортогональную таблицу OA(|Y |, |X|) над Y и распределение вероятностей PK является равномерным. Следствие 1. Пусть для кода аутентификации (X, K, Y, h) выполнено равенство |K| = |Y |2 . Код аутентификации (X, K, Y, h) является оптимальным тогда и только тогда, когда выполнены следующие условия: (i) табличное задание хеш-функции h представляет собой ортогональную таблицу OA(|Y |, |X|); 180 О кодах аутентификации на основе ортогональных таблиц (ii) распределение вероятностей на множестве K равномерно. Пусть (X, K, Y, h) - код аутентификации, |X| = n, K = {k1 , . . . , kr }, с распределением вероятностей PK на множестве ключей K и табличным заданием хеш-функции A размера r × n над множеством Y . При этом строки матрицы A пронумерованы элементами множества K, а столбцы - элементами множества X. Пусть также для некоторого другого ключевого множества K, |K| |K|, с распределением вероятностей PK найдется такое разбиение на r непустых непересекающиеся подмножеств K = K1 ∪ K2 ∪ · · · ∪ Kr , (1) для которого выполнены равенства PK (Ki ) = PK (k) = PK (ki ), i = 1, . . . , r. (2) k∈Ki Построим код аутентификации (X, K, Y, h). Как видно, для данного кода остается задать хеш-функцию h. Зададим ее таблично следующим образом: j-тую строку матрицы A продублируем |Kj | раз, j = 1, . . . , r, и из всех полученных (продублированных) строк составим матрицу B. Матрица B и будет табличным заданием хеш-функции h. Предложение 1. Вероятности успехов имитации и успехов подмены для кодов аутентификации (X, K, Y, h) и (X, K, Y, h) соответственно равны, в частности, из оптимальности одного кода аутентификации следует оптимальность другого. Д о к а з а т е л ь с т в о. Следующие равенства P (K(x, y)) = P (K(x, y)), P (K(x, y) | K(x, y)) = P (K(x, y) | K(x, y)) выполняются, так как для любых x, x ∈ X, x = x, y, y ∈ Y , i = 1, . . . , r ki ∈ K(x, y) ⇔ Ki ⊆ K(x, y). Данное утверждение показывает, что оптимальные коды можно строить не только для случая, когда PK равномерно. Пусть K = K1 ∪ K2 ∪ · · · ∪ Ks2 (3) - разбиение множества K на непустые непересекающиеся подмножества с условием 1 (4) PK (Ki ) = PK (k) = 2 , i = 1, . . . , s2 . s k∈Ki Пусть также для чисел s и n существует ортогональная таблица OA(s, n) над некоторым множеством Y = {y1 , ..., ys }. Построим из данной таблицы (как 181 Р а ц е е в С. М., Ч е р е в а т е н к о О. И. и до предложения 1) матрицу B размера |K| × n, которая будет таблично представлять хеш-функцию h : K × X → Y , где X = {x1 , . . . , xn } - некоторое множество открытых текстов. Предложение 2. Полученный код аутентификации будет являться оптимальным. Д о к а з а т е л ь с т в о следует из предложения 1 и следствия 1. Пример. Пусть X = {x1 , x2 , x3 }, Y = {0, 1}, K = {k1 , . . . , k7 } и распределение вероятностей на множестве K имеет вид K PK k1 k2 k3 k4 k5 k6 k7 . 1/16 3/16 1/20 1/10 1/10 1/4 1/4 В этом случае существует разбиение вида (3) с условием (4): K1 = {k1 , k2 }, K2 = {k3 , k4 , k5 }, K3 = {k6 }, K4 = {k7 }, PK (K1 ) = PK (K2 ) = PK (K3 ) = PK (K4 ) = 1/4. Составим ортогональную таблицу OA(2, 3) над Y , а на ее основе построим матрицу B, которая будет являться табличным представлением хеш-функции h: OA(2, 3) : 0 0 1 1 0 1 0 1 0 1 , 1 0 B: K X k1 k2 k3 k4 k5 k6 k7 x1 x2 x3 0 0 0 0 0 0 0 1 1 . 0 1 1 0 1 1 1 0 1 1 1 0 Из предложения 2 следует, что полученный код аутентификации является оптимальным, причем Pim = Psubst = 1/2. Заметим, что недостатком данной математической модели кода аутентификации является ограничения, накладываемые на мощности множеств X и K. Рассмотрим математическую модель кода аутентификации без этих ограничений, введенную в работе [4], которая является аналогом математической модели шифров замены с ограниченным и неограниченным ключом, введенную А. Ю. Зубовым в работе [5] и позволяющую строить совершенные имитостойкие шифры [6, 7]. Пусть U , V - соответственно конечные множества возможных кодвеличин и кодобозначений (как аналогия шифрвеличин и шифробозначений в модели шифра замены с неограниченным ключом [5]). Перед выработкой кода аутентификации сообщение x ∈ X предварительно представляется в виде 182 О кодах аутентификации на основе ортогональных таблиц последовательности кодвеличин, которые в процессе выработки кода аутентификации заменяются на кодобозначения. Пусть также имеются конечное множество ключей K и ключевая хеш-функция h : K × U → V. Процесс выработки кода аутентификации для сообщения x = u1 . . . ul на ключе k1 . . . kl заключается в замене каждой кодвеличины ui на кодобозначение vi в соответствии с ключом ki , i = 1, . . . , l. Опорным кодом кода аутентификации назовем совокупность ∆0 = (U, K, V, h), для которой V = k∈K hk (U ). H l-той степенью опорного кода ∆0 назовем совокупность H ∆l = (U l , K l , V l , h(l) ), H где U l , K l , V l - декартовы степени соответствующих множеств U , K, V ; множество h(l) состоит из отображений hk : U l → V l , k ∈ K l , таких, что для любых u = u1 . . . ul ∈ U l , k = k1 . . . kl ∈ K l выполнено равенство hk (u) = hk1 (u1 )...hkl (ul ) = v1 . . . vl ∈ V l . Кодом аутентификации с неограниченным ключом назовем семейство ∆H = (∆l , l ∈ N; ψc ), H где ψc - случайный генератор ключевого потока. Будем говорить, что код аутентификации с неограниченным ключом ∆H является оптимальным, если оптимальным является код ∆l для любого l ∈ N. H Теорема 3 [4]. Пусть для кода аутентификации ∆H выполнены следующие условия: (i) |K| = |V |2 ; (ii) для любых u1 , u2 ∈ U, v1 , v2 ∈ V существует, и притом единственный, ключ k ∈ K, для которого hk (u1 ) = v1 и hk (u2 ) = v2 ; (iii) распределение вероятностей на множестве K равномерно. Тогда код аутентификации ∆H является оптимальным. Следствие 2. Пусть для кода аутентификации ∆H выполнено равенство |K| = |V |2 . Тогда ∆H является оптимальным, тогда и только тогда, когда выполнены следующие условия: (i) для любых u1 , u2 ∈ U, v1 , v2 ∈ V существует, и притом единственный, ключ k ∈ K такой, что hk (u1 ) = v1 , hk (u2 ) = v2 ; (ii) распределение вероятностей на множестве K равномерно. l Для кода аутентификации ∆l , l ∈ N, обозначим через Pim вероятность H l успеха имитации, а через Psubst (s) - вероятность успеха подмены в сообщении ровно s пар элементов вида (ui , vi ) ∈ U × V , где vi = hki (ui ). Тогда, если код аутентификации ∆H является оптимальным, то l Pim = 1/|V |l , l Psubst (s) = 1/|V |s , 183 Р а ц е е в С. М., Ч е р е в а т е н к о О. И. l l то есть Pim → 0 при l → ∞, Psubst (s) → 0 при s → ∞. Пусть ∆H - некоторый код аутентификации с неограниченным ключом с опорным кодом ∆0 = (U, K, V, h), |U | = n, |V | = s, |K| = r, распределеH нием вероятностей PK для случайного генератора ψc и табличным заданием хеш-функции A размера r × n над множеством V для кода ∆0 . Пусть также H для некоторого ключевого множества K, |K| = r, r r, имеется случайный генератор ψc с распределением вероятностей PK и условием, что найдется разбиение множества K на r частей вида (1) с условием (2). Построим код аутентификации с неограниченным ключом ∆H со случайным генератором ψc и опорным кодом ∆0 = (U, K, V, h) со значениями U и V , как и в опорном H коде ∆0 . Определим хеш-функцию h с помощью табличного представления B H размера r × n над множеством V , в которой строки пронумерованы элементами множества K, а столбцы - элементами множества U следующим образом: j-тую строку матрицы A продублируем |Kj | раз, j = 1, . . . , r, и из всех полученных (продублированных) строк составим матрицу B, которая и будет представлять хеш-функцию h. Предложение 3. Вероятности успехов имитации и успехов подмены для кодов аутентификации ∆H и ∆H соответственно равны, в частности, из оптимальности одного кода аутентификации следует оптимальность другого. Д о к а з а т е л ь с т в о следует из предложения 1. Пусть имеется разбиение (3) с условием (4). Пусть также для чисел s и n существует ортогональная таблица OA(s, n) над множеством V = {v1 , . . . , vs }. Построим из данной таблицы матрицу B размера s2 × n, которая будет таблично представлять хеш-функцию h : K × U → V . Предложение 4. Полученный код аутентификации ∆H будет являться оптимальным. Д о к а з а т е л ь с т в о следует из предложения 2.