Skip to content
กลับไปยังผลการค้นหา

การวิเคราะห์การเข้ารหัสเชิงเส้น

ผู้เสนอ
Mitsuru Matsui
ปี
1993
ประเภท
linear approximation attack
กลุ่มวิธี
Cryptanalytic technique

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การวิเคราะห์การเข้ารหัสเชิงเส้นเป็นการโจมตีแบบทราบข้อความธรรมดา (known-plaintext attack) ที่ใช้ประโยชน์จากการประมาณค่าเชิงเส้นของการแปลงที่ไม่ใช่เชิงเส้นของรหัสลับเพื่อกู้คืนบิตของกุญแจลับ การวิเคราะห์การเข้ารหัสเชิงเส้นซึ่งนำเสนอโดย Mitsuru Matsui ในปี 1993 ทำให้สามารถโจมตีรหัสลับ เช่น DES ได้จริง โดยมีความซับซ้อนในการคำนวณน้อยกว่าการโจมตีแบบ brute force เทคนิคนี้วิเคราะห์ความเอนเอียงทางสถิติของความสัมพันธ์เชิงเส้นระหว่างบิตของข้อความธรรมดาและข้อความเข้ารหัสกับบิตของกุญแจ ทำให้สามารถกู้คืนกุญแจได้โดยใช้ข้อมูลน้อยลง

แนวคิดเบื้องหลังวิธีการ

การวิเคราะห์การเข้ารหัสเชิงเส้นค้นหาสมการเชิงเส้นที่เชื่อมโยงบิตของข้อความธรรมดา บิตของข้อความเข้ารหัส และบิตของกุญแจ เนื่องจากมีการผสมผสานที่ไม่สมบูรณ์ในรอบการเข้ารหัส สมการเชิงเส้นเหล่านี้จึงเป็นจริงด้วยความน่าจะเป็นที่สูงกว่าค่าสุ่มเล็กน้อย โดยการรวบรวมคู่ข้อความธรรมดา-ข้อความเข้ารหัสจำนวนมากและสังเกตว่าค่ากุญแจใดที่ทำให้สมการเหล่านี้เป็นจริงบ่อยขึ้น ผู้โจมตีสามารถจำกัดวงกุญแจที่ถูกต้องได้

ประวัติศาสตร์

การวิเคราะห์การเข้ารหัสเชิงเส้นถูกนำเสนอโดย Matsui ในปี 1993 ในฐานะการโจมตีแบบทราบข้อความธรรมดาต่อ DES ในปี 1994 Matsui ได้สาธิตการวิเคราะห์การเข้ารหัสเชิงทดลองครั้งแรกของมาตรฐาน DES โดยใช้การวิเคราะห์การเข้ารหัสเชิงเส้น กู้คืนกุญแจได้ด้วยข้อความธรรมดาที่ทราบ 2^43 การค้นพบครั้งสำคัญนี้แสดงให้เห็นถึงการโจมตีจริงต่อมาตรฐานที่ใช้งานอยู่ และมีอิทธิพลต่อการพัฒนา AES ด้วยขอบเขตความต้านทานที่พิสูจน์ได้

ควรใช้เมื่อใด

การวิเคราะห์การเข้ารหัสเชิงเส้นใช้ในการวิจัยการวิเคราะห์การเข้ารหัสและการประเมินการออกแบบรหัสลับ เป็นแนวทางสำหรับผู้ออกแบบรหัสลับในการเลือก S-box และการแปลงที่ทนทานต่อการประมาณค่าเชิงเส้น รหัสลับสมัยใหม่ได้รับการออกแบบโดยมีขอบเขตที่พิสูจน์ได้เกี่ยวกับความแข็งแกร่งของการประมาณค่าเชิงเส้น

ข้อจำกัดและข้อควรพิจารณา

  • รหัสลับสมัยใหม่ (AES) ได้รับการออกแบบอย่างระมัดระวังเพื่อทนทานต่อการวิเคราะห์การเข้ารหัสเชิงเส้นด้วยขอบเขตที่พิสูจน์ได้
  • ต้องการคู่ข้อความธรรมดา-ข้อความเข้ารหัสที่ทราบ ซึ่งอาจไม่มีให้ในทุกสถานการณ์
  • ความต้องการในการคำนวณและข้อมูลอาจเกินความเป็นจริงที่ใช้งานได้สำหรับรหัสลับที่ออกแบบมาอย่างดี
  • การค้นหาการประมาณค่าเชิงเส้นที่แข็งแกร่งสำหรับรหัสลับสมัยใหม่เป็นเรื่องยากมาก

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • การโจมตีจริงต่อ DES ที่ต้องการคู่ข้อความธรรมดา-ข้อความเข้ารหัส 2^43 และการดำเนินการ 2^39
  • กรอบการทำงานทางคณิตศาสตร์ที่มีรูปแบบชัดเจน (piling-up lemma) สำหรับการวิเคราะห์ความเอนเอียงของการประมาณค่า
  • เสริมการวิเคราะห์การเข้ารหัสเชิงอนุพันธ์ (differential cryptanalysis) โดยค้นหาจุดอ่อนที่การวิเคราะห์เชิงอนุพันธ์อาจมองข้าม
  • กำหนดข้อกำหนดการออกแบบรหัสลับสำหรับการเลือก S-box และการแปลงรอบ

การประยุกต์ใช้

  • การวิเคราะห์การเข้ารหัสลับของรหัสบล็อก (block ciphers) การประเมินคุณสมบัติด้านความปลอดภัยในการวิจัยและการกำหนดมาตรฐาน
  • การออกแบบรหัสลับและการเลือก S-box เพื่อให้แน่ใจว่ามีขอบเขตการประมาณค่าเชิงเส้นที่เพียงพอ
  • การตรวจสอบความถูกต้องของมาตรฐานการเข้ารหัสลับ (NIST, ETSI) ที่ต้องการการวิเคราะห์ความต้านทานเชิงเส้น
  • การประเมินรหัสลับรุ่นเก่าเพื่อการตัดสินใจปลดประจำการและเปลี่ยน

วิธีการทำงาน

วิธีการทำงาน

1

ค้นหาการประมาณค่าเชิงเส้น: ความสัมพันธ์เชิงเส้นระหว่างบิตของข้อความธรรมดา บิตของข้อความเข้ารหัส และบิตของกุญแจ ที่เป็นจริงด้วยความน่าจะเป็นที่แตกต่างจาก 0.5 อย่างมีนัยสำคัญ

2

ประมาณค่าความเอนเอียง (การเบี่ยงเบนจาก 0.5) ของการประมาณค่าเชิงเส้นแต่ละรายการโดยใช้การวิเคราะห์ทางสถิติของการแปลงรอบ

3

สำหรับค่ากุญแจที่คาดเดา ให้คำนวณความถี่ที่การประมาณค่าเชิงเส้นเป็นจริงในคู่ข้อความธรรมดา-ข้อความเข้ารหัสที่ทราบ กุญแจที่ถูกต้องทำให้การประมาณค่าเป็นจริงบ่อยที่สุด

4

ตรวจสอบบิตกุญแจที่กู้คืนได้โดยการถอดรหัสข้อความเข้ารหัสและตรวจสอบความถูกต้อง

ข้อผิดพลาดที่พบบ่อย

  • สมมติว่าการประมาณค่าเชิงเส้นทั้งหมดสามารถนำไปใช้ประโยชน์ได้ การประมาณค่าที่อ่อนแอให้ประโยชน์เพียงเล็กน้อย
  • การประเมินความยากของการโจมตีจริงต่ำเกินไปเมื่อข้อกำหนดข้อมูลทางทฤษฎีดูสมเหตุสมผล
  • การละเลยปฏิสัมพันธ์ระหว่างคุณสมบัติเชิงเส้นและคุณสมบัติเชิงอนุพันธ์ในการวิเคราะห์รหัสลับ

คำถามที่พบบ่อย

Piling-up lemma คืออะไร?

Piling-up lemma เป็นวิธีการคำนวณความเอนเอียงของการประมาณค่าเชิงเส้นข้ามหลายรอบ โดยการรวมความเอนเอียงของการประมาณค่าแต่ละรอบ เป็นพื้นฐานของการวิเคราะห์การเข้ารหัสเชิงเส้น

AES ทนทานต่อการวิเคราะห์การเข้ารหัสเชิงเส้นได้อย่างไร?

AES ใช้ S-box ที่เลือกเพื่อลดความน่าจะเป็นสูงสุดของการประมาณค่าเชิงเส้น และชั้นการกระจาย (diffusion layer) ที่ทำให้การกระจายความเอนเอียงเชิงเส้นข้ามรอบเป็นไปอย่างรวดเร็ว ขอบเขตที่พิสูจน์ได้รับประกันว่าไม่มีการประมาณค่าเชิงเส้นที่ใช้งานได้จริง

ความแตกต่างระหว่างการวิเคราะห์การเข้ารหัสเชิงเส้นและการวิเคราะห์การเข้ารหัสเชิงอนุพันธ์คืออะไร?

การวิเคราะห์เชิงอนุพันธ์ศึกษาความแตกต่างของอินพุต-เอาต์พุต ในขณะที่การวิเคราะห์เชิงเส้นศึกษาการประมาณค่าเชิงเส้น (XOR ของบิตข้อความธรรมดาและข้อความเข้ารหัส) ทั้งสองอย่างใช้ประโยชน์จากจุดอ่อนเชิงโครงสร้างในรหัสลับ

การวิเคราะห์การเข้ารหัสเชิงเส้นสามารถเจาะรหัสลับสมัยใหม่ได้หรือไม่?

ในทางปฏิบัติไม่ได้ รหัสลับสมัยใหม่เช่น AES มีขอบเขตที่พิสูจน์ได้เกี่ยวกับการประมาณค่าเชิงเส้น ทำให้การโจมตีไม่สามารถคำนวณได้จริง

ฉันจะประเมินความต้านทานเชิงเส้นในการออกแบบรหัสลับของฉันได้อย่างไร?

วิเคราะห์ตารางการประมาณค่าเชิงเส้นของ S-box และคำนวณความเอนเอียงสูงสุดข้ามรอบโดยใช้ piling-up lemma ตรวจสอบให้แน่ใจว่าความเอนเอียงสูงสุดมีค่าน้อยมากสำหรับการประมาณค่าเชิงเส้นที่เป็นไปได้ทั้งหมด

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว