การโจมตีแบบพบกันตรงกลางและความสมดุลระหว่างเวลาและหน่วยความจำ

การโจมตีแบบ MITM แบ่งรหัสลับออกเป็นสองส่วนแล้วโจมตีแต่ละส่วนอย่างอิสระ ผู้โจมตีสร้างตารางจากปลายด้านหนึ่ง จากนั้นค้นหาจากอีกปลายหนึ่งเพื่อหาค่าที่ตรงกัน การโจมตีนี้ลดความซับซ้อนจาก O(2^{2n}) เหลือ O(2^n) โดยต้องใช้หน่วยความจำ O(2^n)

Double-DES ใช้ DES สองครั้ง: C = DES_{K2}(DES_{K1}(P)) พื้นที่กุญแจมีขนาด 2^{112} การโจมตีแบบ MITM: สำหรับค่า K1 ทั้งหมด 2^{56} ค่า ให้คำนวณ DES_{K1}(P) และจัดเก็บไว้ สำหรับค่า K2 ทั้งหมด 2^{56} ค่า ให้คำนวณ DES_{K2}^{-1}(C) แล้วค้นหาในตาราง หากพบค่าตรงกัน → ได้ตัวเลือก (K1, K2) ใช้ความพยายามรวมเพียง 2^{57}

ขั้นที่ 1: เข้ารหัสข้อความต้นฉบับ P ด้วย K1 ที่เป็นไปได้ทั้งหมด → ตาราง T[DES_{K1}(P)] = K1 ขั้นที่ 2: สำหรับ K2 แต่ละค่า ให้ถอดรหัสข้อความเข้ารหัส C: v = DES^{-1}_{K2}(C) ตรวจสอบว่า v ∈ T หรือไม่ หากมี T[v] = K1 ให้ตรวจสอบ (K1, K2) กับคู่ข้อความต้นฉบับและข้อความเข้ารหัสอีกคู่หนึ่ง โดยคาดว่าจะพบการจับคู่เท็จ 1–2 รายการ ให้ตัดรายการเหล่านั้นทิ้ง

Triple-DES (3DES) ใช้กุญแจสามดอก K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))) ยังคงใช้ MITM ได้ แต่มีประสิทธิผลลดลง: 3DES แบบสองกุญแจ (K3=K1) ลดรูปเป็นการโจมตีที่ใช้ความพยายาม 2^{112} 3DES แบบสามกุญแจมีการโจมตี MITM ที่ใช้ความพยายาม 2^{112} อยู่ จึงอธิบายได้ว่า 3DES ให้ความปลอดภัยที่มีผลจริงเพียงประมาณ 112 บิต แม้จะมีกุญแจขนาด 168 บิต

Hellman (1980): คำนวณตารางสายโซ่ (start_point, end_point) ล่วงหน้าเพื่อเร่งการค้นหากุญแจแบบออฟไลน์ เมื่อมีค่าแฮชหรือข้อความเข้ารหัสเป้าหมาย ให้ค้นหาในตาราง Hellman เพื่อหาสายโซ่ที่มีค่านั้น การแลกเปลี่ยนคือ P = N (เวลา × หน่วยความจำ = ค่าคงที่ของพื้นที่) ซึ่งเป็นพื้นฐานของตารางสายรุ้ง

ตารางสายรุ้ง (Oechslin, 2003) ปรับปรุงตาราง Hellman โดยใช้ฟังก์ชันลดรูปที่แตกต่างกันในแต่ละตำแหน่งของสายโซ่ จึงกำจัดการแจ้งเตือนเท็จจากสายโซ่ที่ถูกรวมกันได้ ตารางนี้มีประสิทธิภาพสำหรับการถอดรหัสค่าแฮชรหัสผ่านที่ไม่ใส่ค่าเกลือ การค้นหาใช้เวลา O(table_size/chain_length)

ค่าเกลือคือค่าสุ่มที่เติมไว้หน้ารหัสผ่านก่อนการแฮช: H(salt||password) ค่าเกลือที่แตกต่างกันจะให้ค่าแฮชที่แตกต่างกันสำหรับรหัสผ่านเดียวกัน ดังนั้นตารางสายรุ้งสำหรับ “รหัสผ่าน” จึงใช้ไม่ได้หากใช้ค่าเกลืออื่น ต้องจัดเก็บค่าเกลือไว้คู่กับค่าแฮช

การโจมตีแบบ MITM ต่อ AES-128 (10 รอบ): การโจมตีที่รู้จักกันดีที่สุดแบ่งที่รอบที่ 5 โดยเข้ารหัสไปข้างหน้า 5 รอบ ถอดรหัสย้อนกลับ 5 รอบ แล้วมาพบกันตรงกลาง การโจมตีที่ดีที่สุดที่รู้จักคือการโจมตีแบบไบคลิก ซึ่งลด 2^{128} เหลือ 2^{126.1} แม้ยังไม่สามารถทำได้จริง แต่แสดงให้เห็นว่า AES ไม่มีส่วนเผื่อความปลอดภัยต่อแนวทางแบบ MITM

สำหรับแฮชแบบ Merkle-Damgard การโจมตีแบบ MITM สามารถค้นหาอินพุตต้นทางได้เร็วกว่าการไล่ลองทุกค่าในโครงสร้างบางแบบ การโจมตีคือสร้างตารางจากบล็อกข้อความโดยเริ่มจาก IV แล้วค้นหาย้อนกลับจากค่าแฮชเป้าหมาย สำหรับ SHA-256 ที่ใช้รอบการทำงานครบทั้งหมดยังคงอยู่ที่ประมาณ 2^{255} ซึ่งไม่ดีขึ้นกว่าการไล่ลองทุกค่า

การโจมตีแบบแยกส่วนขยายแนวคิด MITM ไปสู่การแบ่งออกเป็น r ส่วน สำหรับการแบ่งรหัสลับเป็น 3 ส่วน ให้เข้ารหัสไปข้างหน้า 1/3 ของรอบการทำงาน มาพบกันตรงกลางสายโซ่ แล้วถอดรหัสย้อนกลับ 1/3 ต้องใช้เวลา O(2^{n*2/3}) และหน่วยความจำ O(2^{n/3}) จึงเป็นการแลกเปลี่ยนที่สมดุลกว่า

ในโพรโทคอล สามารถป้องกันการโจมตีแบบ MITM ได้โดยใช้กุญแจยาวที่สร้างจาก KDF และรหัสผ่านที่มีเอนโทรปีสูง (ลดขนาดพื้นที่กุญแจที่สามารถไล่แจกแจงได้) ใช้อุปกรณ์โทเค็นฮาร์ดแวร์ (FIDO2) ซึ่งกุญแจจะไม่ออกจากอุปกรณ์ หรือใช้การยืนยันตัวตนด้วยกุญแจสาธารณะ (ไม่มีข้อมูลลับร่วมกันให้ไล่แจกแจง)

ความปลอดภัยที่มีผลจริงของ Double-DES (DES สองครั้ง กุญแจรวมขนาด 112 บิต) ต่อการโจมตีแบบ MITM คือเท่าใด

การโจมตีแบบ MITM แบ่งรหัสลับออกเป็นสองส่วน ลดเวลาจาก 2^{2n} เหลือ 2^n โดยใช้หน่วยความจำ 2^n การโจมตีนี้ทำลาย Double-DES ได้ ส่วน 3DES มีการบรรเทาผลกระทบ แต่มีความปลอดภัยที่มีผลจริง 112 บิต ตารางสายรุ้งใช้แนวคิด MITM เพื่อถอดรหัสผ่าน และถูกป้องกันได้ด้วยการใส่ค่าเกลือ ถัดไป: การโจมตีด้วยเวลาและการโจมตีช่องทางข้างเคียง