การวิเคราะห์การเข้ารหัสเชิงเส้นและตารางประมาณค่า

การวิเคราะห์รหัสลับเชิงเส้น (Matsui, 1993) เป็นการโจมตีด้วยข้อความธรรมดาที่ทราบ ซึ่งค้นหาการประมาณค่าเชิงเส้น (XOR ของบิตที่เลือก) ของรหัสลับที่เป็นจริงด้วยความน่าจะเป็น p ≠ 1/2 เมื่อใช้คู่ข้อความธรรมดาและข้อความเข้ารหัสจำนวนมาก ความเอนเอียงทางสถิติจะเปิดเผยบิตของคีย์

การประมาณค่าเชิงเส้นสำหรับกล่อง S: ผลรวมของบิตอินพุตที่เลือก XOR ผลรวมของบิตเอาต์พุตที่เลือก = 0 (mod 2) ด้วยความน่าจะเป็น p เขียนได้เป็น: P[a·x XOR b·y = 0] = 1/2 + ε โดย a,b เป็นมาสก์บิต และ ε คือความเอนเอียง (ต้องการให้ |ε| >> 0)

LAT นับจำนวนอินพุต x ที่ทำให้ (a·x) XOR (b·S(x)) = 0 สำหรับมาสก์อินพุต a และมาสก์เอาต์พุต b แต่ละคู่ ลบ 2^{n-1} เพื่อให้ได้ความเอนเอียง กล่อง S ที่ดีมี |max_bias| = 1 (ความน่าจะเป็น 1/2 ± 1/2^{n/2}) ซึ่งแบนราบสม่ำเสมอมากที่สุด

สำหรับการประมาณค่าเชิงเส้นอิสระที่ผ่านหลายรอบ ความเอนเอียงจะคูณกัน: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r การประมาณค่าในแต่ละรอบทำให้ความเอนเอียงที่มีผลลดลงครึ่งหนึ่ง หลังผ่านหลายรอบ ความเอนเอียงรวมจะเข้าใกล้ 0 ทำให้ต้องใช้คู่ข้อมูลเพิ่มขึ้นแบบเลขชี้กำลังจึงจะตรวจพบได้

หากต้องการโจมตีรหัสลับ r รอบ ให้ค้นหาเส้นทางเชิงเส้น ε ผ่าน r-1 รอบ รวบรวมข้อความธรรมดาที่ทราบจำนวน N = 1/ε^2 รายการ สำหรับไบต์คีย์รอบสุดท้ายที่เป็นไปได้แต่ละค่า k' ให้ถอดรหัสรอบสุดท้ายบางส่วนด้วย XOR แล้วตรวจสอบว่าการประมาณค่าเชิงเส้นเป็นจริงมากกว่า N/2 ครั้งหรือไม่ k' ที่ถูกต้องจะแสดงความเอนเอียงที่ถูกต้อง

Matsui โจมตี DES 16 รอบในปี 1993 โดยใช้การประมาณค่าเชิงเส้น 14 รอบที่มีความเอนเอียง 2^{-21.4} ต้องใช้ข้อความธรรมดาที่ทราบจำนวน 2^{43} รายการ ในระยะแรกกู้คืนบิตคีย์ได้ 26 บิต และใช้การค้นหาอย่างละเอียดถี่ถ้วนเพื่อกู้คืนอีก 30 บิต นับเป็นการโจมตีเชิงปฏิบัติครั้งแรกที่เร็วกว่าการลองทุกค่ากับ DES ทั้งหมด

กล่อง S ของ AES มีค่าใน LAT สูงสุด |ε| = 4/256 = 1/64 ต่อกล่อง S กลยุทธ์เส้นทางกว้างจำกัดจำนวนกล่อง S ที่ทำงานอยู่ในเส้นทาง 4 รอบใด ๆ ให้มีอย่างน้อย 25 กล่อง ความเอนเอียงรวม ≤ (1/64)^{25/2} ≈ 2^{-75} ต้องใช้ข้อความธรรมดาที่ทราบจำนวน 2^{150} รายการ ซึ่งไม่สามารถทำได้ในทางปฏิบัติ

เชิงผลต่าง: ใช้คู่ข้อความธรรมดาที่ทราบหรือเลือกเอง และใช้ประโยชน์จากผลต่างเอาต์พุต เชิงเส้น: ใช้ข้อความธรรมดาที่ทราบ และใช้ประโยชน์จากการประมาณค่าเชิงเส้นทางสถิติ ทั้งสองวิธีใช้ข้อความธรรมดาที่เลือกในการโจมตีเชิงปฏิบัติ และทั้งคู่เป็นเกณฑ์ในการออกแบบ: กล่อง S ต้องต้านทานทั้งสองวิธี (ค่า DDT สูงสุดต่ำ และค่า LAT สูงสุดต่ำ)

ใช้การประมาณค่าเชิงเส้นหลายรายการพร้อมกันเพื่อลดความซับซ้อนด้านข้อมูล Nyberg และ Leander ขยายวิธีของ Matsui โดยการรวมการประมาณค่า M รายการเข้าด้วยกันเพื่อลดปริมาณข้อมูลลงด้วยตัวคูณ log(M) วิธีนี้ใช้กับ PRESENT, SIMON และรหัสลับน้ำหนักเบาอื่น ๆ

การใช้การประมาณค่าเชิงเส้นกับรหัสลับแบบสตรีม: ค้นหาสหสัมพันธ์ระหว่างกระแสคีย์กับฟังก์ชันเชิงเส้นของเอาต์พุต LFSR หากสหสัมพันธ์นี้ไม่เป็นศูนย์ ก็จะกู้คืนคีย์ได้เร็วกว่าการลองทุกค่า แนวคิดนี้มีอิทธิพลต่อการออกแบบฟังก์ชันผสมแบบไม่เชิงเส้นในรหัสลับแบบสตรีม

การวิเคราะห์รหัสลับแบบอินทิกรัล (Knudsen-Wagner): เลือกชุดข้อความธรรมดาที่ไบต์บางตำแหน่งมีค่าครบทั้ง 256 ค่า ขณะที่ตำแหน่งอื่นคงที่ หลังผ่านหลายรอบ XOR ของเอาต์พุตทั้งหมดในตำแหน่งที่กำหนดจะเป็น 0 (สมดุล) วิธีนี้ใช้ประโยชน์จากโครงสร้างของ AES และสามารถทำลาย AES ที่ลดจำนวนรอบได้อย่างมีประสิทธิภาพ

บทตั้งการสะสมกล่าวถึงการรวมการประมาณค่าเชิงเส้นว่าอย่างไร

การวิเคราะห์รหัสลับเชิงเส้นค้นหาการประมาณค่าเชิงเส้นของกล่อง S ที่มีความเอนเอียง AES ต้านทานการโจมตีนี้ด้วยกล่อง S ที่เหมาะสมที่สุดตาม LAT และกลยุทธ์เส้นทางกว้าง Matsui ทำลาย DES ด้วยข้อความธรรมดาที่ทราบจำนวน 2^43 รายการโดยใช้เส้นทาง 14 รอบ บทถัดไป: การโจมตีแบบวันเกิดและการค้นหาการชนกัน