Linear Cryptanalysis ในความปลอดภัยข้อมูลคืออะไร?

Linear Cryptanalysis คืออะไร?

เป็น Known-plaintext Attack ที่โจมตีศึกษาความสัมพันธ์เชิงเส้นโอกาส (Linear Approximations) ระหว่าง Parity Bits ของ Plaintext, Ciphertext และ Secret Key โจมตีคำนวณ Parity Bits ของ Plaintext และ Ciphertext ที่รู้จัก เพื่อหา Parity Bit ของ Secret Key ด้วยความน่าจะเป็นสูง ใช้ Auxiliary Technique ขยายการโจมตีหาบิตอื่นๆ ของ Key

สองส่วนหลัก

1. สร้างสมการเชิงเส้นเชื่อมโยง Plaintext, Ciphertext, Key Bits ที่มี Bias สูง (ความน่าจะเป็นใกล้ 0 หรือ 1)
2. ใช้สมการเหล่านี้ร่วมกับคู่ Plaintext-Ciphertext ที่รู้จัก เพื่อสรุป Key Bits

หลักการทำงาน

ใช้ Linear Approximation สร้างแบบจำลองกระบวนการ Non-linear ในการเข้ารหัส ใช้ Approximation กับ Known-plaintext จำนวนมาก จะหา Key Bit ได้ถูกต้องด้วยความน่าจะเป็นเฉพาะ สามารถปรับปรุงเพื่อหา Key Bits หลายตัวได้

โจมตี DES: ต้องการ 2⁴³ Known-plaintexts ต่างจาก 2⁴⁷ Chosen-plaintexts ของ Differential Cryptanalysis แม้ดีกว่าเล็กน้อย แต่ Known-plaintext ได้ง่ายกว่า ทำให้ Linear Cryptanalysis เป็นไปได้จริงกว่า

สมการเป้าหมาย

P[α₁,α₂...αₐ] ⊕ C[β₁,β₂...βᵦ] = K[γ₁,γ₂...γᵦ] ที่เกิดขึ้นด้วยความน่าจะเป็น p ≠ 0.5 ยิ่ง p ห่างจาก 0.5 ยิ่งมีประสิทธิภาพ