การวิเคราะห์การเข้ารหัสเชิงเส้น
- ผู้เสนอ
- 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) ที่ต้องการการวิเคราะห์ความต้านทานเชิงเส้น
- การประเมินรหัสลับรุ่นเก่าเพื่อการตัดสินใจปลดประจำการและเปลี่ยน
วิธีการทำงาน
วิธีการทำงาน
ค้นหาการประมาณค่าเชิงเส้น: ความสัมพันธ์เชิงเส้นระหว่างบิตของข้อความธรรมดา บิตของข้อความเข้ารหัส และบิตของกุญแจ ที่เป็นจริงด้วยความน่าจะเป็นที่แตกต่างจาก 0.5 อย่างมีนัยสำคัญ
ประมาณค่าความเอนเอียง (การเบี่ยงเบนจาก 0.5) ของการประมาณค่าเชิงเส้นแต่ละรายการโดยใช้การวิเคราะห์ทางสถิติของการแปลงรอบ
สำหรับค่ากุญแจที่คาดเดา ให้คำนวณความถี่ที่การประมาณค่าเชิงเส้นเป็นจริงในคู่ข้อความธรรมดา-ข้อความเข้ารหัสที่ทราบ กุญแจที่ถูกต้องทำให้การประมาณค่าเป็นจริงบ่อยที่สุด
ตรวจสอบบิตกุญแจที่กู้คืนได้โดยการถอดรหัสข้อความเข้ารหัสและตรวจสอบความถูกต้อง
ข้อผิดพลาดที่พบบ่อย
- สมมติว่าการประมาณค่าเชิงเส้นทั้งหมดสามารถนำไปใช้ประโยชน์ได้ การประมาณค่าที่อ่อนแอให้ประโยชน์เพียงเล็กน้อย
- การประเมินความยากของการโจมตีจริงต่ำเกินไปเมื่อข้อกำหนดข้อมูลทางทฤษฎีดูสมเหตุสมผล
- การละเลยปฏิสัมพันธ์ระหว่างคุณสมบัติเชิงเส้นและคุณสมบัติเชิงอนุพันธ์ในการวิเคราะห์รหัสลับ
คำถามที่พบบ่อย
Piling-up lemma คืออะไร?
Piling-up lemma เป็นวิธีการคำนวณความเอนเอียงของการประมาณค่าเชิงเส้นข้ามหลายรอบ โดยการรวมความเอนเอียงของการประมาณค่าแต่ละรอบ เป็นพื้นฐานของการวิเคราะห์การเข้ารหัสเชิงเส้น
AES ทนทานต่อการวิเคราะห์การเข้ารหัสเชิงเส้นได้อย่างไร?
AES ใช้ S-box ที่เลือกเพื่อลดความน่าจะเป็นสูงสุดของการประมาณค่าเชิงเส้น และชั้นการกระจาย (diffusion layer) ที่ทำให้การกระจายความเอนเอียงเชิงเส้นข้ามรอบเป็นไปอย่างรวดเร็ว ขอบเขตที่พิสูจน์ได้รับประกันว่าไม่มีการประมาณค่าเชิงเส้นที่ใช้งานได้จริง
ความแตกต่างระหว่างการวิเคราะห์การเข้ารหัสเชิงเส้นและการวิเคราะห์การเข้ารหัสเชิงอนุพันธ์คืออะไร?
การวิเคราะห์เชิงอนุพันธ์ศึกษาความแตกต่างของอินพุต-เอาต์พุต ในขณะที่การวิเคราะห์เชิงเส้นศึกษาการประมาณค่าเชิงเส้น (XOR ของบิตข้อความธรรมดาและข้อความเข้ารหัส) ทั้งสองอย่างใช้ประโยชน์จากจุดอ่อนเชิงโครงสร้างในรหัสลับ
การวิเคราะห์การเข้ารหัสเชิงเส้นสามารถเจาะรหัสลับสมัยใหม่ได้หรือไม่?
ในทางปฏิบัติไม่ได้ รหัสลับสมัยใหม่เช่น AES มีขอบเขตที่พิสูจน์ได้เกี่ยวกับการประมาณค่าเชิงเส้น ทำให้การโจมตีไม่สามารถคำนวณได้จริง
ฉันจะประเมินความต้านทานเชิงเส้นในการออกแบบรหัสลับของฉันได้อย่างไร?
วิเคราะห์ตารางการประมาณค่าเชิงเส้นของ S-box และคำนวณความเอนเอียงสูงสุดข้ามรอบโดยใช้ piling-up lemma ตรวจสอบให้แน่ใจว่าความเอนเอียงสูงสุดมีค่าน้อยมากสำหรับการประมาณค่าเชิงเส้นที่เป็นไปได้ทั้งหมด
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วMatsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว