การโจมตี Meet-in-the-Middle บน Double DES ทำงานอย่างไร?

Double DES และช่องโหว่

Double DES เข้ารหัส 2 รอบ: C = E_{K2}(E_{K1}(P)) กุญแจรวม 112 บิต คาดว่าจะแข็งแกร่ง 2¹¹² แต่...

หลักการ Meet-in-the-Middle (MitM) Attack

แนวคิด: โจมตีจากทั้ง 2 ด้าน พบกันกลาง ลดความซับซ้อนจาก 2¹¹² → ~2⁵⁷

ขั้นตอนการโจมตี

1. โจมตีมี Known Plaintext-Ciphertext Pair (P, C) อย่างน้อย 1 คู่
2. Forward (Encryption): ลองทุกค่า K1 ที่เป็นไปได้ (2⁵⁶ ค่า) คำนวณ M = E_{K1}(P) เก็บคู่ (M, K1) ในตารางแฮช
3. Backward (Decryption): ลองทุกค่า K2 ที่เป็นไปได้ (2⁵⁶ ค่า) คำนวณ M' = D_{K2}(C) ตรวจสอบว่า M' อยู่ในตารางหรือไม่
4. หากพบ M' = M → (K1, K2) เป็นกุญแจที่ถูกต้อง (Candidate)
5. ตรวจสอบด้วยคู่ (P', C') เพิ่มเติม เพื่อกรอง False Positives

การวิเคราะห์ความซับซ้อน

ข้อสังเกตสำคัญ

• MitM เป็นการแลก Time กับ Space (Time-Space Tradeoff)
• ต้องการหน่วยความจำมาก (2⁵⁶ × ~16 ไบต์ ≈ 1 Exabyte) → ยังไม่เป็นไปได้จริงในปัจจุบัน แต่ทฤษฎีแล้วแตกได้
• นี่คือเหตุผลที่ 3DES ใช้ 3 รอบ (E-D-E) ไม่ใช่ 2 รอบ (E-E)
• 3DES 3-key: MitM ลดความแข็งแกร่งจาก 168 → ~112 บิต (ยังปลอดภัย)

การป้องกัน

• ใช้ 3DES (3-key) หรือ AES แทน Double DES
• เพิ่มขนาดบล็อก (AES 128 บิต vs DES 64 บิต)
• ใช้โหมดการทำงานที่เหมาะสม (CBC, CTR, GCM) พร้อม IV/Nonce ที่ไม่ซ้ำ

Triple DES คืออะไร?

การเข้ารหัส IDEA ทำงานอย่างไร?