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

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

Во первых, сообщение дополняется, чтобы его длина была кратной 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

Блок сообщения превращается из 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

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

 

Рис 3.3. Одна операция SHA

 

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

 

SHA-2

SHA-2 - это семейство криптографических алгоритмов — однонаправленных хеш-функций, включающее в себя алгоритмы SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 и SHA-512/224. Создан и принят как 2002г. Включает в себя SHA-1. Алгоритмически аналогична SHA.

Хотя в ходе атак были показаны уязвимости в форме коллизий. В США допускается его использование для данных БЕЗ грифа секретности.

SHA-256 используется Bitcoint в механизме доказательства выполнения работы, так как SHA-2 работают в 2—3 раза медленнее других популярных хеш-алгоритмов MD5, SHA-1, Tiger и RIPEMD-160. В DataMining BitCoint вовлечены столь значительные специализированные вычислительные средства, что криптостойкость SHA-2 вероятно под сомнением.

 

SHA-3

SHA-3 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта. Построен по принципу криптографической губки.

Алгоритм получения значения хеш-функции можно разделить на несколько этапов:

· Исходное сообщение M {\displaystyle M} M дополняется до строки P {\displaystyle P} P длины, кратной r {\displaystyle r}r, с помощью функции дополнения (pad-функции).

· Строка P {\displaystyle P} M делится на n {\displaystyle n} n блоков длины r {\displaystyle r}r:P 0, P 1,..., P n − 1 {\displaystyle P_{0},P_{1},...,P_{n-1}} P₀,P₁... P_n

· «Впитывание»: каждый блок P i {\displaystyle P_{i}} P_i дополняется нулями до строки длины b {\displaystyle b} b бит и суммируется по модулю 2 со строкой состояния S {\displaystyle S}S, где S {\displaystyle S}S — строка длины b {\displaystyle b} b бит (b {\displaystyle b}b = r {\displaystyle r} r + c {\displaystyle c}c). Перед началом работы функции все элементы S {\displaystyle S} S равны нулю. Для каждого следующего блока состояние — строка, полученная применением функции перестановок f {\displaystyle f} f к результату предыдущего шага.

· «Отжимание»: пока длина Z {\displaystyle Z} Z меньше d {\displaystyle d} d (d {\displaystyle d}d — количество бит в результате хеш-функции), к Z {\displaystyle Z} Z добавляется r первых бит состояния S {\displaystyle S}S, после каждого прибавления к S {\displaystyle S} S применяется функция перестановок f {\displaystyle f}f. Затем S {\displaystyle S} S обрезается до длины d {\displaystyle d} d бит.

· Строка Z {\displaystyle Z} S длины d {\displaystyle d} d бит возвращается в качестве результата

 

ГОСТ Р 34.11‑94

Алгоритм вычисления шаговой хеш-функции включает в себя три части, реализуемые последовательно:

· генерация ключей – слов длиной 256 битов;

o для генерации ключей используется стартовый вектор хеширования, последовательность двоичных символов, подлежащих хешированию и три параметра С₂=С₃=0²⁵⁶, С₄=1⁸0⁸1¹⁶0²⁴1¹⁶0⁸(0⁸1⁸)²1⁸0⁸(0⁸1⁸)⁴(1⁸0⁹)⁴

· шифрующее преобразование – зашифрование 64-битных подслов стартового вектора хеширования (256 бит) на ключах K_i (i=0,..4) с использованием алгоритма по ГОСТ 28147-89 в режиме простой замены;

· перемешивающее преобразование результата хеширования

Хэш-значение последнего блока сообщения не является его окончательным хэш-значением. На деле используется три переменные сцепления: H_n- это хэш-значение последнего блока, Z - это XOR всех блоков сообщения, а L- длина сообщения. С использованием этих переменных и дополненного последнего блока M', окончательное хэш-значение равно:

H = f(Z Å M',f(L,f(M', H_n)))