MMB-шифр (MMB-onsj)

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]

σ[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 был:

   x_i           , если x_i  = 2³² - 1 
   x_i  ⊗ G_i  ,   если x_i  ≠ 2³²  - 1

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

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

   y_i           ,если y_i  = 2³² - 1 
   y_i  ⊗ G_i⁻¹  ,   если y_i  ≠ 2³²  - 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 с использованием данного метода криптоанализа. Основная раундовая функция 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 года.