Упрощение ГОСТ 28147-89

L1=L; R1=R

R2=K1^S(R1)^L1
L2=R1

<...>

R9=K8^S(R8)^L8
L9=R8

Дальше подключи раундов повторяются:

R10=K1^S(R9)^L9=K1^S(K8^S(R8)^L8)=K1^S(K8^S(K7^S(R7)^L7)^L8)=K1^S(K8^S(K7^S(R7)^L7)^L8), ну и т.д.
в общем можно подставить и посократить все ключи.

Ключ сократить нельзя, поскольку S-box действует не только на Ri, но и на ключ.

S-блок 4x4 действует на кусок открытого текста, а раз нет смешения операций (XOR + ADD), а действие S-блока не распространяется при помощи циклического сдвига на всю половину сети Файстеля (нет диффузии), то на выходе будет предсказуемое изменение, по крайней мере по разнице двух открытых текстов и шифртекстов подключи восстановить точно можно и вот там действием раундовых подключей можно пренебречь.

Вас не затруднит описать это формулами, а то мне все равно непонятно?... =(

Ну начать можно с этого:

ГОСТ:

R2=(11<<<(S{0...7}(R1+K0(mod2³²)))) ^ L1
L2=R1

Упрощённый ГОСТ:

R2=(S{0...7}(R1 ^ K0)) ^ L1
L2=R1

Так?

Дальше, из-за того что нет смешения с помощью сдвига, то можно рассмотреть изменение при обработке только одним S-блоком при изменении только 4 бит исходного текста, так как изменения не распространяются на соседние блоки.

R2=(S(0)(R1_0 ^ K0_0) || S1(R1_1 ^ K0_1 ) || ... || S7(R1_7 ^ K0_7)) ^ L1

А дальше громоздкие формулы получаются. Но алгоритм должен трививально взламываться.

И каково в данном случае будет изменение стойкости?

Ну смотрите. Из-за того что сдвига нет, то нет распространения изменений битов на соседние S-блоки (диффузии). Из-за того что сложение по модулю заменили на XOR, получаем побитовое воздействие части подключа раунда на часть блока опять же (вместо целого). Даже если не знать значение S-блоков, можно не учитывать вообще их воздействие на каждом раунде и заменить весь алгоритм набором таблиц 4x4, которые находятся подбором открытых текстов.
Стойкость будет зависть от типа атаки (известные, подобраные тексты) и того, какой способ взлома будет применен. Может можно придумать какой-нибудь самый эффективный (по одному известному блоку). Здесь сработает практически любой общий способ или придуманный специально по случаю.

Обычно стойкость оценивается таким способом: 2^{длина ключа}. То есть для ГОСТа 28147-89 можно говорить о 2^256... (как верхней и самой худшей оценке). А как тогда с упрощенным?

Обычно стойкость оценивается таким способом: 2^{длина ключа}.

Это для полного перебора или атак на процедуры работы с ключом (ключевое расписание и т.п.). Для других атак, таких как атаки с подобранными открытыми и шифртекстами и пр., сложность измеряется в иных единицах.

Всё зависит от того, какой способ атаки вы выбрали для вашего примера.

Если работает способ с раздельным перебором таблиц (лень проверять, первое что на ходу придумалось), то перебор каждой таблицы 4x4 бит (т.е. 16!= 20922789888000) при их числе = 8 даст примерно 2⁽⁴⁴⁺³⁾ = 2⁴⁷ бит.

Но это примитивный раздельный перебор (метод divide and conquer), а если применить что-то более серъёзное, с учётом того, что S-блоки известны, то возможно придумать атаку и за несколько подобранных текстов.

На самом деле, я пытаюсь оценить влияние этого упрощения на ГОСТ 34.11-94... просто застопорилась на упрощении и не могу сдвинуться)
Спасибо за помощь)

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

Вообще, есть такой алгоритм 20-раундовый алгоритм GOSTÅ, в раунде которого для наложения ключа используется операция XOR вместо сложения по модулю 2 в 32, т.н. ускоренный ГОСТ (неофициальный)

см. Oreku G. S., Li J., Pazynyuk T., Mtenzi F. J. Modified S-box to Archive Accelerated GOST. // http://paper.ijcsns.org – International Journal of Computer Science and Network Security, VOL. 7 No. 6, June 2007.

Здесь пример явно приведён в качестве какого-то домашнего задания.

Сложение по модулю 2³² и XOR действительно дают дополнительный смешивающий эффект, но даже если убирается циклический сдвиг, то некоторая диффузия изменений битов за счёт совместного применения XOR и сложения ещё бы оставалась, а если уж и сложение заменяется на XOR и сеть Файстеля работает через XOR половинок и цклический сдвиг убирается, то диффузии битов между S-блоками нет.

Шифр больше не представляет собой полноценную PRP (псевдослучайную перестановку), а является набором действующих независимо друг от друга PRP размеров с S-блок.

Это значит, что если разбить входной блок на 4-битные фрагменты P_0 ... P_63, то изменение к примеру во фрагменте P0 или P8 или сразу в двух из них приведёт к изменению только 4-битных фрагментов шифртекста (C0, C8) в блоке.

Простой перебор даёт 8*2^^(4+4) = 2¹⁹ подобранных открытых текстов для независимого поиска всех 4-битных фрагментов PRP. После чего можно читать все тексты без знания ключа.

Можно восстановить и ключ если надо.
Подберём пару (P0, P8) так, чтобы на выходе получилось (C_y, 0). Ноль может получиться, только если значение 4-битового фрагмента левой половины последнего раунда равно выходу S-блока.
теперь мы знаем выход S-блока. Он равен C_y, пропустим это значение через S-блок в обратном порядке и получим значение на входе S-блока. Но значение на входе S-блока в случае отсутствия смешения тоже равно C_y, но поксореное с подключом раунда. Итак, мы можем восстановить 4-ьитный кусок подключа раунда.

Сколько на это потребуется операций? Максимум 2¹⁶, но согласно принципу парадокса дней рождений в среднем 2⁸.

8 * 2⁸ и весь подключ последнего раунда восстановлен. Раз мы знаем последний подключ и полностью контролируем выод последнего раунда, то также можно сделать и с предпоследним и далее подняться до самого первого. итого: 32*8* 2⁸ = 2¹⁶ операций (не считая небольшого числа промежуточных).

Мы уже достаточно упростили ГОСТ? ;-)

итого: 32*8* 28 = 2¹⁶ операций (не считая небольшого числа промежуточных).

Восстанавливать подключи всех 32-ух раундов необязательно из-за особенностей ключевого расписания. Так как они четыре раза повторяются, значит ключ можно восстановить по подключам последних восьми раундов:

8 * 8 * 2⁸ = 2¹²