Pertemuan di Tengah & Pertukaran Masa-Memori

Serangan MITM membahagikan sifir kepada dua bahagian dan menyerangnya secara berasingan. Penyerang membina jadual dari satu hujung, kemudian mencari padanan dari hujung yang satu lagi. Ini mengurangkan kerumitan serangan daripada O(2^{2n}) kepada O(2^n), dengan kos memori O(2^n).

Double-DES menggunakan DES sebanyak dua kali: C = DES_{K2}(DES_{K1}(P)). Ruang kunci: 2^{112}. Serangan MITM: bagi semua 2^{56} nilai K1, kira DES_{K1}(P) dan simpan hasilnya. Bagi semua 2^{56} nilai K2, kira DES_{K2}^{-1}(C) dan cari hasilnya dalam jadual. Padanan → calon (K1, K2). Jumlah usaha hanya 2^{57}.

Langkah 1: sulitkan teks biasa P dengan semua K1 yang mungkin → jadual T[DES_{K1}(P)] = K1. Langkah 2: bagi setiap K2, nyahsulitkan siferteks C: v = DES^{-1}_{K2}(C). Semak sama ada v ∈ T. Jika T[v] = K1 wujud, sahkan (K1, K2) pada pasangan teks biasa-siferteks kedua. Jangkakan 1–2 padanan palsu; buang padanan tersebut.

Triple-DES (3DES) menggunakan tiga kunci K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM masih terpakai tetapi kurang berkesan: 3DES dua kunci (K3=K1) mengurangkan usaha kepada 2^{112}. Bagi 3DES tiga kunci, wujud serangan MITM dengan usaha 2^{112}, yang menjelaskan mengapa 3DES hanya memberikan kira-kira 112 bit keselamatan berkesan walaupun mempunyai kunci 168 bit.

Hellman (1980): pra-kira jadual rantai (start_point, end_point) untuk mempercepatkan carian kunci luar talian. Diberikan cincangan atau siferteks sasaran, cari dalam jadual Hellman rantai yang mengandunginya. Pertukaran: P = N (masa × memori = pemalar ruang). Inilah asas bagi jadual pelangi.

Jadual pelangi (Oechslin, 2003) menambah baik jadual Hellman dengan menggunakan fungsi pengurangan yang berbeza pada setiap kedudukan rantai, lalu menghapuskan amaran palsu (rantai yang bercantum). Jadual ini berkesan untuk memecahkan cincangan kata laluan tanpa garam. Carian mengambil masa O(table_size/chain_length).

Garam ialah nilai rawak yang ditambah di hadapan kata laluan sebelum pencincangan: H(salt||password). Garam yang berbeza menghasilkan cincangan yang berbeza untuk kata laluan yang sama — jadual pelangi untuk "password" tidak berguna jika garam lain digunakan. Garam mesti disimpan bersama cincangan.

Serangan MITM terhadap AES-128 (10 pusingan): serangan yang diketahui membahagikannya pada pusingan 5 — sulitkan ke hadapan sebanyak 5 pusingan, nyahsulitkan ke belakang sebanyak 5 pusingan, lalu bertemu di tengah. Serangan terbaik yang diketahui: serangan biclique mengurangkan 2^{128} kepada 2^{126.1} — tidak praktikal, tetapi menunjukkan bahawa AES tidak mempunyai margin keselamatan terhadap pendekatan gaya MITM.

Bagi cincangan Merkle-Damgard, MITM boleh mencari praimej dengan lebih pantas daripada carian menyeluruh dalam sesetengah binaan. Serangan ini membina jadual daripada blok mesej bermula dari IV, kemudian mencari ke belakang daripada cincangan sasaran. Terhadap SHA-256 dengan pusingan penuh: masih kira-kira 2^{255} — tiada penambahbaikan berbanding carian menyeluruh.

Serangan diseksi menggeneralisasikan MITM kepada pembahagian r-hala. Bagi pembahagian sifir kepada 3 hala: sulitkan ke hadapan sebanyak 1/3 pusingan, bertemu di tengah rantai, kemudian nyahsulitkan ke belakang sebanyak 1/3 pusingan. Serangan ini memerlukan masa O(2^{n*2/3}) dan memori O(2^{n/3}) — pertukaran yang lebih seimbang.

Dalam protokol, serangan MITM boleh dicegah dengan: menggunakan kunci panjang yang diterbitkan oleh KDF daripada kata laluan berentropi tinggi (mengurangkan ruang kunci yang boleh disenaraikan), menggunakan token perkakasan (FIDO2) yang kuncinya tidak pernah meninggalkan peranti, atau menggunakan pengesahan kunci awam (tiada rahsia bersama untuk disenaraikan).

Serangan MITM membahagikan sifir kepada dua bahagian, lalu mengurangkan masa daripada 2^{2n} kepada 2^n dengan memerlukan memori 2^n. Serangan ini memecahkan Double-DES; 3DES mengurangkan kesannya tetapi hanya mempunyai keselamatan berkesan 112 bit. Jadual pelangi menggunakan logik MITM untuk memecahkan kata laluan — dan boleh ditewaskan dengan penggunaan garam. Seterusnya: serangan pemasaan dan serangan saluran sampingan.