MMB-шифр

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

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

Нелинейность шифра возникает из-за операции умножения по модулю 2³²−1 (следует из названия шифра). Шифр состоит из шести раундов. Вектор инициализации и финальный шаг в данном шифре не используются. Размер ключа и блока в MMB равен 128 битам. Блок и ключ разделены на 4 32-битовых слова каждый x₀, x₁, x₂, x₃ и k₀, k₁, k₂, k₃ соответственно. В каждом раунде выполняются 4 преобразования над этими словами: σ[k^j], γ, η, и θ над этими словами. Операции σ[k^j], η, и θ — это инволюции.

σ[k^j]: это преобразование добавляет ключ к тексту. Оно выполняет операцию XOR между частью ключа и сообщением следующим образом: σ[k^j](x₀, x₁, x₂, x₃) = (x₀ ⊕ k^j₀, x₁ ⊕ k^j₁, x₂ ⊕ k^j₂, x₃ ⊕ k^j₃), где ⊕ обозначает исключающую-или операцию, а j обозначает номер раунда. Данное преобразование выполняется 7 раз, по одному разу в раунд и еще один раз после последнего раунда.

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

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

G₁ = 2⊗G₀, G₂ = 8⊗G₀, G₃ = 128⊗G₀. Таким образом, результатом операции γ является вектор (y₀, y₁, y₂, y₃) = γ(x₀, x₁, x₂, x₃).

Обратная операция к γ является умножением по модулю шифртекста на G_i⁻¹ следующим образом: x_i =

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

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

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

Преобразование θ выполняет перемешивание между словами. Перемешивание выполняется таким образом, что любое изменение в одном из слов влияет на другие слова на выходе. Таким образом: θ(x₀, x₁, x₂, x₃) = (x₀ ⊕ x₁ ⊕ x₃, x₀ ⊕ x₁ ⊕ x₂, x₁ ⊕ x₂ ⊕ x₃, x₀ ⊕ x₂ ⊕ x₃).

В результате на j раунде выполняется следующее преобразование блока: ρ[k^j](X) =θ(η(γ(σ[k^j](X)))) а все описание MMB укладывается в следующую строку: σ[k⁶](ρ[k⁵](ρ[k⁴](ρ[k³](ρ[k²](ρ[k¹](ρ[k⁰](P)))))))

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

Создатели MMB заявляли, что данный шифр стоек к дифференциальному криптоанализу, но существует несколько примеров успешного взлома MMB с использованием данного метода криптоанализа. Основная раундовая функция MMB — функция умножения в группе Z_2ⁿ−1. Таким образом, для успешной атаки на этот шифр, криптоаналитик должен минимизировать количество активно использующихся перемножений для увеличения качества дифференциальных характеристик. В результате данной атаки, для взлома шифра требуется 2¹¹⁸ шифротекстов, 2^95,91 операций шифрования MMB и памяти, размером в 2⁶⁴ 64-битных блоков.

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

Был выполнен интегральный криптоанализ четырёхраундового MMB. Для успешной атаки требуется 2³⁴ шифротекстов, 2^126,32 операций шифрования MMB и память размером в 2⁶⁴ текстовых блоков.

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

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

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

• Книга, содержащая криптоанализ полного шестираундового MMB (англ.).

• Страница с ссылками на статьи по криптоанализу. Статья, посвященная атаке на основе связанных ключей на MMB находится под номером c54 (англ.). Дата обращения: 18 декабря 2014. Архивировано из оригинала 18 декабря 2014 года.
• Презентация, содержащая описание различных атак на MMB, была представлена в Канаде в 2009 (англ.). (недоступная ссылка)
• Статья, описывающая различные дифференциальные атаки на MMB (англ.). Архивировано из оригинала 20 апреля 2015 года.

Для улучшения этой статьи желательно: Оформить список литературы. Проставить сноски, внести более точные указания на источники. Оформить статью по правилам. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.