On authentication codes based on orthogonal tables

Abstract

The authentication codes resistant to messages imitation and substitution are investigated. The case when the probabilities of imitation and substitution reach the lower limits has been highlighted. Such authentication codes are called optimal. We study constructions of optimal authentication codes based on orthogonal tables. The case of optimal authentication codes with optional uniform distribution on the set of keys is studied.

Full Text

Пусть 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.