*Доказательство беопасности

140
РИСУНОК 4.2: Вариант CBC-MAC, защищенного для аутентификации со-
общений проивольной длины.
функцию CBC , которая, учитывая параметр защиты n, преобразовывает 
n-битные ключи и входные данные в ({0, 1}n)* (то есть строки, длина которых 
кратная n) в n-битные выходные данные. Данная функция определяется как
CBC (x , . . . , x ) 
F (F (• • • F (F (x ) ⊕ x ) ⊕ • • • ) ⊕ x ) ,
где |x1| = • • • = |xA | = |k| = n. (Мы оставляем CBCk неопределенной на пу-
стую строку.) Обратите внимание, что CBC точь в точь базовый CBC-MAC, 
хотя здесь мы рассматриваем входные данные различной длины.
Набор строк P ∈ ({0, 1}n)* является бе зпрефиксным, если он не содержит 
пустых строк, и ни одна строка X ∈ P не является префиксом какой-либо другой 
строки Xr ∈ P . Покажем:
ТЕОРЕМА 4.13  Если F является псевдослучайной функцией, тогда и CBC 
является псевдослучайной функцией, поскольку набор входных данных, ко-
торый она опрашивает, является беспрефиксным. Строго говоря, для всех ве-
роятностных полиномиально-временных идентификаторов D , которые опра-
шивают своего оракула касательно беспрефиксного набора входных данных, 
существует пренебрежимо малая функция negl такая, что
где k выбирается единообразно из {0, 1}n, а f выбирается единообразно из на-
бора функций, преобразующих ({0, 1}n)* в {0, 1}n (то есть значение f при 
каждом входном элементе является универсальным и независимым от значений 
f при всех остальных входных данных).
Таким образом, мы можем преобразовать псевдослучайную функцию F для
входных данных фиксированной длины в псевдослучайную функцию CBC для 
входных данных произвольной длины (подчиняющихся условию, по которому 
входные данные были запрошены)! Чтобы использовать это для аутентификации 
сообщений, мы адаптируем идею Конструкции 4.5 следующим образом: чтобы 
аутентифицировать сообщение m, для начала применим некоторую функцию 
шифрования encode, чтобы получить (непустую) строку encode(m) ∈ ({0, 1}n)*;
затем выведем тег CBCk (encode(m)). Здесь, чтобы обеспечить защищенность 
(сравните доказательством Теоремы 4.6), шифрование должно быть без префикс-

141
ным, а именно, иметь такое свойство, чтобы для любого нового (законного) со-
общения m1, m2, строка encode(m1) не являлась префиксом строки encode(m2). 
Это подразумевает то, что для любого набора (законных) сообщений {m1, . . .}, 
набор зашифрованных сообщений {encode(m1), . . .} будет беспрефиксным.
Давайте теперь изучим два конкретных применения этой идеи:
• Зафиксируйте A, и пусть набор законных сообщений будет {0, 1}A(n)•n. За-
тем мы можем взять тривиальное шифрование encode(m) = m, которое является 
беспрефиксным, поскольку строка не может быть префиксом другой строки той 
же длины. Это точь в точь базовый CBC-MAC, и как мы уже говорили выше, 
это подразумевает, что базовый CBC-MAC является защищенным для сообще-
ний любой фиксированной длины (сравните с Теоремой 4.12).
• Один из способов обработки (непустых) сообщений произвольной длины (тех-
нически, сообщений длиной меньше чем 2n) - это зашифровать строку m ∈ {0, 1}* 
посредством добавления в начало строки ее длины |m| (зашифрованной n-битной 
строкой), а затем добавления в конец строки стольких нулей, сколько будет нужно, 
чтобы сделать длину итоговой строки кратной n. (Это очень важно, что и показано 
на Рисунке 4.2.) такое шифрование является беспрефиксным, и мы, таким образом, 
получаем защищенный MAC для сообщений произвольной длины.
Оставшаяся часть раздела посвящена доказательству Теоремы 4.13. Доказывая 
теорему, мы анализируем CBC , когда она «ключевая» при случайной функции g 
, а не случайном ключе k для какой-то присутствующей псевдослучайной функ-
ции F . То есть мы рассматриваем ключевую функцию CBCg , определенную как
CBC (x , . . . , x ) 
g (g (• • • g(g(x ) ⊕ x ) ⊕ • • • ) ⊕ x )
где, учитывая параметр защиты n, функция g преобразовывает n-битные вход-
ные данные вn-битные выходные данные, и |x1| = • • • = |xA | = n. Обратите 
внимание, что CBCg , как было здесь определено, не является эффективной 
(поскольку представление g требует экспоненциала пространства в n); тем не 
менее, она все еще хорошо определенная, ключевая функция.
Мы покажем, что если g выбирается единообразно из Funcn, то CBCg является 
неотличимой от случайной функции, преобразующей ({0, 1}n)* в n-битные строки 
при условии, что опрашивается беспрефиксный набор входных данных. Более точно:

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: