GOST_R_34.11-94_Pub (Анализ алгоритмов, использованных в ГОСТ Р 34.11-94 (Функция хэширования))

ГОСТ Р 34.11 – 94. Функция хэширования.Краткий анализШефановский Д.Б.1Май 2001Обозначения∗{01} - множество двоичных строк произвольной конечной длины;n{01} - множество двоичных строк длиной n бит;n{0} - двоичная строка из n нулей;| A | - длина слова A в битах;A ⊕ B - побитное сложение слов A и B по mod 2 , или попросту XOR;A B - сложение слов A и B по mod 2256 ;← оператор присвоения;|| - конкатенация;GF ( 2) - поле Галуа характеристики 2.ВведениеКриптографические хэш функции играют фундаментальную роль в современнойкриптографии. Говоря в общем хэш функция h отображает двоичные строкипроизвольной конечной длины в выходы небольшой (например, 64, 128, 160,192, 224, 256,384, 512) фиксированной длины называемые хэш величинами за полиномиальное время:∗nh : {01} → {01} ,∗iгде {01} ∈ ∪ i∈ {01} (в ГОСТ Р 34.11 – 94 n = 256 ).

Основная идея криптографическихфункций состоит в том, чтобы хэш величины служили как компактный репрезентативныйобраз входной двоичной строки, и их можно использовать как если бы они однозначноотождествлялись с этой строкой, хотя для области определения D и области значений Rс DR (имеются ввиду мощности множеств), функция типа “множество – один”подразумевает, что существование столкновений (пары входов с одинаковым выходом)неизбежно.

Область применения хэш функции четко не оговорена: используется “дляреализации процедур электронной цифровой подписи (ЭЦП), при передаче, обработке ихранении информации в автоматизированных системах”.Сообщения с произвольной длины можно сжать используя хэш функцию сфиксированным размером входа при помощи двух методов:− последовательного (итерационного);1Учебный центр «ИНФОРМЗАЩИТА» 127018, г. Москва, ул. Образцова, 38 а/я 55(095) 289-4232, 289-8998, 289-3162, 219-3188shefanovski@infosec.ru− параллельного.Создатели ГОСТ Р 34.11 – 94 пошли по первому пути и использовали методпоследовательного хэширования использующий хэш функцию с фиксированным2nnразмером входа h : {01} → {01} (см.

Рис. 1), то есть функцию сжатия с коэффициентом2.m1IVHmlm2h1Hh2hl−1HhитогРис. 1 Метод последовательного хэшированияЕсли необходимо хэшировать сообщение m = ( m1 , m2 ,…, ml ) , то хэшированиевыполняется следующим образом:h0 ← IV ,hi ← H (mi , hi−1 ) , для i = 1, 2,…, lhитог ← hl .Здесь H i - функция сжатия, а hi - переменная сцепления.Если последний блок меньше чем n бит, то он набивается одним из существующихметодов до достижения длины кратной n . В отличие от стандартных предпосылок, чтосообщение разбито на блоки и произведена набивка последнего блока (форматированиевхода априори), если необходимо, до начала хэширования, то в ГОСТ Р 34.11 – 94процедура хэширования ожидает конца сообщения (форматирование входного сообщенияпостериори).

Набивка производится следующим образом: последний блок сдвигаетсявправо, а затем набивается нулями до достижения длины в 256 бит.На первый взгляд алгоритм хэширования по ГОСТ Р 34.11 – 94 можно классифицироватькак устойчивый к столкновениям ( n = 256 , следовательно атака по парадоксу днейрождения потребует приблизительно 2256 / 2 операций хэширования) код выявляющиймодификации (Collision Resistant Hash Function, CRHF), см. Замечание 4.

Нельзя забывать,что хэш функцию по ГОСТ Р 34.11 – 94 можно легко преобразовать в код аутентификациисообщения любым известным методом (например, HMAC [1], методом секретногопрефикса, суффикса, оболочки и т.д.). Однако конструкторы предусмотрелидополнительные меры защиты: параллельно рассчитываются контрольная суммапредставляющая собой сумму всех блоков сообщения (последний суммируется уженабитым) по правилу A + B mod 2 k , где k =| A |=| B | , а | A | и | B | битовые длины слов Aи B (далее на рисунках и в тексте эту операцию будем обозначать значком ⊗ ), и битоваядлина хэшируемого сообщения приводимая по mod 2256 (MD - усиление), которые вфинальной функции сжатия используются для вычисления итогового хэша (см.

Рис. 2).Учебный центр “Информзащита”2m1m2h1H*IV...h2H*256Σ1Σ2...256L1L2...{0}{0}(256)10(256)10mlФункция сжатияфинальной итерациинабивка... hl −1... Σ...H*H*hитогH*l−1Ll−1| ml |Рис. 2 Общая схема функции хэширования по ГОСТ Р 34.11 – 94Замечание 1 (набивка) Указывать в передаваемом сообщении сколько было добавленонулей к последнему блоку не требуется, так как длина сообщения участвует вхэшировании.| ml |256m1m2...ml−1ml00...0256−|ml |{0}Рис. 3 Набивка сообщенияЗамечание 2 (начальный вектор IV ) Согласно ГОСТ Р 34.11 – 94 IV - произвольное256фиксированное слово длиной 256 бит ( IV ∈ {01} ).

В таком случае, если он априорно неизвестен верифицирующему целостность сообщения, то он должен передаваться вместе ссообщением с гарантией целостности. При небольших сообщениях можно усложнитьзадачу противнику, если IV выбирается из небольшого множества допустимых величин(но при этом увеличивается вероятность угадывания хэш величины противником). Такжеон может задаваться в рамках организации, домена как константа (обычно как в тестовомпримере).Учебный центр “Информзащита”3Детальное рассмотрение1. Функция сжатия внутренних итераций (по ГОСТ “шаговая функцияхэширования”)Функция сжатия внутренних итераций χ отображает два слова длиной 256 бит в однослово длиной 256 бит:χ : {01}256 × {01}256 → {01}256 ,и состоит из трех процедур (см. Рис. 4):− Перемешивающего преобразования (по существу модифицированной схемыФейстеля),− Шифрующего преобразования;− Генерирования ключей.mi256H*перемешивающеепреобразованиеhi−1hiχ (hi−1 , mi , si )256256siшифрующеепреобразование,генерированиеключейРис.

4 Структура функции сжатия в ГОСТ Р 34.11 – 94а) Перемешивающее преобразованиеЗдесь использована модифицированная для хэширования перестановка Фейстеля, где n битный вход разделяется на k блоков по r бит, так чтобы kl = n :rrrrFp : {01} × ×{01} → {01} × ×{01} ,llnгде p - входное сообщение. Пусть вход A = ( A1 , …, Al ) ∈ {01} , а выходnB = ( B1 , …, Bl ) ∈ {01} , тогда Fp ( A) описывается следующим образом: Bl ← A1 ⊕ f p ( A2 , … , Al ) , Bl−1 ← Al , … , B1 ← A2 .Схематически модифицированная функция Фейстеля представлена на Рис. 5 (безпретензий на общность).Учебный центр “Информзащита”4AlA2A1Fp.........BlBl −1B1Рис. 5 Модифицированная схема Фейстеля для хэшированияПеремешивающее преобразование имеет видhi = χ (mi , hi−1 , si ) = ψ 61 (hi−1 ⊕ ψ (mi ⊕ ψ12 ( si ))) ,где ψ j - j -я степень преобразования ψ .

Схематически данное преобразованиепредставлено на Рис. 6.misiψ12ψψ 61hi−1hiРис. 6 Перемешивающее преобразование ГОСТ Р 34.11 – 94Заметим (см. Рис. 6), что si выводится из hi−1 (см. Рис. 4). Функция256ψ : {01}256→ {01}преобразует слово η16 ||η1 ⊕ η2 ⊕ η3 ⊕ η4 ⊕ η13 ⊕ η16 || η16 || η15 ||Учебный центр “Информзащита”|| η2 (см. Рис. 7).516|| η1 , ηi ∈ {01} , i = 1,16 в словоη16η15η4η3η2η1ψ...η13Рис. 7 Функцияψ перемешивающего преобразованияЗамечание 3 Функция ψ перемешивающего преобразования не удовлетворяетследующим локальным критериям:− 0-1 сбалансированности (гарантирует, что выходы функции будут 0 или 1 свероятностью 0,5 когда вход функции выбирается случайно и равновероятно надвсеми возможными векторами);− большой нелинейности (Функция f называется линейной функцией, если f имеетвид f ( xn , xn−1 , … , x1 ) = an xn ⊕ an−1 xn−1 ⊕ … ⊕ a1 x1 ⊕ a0 , где ai ∈ GF (2) ; Еслиобратить внимание на вид функции ψ , то очевидно, что это линейная функция);− строгому лавинному критерию (Strict Avalanche Criterion, SAC) (говорят, что fудовлетворяет строгому лавинному критерию, если для каждого 1 ≤ i ≤ n,дополнение xi даст в результате выход f являющийся дополнением для 50% всехвозможных входных векторов).Кроме этого в перемешивающем преобразовании применяется только одна функция ψ , аследовательно оно не обладает следующими общими свойствами:− линейной неэквивалентности структуры (две функции f и g линейноэквивалентны по структуре, если f можно преобразовать в g линейнымпреобразованием координат и дополнениями функций, т.е имеется неособеннаяn× n матрица A над GF ( 2) а также вектор B ∈ Vn такой что f ( xA ⊕ B ) = g ( x ) ,или f ( xA ⊕ B) ⊕ 1 = g ( x) , где x = ( xn , xn−1 , … , x1 ) ; этот критерий гарантирует, чтофункции используемые криптографическим алгоритмом не обладают схожестьюструктуры);− взаимной некоррелированности выходов (функции f и взаимно некоррелированыпо выходу, если f , g и f ⊕ g - 0-1 сбалансированные нелинейные функции;гарантирует, что последовательности функций не будут взаимно коррелированныили через линейные функции, или через смещение в выходных битах).Остается вопрос, из каких критериев исходили конструктора?Учебный центр “Информзащита”6б) Подпрограмма генерирования ключейДанная подпрограмма использует следующие функции и константы:− Константы256C2 , C4 = {0} , C3 = 0 xf 0 ff 000 ff 00 f 0 ff 00 f 0 f 0 f 0 ff 0 f 0 f 0 f 0.− Функции256256o P : {01} → {01} .

Пусть X = ξ32 || ξ31 ||P ( X ) = ξϕ(32) || ξϕ(31) ||o256A : {01}|| ξ1 , тогда|| ξϕ(1) , где ϕ (i + 1 + 4 (k −1)) = 8i + k , i = 0,3, k = 1,8.256→ {01} . Пусть X = x4 || x3 || x2 || x1 , тогдаA( X ) = ( x1 ⊕ x2 ) || x4 || x3 || x2 .Алгоритм 1 Подпрограмма генерирования ключей1. U ← mi , V ← hi−1 , W ← U ⊕ V , K1 ← P (W )2.