Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA)

<86 87 888990 91 92 >

NIST, вместе с NSA, для Стандарта цифровой подписи (Digital Signature Standard, см. Раздел 20.2) разработал Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA) [1154 (Digital Signature Standard]. (Сам стандарт называется Стандарт безопасного хэширования (Secure Hash Standard, SHS), а SHA - это алгоритм, используемый в стандарте.) В соответствии с Federal Register[539]:

Предлагается Федеральный стандарт обработки информации (Federal Information Processing Standard, FIPS) для Стандарта безопасного хэширования (Secure Hash Standard, SHS). Этот предложение определяет Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA) для использования вместе со Стандартом цифровой подписи (Digital Signature Standard) . . .. Кроме того, для приложений, в которых не требуется цифровая подпись, SHA должен использоваться во всех Федеральных приложениях, в которых понадобится алгоритм безопасного хэширования.

Этот Стандарт определяет Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA), необходимый для обеспечения безопасности Алгоритма цифровой подписи (Digital Signature Algorithm, DSA). Для любого входного сообщения длиной меньше 2⁶⁴ битов SHA выдает 160-битовый результат, называемый кратким содержанием сообщения. Далее, краткое содержание сообщения становится входом DSA, который вычисляет подпись для сообщения. Подписывание краткого содержания вместо всего сообщения часто повышает эффективность процесса, так как краткое содержание сообщения намного меньше, чем само сообщение. То же краткое содержание сообщения должно быть получено тем, кто проверяет подпись, если принятая им версия сообщения используется в качестве входа SHA. SHA называется безопасным, так как он разработан так, чтобы было вычислительно невозможно найти сообщение, соответствующее данному краткому содержанию сообщения или найти два различных сообщения с одинаковым кратким содержанием сообщения. Любые изменения, произошедшие при передаче сообщения, с очень высокой вероятностью приведут к изменению краткого содержания сообщения, и подпись не пройдет проверку. Принципы, лежащие в основе SHA, аналогичны использованным профессором Рональдом Л. Ривестом из MIT при проектировании алгоритма краткого содержания сообщения MD4 [1319]. SHA разработан по образцу упомянутого алгоритма.

SHA выдает 160-битовое хэш-значение, более длинное, чем у MD5.

Описание SHA

Во первых, сообщение дополняется, чтобы его длина была кратной 512 битам. Используется то же дополнение, что и в MD5: сначала добавляется 1, а затем нули так, чтобы длина полученного сообщения была на 64 бита меньше числа, кратного 512, а затем добавляется 64-битовое представление длины оригинального сообщения.

Инициализируются пять 32-битовых переменных (в MD5 используется четыре переменных, но рассматриваемый алгоритм должен выдавать 160-битовое хэш-значение):

A = 0x67452301

B = 0xefcdab89

C= 0x98badcfe

D= 0x10325476

E = 0xc3d2e1fO

Затем начинается главный цикл алгоритма. Он обрабатывает сообщение 512-битовыми блоками и продолжается, пока не исчерпаются все блоки сообщения.

Сначала пять переменных копируются в другие переменные: Aв a, B в b, C в c, D в d и E в e.

Главный цикл состоит из четырех этапов по 20 операций в каждом (в MD5 четыре этапа по 16 операций в каждом). Каждая операция представляет собой нелинейную функцию над тремя из a, b, c, d и e, а затем выполняет сдвиг и сложение аналогично MD5. В SHA используется следующий набор нелинейных функций:

f_t(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z) , для t=0 до 19

f_t(X,Y,Z) = XÅ Y Å Z , для t=20 до 39

f_t(X,Y,Z) = (X Ù Y) Ú(X Ù Z) Ú (Y Ù Z) , для t=40 до 59

f_t(X,Y,Z) = XÅ Y Å Z , для t=60 до 79

в алгоритме используются следующие четыре константы:

K_t = 0x5a827999, для t=0 до 19

K_t = 0x6ed9eba1 , для t=20 до 39

K_t = 0x8flbbcdc, для t=40 до 59

K_t = 0xca62c1d6, для t=60 до 79

(Если интересно, как получены эти числа, то:0x5a827999 = 2^1/2/4, 0x6ed9eba1 = 3^1/2/4, 0x8flbbcdc = 5^1/2/4, 0xca62c1d6 = 10^1/2/4.)

Блок сообщения превращается из 16 32-битовых слов (M₀по M₁₅) в 80 32-битовых слов (W₀ по W₇₉) с помощью следующего алгоритма:

W_t= M_t, для t = 0 по 15

W_t=(W_t_-3 Å W_t_-8 Å W_t_-14 Å W_t_-16) <<<1, для t= 16 по 79

(В качестве интересного замечания, в первоначальной спецификации SHA не было циклического сдвига влево. Изменение "исправляет технический изъян, который делал стандарт менее безопасным, чем предполагалось" 1543]. NSA отказалось уточнить истинную причину изъяна.)

Если t - это номер операции (от 1 до 80), W_tпредставляет собой t-ый подблок расширенного сообщения, а <<<s- это циклический сдвиг влево на s битов, то главный цикл выглядит следующим образом:

FOR t= 0 to 79

TEMP= (a <<<5) + f_t(b,c,d)+ e+ W_t+ K_t

e= d

d=c

c= b <<<30

b= a

a= TEMP

На Рис. 18-7 показана одна операция. Сдвиг переменных выполняет ту же функцию, которую в MD5 выполняет использование в различных местах различных переменных.

Рис. 18-7. Одна операция SHA.

После всего этого a, b, c, d и e добавляются к A, B, C D и E, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C D и E.

Безопасность SHA

SHA очень похожа на MD4, но выдает 160-битовое хэш-значение. Главным изменением является введение расширяющего преобразования и добавление выхода предыдущего шага в следующий с целью получения более быстрого лавинного эффекта. Рон Ривест опубликовал цели, преследуемые им при проектировании MD5, но разработчики SHA этого не сделали. Вот улучшения, внесенные Ривестом в MD5 относительно MD4, и их сравнение с SHA:

1. "Добавился четвертый этап." В SHA тоже. Однако в SHA на четвертом этапе используется та же функция f, что и на втором этапе.

2. "Теперь в каждом действии используется уникальная прибавляемая константа." SHA придерживается схемы MD4, повторно используя константы для каждой группы их 20 этапов.

3. "Функция G на этапе 2 с ((XÙY)Ú(XÙZ)Ú(YÙZ)) была изменена на (XÙZ)Ú(YÙ(ØZ)), чтобы сделать G менее симметричной." В SHA используется версия функции из MD4: (X Ù Y) Ú(X Ù Z) Ú (Y Ù Z).

4. "Теперь каждое действие добавляется к результату предыдущего этапа. Это обеспечивает более быстрый лавинный эффект." Это изменение было внесено и в SHA. Отличие состоит в том, что в SHA добавлена пятая переменная к b, c и d, которые уже используются в f_t. Это незначительное изменение делает применения вскрытия MD5 ден Боером и Босселаерсом невозможным по отношению к SHA.

5. "Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3, чтобы сделать шаблоны менее похожими." SHA в этом месте совершенно отличается, так как использует циклический код исправления ошибок.

6. "Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для ускорения лавинного эффекта. Четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на других этапах." SHA на каждом этапе использует постоянное значение сдвига. Это значение - взаимно простое число с размером слова, как и в MD4.

Это приводит к следующему заключению: SHA - это MD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. MD5 - это MD4 с улучшенным битовым хэшированием, дополнительным этапом и улучшенным лавинным эффектом.

Сведения об успешных криптографических вскрытиях SHA отсутствуют. Так как эта однонаправленная хэш-функция выдает 160-хэш-значение, она устойчивее к вскрытию грубой силой (включая вскрытие методом дня рождения), чем 128-битовые хэш-функции, рассматриваемые в этой главе.

RIPE-MD

RIPE-MD была разработана для проекта RIPE Европейского сообщества [1305] (см. раздел 25.7). Этот алгоритм представляет собой вариант MD4, разработанный так, чтобы противостоять известным методам криптографического вскрытия, и выдает 128-битовое хэш-значение. Внесены изменения в циклические сдвиги и порядок слов сообщения. Кроме того, параллельно работают две копии алгоритма, отличающиеся константами. После каждого блока результат обоих копий добавляется к переменным сцепления. По видимому, это повышает устойчивость алгоритма к криптоанализу.

HAVAL

HAVAL - это однонаправленная хэш-функция переменной длины [1646]. Она является модификацией MD5. HAVAL обрабатывает сообщение блоками по 1024 бита, в два раза большими, чем в MD5. Используется восемь 32-битовых переменных сцепления, в два раза больше, чем в MD5, и переменное число этапов, от трех до пяти (в каждом 16 действий). Функция может выдавать хэш-значения длиной 128, 160, 192, 224 или 256 битов.

HAVAL заменяет простые нелинейные функции MD5 на сильно нелинейные функции 7 переменных, каждая из которых удовлетворяет строгому лавинному критерию. На каждом этапе используется одна функция, но при каждом действии входные переменные переставляются различным образом. Используется новый порядок сообщения, и при каждом этапе (кроме первого этапа) используется своя прибавляемая константа. В алгоритме также используется два циклических сдвига.

Ядром алгоритма являются следующие действия:

TEMP= (f(j,A,B,C,D,E,F,G)<<<7)+ (H<<<11) + M[i][r(j)+K(j)]

H= G; G= F; F = E; E = D; D = C; C = B; B = A; A = TEMP

Переменное количество этапов и переменная длина выдаваемого значения означают, что существует 15 версий алгоритма. Вскрытие MD5, выполненное ден Боером и Босселаерсом [203], неприменимо к HAVAL из-за циклического сдвига H.

<86 87 888990 91 92 >

Дата добавления: 2021-01-26; просмотров: 375;