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

   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 с использованием данного метода криптоанализа. Основная раундовая функция 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 шифртекстов.

---

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

Литература

• (англ.) .

Ссылки

• (англ.) . Дата обращения: 18 декабря 2014. Архивировано из 18 декабря 2014 года.
• (англ.) . (недоступная ссылка)
• (англ.) . Архивировано из 20 апреля 2015 года.