MMB-шифр (MMB-onsj)

Перейти к навигации Перейти к поиску

MMB-шифр (англ. modular multiplication-based block cipher — модульный блочный шифр, использующий умножение) — блочный алгоритм шифрования, основанный на операции умножения в конечной группе.

Общая информация

[править | править код]

Блочный шифр, основанный на операции умножения в конечной группе (MMB) представляет собой блочный шифр, разработанный Йоан Дайменом в 1993 году как улучшение шифра IDEA. Основное новшество этого шифра заключается в использовании циклического умножения в группе Z2n−1. Создатели шифра предлагали сделать n=32, таким образом умножение будет производиться в группе Z4294967295. Также стоит отметить, что длина слов, с которыми будут производиться операции, равна n, то есть 32 в данном случае. Основная цель, которая преследовалась при создании этого шифра — создать шифр, устойчивый к дифференциальному криптоанализу. Недостатки в ключевом расписании были обнаружены Эли Бихамом, что, в комбинации с тем фактом, что шифр не был защищён от линейного криптоанализа, привело к использованию других шифров, например 3-Way шифра.

Описание шифра

[править | править код]

Нелинейность шифра возникает из-за операции умножения по модулю 232−1 (следует из названия шифра). Шифр состоит из шести раундов. Вектор инициализации и финальный шаг в данном шифре не используются. Размер ключа и блока в MMB равен 128 битам. Блок и ключ разделены на 4 32-битовых слова каждый x0, x1, x2, x3 и k0, k1, k2, k3 соответственно. В каждом раунде выполняются 4 преобразования над этими словами: σ[kj], γ, η, и θ над этими словами. Операции σ[kj], η, и θ — это инволюции.

Преобразование σ[kj]

[править | править код]

σ[kj]: это преобразование добавляет ключ к тексту. Оно выполняет операцию XOR между частью ключа и сообщением следующим образом: σ[kj](x0, x1, x2, x3) = (x0 ⊕ kj0, x1 ⊕ kj1, x2 ⊕ kj2, x3 ⊕ kj3), где ⊕ обозначает исключающую-или операцию, а j обозначает номер раунда. Данное преобразование выполняется 7 раз, по одному разу в раунд и еще один раз после последнего раунда.

Преобразование γ

[править | править код]

Преобразование γ производит умножение числа по модулю 232−1. Эта операция умножения — единственная нелинейная операция в этом шифре. В каждом раунде каждое 32-битное слово умножается на фиксированную константу, такую, чтобы результат умножения yi был:

   xi           , если xi  = 232 - 1 
   xi  ⊗ Gi  ,   если xi  ≠ 232  - 1

G1 = 2⊗G0, G2 = 8⊗G0, G3 = 128⊗G0. Таким образом, результатом операции γ является вектор (y0, y1, y2, y3) = γ(x0, x1, x2, x3).

Обратная операция к γ является умножением по модулю шифртекста на Gi−1 следующим образом: xi =

   yi           ,если yi  = 232 - 1 
   yi  ⊗ Gi−1  ,   если yi  ≠ 232  - 1

Для каждого входящего слова γ тривиальное отображение 0 → 0 выполняется с вероятностью 1. Другое интересное свойство, заключается в том, что отображение FFFFFFFFx → FFFFFFFFx через γ также выполняется с вероятностью 1.

Преобразование η

[править | править код]

Преобразование η зависит от самого левого и самого правового слова в блоке. Если самый левый символ в слове это 1, то выполняется операция XOR между этим словом и заранее определённой константой δ. Таким образом: η(x0, x1, x2, x3) = (x0 ⊕(lsb(x0) • δ), x1, x2, x3 ⊕ (lsb(x3) • δ))

Преобразование θ

[править | править код]

Преобразование θ выполняет перемешивание между словами. Перемешивание выполняется таким образом, что любое изменение в одном из слов влияет на другие слова на выходе. Таким образом: θ(x0, x1, x2, x3) = (x0 ⊕ x1 ⊕ x3, x0 ⊕ x1 ⊕ x2, x1 ⊕ x2 ⊕ x3, x0 ⊕ x2 ⊕ x3).

В результате на j раунде выполняется следующее преобразование блока: ρ[kj](X) =θ(η(γ(σ[kj](X)))) а все описание MMB укладывается в следующую строку: σ[k6](ρ[k5](ρ[k4](ρ[k3](ρ[k2](ρ[k1](ρ[k0](P)))))))

Ключевое расписание

[править | править код]

Изначальная версия MMB использовала простой алгоритм ключевого расписания, который заключался в перемещении ключевого слова влево на одну позицию (например (k0, k1, k2, k3) в раунде 0 и (k1, k2, k3, k0) в первом раунде). Такое ключевое расписание циклично и повторяется каждые 4 раунда. Чтобы избежать обнаружения симметричных свойств, в последней версии MMB вдобавок к смещению каждое ключевое слово складывается с константой, величина которой зависит от раунда. Таким образом, ключевое слово i для раунда j: kji = ki+j mod 4 ⊕ (2^j• B), где B — константа.

Атаки на MMB

[править | править код]

Дифференциальный криптоанализ

[править | править код]

Создатели MMB заявляли, что данный шифр стоек к дифференциальному криптоанализу, но существует несколько примеров успешного взлома MMB с использованием данного метода криптоанализа. Основная раундовая функция MMB — функция умножения в группе Z2n−1. Таким образом, для успешной атаки на этот шифр, криптоаналитик должен минимизировать количество активно использующихся перемножений для увеличения качества дифференциальных характеристик. В результате данной атаки, для взлома шифра требуется 2118 шифротекстов, 295,91 операций шифрования MMB и памяти, размером в 264 64-битных блоков.


Одна из атак на основе дифференциального криптоанализа носит название атаки на основе связанных ключей. Израильскими криптоаналитиками Томер Ашуром и Орр Данкелманом было показано, что, используя атаку на основе связанных ключей, имея 219 шифротекстов можно найти 32 из 128 битов ключа за 219,22 операций. Используя другую простую атаку (1R атака), можно узнать другие 32 бита ключа. Оставшиеся биты находятся простым перебором. В результате данная атака требует 235,2 операций, 220 шифртекстов и память размером в 220,3 текстовых блоков.

Был выполнен интегральный криптоанализ четырёхраундового MMB. Для успешной атаки требуется 234 шифротекстов, 2126,32 операций шифрования MMB и память размером в 264 текстовых блоков.

Линейный криптоанализ

[править | править код]

Атака на основе известного открытого текста Используя трёхраундовое приближение, возможно успешно атаковать MMB (получить 128-битный ключ) с 2114,56 открытыми текстами и 2126 трёхраундовыми операциями шифрования.


Атака на основе шифртекста Если открытый текст в формате ASCII, то для атаки на основе шифртекста потребуются только самые значимые биты. Линейное соотношение в данном случае будет 2−45,30 и для успешной атаки на двухраундовый MMB требуется 293,60 шифртекстов.


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

Литература

[править | править код]