Как вскрыть шифр, если в нем отсутствует нелинейная часть?

Question

[snovvcrash]

Приветствую!

Помогите разобраться: имеется блочный шифр без нелинейной компоненты. Описать способ вскрытия криптограммы, полученной с помощью такого шифра, если атакующий имеет возможность выбора пар текст-шифртекст.

Answer 1

[Labunsky]

Для начала, известно ли расположение дешифрованной части открытого текста? Если нет - необходимо перебрать все возможные позиции, включая смещение внутри блоков.
После чего, сопоставляешь блоки с открытым текстом и составляешь часть ту часть S-box, что можешь. Используя ее, открываешь дополнительно те блоки криптограммы, что возможно. Далее идет либо перебор оставшейся части таблицы, либо анализ известной части текста и дополнение таблицы с помощью простой аналитики.

Но для этого необходимо знать, какой формат имеет S-box. Потому что не все легко подобрать. Например, таблицы, по типу использующихся в DES, подбирать совсем не просто. Если же имеется использование лишь одной таблицы для прямого преобразования блока "туда и обратно", то задача и правда тривиальна

Comments

[snovvcrash]

Спасибо за ответ, добавил правку в формулировку вопроса. Исходя из этой правки, можете, пожалуйста, подробнее расписать мои действия для восстановления открытого текста?

[Labunsky]

snovvcrash: я правильно понял, размер блока - 8 бит? Если да, то известно ли его разделение (метод) на два 4-битных?
P.S. Не пугай людей странными аналогиями с AES)

[snovvcrash]

Labunsky: В том то и дело, что я не хотел пугать) Дело в том, что в оригинале задача выглядит так: из AES-256 убрали родной Sbox, вставили такой "бесполезный", зашифровали файл размером 100 блоков (12800 бит) в режиме кодовой книги и по 10 известным блокам из 100 требуется вскрыть неизвестную часть файла. Т. е. алгоритм шифрования - это чистый AES-256 только с измененным Sbox'ом (со всеми вытекающими: блок 128 бит, 14 раундов и т. д.)

[Labunsky]

snovvcrash: вот это должно было быть в формулировке)
Сейчас я, честно говоря, не придумаю ничего, особенно с примером. Оригинальный AES с нелинейным S-Box'ом в таких ситуациях ломается простым брутфорсом с использованием однозначного маппинга между ОТ и криптограммой. Очевидно, что без известной таблицы такой вариант невозможен - сначала требуется ее (таблицы) перебор.

Однако, если таблица получена в результате линейной функции, между блоками ОТ и криптограммы должна образовываться зависимость (изменение блока ОТ не приводит к сильному изменению блока криптограммы, Шеннон плачет в углу. Пример - 0x0 -> 0x1, 0x1 -> 0x2 ... 0x9->0x10 - все сразу с таблицей понятно). Без данных на руках особо ничего не сказать не могу (да и с ними не факт, что смогу), но посмотреть стоит. Найдя данную зависимость, можно восстановить таблицу аналитически, не применяя ее брутфорс (или применяя его для восстановления лишь части, что куда реальнее). Далее, так как она линейная, то можно прогнать процесс шифрования "в обратку", для известного блока, получив ключ.

На этом все, что сейчас могу сейчас сказать на ночь, дополнительную инфу можно нагуглить по запросу "aes ecb known plaintext attack"

[snovvcrash]

Labunsky: Понял, спасибо. Дальше буду пробовать сам :)

[Labunsky]

snovvcrash: если захочешь - выложи куда-нибудь, может, тоже на выходных подумаю)