Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- РИСУНОК 5.2
| КОНСТРУКЦИЯ 5.7
Пусть (GenH, H) будет хэш-функцией, сконструированной с применением преобрахзования Меркле-Дамгорда для функции сжатия (GenH, h), принима- ющей входные данные длиной n + nr. (См. текст.) Пусть opad и ipad будут фик- сированными константами длиной nr. Определяйте MAC следующим образом: • Gen: при вводе 1n, запустите GenH (1n), чтобы получить ключ s. Также под- берите универсальный k ∈ {0, 1 nt . } Выведите ключ (s, k). • Mac: при вводе ключа (s, k) и сообщения m ∈ {0, 1}* , выведите t := Hs.(k ⊕ opad) " Hs. (k ⊕ ipad) " m.. . • Vrfy: при вводе ключа (s, k), сообщения m ∈ {0, 1}* и тега t, выведите 1, если и только если t =? Hs.(k ⊕opad) || Hs. (k ⊕ ipad) || m... HMAC. РИСУНОК 5.2: HMAC, наглядный пример. Почему у нас должна быть какая-то уверенность, что HMAC является за- щищенным? Одна из причин заключается в том, что мы можем рассматривать HMAC как специфическую реализацию парадигмы хэш-и-MAC из предыду- щего раздела. Чтобы это увидеть, мы заглянем «за кулисы» на то, что проис- ходит, когда сообщение проходит аутентификацию; см. Рисунко 5.2. Мы так же 178 должны более тщательно определять параметры и более подробно остановится на том, как на практике внедряется преобразование Меркле-Дамгорда. Скажем, (GenH, H) сконструирована на основе функции сжатия (GenH, h), в которой h преоразовывает входные данные длиной n + nr в выходные данные длиной n (где, строго говоря, nr - это функция n). Когда мы описывали преоб- разование Меркле-Дамгорда в Разделе 5.2, мы предполагали, что nr = n, но не обязательно должно быть именно так. Мы также говорили, что длина сообще- ния, которое должно хэшироваться, была зашифрована в дополнительный блок, который присодинялся к сообщению. На практике длина вместо этого зашиф- ровывается в часть блока с использованием битов A < nr . То есть вычисление Hs(x) начинается с добавления x с нулями к строке длиной ровно на A меньше, чем кратное nr; затем добавляется длина L = |x|, зашифрованная с использова- нием ровно A бит. Хэш получившейся последовательности nr-битных блоков x1, . . . затем вычисляется как в Конструкции 5.3. Мы предположим, что n + A ≤ nr. Это означает, в частности, что если мы хэшируем входные данные x длиной nr + n, тогда дополненный результат (включая длину) будет точно длиной 2nr бит. Доказательство Теоремы 5.4, показывающее, что (GenH, H) является стой- кой к коллизиям, если (GenH, h) стойкая к коллизиям, остается неизменным. Возвращаясь к HMAC и глядя на Рисунок 5.2, мы можем увидеть, что общая форма HMAC задействует хэширование сообщения произвольной длины в ко- роткую строку y Hs( (k ⊕ ipad) « m), а затем вычисление (секретно кодиро- ванной) функции Hs((k ⊕ opad) « y) результата. Но мы можем сказать даже еще больше. Сначала обратите внимания, что «внутреннее» вычисление H˜ s(m) Hs( (k ⊕ ipad) || m) является стойким к коллизиям (предпологая, что h имеет место) при любом зна- чении k ∈ ipad. Более того, первый шаг «внешнего» вычисления Hs((k ⊕ opad) || y) должен вычислить значение kout hs(IV || (k ⊕ opad)). Затем, мы определим hs(k|| yˆ), где y сслыается на дополненное значение y (то есть включая длину (k ⊕ opad) || y, которая всегда nr + n бит, зашифрованная с использованием ровно A бит). Таким образом, если мы будем считать kout как универсальным, мы будем относиться к нижеописанному более формально и предположим, что M˜ac (y) hs(k || yˆ) (5.2) является защищенным MAC фиксированной длины, тогда HMAC можно рас- симатривать как реализацию подхода хэш-и-MAC с HMACs,k (m) = M˜ackout (H˜ (m)) (5.3) (где kout = hs(IV || (k ⊕ opad))). Благодаря способу разработки функции сжатия h (см. Раздел 6.3.1), предположение, что M˜ac является защищенным MAC фик- сированной длины, имеет смысл. |