Введение
Общая криптографическая атака, основанная на компромиссе между временем и объемом памяти, — процесс оптимизации криптоанализа. Атака «встреча посередине» (MITM), являющаяся разновидностью атаки с известным открытым текстом, представляет собой общую криптографическую атаку, основанную на компромиссе между временем и объемом памяти, направленную против схем шифрования, которые полагаются на последовательное выполнение множественных операций шифрования. Атака MITM является основной причиной, по которой Double DES не используется, и почему ключ Triple DES (168 бит) может быть взломан злоумышленником с использованием 2<sup>56</sup> объема памяти и 2<sup>112</sup> операций. Атака MITM пытается найти ключи, используя как область значений (шифротекст), так и область определения (открытый текст) композиции нескольких функций (или блочных шифров) таким образом, чтобы прямое отображение через первые функции совпадало с обратным отображением (прообразом) через последние функции, буквально «встречаясь» в середине составной функции. Например, хотя Double DES шифрует данные с использованием двух различных 56-битных ключей, Double DES может быть взломан с помощью 2<sup>57</sup> операций шифрования и дешифрования. Многомерная MITM (MD MITM) использует комбинацию нескольких одновременных атак MITM, как описано выше, где «встреча» происходит в нескольких позициях в составной функции.
the cryptanalysis optimisation process
The meet in the middle attack (MITM), a known plaintext attack, is a generic space–time tradeoff cryptographic attack against encryption schemes that rely on performing multiple encryption operations in sequence. The MITM attack is the primary reason why Double DES is not used and why a Triple DES key (168 bit) can be brute forced by an attacker with 256 space and 2112 operations. attack. The MITM attack attempts to find the keys by using both the range (ciphertext) and domain (plaintext) of the composition of several functions (or block ciphers) such that the forward mapping through the first functions is the same as the backward mapping (inverse image) through the last functions, quite literally meeting in the middle of the composed function. For example, although Double DES encrypts the data with two different 56 bit keys, Double DES can be broken with 257 encryption and decryption operations. The multidimensional MITM (MD MITM) uses a combination of several simultaneous MITM attacks like described above, where the meeting happens in multiple positions in the composed function.
История
Диффи и Хеллман впервые предложили атаку "встреча в середине" на гипотетическом расширении блочного шифра в 1977 году. Их атака использовала компромисс между пространством и временем, чтобы взломать схему двойного шифрования всего в два раза быстрее, чем требуется для взлома схемы одинарного шифрования. В 2011 году Бо Чжу и Гуан Гонг исследовали многомерную атаку "встреча в середине" и представили новые атаки на блочные шифры GOST, KTANTAN и Hummingbird 2. Triple DES использует ключ "тройной длины" (168 бит) и также уязвим для атаки "встреча в середине", требующей 256 единиц памяти и 2112 операций, но считается безопасным благодаря размеру своего пространства ключей.
Сложность MITM
Если размер ключа равен k, эта атака использует только 2k+1 шифрований (и дешифрований) и O(2k) памяти для хранения результатов прямых вычислений в таблице поиска, в отличие от наивного подхода, которому требуется 22·k шифрований, но O(1) памяти.
Общий пример 2D-MITM
Это общее описание того, как выполняется атака «человек посередине» в двух измерениях (2D MITM) на шифрование блочными шифрами. В двухмерной атаке «человек посередине» (2D MITM) метод заключается в достижении двух промежуточных состояний при многократном шифровании открытого текста. См. рисунок ниже: