Криптоанализ ГОСТ 34.11-2012

Криптоанализ ГОСТ-Р 34.11-2012

ГОСТ Р 34.11-2012

ГОСТ Р 34.11-2012 (неофициальное название — Стрибог) — российский криптографический стандарт на хеш-функцию, введенный 1 января 2013 года вместо устаревшего ГОСТ Р 34.11-94.

Данная хеш-функция основана на схеме Меркеля-Дамгарда.

Для хеширования данные разбиваются на блоки размером 512 бит, при необходимости блок дополняется вектором <math>(0..01)</math> такой длины, чтобы размер блока стал равным 512 бит.

Затем для каждого блока итеративно применяется функция сжатия. После этого проводится ещё две итерации — для длины входного сообщения и для контрольной суммы всех блоков, из которых состояло сообщение.

Значение функции сжатия на каждом шаге зависит от значения этой функции на предыдущем шаге, что делает принципиально невозможной параллельную обработку блоков сообщения.

Выходные данные представляют собой последовательность длиной 512 или 256 бит.

Функция сжатия

В основу функции сжатия положен 12-раундовый AES-подобный шифр (соответствие было показано, например, в работе А.Казимирова и В.Казимировой). Важной частью функции сжатия является XSPL-преобразование, являющееся композицией четырёх функций:

1. X — операция сложения по модулю 2 с раундовым ключом или раундовой константой (в зависимости от того, получаем ли мы шифр блока сообщения или получаем раундовый ключ)
2. S — нелинейная замена каждого байта блока некоторым другим по стандартной таблице подстановок.
3. P — перестановка байтов блока по определенному стандартом порядку.
4. L — линейное преобразование, эквивалентное умножению восьми 64-битных векторов на определенную стандартом матрицу.

В работе утверждается, что с помощью приведения функции сжатия к AES-подобному виду, можно показать устойчивость функции сжатия и, соответственно, всей хеш-функции к атакам, основанным на методах дифференциального и линейного криптоанализа. Однако, вместо операции ShiftRows, характерной для структур, основанных на AES, используется линейное преобразование — матричная перестановка. И, хотя с момента разработки и введения стандарта прошло не так много времени, уже появилось несколько работ, показывающих, что такое решение, вероятно, приводит к большей уязвимости.

Атака рикошетом

Данная [en.wikipedia.org/wiki/Rebound_attack атака] (англ. Rebound Attack) была представлена в 2009 году Менделем в качестве атаки на хеш-функции, основанные на AES-подобных шифрах, такие, как Whirlpool и Grøstl, является статистической.

В этой атаке криптографический примитив E делится на три части: <math>E = E_{fw} \circ E_{in} \circ E_{bw}</math>, а сама атака состоит из двух частей: внутренней фазы (inbound phase) и внешней (outbound phase).

Внутренняя фаза

Данная часть (иногда называющаяся match-in-the-middle phase — «совпадение посередине») начинается с нескольких выбранных входных/выходных разностей для E_in, которые затем подвергаются линейным преобразованиям в прямом и обратном направлениях. Под разностями (реже употребляется термин «дифференциалы») здесь понимается результат операции сложения по модулю 2. На основе этого генерируются всевозможные пары значений, которые удовлетворяют выбранным значениям разностей. Эти значения являются «начальными данными» для следующей части.

Внешняя фаза

Данные, полученные на предыдущем шаге, «продвигаются» в прямом и обратном направлениях (преобразования E_fw и E_bw), после чего ищутся совпадения для поиска коллизий или «близких коллизий» (англ. near-collision).

Функция сжатия «ГОСТ Р»

В работе показано построение атаки, выявляющей коллизию, на усеченную функцию сжатия с 4.5, 5.5, 7.5 и 9.5 раундами. <math>i</math>-ым раундом называется последовательность преобразований <math> X[k_{i+1}] \circ L \circ P \circ S</math>, где <math>k_{i+1}</math> — раундовый ключ, за половину раунда в данных атаках считают последовательность преобразований <math>P \circ S</math>.

Оценка эффективности атак:

Количество раундов	Количество операций / Затраты на память
<math>4.5</math>	<math>2^{64} / 2^{16}</math>
<math>5.5</math>	<math>2^{64} / 2^{64}</math>
<math>7.5</math>	<math>2^{128} / 2^{16}</math>
<math>9.5</math>	<math>2^{240} / 2^{16}</math>(<math>2^{176} / 2^{128}</math>)

Далее показан пример построения «атаки рикошетом» для функции сжатия, усеченной до 4.5 раундов.

Атака на 4.5 раундовую функцию сжатия «ГОСТ Р»

Предлагается следующий способ разбиения на внутреннюю и внешнюю фазы:

Обозначения:

В скобках записаны преобразования X, L, S, P, использующиеся в функции сжатия «Стрибога», они описаны выше.

m — сообщение или его блок, проходящий сквозь функцию сжатия.

R с различными индексами — состояние блока, проходящего сквозь функцию сжатия.

Внутренняя: <math>R^P_2 \longrightarrow ( L \circ X[k_3]) \longrightarrow R_3 \longrightarrow ( S ) \longleftarrow R^S_3 \longleftarrow ( P \circ L ) \longleftarrow R^L_3 </math>

Внешняя: <math>m \longleftarrow ( X[k_1] ) \longleftarrow R_1 \longleftarrow ( S \circ P \circ L \circ X[k_2] ) \longleftarrow R_2 ( S \circ P ) \longleftarrow INBOUND \longrightarrow </math>

<math> \longrightarrow ( X[k_4] \circ S \circ P \circ L \circ X[k_5] ) \longrightarrow R_5 \longrightarrow ( S \circ P ) \longrightarrow R^P_5 \longrightarrow XOR(h_{i-1}) \longrightarrow XOR(m) \longrightarrow h' </math>

Здесь <math>h_{i-1}</math> и <math>h_{i}</math> — т. н. «сцепленная переменная» (chaining variable) — значения функции сжатия для <math>(i-1)</math> и <math>i</math> блоков сообщения соответственно.

Внутренняя фаза

Данный этап начинается с выбора 8-байтовой разности в R₂^P и R₃^L (Здесь под разностями так же подразумевается результат сложения по модулю 2). Далее мы подвергаем эти разности преобразованиям в прямом и обратном направлениях для получения R₃ и R₃^S соответственно. Из свойств L-преобразования следует, что мы получим полностью активное состояние и в R₃, и R₃^S. Далее, с помощью таблицы распределения разностей для S-преобразования (SBox Difference Disrtibution Table) ищутся решения, удовлетворяющие входной/выходной разности из равенства <math>S(x) \oplus S(x \oplus a) = b </math>. В среднем ожидается нахождение одного решения для одной пары разностей (a, b).

Внешняя фаза

Теперь нужно использовать значения, вычисленные на предыдущем шаге, и точно так же провести вычисления в обоих направлениях. Разности при этом проявятся только в первых столбцах состояний R₁ и R₅^p (по 8 байт в каждом).

Функция сжатия работает следующим образом: <math>h' = h \oplus E_{4.5}(k, m) \oplus m</math>. Следовательно, для одинаковых h и k коллизия получится автоматически, если разности m и E(k, m) равны. Вероятность этого равна 2⁻⁶⁴. Поэтому нужно генерировать 2⁶⁴ точек, а хранить только таблицу распределения разностей для S-преобразования(уже упоминавшийся SBox Difference Distribution Table) размером 256х256 байт, так что временная сложность построения коллизии для такой функции составляет 2⁶⁴ при затратах на память в 2¹⁶ байт. В работах и данная атака улучшена и проведена на функции сжатия, усеченной до 5.5, 7.5 и 9.5 раундов.

Интегральный различитель

Вместе с проверкой на устойчивость к дифференциальным атакам так же исследовалась и устойчивость к интегральным атакам. В частности, искался интегральный различитель. Вкратце, интегральным различителем называется атака, позволяющая выяснить, действительно ли в качестве функции сжатия используется функция, вид которой был предположен аналитиком, а не какая-то иная. В работе были получены различители для 6.5 и 7.5 раундов внутренней перестановки и для 7-раундовой функции сжатия. Однако, удалось получить более сильный результат для 10-раундовой функции сжатия. Результат, полученный с помощью атаки на 9.5-раундовую функцию сжатия, используют для функции сжатия, усеченной до 10 раундов. Тогда все разности на входе лежат в пространстве размерности 2⁶⁴, а на выходе — 2¹²⁸ (вследствие свойств преобразований L и P). Таким образом, временная сложность проверки для нашей функции сжатия составляет 2¹⁷⁶ с затратами по памяти в 2¹⁶ байт, или 2¹²⁸ по времени и 2¹²⁸ по памяти, в то время, как для произвольной функции нам придется произвести 2^512-64-128=2³²⁰ вычислений, чтобы получить такое же отображение разностей на входе и на выходе. В работе также описано подробное построение различителя для 9.5-раундовой функции сжатия.

Построение мультиколлизий

k-коллизией называется нахождение k открытых текстов, имеющих одно значение хеш-суммы. Считается, что для идеальной хеш-функции временная сложность поиска обычной (парной) коллизии составляет 2^n/2 (вследствие парадокса «дней рождения»), в то время, как поиск k-коллизии для такой функции составит 2^{n*(k — 1) / k}, что при больших k приведет к 2ⁿ.

Однако, Антуан Жу (Antoine Joux) в работе, посвященной поиску мультиколлизий (k-коллизий при <math> k > 2 </math>) показал оригинальный способ построения мультиколлизий для хеш-функций, основанных на итеративной функции сжатия, за меньшее, чем 2^n*(k-1)/k время.

В своей работе он исходил из того, что криптоаналитику уже известен способ найти парную коллизию, то есть, у него есть доступ к некоторой функции C, которая получает на вход значение «сцепленной переменной» h и генерирует два блока — B и B' такие, что <math>f(h, B) = f(h, B')</math>, где f — функция сжатия.

Далее, покажем, что за два обращения к этой функции мы можем получить 4-коллизию:

1. Положим <math>h_0 = \mathrm{IV}</math> (Initial Value — начальное значение, определенное либо стандартом хеш-функции, либо её реализацией) и получим <math> (B_0, B'_0) = C(h_0) </math>. Исходя из свойств С: <math>f(IV, B_0) = f(IV, B'_0)</math>
2. Обозначим <math>f(IV, B_0) = h_1</math>, и с помощью функции C найдем блоки <math> (B_1, B'_1) = C(h_1) </math>.

Отсюда получаем: <math>f(h_1, B_1) = f(h_1, B'_1) = </math>

<math>= f(f(IV, B_0), B_1) = f(f(IV, B'_0), B_1) = f(f(IV, B_0), B'_1) = f(f(IV, B'_0), B'_1)</math>

Следовательно, мы получили 4 сообщения <math>B_0|B_1, B'_0|B_1, B_0|B'_1, B'_0|B'_1</math>, имеющих одинаковую хеш-сумму. Аналогично мы можем показать, что за t обращений к функции С получается 2^t коллизий.

Считая, что поиск одной парной коллизии (иначе говоря, время работы функции С) есть <math>2^{n/2}</math>, получаем, что за <math>t*2^{n/2}</math> можно сгенерировать <math>2^t</math> сообщений, дающих одно значение хеш-суммы.

Этот способ был взят за основу в работе. Авторы показали, что данная атака применима и к функции сжатия «ГОСТ Р», и она позволяет найти k-коллизии для сообщений длиной в <math>t</math> блоков, где <math> 176 < t < 2^{256} </math> за <math> 2^{(\log_2t + 256 ) * (k-1)/k} </math> операций.

См. также

• Атака «дней рождения»
• ГОСТ Р 34.11-2012
• Криптоанализ ГОСТа 28147-89

Отрывок, характеризующий Криптоанализ ГОСТ 34.11-2012

Он чувствовал, что от одного слова этого человека зависело то, чтобы вся громада эта (и он, связанный с ней, – ничтожная песчинка) пошла бы в огонь и в воду, на преступление, на смерть или на величайшее геройство, и потому то он не мог не трепетать и не замирать при виде этого приближающегося слова.
– Урра! Урра! Урра! – гремело со всех сторон, и один полк за другим принимал государя звуками генерал марша; потом Урра!… генерал марш и опять Урра! и Урра!! которые, всё усиливаясь и прибывая, сливались в оглушительный гул.
Пока не подъезжал еще государь, каждый полк в своей безмолвности и неподвижности казался безжизненным телом; только сравнивался с ним государь, полк оживлялся и гремел, присоединяясь к реву всей той линии, которую уже проехал государь. При страшном, оглушительном звуке этих голосов, посреди масс войска, неподвижных, как бы окаменевших в своих четвероугольниках, небрежно, но симметрично и, главное, свободно двигались сотни всадников свиты и впереди их два человека – императоры. На них то безраздельно было сосредоточено сдержанно страстное внимание всей этой массы людей.
Красивый, молодой император Александр, в конно гвардейском мундире, в треугольной шляпе, надетой с поля, своим приятным лицом и звучным, негромким голосом привлекал всю силу внимания.
Ростов стоял недалеко от трубачей и издалека своими зоркими глазами узнал государя и следил за его приближением. Когда государь приблизился на расстояние 20 ти шагов и Николай ясно, до всех подробностей, рассмотрел прекрасное, молодое и счастливое лицо императора, он испытал чувство нежности и восторга, подобного которому он еще не испытывал. Всё – всякая черта, всякое движение – казалось ему прелестно в государе.
Остановившись против Павлоградского полка, государь сказал что то по французски австрийскому императору и улыбнулся.
Увидав эту улыбку, Ростов сам невольно начал улыбаться и почувствовал еще сильнейший прилив любви к своему государю. Ему хотелось выказать чем нибудь свою любовь к государю. Он знал, что это невозможно, и ему хотелось плакать.
Государь вызвал полкового командира и сказал ему несколько слов.
«Боже мой! что бы со мной было, ежели бы ко мне обратился государь! – думал Ростов: – я бы умер от счастия».
Государь обратился и к офицерам:
– Всех, господа (каждое слово слышалось Ростову, как звук с неба), благодарю от всей души.
Как бы счастлив был Ростов, ежели бы мог теперь умереть за своего царя!
– Вы заслужили георгиевские знамена и будете их достойны.
«Только умереть, умереть за него!» думал Ростов.
Государь еще сказал что то, чего не расслышал Ростов, и солдаты, надсаживая свои груди, закричали: Урра! Ростов закричал тоже, пригнувшись к седлу, что было его сил, желая повредить себе этим криком, только чтобы выразить вполне свой восторг к государю.
Государь постоял несколько секунд против гусар, как будто он был в нерешимости.
«Как мог быть в нерешимости государь?» подумал Ростов, а потом даже и эта нерешительность показалась Ростову величественной и обворожительной, как и всё, что делал государь.
Нерешительность государя продолжалась одно мгновение. Нога государя, с узким, острым носком сапога, как носили в то время, дотронулась до паха энглизированной гнедой кобылы, на которой он ехал; рука государя в белой перчатке подобрала поводья, он тронулся, сопутствуемый беспорядочно заколыхавшимся морем адъютантов. Дальше и дальше отъезжал он, останавливаясь у других полков, и, наконец, только белый плюмаж его виднелся Ростову из за свиты, окружавшей императоров.
В числе господ свиты Ростов заметил и Болконского, лениво и распущенно сидящего на лошади. Ростову вспомнилась его вчерашняя ссора с ним и представился вопрос, следует – или не следует вызывать его. «Разумеется, не следует, – подумал теперь Ростов… – И стоит ли думать и говорить про это в такую минуту, как теперь? В минуту такого чувства любви, восторга и самоотвержения, что значат все наши ссоры и обиды!? Я всех люблю, всем прощаю теперь», думал Ростов.
Когда государь объехал почти все полки, войска стали проходить мимо его церемониальным маршем, и Ростов на вновь купленном у Денисова Бедуине проехал в замке своего эскадрона, т. е. один и совершенно на виду перед государем.
Не доезжая государя, Ростов, отличный ездок, два раза всадил шпоры своему Бедуину и довел его счастливо до того бешеного аллюра рыси, которою хаживал разгоряченный Бедуин. Подогнув пенящуюся морду к груди, отделив хвост и как будто летя на воздухе и не касаясь до земли, грациозно и высоко вскидывая и переменяя ноги, Бедуин, тоже чувствовавший на себе взгляд государя, прошел превосходно.
Сам Ростов, завалив назад ноги и подобрав живот и чувствуя себя одним куском с лошадью, с нахмуренным, но блаженным лицом, чортом , как говорил Денисов, проехал мимо государя.
– Молодцы павлоградцы! – проговорил государь.
«Боже мой! Как бы я счастлив был, если бы он велел мне сейчас броситься в огонь», подумал Ростов.
Когда смотр кончился, офицеры, вновь пришедшие и Кутузовские, стали сходиться группами и начали разговоры о наградах, об австрийцах и их мундирах, об их фронте, о Бонапарте и о том, как ему плохо придется теперь, особенно когда подойдет еще корпус Эссена, и Пруссия примет нашу сторону.
Но более всего во всех кружках говорили о государе Александре, передавали каждое его слово, движение и восторгались им.
Все только одного желали: под предводительством государя скорее итти против неприятеля. Под командою самого государя нельзя было не победить кого бы то ни было, так думали после смотра Ростов и большинство офицеров.
Все после смотра были уверены в победе больше, чем бы могли быть после двух выигранных сражений.


На другой день после смотра Борис, одевшись в лучший мундир и напутствуемый пожеланиями успеха от своего товарища Берга, поехал в Ольмюц к Болконскому, желая воспользоваться его лаской и устроить себе наилучшее положение, в особенности положение адъютанта при важном лице, казавшееся ему особенно заманчивым в армии. «Хорошо Ростову, которому отец присылает по 10 ти тысяч, рассуждать о том, как он никому не хочет кланяться и ни к кому не пойдет в лакеи; но мне, ничего не имеющему, кроме своей головы, надо сделать свою карьеру и не упускать случаев, а пользоваться ими».
В Ольмюце он не застал в этот день князя Андрея. Но вид Ольмюца, где стояла главная квартира, дипломатический корпус и жили оба императора с своими свитами – придворных, приближенных, только больше усилил его желание принадлежать к этому верховному миру.
Он никого не знал, и, несмотря на его щегольской гвардейский мундир, все эти высшие люди, сновавшие по улицам, в щегольских экипажах, плюмажах, лентах и орденах, придворные и военные, казалось, стояли так неизмеримо выше его, гвардейского офицерика, что не только не хотели, но и не могли признать его существование. В помещении главнокомандующего Кутузова, где он спросил Болконского, все эти адъютанты и даже денщики смотрели на него так, как будто желали внушить ему, что таких, как он, офицеров очень много сюда шляется и что они все уже очень надоели. Несмотря на это, или скорее вследствие этого, на другой день, 15 числа, он после обеда опять поехал в Ольмюц и, войдя в дом, занимаемый Кутузовым, спросил Болконского. Князь Андрей был дома, и Бориса провели в большую залу, в которой, вероятно, прежде танцовали, а теперь стояли пять кроватей, разнородная мебель: стол, стулья и клавикорды. Один адъютант, ближе к двери, в персидском халате, сидел за столом и писал. Другой, красный, толстый Несвицкий, лежал на постели, подложив руки под голову, и смеялся с присевшим к нему офицером. Третий играл на клавикордах венский вальс, четвертый лежал на этих клавикордах и подпевал ему. Болконского не было. Никто из этих господ, заметив Бориса, не изменил своего положения. Тот, который писал, и к которому обратился Борис, досадливо обернулся и сказал ему, что Болконский дежурный, и чтобы он шел налево в дверь, в приемную, коли ему нужно видеть его. Борис поблагодарил и пошел в приемную. В приемной было человек десять офицеров и генералов.
В то время, как взошел Борис, князь Андрей, презрительно прищурившись (с тем особенным видом учтивой усталости, которая ясно говорит, что, коли бы не моя обязанность, я бы минуты с вами не стал разговаривать), выслушивал старого русского генерала в орденах, который почти на цыпочках, на вытяжке, с солдатским подобострастным выражением багрового лица что то докладывал князю Андрею.
– Очень хорошо, извольте подождать, – сказал он генералу тем французским выговором по русски, которым он говорил, когда хотел говорить презрительно, и, заметив Бориса, не обращаясь более к генералу (который с мольбою бегал за ним, прося еще что то выслушать), князь Андрей с веселой улыбкой, кивая ему, обратился к Борису.
Борис в эту минуту уже ясно понял то, что он предвидел прежде, именно то, что в армии, кроме той субординации и дисциплины, которая была написана в уставе, и которую знали в полку, и он знал, была другая, более существенная субординация, та, которая заставляла этого затянутого с багровым лицом генерала почтительно дожидаться, в то время как капитан князь Андрей для своего удовольствия находил более удобным разговаривать с прапорщиком Друбецким. Больше чем когда нибудь Борис решился служить впредь не по той писанной в уставе, а по этой неписанной субординации. Он теперь чувствовал, что только вследствие того, что он был рекомендован князю Андрею, он уже стал сразу выше генерала, который в других случаях, во фронте, мог уничтожить его, гвардейского прапорщика. Князь Андрей подошел к нему и взял за руку.
– Очень жаль, что вчера вы не застали меня. Я целый день провозился с немцами. Ездили с Вейротером поверять диспозицию. Как немцы возьмутся за аккуратность – конца нет!
Борис улыбнулся, как будто он понимал то, о чем, как об общеизвестном, намекал князь Андрей. Но он в первый раз слышал и фамилию Вейротера и даже слово диспозиция.
– Ну что, мой милый, всё в адъютанты хотите? Я об вас подумал за это время.
– Да, я думал, – невольно отчего то краснея, сказал Борис, – просить главнокомандующего; к нему было письмо обо мне от князя Курагина; я хотел просить только потому, – прибавил он, как бы извиняясь, что, боюсь, гвардия не будет в деле.