Универсальные функции хэширования

Аналогично определению 8.2 введем понятие универсальная функция хэширования для функций, зависящих от секретного ключа к, принадлежащего некоторому множеству /С.

Определение 8.4 (см. [3, 5]). Пусть к е /С. Отображение

называют в-почти универсальной функцией хэширования (в-almost universal, в-AU), если найдется действительное число в такое, что О < в ^ 1, и для любых двух различных элементов х. у е F2⁰ выполнена оценка.

Если выполнено равенство е — 2~^п, то отображение h (k, х) называют универсальной функцией хэширования.

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

Определение 8.5 (см. [3, 5J). Пусть, как и ранее, к ? 1C. Отображение h,(k, x) называют s-почти строго универсальным (в-almost strong universal, в-ASU), если выполнены следующие условия.

2. Для любых различных х, у G F^ и для любых h. t G F₂ выполнена оценка.

Если выполнено равенство е = 2 ^п, то отображение h (k, x) называют строго универсальной функцией хэширования.

Для e-ASU функций хэширования значение е задаст величину условной вероятности появления события h (k, y) — b при выполнении события h (k, x) = а. Можно показать, что всякая функция, удовлетворяющая определению 8.5, также удовлетворяет и определению 8.4.

Приведем несколько универсальных функций, для которых доказано, что они являются e-ASU функциями при некоторых значениях ?. Будем считать, что множества /С и F^⁵ совпадают, а для каждого сообщения х G F^ используемый ключ к удовлетворяет равенству! спж = lcnfc. Для сообщений х и ключей к мы будем использовать запись.

при некотором натуральном t. Тогда, e-ASU являются следующие функции.

1. ММН. Определим р — 2³² + 15 — простое число, тогда.

где к_п, х_п G Z₂32.

2. Square Hash. Пусть w > 2 — натуральное число, р — наибольшее простое число меньшее, чем 2^Ш. Определим.

где k_n, x_n G Ъ₂и-.

3. NMH. Пусть t = 21, l G N и p = 2³² + 15 — простое число.

Определим.

где к_п, х_п G Z₂32.

4. NH (алгоритм UMAC). Пусть w G N, w ^ 2, t, = 21, I G N.

Определим.

где z_n = к_п + х_п (mod 2^W), к_п, х_п G и h (k, x) G Z₂zw.

5. Badger. Пусть t — 41, l G N. Определим.

где Zn = кп -(- Xji (mod 2 Vn — X4к—iP 2* .t'i, A, xG Z-ysi

и ⁼ Z₂64 и /z (/t, ж) G Z₂2u?.

Как видно из приведенных примеров, все функции обладают большим ключом, длина которого совпадает с длиной сообщения, для которого вычисляется код целостности. На практике ключи аутентификации имеют небольшую длину. В связи с этим, прямое использование универсальных функций хэширования затруднительно и требует описания дополнительного алгоритма развертки ключа. Наиболее известным алгоритмом, построенным на принципах универсальных функций хэширования, стал ориентированный на реализацию на 32-х битных процессорах алгоритм UMAC^[1].

Данный алгоритм использует алгоритм выработки производного ключа, основанный на применении блочного алгоритма шифрования, которым, по мнению авторов UMAC, должен являться алгоритм AES, см. раздел 7.5.1.

Представим исходное сообщение а, для которого нужно вычислить код целостности, в виде.

Пусть к е F™ — ключ аутентификации, а Е (к,-) — алгоритм зашифрования блочного шифра с длиной блока п, кратной 32. Обозначим s = тогда производным ключом является последовательность значений ki,…k₂i G Z₂32, вычисляемая по следующему правилу:

в котором величина to = (1110 • • • 0).

После выработки производного ключа алгоритм UMAC определяет значение кода целостности равенством.

где z_n = к_п + х_п (mod 2³²) и к_п, х_п G Z₂32.

• [1] См. Black J., Halevi S., Krawczyk II., Krovetz T., Rogaieay P. UMAC: Fast andSecure Message Authentication // Proceedings Of Crypto'99. — LNCS 1666. —Springer-Verlag. — 1999. — pp.216−233.