Pertemuan di Tengah & Kompromi Waktu-Memori

Serangan MITM membagi sebuah sandi menjadi dua bagian dan menyerang keduanya secara terpisah. Penyerang membuat tabel dari satu ujung, lalu mencari dari ujung lainnya untuk menemukan kecocokan. Kompleksitas serangan berkurang dari O(2^{2n}) menjadi O(2^n), dengan biaya memori O(2^n).

Double-DES menerapkan DES dua kali: C = DES_{K2}(DES_{K1}(P)). Ruang kunci: 2^{112}. Serangan MITM: untuk semua 2^{56} nilai K1, hitung DES_{K1}(P) dan simpan. Untuk semua 2^{56} nilai K2, hitung DES_{K2}^{-1}(C) dan cari hasilnya di tabel. Kecocokan → kandidat (K1, K2). Total usahanya hanya 2^{57}.

Langkah 1: enkripsi teks terang P dengan semua K1 yang mungkin → tabel T[DES_{K1}(P)] = K1. Langkah 2: untuk setiap K2, dekripsi teks sandi C: v = DES^{-1}_{K2}(C). Periksa apakah v ∈ T. Jika T[v] = K1 ada, verifikasi (K1, K2) pada pasangan teks terang-teks sandi kedua. Diperkirakan ada 1–2 kecocokan palsu; buang kecocokan tersebut.

Triple-DES (3DES) menggunakan tiga kunci K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM tetap berlaku, tetapi dengan efektivitas yang lebih rendah: 3DES dua kunci (K3=K1) memerlukan usaha 2^{112}. Untuk 3DES tiga kunci, terdapat serangan MITM 2^{112}, yang menjelaskan mengapa 3DES hanya memberikan sekitar 112 bit keamanan efektif meskipun memiliki kunci 168-bit.

Hellman (1980): lakukan prapenghitungan tabel rantai (start_point, end_point) untuk mempercepat pencarian kunci secara luring. Dengan nilai pencincangan atau teks sandi target, cari rantai yang memuatnya di tabel Hellman. Pertukarannya: P = N (waktu × memori = konstanta ruang). Inilah dasar tabel pelangi.

Tabel pelangi (Oechslin, 2003) menyempurnakan tabel Hellman dengan menggunakan fungsi reduksi yang berbeda pada setiap posisi rantai, sehingga menghilangkan alarm palsu (rantai yang bergabung). Tabel ini efisien untuk memecahkan nilai pencincangan kata sandi tanpa garam. Satu pencarian memerlukan waktu O(table_size/chain_length).

Garam adalah nilai acak yang ditambahkan di awal kata sandi sebelum pencincangan: H(salt||password). Garam yang berbeda menghasilkan nilai pencincangan yang berbeda untuk kata sandi yang sama — tabel pelangi untuk "password" tidak berguna jika garam yang berbeda digunakan. Garam harus disimpan bersama nilai pencincangan.

Serangan MITM pada AES-128 (10 ronde): serangan yang diketahui membagi pada ronde 5 — mengenkripsi maju selama 5 ronde, mendekripsi mundur selama 5 ronde, lalu bertemu di tengah. Serangan terbaik yang diketahui: serangan biclique mengurangi 2^{128} menjadi 2^{126.1} — tidak praktis, tetapi menunjukkan bahwa AES tidak memiliki margin keamanan terhadap pendekatan bergaya MITM.

Untuk fungsi pencincangan Merkle-Damgard, MITM dapat menemukan prapeta lebih cepat daripada pencarian menyeluruh pada beberapa konstruksi. Serangannya: buat tabel dari blok-blok pesan yang dimulai dari IV; cari mundur dari nilai pencincangan target. Terhadap SHA-256 dengan ronde penuh: masih sekitar 2^{255} — tidak ada peningkatan dibandingkan pencarian menyeluruh.

Serangan diseksi menggeneralisasi MITM menjadi pembagian r-arah. Untuk pembagian sandi menjadi 3 bagian: enkripsi maju selama 1/3 ronde, bertemu di tengah rantai, lalu dekripsi mundur selama 1/3 ronde. Serangan ini memerlukan waktu O(2^{n*2/3}) dan memori O(2^{n/3}) — pertukaran yang lebih seimbang.

Dalam protokol, serangan MITM dapat dicegah dengan: menggunakan kunci panjang yang diturunkan KDF dari kata sandi berentropi tinggi (mengurangi ruang kunci yang dapat dienumerasi), menggunakan token perangkat keras (FIDO2) yang kuncinya tidak pernah meninggalkan perangkat, atau menggunakan autentikasi kunci publik (tidak ada rahasia bersama yang dapat dienumerasi).

Berapa keamanan efektif Double-DES (2x DES, kunci gabungan 112-bit) terhadap serangan MITM?

Serangan MITM membagi sandi menjadi dua bagian, sehingga mengurangi waktu dari 2^{2n} menjadi 2^n dengan memori 2^n. Serangan ini mematahkan Double-DES; 3DES telah mengurangi dampaknya, tetapi memiliki keamanan efektif 112-bit. Tabel pelangi menggunakan logika MITM untuk memecahkan kata sandi — dan dapat dikalahkan dengan pemberian garam. Berikutnya: serangan waktu dan serangan saluran samping.