GOST_R_34.11-94_Pub (1014209)
Текст из файла
ГОСТ Р 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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
