อัลกอริทึม GOST 28147 89 คือ มาตรฐานการเข้ารหัสข้อมูลในประเทศ การเปลี่ยนแปลงในธีมของแขก
ต่างจาก American DES มาตรฐานในประเทศใช้คีย์ที่ยาวกว่า - 256 บิต นอกจากนี้ มาตรฐานของรัสเซียแนะนำให้ใช้การเข้ารหัส 32 รอบ ในขณะที่ DES ต้องการเพียง 16 รอบเท่านั้น
ดังนั้นพารามิเตอร์หลักของอัลกอริธึมการแปลงข้อมูลการเข้ารหัส GOST 28147-89 จึงเป็นดังนี้: ขนาดบล็อกคือ 64 บิต, ขนาดคีย์คือ 256 บิต, จำนวนรอบคือ 32
อัลกอริทึมนี้เป็นเครือข่าย Feishtel แบบคลาสสิก บล็อกข้อมูลที่เข้ารหัสจะถูกแบ่งออกเป็นสองส่วนที่เหมือนกัน คือ R ขวาและ L ซ้าย ส่วนด้านขวาจะถูกเพิ่มลงในคีย์ย่อยแบบกลม และใช้อัลกอริธึมบางตัวในการเข้ารหัสส่วนด้านซ้าย ก่อนรอบต่อไปจะมีการสลับส่วนซ้ายและขวา โครงสร้างนี้อนุญาตให้ใช้อัลกอริธึมเดียวกันสำหรับการเข้ารหัสและการถอดรหัสบล็อก
อัลกอริธึมการเข้ารหัสใช้การดำเนินการต่อไปนี้:
- การเติมคำแบบโมดูโล 2 32;
- เลื่อนคำไปทางซ้ายแบบวนตามจำนวนบิตที่ระบุ
- โมดูโลบวกระดับบิต 2;
- ทดแทนตามตาราง
ในขั้นตอนต่างๆ ของอัลกอริธึม GOST ข้อมูลที่ทำงานจะถูกตีความและนำไปใช้ในรูปแบบที่แตกต่างกัน ในบางกรณี องค์ประกอบข้อมูลจะถือเป็นอาร์เรย์ของบิตอิสระ ในกรณีอื่น ๆ เป็นจำนวนเต็มที่ไม่ได้ลงนาม ในกรณีอื่น ๆ ว่ามีโครงสร้าง องค์ประกอบที่ซับซ้อนประกอบด้วยองค์ประกอบที่เรียบง่ายกว่าหลายประการ
โครงสร้างทรงกลม GOST 28147-89
โครงสร้างของหนึ่งรอบของ GOST 28147-89 แสดงไว้ในรูปที่ 1 5.1.
บล็อกข้อมูลที่เข้ารหัสจะถูกแบ่งออกเป็นสองส่วน ซึ่งจากนั้นจะถูกประมวลผลเป็นจำนวนเต็ม 32 บิตที่ไม่ได้ลงนามแยกกัน ขั้นแรก ครึ่งขวาของบล็อกและคีย์ย่อยของรอบจะถูกเพิ่มแบบโมดูโล 2 32 จากนั้นจึงทำการทดแทนแบบทีละบล็อก ค่า 32 บิตที่ได้รับในขั้นตอนก่อนหน้า (เรียกว่า S) จะถูกตีความเป็นอาร์เรย์ของบล็อกโค้ด 4 บิตจำนวน 8 บล็อก: ส=(ส 0 ,ส 1 ,ส 2 ,ส 3 ,ส 4 ,ส 5 ,ส 6 ,ส 7 ). ถัดไปค่าของแต่ละบล็อกทั้งแปดจะถูกแทนที่ด้วยบล็อกใหม่ซึ่งเลือกจากตารางการแทนที่ดังนี้: ค่าของบล็อก S i จะถูกแทนที่ด้วยองค์ประกอบ S i -th ตามลำดับ (นับจากศูนย์) ของโหนดการแทนที่ i-th (เช่น ตารางการแทนที่แถวที่ i การกำหนดหมายเลขตั้งแต่เริ่มต้นด้วย) กล่าวอีกนัยหนึ่ง องค์ประกอบที่มีหมายเลขแถวเท่ากับจำนวนของบล็อกที่ถูกแทนที่ และหมายเลขคอลัมน์เท่ากับค่าของบล็อกที่ถูกแทนที่เป็นจำนวนเต็มที่ไม่ใช่ลบ 4 บิต จะถูกเลือกเพื่อแทนที่ค่าของ บล็อก แต่ละบรรทัดของตารางทดแทนจะมีตัวเลขตั้งแต่ 0 ถึง 15 ตามลำดับแบบสุ่มโดยไม่ซ้ำกัน ค่าขององค์ประกอบตารางการทดแทนจะถูกนำมาตั้งแต่ 0 ถึง 15 เนื่องจากสี่บิตที่ถูกแทนที่สามารถมีจำนวนเต็มที่ไม่ได้ลงนามในช่วงตั้งแต่ 0 ถึง 15 ตัวอย่างเช่น แถวแรกของ S-box อาจมีค่าต่อไปนี้: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . ในกรณีนี้ ค่าของบล็อก S 0 (สี่บิตที่มีนัยสำคัญน้อยที่สุดของหมายเลข S แบบ 32 บิต) จะถูกแทนที่ด้วยตัวเลขที่ตำแหน่งซึ่งตัวเลขเท่ากับค่าของบล็อกที่ถูกแทนที่ ถ้า S 0 = 0 จะถูกแทนที่ด้วย 5 ถ้า S 0 = 1 ก็จะถูกแทนที่ด้วย 8 เป็นต้น
ข้าว. 5.1.
หลังจากดำเนินการทดแทนแล้ว บล็อก 4 บิตทั้งหมดจะต่อกันอีกครั้งเป็นคำ 32 บิตเดียว ซึ่งจากนั้นจะหมุน 11 บิตไปทางซ้าย สุดท้ายก็ใช้การดำเนินการระดับบิต "รวมโมดูโล 2"ผลลัพธ์จะรวมกับครึ่งซ้ายทำให้เกิดครึ่งขวาใหม่ของ R i ด้านซ้ายใหม่ L i จะถูกนำมาเท่ากับส่วนล่างของบล็อกที่แปลงแล้ว: L i = R i-1 .
ค่าผลลัพธ์ของบล็อกที่แปลงแล้วถือเป็นผลลัพธ์ของอัลกอริธึมการเข้ารหัสหนึ่งรอบ
ขั้นตอนการเข้ารหัสและถอดรหัส
GOST 28147-89 จึงเป็นรหัสบล็อก การแปลงข้อมูลดำเนินการเป็นบล็อกในสิ่งที่เรียกว่า รอบพื้นฐาน. ลูปพื้นฐานประกอบด้วยการดำเนินการซ้ำของรอบหลักที่เรากล่าวถึงก่อนหน้านี้สำหรับบล็อกข้อมูล โดยใช้องค์ประกอบหลักที่แตกต่างกันและแตกต่างกันตามลำดับที่ใช้องค์ประกอบหลัก แต่ละรอบใช้หนึ่งในแปดคีย์ย่อย 32 บิตที่เป็นไปได้
มาดูกระบวนการสร้างคีย์ย่อยแบบกลมกัน ใน GOST ขั้นตอนนี้ง่ายมาก โดยเฉพาะเมื่อเปรียบเทียบกับ DES คีย์ K แบบ 256 บิตแบ่งออกเป็นคีย์ย่อยแบบ 32 บิตจำนวนแปดคีย์ ซึ่งหมายถึง K0, K1, K2,K3, K4, K5, K6, K7 อัลกอริธึมประกอบด้วย 32 รอบ ดังนั้นแต่ละคีย์ย่อยในระหว่างการเข้ารหัสจะใช้เป็นสี่รอบตามลำดับที่แสดงในตาราง 5.1
| กลม | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| การก่อสร้างเต็มรูปแบบ | เค 0 | เค 1 | K2 | เค 3 | เค 4 | K5 | เค 6 | เค 7 |
| กลม | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| การก่อสร้างเต็มรูปแบบ | เค 0 | เค 1 | K2 | เค 3 | เค 4 | K5 | เค 6 | เค 7 |
| กลม | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| การก่อสร้างเต็มรูปแบบ | เค 0 | เค 1 | K2 | เค 3 | เค 4 | K5 | เค 6 | เค 7 |
| กลม | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| การก่อสร้างเต็มรูปแบบ | เค 7 | เค 6 | K5 | เค 4 | เค 3 | K2 | เค 1 | เค 0 |
กระบวนการถอดรหัสดำเนินการโดยใช้อัลกอริธึมเดียวกันกับการเข้ารหัส ข้อแตกต่างเพียงอย่างเดียวคือลำดับการใช้คีย์ย่อย K i เมื่อถอดรหัสจะต้องใช้คีย์ย่อยในลำดับย้อนกลับตามที่ระบุไว้ใน
อัลกอริธึมนี้จำเป็นสำหรับใช้เป็นอัลกอริธึมการเข้ารหัสในองค์กรภาครัฐของสหพันธรัฐรัสเซียและองค์กรเชิงพาณิชย์หลายแห่ง
คำอธิบายของอัลกอริทึม
แผนภาพอัลกอริทึมแสดงในรูป 3.1. อย่างที่คุณเห็น การออกแบบอัลกอริธึมนี้ค่อนข้างง่าย ซึ่งทำให้การใช้งานซอฟต์แวร์หรือฮาร์ดแวร์ง่ายขึ้นอย่างชัดเจน
อัลกอริธึม GOST 28147-89 เข้ารหัสข้อมูลในบล็อกขนาด 64 บิต ซึ่งแบ่งออกเป็นสองบล็อกย่อย 32 บิต (N1 และ N2) Subblock N1 ได้รับการประมวลผลด้วยวิธีใดวิธีหนึ่ง หลังจากนั้นมูลค่าของมันจะถูกรวมเข้าด้วยกัน
ด้วยค่าของบล็อกย่อย N2 (ดำเนินการเพิ่มเติมแบบโมดูโล 2) จากนั้นบล็อกย่อยจะถูกสลับ การแปลงนี้ดำเนินการในจำนวนรอบที่กำหนด: 16 หรือ 32 ขึ้นอยู่กับโหมดการทำงานของอัลกอริทึม (อธิบายไว้ด้านล่าง) ในแต่ละรอบจะมีการดำเนินการดังต่อไปนี้:
1. การสมัครที่สำคัญ เนื้อหาของบล็อกย่อย /VI จะถูกเพิ่มแบบโมดูโล 2 32 พร้อมกับส่วนหนึ่งของคีย์ Kx
คีย์เข้ารหัสของอัลกอริทึม GOST 28147-89 มีขนาด 256 บิตและ Kx เป็นส่วน 32 บิตนั่นคือ คีย์การเข้ารหัส 256 บิตจะแสดงเป็นการต่อข้อมูลของคีย์ย่อย 32 บิต (รูปที่ 3.2):
รองรับ ATI, AG2, Yu, AG4, K5, Kb, K7
ในระหว่างกระบวนการเข้ารหัส จะมีการใช้คีย์ย่อยเหล่านี้อย่างใดอย่างหนึ่ง ขึ้นอยู่กับหมายเลขรอบและโหมดการทำงานของอัลกอริทึม
ข้าว. 3.1. แผนภาพอัลกอริทึม GOST 28147-
ข้าว. 3.2. คีย์การเข้ารหัสของอัลกอริทึม GOST 28147-89
2. การเปลี่ยนโต๊ะ หลังจากการคีย์ บล็อกย่อย /VI จะถูกแบ่งออกเป็น 8 ส่วน ๆ ละ 4 บิต ค่าของแต่ละส่วนจะถูกแทนที่แยกกันตามตารางการแทนที่สำหรับส่วนนี้ของบล็อกย่อย การทดแทนตาราง (กล่องทดแทน, S-box) มักใช้ในอัลกอริธึมการเข้ารหัสสมัยใหม่ ดังนั้นจึงควรพิจารณารายละเอียดเพิ่มเติม
การทดแทนตารางถูกใช้ในลักษณะนี้: บล็อกของข้อมูลขนาดหนึ่ง (ในกรณีนี้คือ 4 บิต) จะถูกส่งไปยังอินพุตซึ่งการแสดงตัวเลขจะกำหนดจำนวนของค่าเอาต์พุต ตัวอย่างเช่น เรามี S-box ในรูปแบบต่อไปนี้:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
ปล่อยให้บล็อก 4 บิต "0100" มาที่อินพุตนั่นคือ ค่า 4 ตามตารางค่าเอาต์พุตจะเท่ากับ 15 เช่น “1111” (0 ถูกแทนที่ด้วย 4, 1 ด้วย 11, ค่าของ 2 ยังคงไม่เปลี่ยนแปลง ฯลฯ)
อย่างที่คุณเห็น การออกแบบอัลกอริทึมนั้นง่ายมาก ซึ่งหมายความว่าภาระที่ยิ่งใหญ่ที่สุดของการเข้ารหัสข้อมูลตกอยู่ที่ตารางทดแทน น่าเสียดายที่อัลกอริทึมมีคุณสมบัติที่มีตารางทดแทนที่ "อ่อนแอ" ซึ่งอัลกอริทึมนี้สามารถแก้ไขได้ด้วยวิธีการเข้ารหัส ตารางที่อ่อนแอ ได้แก่ ตารางที่เอาต์พุตเท่ากับอินพุต:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. เลื่อนแบบวนไปทางซ้าย 11 บิต
โหมดการทำงานของอัลกอริทึม
อัลกอริทึม GOST 28147-89 มีโหมดการทำงาน 4 โหมด:
□ โหมดการเปลี่ยนอย่างง่าย
□ โหมดแกมมา;
P โหมดแกมมาด้วย ข้อเสนอแนะ;
□ โหมดการพัฒนาสิ่งที่แนบมาเลียนแบบ
โหมดเหล่านี้ค่อนข้างแตกต่างจากโหมดที่ยอมรับโดยทั่วไป (อธิบายไว้ในส่วนที่ 1.4) ดังนั้นจึงควรพิจารณารายละเอียดเพิ่มเติม
โหมดเหล่านี้มีวัตถุประสงค์ที่แตกต่างกัน แต่ใช้การแปลงการเข้ารหัสแบบเดียวกับที่อธิบายไว้ข้างต้น
โหมดการเปลี่ยนง่าย
ในโหมดการแทนที่อย่างง่าย บล็อกข้อมูล 64 บิตแต่ละบล็อกจะถูกเข้ารหัสโดยใช้ 32 รอบที่อธิบายไว้ข้างต้น คีย์ย่อย 32 บิตถูกใช้ในลำดับต่อไปนี้:
□ น็อก, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI ฯลฯ - ในรอบที่ 1 ถึง 24;
□ K1, Kb, K5, K4, KZ, K2, K\, KO - ในรอบที่ 25 ถึง 32
การถอดรหัสในโหมดการแทนที่อย่างง่ายนั้นดำเนินการในลักษณะเดียวกันทุกประการ แต่มีลำดับการใช้คีย์ย่อยที่แตกต่างกันเล็กน้อย:
□ น็อก, K\, K2, KZ, K4, K5, Kb, KP - ในรอบ 1 ถึง 8;
□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb, ฯลฯ - ในรอบที่ 9 ถึง 32
เช่นเดียวกับโหมด ECB มาตรฐาน เนื่องจากการเข้ารหัสบล็อกที่แยกจากกัน จึงไม่แนะนำให้ใช้โหมดการแทนที่อย่างง่ายสำหรับการเข้ารหัสข้อมูลโดยเคร่งครัด ควรใช้เพื่อเข้ารหัสคีย์เข้ารหัสอื่น ๆ ในรูปแบบหลายคีย์เท่านั้น
โหมดแกมมา
ในโหมดแกมมา (รูปที่ 3.3) แต่ละบล็อกข้อความธรรมดาจะถูกเพิ่มทีละบิตแบบโมดูโล 2 เข้ากับบล็อกแกมมาการเข้ารหัสแบบ 64 บิต รหัสแกมมาเป็นลำดับพิเศษที่สร้างขึ้นโดยใช้การแปลงที่อธิบายไว้ข้างต้นดังต่อไปนี้:
1. การกรอกเริ่มต้นถูกเขียนเพื่อลงทะเบียน N1 และ N2 - ค่า 64 บิตที่เรียกว่า "ข้อความซิงค์" (ข้อความซิงค์นั้นเป็นอะนาล็อกของเวกเตอร์การเริ่มต้นในโหมด CBC, CFB และ OFB)
2. เนื้อหาของรีจิสเตอร์ /VI และ N2 (ในกรณีนี้คือข้อความซิงค์) จะถูกเข้ารหัสในโหมดการแทนที่อย่างง่าย
3. เนื้อหาของ N1 จะถูกเพิ่มแบบโมดูโล (2 32 – 1) โดยมีค่าคงที่ CI = 2 24 + 2 16 + 2 8 + 4 ผลลัพธ์ของการเติมจะถูกเขียนลงในรีจิสเตอร์ /VI
4. เนื้อหาของ N2 จะถูกเพิ่มแบบโมดูโล 2 โดยมีค่าคงที่ C2 = 2 24 + 2 16 + 2 8 +1 ผลลัพธ์ของการบวกจะถูกเขียนเพื่อลงทะเบียน N2
5. เนื้อหาของรีจิสเตอร์ /VI และ N2 จะถูกส่งออกเป็นบล็อกแกมมาการเข้ารหัส 64 บิต (เช่น ในกรณีนี้ /VI และ N2 จะสร้างบล็อกแกมมาแรก)
6. หากจำเป็นต้องใช้บล็อกแกมม่าถัดไป (เช่น จำเป็นต้องเข้ารหัสหรือถอดรหัสเพิ่มเติม) ให้กลับไปที่ขั้นตอนที่ 2
สำหรับการถอดรหัส แกมมาจะถูกสร้างขึ้นในลักษณะที่คล้ายกัน จากนั้นไซเฟอร์เท็กซ์และบิตแกมม่าจะถูก XORed อีกครั้ง
ในการสร้างช่วงการเข้ารหัสเดียวกัน ผู้ใช้ที่ถอดรหัสลับจะต้องมีคีย์เดียวกันและค่าข้อความการซิงโครไนซ์เดียวกันกับที่ใช้ในการเข้ารหัสข้อมูล มิฉะนั้นจะไม่สามารถรับข้อความต้นฉบับจากข้อความที่เข้ารหัสได้
ในการใช้งานอัลกอริทึม GOST 28147-89 ส่วนใหญ่ ข้อความซิงค์ไม่ใช่องค์ประกอบลับ อย่างไรก็ตาม ข้อความซิงค์อาจเป็นความลับพอๆ กับคีย์เข้ารหัส ในกรณีนี้ เราสามารถพิจารณาว่าความยาวคีย์ที่มีประสิทธิผลของอัลกอริทึม (256 บิต) เพิ่มขึ้นอีก 64 บิตของข้อความการซิงโครไนซ์ ซึ่งถือได้ว่าเป็นองค์ประกอบคีย์เพิ่มเติม
โหมดแกมมาพร้อมข้อเสนอแนะ
ในโหมดแกมมาที่มีการป้อนกลับ ผลลัพธ์ของการเข้ารหัสบล็อกข้อความธรรมดาก่อนหน้าจะถูกนำมาใช้เพื่อเติมรีจิสเตอร์ /VI และ L/2 โดยเริ่มจากบล็อกที่ 2 ไม่ใช่บล็อกแกมมาก่อนหน้า แต่เป็นผลลัพธ์ของการเข้ารหัสบล็อกข้อความธรรมดาก่อนหน้า (รูปที่ 3.4) บล็อคแรกเข้ามา. โหมดนี้ถูกสร้างขึ้นอย่างสมบูรณ์คล้ายกับอันก่อนหน้า
ข้าว. 3.4. การสร้างแกมมาการเข้ารหัสในโหมดแกมมาพร้อมข้อมูลป้อนกลับ
โหมดการผลิตสิ่งที่แนบมาเลียนแบบ
คำนำหน้าคือผลรวมตรวจสอบการเข้ารหัสที่คำนวณโดยใช้คีย์เข้ารหัสและออกแบบมาเพื่อตรวจสอบความสมบูรณ์ของข้อความ ในการคำนวณมีโหมดพิเศษของอัลกอริทึม GOST 28147-89
การสร้างคำนำหน้าเลียนแบบจะดำเนินการดังนี้:
1. บล็อกข้อมูล 64 บิตแรกที่คำนวณคำนำหน้าการเลียนแบบจะถูกเขียนเพื่อลงทะเบียน N1 และ N2 และเข้ารหัสในโหมดการแทนที่แบบง่ายที่ลดลงซึ่งมีการดำเนินการ 16 รอบแรกจาก 32 รอบ
2. ผลลัพธ์ที่ได้จะรวมโมดูโล 2 เข้ากับบล็อกข้อมูลถัดไป โดยจัดเก็บผลลัพธ์ไว้ใน N1 และ N2
3. M และ N2 ได้รับการเข้ารหัสอีกครั้งในโหมดการแทนที่แบบง่ายที่สั้นลง ฯลฯ จนกระทั่งบล็อกข้อมูลสุดท้าย
คำนำหน้าการเลียนแบบถือเป็นเนื้อหาผลลัพธ์ 64 บิตของรีจิสเตอร์ N1 และ N2 หรือบางส่วน ส่วนใหญ่มักใช้คำนำหน้าเลียนแบบ 32 บิตนั่นคือ ครึ่งหนึ่งของเนื้อหาของการลงทะเบียน นี่ก็เพียงพอแล้ว เนื่องจากประการแรกสิ่งที่แนบมาเลียนแบบนั้นมีจุดประสงค์เช่นเดียวกับการตรวจสอบผลรวมอื่น ๆ เพื่อป้องกันการบิดเบือนข้อมูลโดยไม่ตั้งใจ เพื่อป้องกันการปรับเปลี่ยนข้อมูลโดยเจตนา จึงมีการใช้วิธีการเข้ารหัสอื่น ๆ ซึ่งส่วนใหญ่เป็นแบบอิเล็กทรอนิกส์ ลายเซ็นดิจิทัล(ดูหัวข้อ 1.1)
คำนำหน้าเลียนแบบใช้ดังนี้:
1. เมื่อเข้ารหัสข้อมูลใด ๆ คำนำหน้าเลียนแบบข้อความธรรมดาจะถูกคำนวณและส่งไปพร้อมกับไซเฟอร์เท็กซ์
2. หลังจากการถอดรหัส คำนำหน้าการเลียนแบบจะถูกคำนวณอีกครั้งและเปรียบเทียบกับคำนำหน้าที่ส่งไป
3. หากคำนำหน้าการจำลองที่คำนวณและส่งไม่ตรงกัน ข้อความการเข้ารหัสจะบิดเบี้ยวระหว่างการส่ง หรือใช้คีย์ที่ไม่ถูกต้องในระหว่างการถอดรหัส
คำนำหน้าการเลียนแบบมีประโยชน์อย่างยิ่งสำหรับการตรวจสอบการถอดรหัสข้อมูลสำคัญที่ถูกต้องเมื่อใช้โครงร่างหลายคีย์
คำนำหน้าการเลียนแบบเป็นอะนาล็อกของรหัสตรวจสอบข้อความ MAC ซึ่งคำนวณในโหมด CBC ข้อแตกต่างคือเมื่อคำนวณคำนำหน้าเลียนแบบ ข้อความการซิงโครไนซ์จะไม่ใช้ ในขณะที่เมื่อคำนวณ MAC จะใช้เวกเตอร์การเริ่มต้น
ความแรงของการเข้ารหัสอัลกอริธึม
ในปี 1994 คำอธิบายของอัลกอริทึม GOST 28147-89 ได้รับการแปลเป็นภาษาอังกฤษและเผยแพร่ หลังจากนั้นผลการวิเคราะห์ซึ่งดำเนินการโดยผู้เชี่ยวชาญจากต่างประเทศก็เริ่มปรากฏให้เห็น อย่างไรก็ตาม ไม่พบการโจมตีที่เข้าใกล้ความเป็นไปได้มาเป็นเวลานานแล้ว
□ ความยาวคีย์ขนาดใหญ่ - 256 บิต เมื่อรวมกับข้อความการซิงโครไนซ์ความลับ ความยาวคีย์ที่มีประสิทธิภาพจะเพิ่มขึ้นเป็น 320 บิต
□ 32 รอบของการเปลี่ยนแปลง; หลังจากผ่านไป 8 รอบแล้ว การกระจายตัวของข้อมูลอินพุตจะเกิดขึ้นอย่างสมบูรณ์: การเปลี่ยนบล็อกข้อความธรรมดาหนึ่งบิตจะส่งผลต่อบิตทั้งหมดของบล็อกข้อความไซเฟอร์เท็กซ์ และในทางกลับกัน กล่าวคือ มีระยะขอบที่แข็งแกร่งหลายจุด
พิจารณาผลลัพธ์ของการเข้ารหัสของอัลกอริทึม GOST 28147-89
การวิเคราะห์ตารางการทดแทน
เนื่องจากมาตรฐานไม่ได้จัดเตรียมตารางทดแทน งานจำนวนหนึ่ง (เช่นใน) แนะนำว่า "องค์กรที่มีความสามารถ" สามารถออกตารางทดแทนทั้ง "ดี" และ "ไม่ดี" ได้ อย่างไรก็ตาม ผู้เชี่ยวชาญชื่อดัง Bruce Schneier เรียกสมมติฐานดังกล่าวว่า "ข่าวลือ" เป็นที่ชัดเจนว่าความแข็งแกร่งของการเข้ารหัสของอัลกอริทึมส่วนใหญ่ขึ้นอยู่กับคุณสมบัติของตารางทดแทนที่ใช้ ดังนั้นจึงมีตารางทดแทนที่อ่อนแอ (ดูตัวอย่างด้านบน) การใช้ซึ่งสามารถลดความซับซ้อนของการโจมตีของอัลกอริทึมได้ อย่างไรก็ตาม ความเป็นไปได้ในการใช้ตารางทดแทนที่แตกต่างกันดูเหมือนจะเป็นแนวคิดที่คุ้มค่ามาก โดยสามารถอ้างอิงข้อเท็จจริงสองประการต่อไปนี้จากประวัติความเป็นมาของมาตรฐานการเข้ารหัส DES ได้ (สำหรับรายละเอียด ดูหัวข้อ 3.15):
□ การโจมตีโดยใช้การเข้ารหัสทั้งเชิงเส้นและเชิงอนุพันธ์ของอัลกอริธึม DES ใช้คุณสมบัติเฉพาะของตารางทดแทน เมื่อใช้ตารางอื่น การเข้ารหัสจะต้องเริ่มต้นใหม่
มีการพยายาม□เพื่อเสริมความแข็งแกร่งของ DES จากการวิเคราะห์เชิงเส้นและเชิงอนุพันธ์โดยใช้ตารางการทดแทนที่แข็งแกร่งยิ่งขึ้น มีการเสนอตารางดังกล่าวซึ่งมีความแข็งแกร่งกว่าจริงๆ เช่น ในอัลกอริทึม s 5 DES แต่อนิจจามันเป็นไปไม่ได้ที่จะแทนที่ DES ด้วย s 5 DES เนื่องจากตารางการแทนที่ถูกกำหนดไว้อย่างเคร่งครัดในมาตรฐาน ดังนั้นการใช้งานอัลกอริทึมอาจไม่รองรับความสามารถในการเปลี่ยนตารางเป็นตารางอื่น
งานจำนวนหนึ่ง (เช่น และ ) สรุปอย่างผิดพลาดว่าตารางการแทนที่ความลับของอัลกอริทึม GOST 28147-89 สามารถเป็นส่วนหนึ่งของคีย์และเพิ่มความยาวที่มีประสิทธิภาพได้ (ซึ่งไม่สำคัญเนื่องจากอัลกอริทึมมีขนาดใหญ่มาก 256 -บิตคีย์) อย่างไรก็ตาม งานนี้พิสูจน์ให้เห็นว่าตารางการแทนที่ข้อมูลลับสามารถคำนวณได้โดยใช้การโจมตีต่อไปนี้ ซึ่งสามารถใช้ได้จริง:
1. ตั้งค่าคีย์ศูนย์และดำเนินการค้นหา "เวกเตอร์ศูนย์" เช่น ค่า z = /(0) โดยที่ /() คือฟังก์ชันกลมของอัลกอริทึม ขั้นตอนนี้ใช้เวลาประมาณ 2 การดำเนินการเข้ารหัส
2. การใช้เวกเตอร์ศูนย์จะคำนวณค่าของตารางการแทนที่ซึ่งใช้เวลาดำเนินการไม่เกิน 2 11 ครั้ง
การปรับเปลี่ยนอัลกอริทึมและการวิเคราะห์
งานดำเนินการวิเคราะห์การเข้ารหัสของการปรับเปลี่ยนอัลกอริทึม GOST 28147-89:
□ อัลกอริทึม GOST-H ซึ่งสัมพันธ์กับอัลกอริธึมดั้งเดิม ลำดับการใช้คีย์ย่อยมีการเปลี่ยนแปลง กล่าวคือในรอบจาก 25 ถึง 32 คีย์ย่อยที่ใช้ตามลำดับโดยตรง นั่นคือ เหมือนกับในรอบก่อนหน้าของอัลกอริทึม ;
□ อัลกอริธึม GOST® 20 รอบ ซึ่งแต่ละรอบใช้ XOR แทนการเพิ่มแบบโมดูโล-2 เพื่อซ้อนทับคีย์
จากผลการวิเคราะห์สรุปได้ว่า GOST-H และ GOST© นั้นอ่อนแอกว่าอัลกอริธึม GOST 28147-89 ดั้งเดิม เนื่องจากทั้งสองมีคลาสของคีย์ที่อ่อนแอ เป็นที่น่าสังเกตว่าในแง่ของ GOST © cryptanalysis งานจะทำซ้ำคำต่อคำในส่วนที่เกี่ยวข้องกับการเข้ารหัสของอัลกอริทึม GOST 28147-89 ซึ่งเป็นผลงานที่มีชื่อเสียงซึ่งตีพิมพ์ในปี 2000 (โดยไม่มีการอ้างอิงใด ๆ ถึงต้นฉบับ) สิ่งนี้ทำให้เกิดคำถามถึงความเป็นมืออาชีพของผู้เขียนงานและผลลัพธ์อื่น ๆ
งานนี้มีการเสนอการปรับเปลี่ยนอัลกอริธึมที่น่าสนใจมาก: ตาราง S\…S จำเป็นต้องแตกต่างออกไป ในแต่ละรอบของอัลกอริธึมจะต้องจัดเรียงใหม่ตามกฎหมายที่กำหนด การเปลี่ยนแปลงนี้อาจขึ้นอยู่กับคีย์เข้ารหัส หรืออาจเป็นความลับด้วย (เช่น เป็นส่วนหนึ่งของคีย์เข้ารหัสที่ใหญ่กว่าคีย์ 256 บิตดั้งเดิม) ตามที่ผู้เขียนระบุ ตัวเลือกทั้งสองนี้เพิ่มความต้านทานของอัลกอริธึมอย่างมีนัยสำคัญต่อการเข้ารหัสเชิงเส้นและดิฟเฟอเรนเชียล
และอีกหนึ่งการแก้ไขที่เกี่ยวข้องกับตารางการทดแทนได้รับในงานซึ่งหนึ่งในนั้น วิธีการที่เป็นไปได้การคำนวณตารางทดแทนตามคีย์เข้ารหัส ผู้เขียนงานสรุปว่าการพึ่งพาดังกล่าวทำให้อัลกอริทึมอ่อนแอลง เนื่องจากจะนำไปสู่การมีคีย์ที่อ่อนแอและทำให้เกิดช่องโหว่ของอัลกอริทึม
การวิเคราะห์อัลกอริทึมแบบเต็มรอบ
นอกจากนี้ยังมีการโจมตี GOST 28147-89 แบบเต็มรอบโดยไม่มีการดัดแปลงใด ๆ หนึ่งในคนแรก งานเปิดซึ่งมีการวิเคราะห์อัลกอริธึม ซึ่งเป็นผลงานที่มีชื่อเสียงซึ่งอุทิศให้กับการโจมตีที่ใช้ประโยชน์จากจุดอ่อนของขั้นตอนการขยายคีย์ของอัลกอริธึมการเข้ารหัสที่รู้จักกันดีจำนวนหนึ่ง โดยเฉพาะอย่างยิ่ง อัลกอริธึม GOST 28147-89 แบบเต็มรอบสามารถใช้งานไม่ได้โดยใช้การเข้ารหัสแบบดิฟเฟอเรนเชียลบนคีย์ที่เกี่ยวข้อง แต่จะต้องใช้เฉพาะในกรณีที่ใช้ตารางทดแทนที่ไม่รัดกุมเท่านั้น อัลกอริธึมเวอร์ชัน 24 รอบ (ซึ่งหายไป 8 รอบแรก) จะถูกเปิดในลักษณะเดียวกันกับตารางการแทนที่ใด ๆ แต่ตารางการแทนที่ที่แข็งแกร่ง (เช่นตารางที่ให้ไว้) ทำให้การโจมตีดังกล่าวไม่สามารถทำได้อย่างสมบูรณ์
นักวิทยาศาสตร์ในประเทศ A.G. Rostovtsev และ E.B. Makhovenko ในปี 2544 เสนอในงานของพวกเขาว่า วิธีการใหม่การเข้ารหัส (ตามที่ผู้เขียนระบุไว้ มีประสิทธิภาพมากกว่าการวิเคราะห์เชิงเส้นและเชิงอนุพันธ์อย่างมีนัยสำคัญ) โดยการสร้างฟังก์ชันวัตถุประสงค์จากข้อความธรรมดาที่รู้จัก ไซเฟอร์เท็กซ์ที่สอดคล้องกันและค่าคีย์ที่ต้องการ และค้นหาส่วนปลายสุดที่สอดคล้องกับมูลค่าที่แท้จริงของคีย์ พวกเขายังพบคีย์อ่อนจำนวนมากของอัลกอริทึม GOST 28147-89 ซึ่งทำให้สามารถเปิดอัลกอริทึมโดยใช้ข้อความธรรมดาที่เลือกเพียง 4 รายการและไซเฟอร์เท็กซ์ที่เกี่ยวข้องซึ่งมีความซับซ้อนค่อนข้างต่ำ การเข้ารหัสลับของอัลกอริธึมยังคงดำเนินต่อไปในการทำงาน
ในปี 2547 กลุ่มผู้เชี่ยวชาญจากเกาหลีเสนอการโจมตีโดยใช้การวิเคราะห์เชิงอนุพันธ์กับคีย์ที่เกี่ยวข้อง สามารถรับคีย์ลับ 12 บิต โดยมีความน่าจะเป็น 91.7% การโจมตีต้องใช้ข้อความธรรมดาที่เลือก 2 35 รายการและการดำเนินการเข้ารหัส 2 36 รายการ อย่างที่คุณเห็น การโจมตีนี้ไม่มีประโยชน์จริง ๆ สำหรับการทำลายอัลกอริธึม
). ในเวลาเดียวกัน ในสื่อรัสเซียและบล็อกของผู้ใช้ชาวรัสเซีย จำนวนบันทึกย่อเกี่ยวกับอัลกอริธึมนี้กำลังเพิ่มขึ้น: ทั้งครอบคลุมผลลัพธ์ของการโจมตีมาตรฐานรัสเซียที่มีระดับความน่าเชื่อถือที่แตกต่างกัน และมีความคิดเห็นเกี่ยวกับลักษณะการทำงานของมัน ผู้เขียน (และผู้อ่าน) บันทึกเหล่านี้มักจะรู้สึกว่าอัลกอริธึมการเข้ารหัสในประเทศนั้นล้าสมัย ช้า และมีช่องโหว่ที่ทำให้เสี่ยงต่อการถูกโจมตีมากกว่าอัลกอริธึมการเข้ารหัสจากต่างประเทศที่มีความยาวคีย์ใกล้เคียงกันอย่างมาก ด้วยบันทึกย่อชุดนี้เราต้องการ แบบฟอร์มที่สามารถเข้าถึงได้พูดคุยเกี่ยวกับสถานะปัจจุบันของมาตรฐานรัสเซีย ส่วนแรกจะครอบคลุมการโจมตี GOST 28147-89 ที่เป็นที่รู้จักในชุมชนการเข้ารหัสระดับนานาชาติและการประเมินความแข็งแกร่งในปัจจุบัน ในการเผยแพร่ในอนาคต เราจะพิจารณาคุณสมบัติของมาตรฐานให้ละเอียดยิ่งขึ้นจากมุมมองของความสามารถในการสร้างการใช้งานที่มีประสิทธิภาพ
Nicolas Courtois - "ผู้ยิ่งใหญ่และน่ากลัว"
เริ่มต้นด้วยเรื่องราวเกี่ยวกับกิจกรรมของ Nicolas Courtois ซึ่งเป็นผู้เขียนผลงานทั้งชุดเกี่ยวกับมาตรฐานการเข้ารหัสบล็อกของรัสเซีย ()
ในเดือนตุลาคม 2010 กระบวนการพิจารณาการรวมอัลกอริธึม GOST 28147-89 ไว้ในมาตรฐานสากล ISO/IEC 18033-3 ได้เริ่มขึ้น ในเดือนพฤษภาคม 2554 บทความของ Nicolas Courtois นักเข้ารหัสชื่อดังปรากฏในเอกสารอิเล็กทรอนิกส์ ePrint โดยมีทัศนคติที่ไม่ชัดเจนต่อเขาจากชุมชนการเข้ารหัสระดับโลก สิ่งพิมพ์ของ Courtois เป็นตัวอย่างที่น่าเศร้าของการบิดเบือนแนวคิดซึ่งไม่ได้เปิดเผยคุณสมบัติใหม่ใด ๆ ของวัตถุที่เป็นปัญหา แต่ด้วยการอ้างสิทธิ์ในความรู้สึกกระตุ้นให้เกิดการแพร่กระจายของความคิดเห็นที่ผิดพลาดเกี่ยวกับคุณสมบัติที่แท้จริงของวัตถุในสภาพแวดล้อมที่ไร้ความสามารถ
วิธีพีชคณิต
การให้เหตุผลของ Courtois ถูกสร้างขึ้นโดยใช้วิธีการเข้ารหัสสองประเภท: วิธีพีชคณิตและวิธีเชิงอนุพันธ์ ลองดูที่วิธีการระดับแรก
ด้วยวิธีที่เรียบง่าย วิธีการเข้ารหัสเชิงพีชคณิตสามารถอธิบายได้ว่าเป็นการรวบรวมและการแก้ระบบสมการขนาดใหญ่ ซึ่งแต่ละคำตอบนั้นสอดคล้องกับเป้าหมายของการเข้ารหัส (ตัวอย่างเช่น หากระบบถูกคอมไพล์โดยใช้คู่เดียว ของข้อความธรรมดาและไซเฟอร์เท็กซ์ ดังนั้นโซลูชันทั้งหมดของระบบนี้จะสอดคล้องกับคีย์ที่ข้อความธรรมดานี้ถูกแปลงเป็นข้อความนี้ถูกเข้ารหัส) นั่นคือในกรณีของปัญหาการเข้ารหัสลับของบล็อคไซเฟอร์ สาระสำคัญของวิธีพีชคณิตของการเข้ารหัสคือกุญแจถูกค้นพบอันเป็นผลมาจากการแก้ระบบสมการพหุนาม ปัญหาหลักคือการสามารถเขียนได้มากที่สุดเท่าที่จะเป็นไปได้โดยคำนึงถึงลักษณะของรหัสเฉพาะ ระบบที่เรียบง่ายเพื่อให้กระบวนการแก้ไขใช้เวลาน้อยที่สุด ต่อไปนี้จะมีบทบาทสำคัญโดยคุณสมบัติของการเข้ารหัสแต่ละรหัสที่กำลังวิเคราะห์
วิธีพีชคณิตที่ใช้โดยกูร์ตัวส์สามารถอธิบายโดยย่อได้ดังนี้ ในขั้นแรก คุณสมบัติดังกล่าวของ GOST 28147-89 จะถูกนำมาใช้เป็นจุดคงที่สำหรับส่วนหนึ่งของการแปลงการเข้ารหัส เช่นเดียวกับจุดสะท้อนที่เรียกว่า ด้วยคุณสมบัติเหล่านี้ คู่หลายคู่จึงถูกเลือกจากคู่ข้อความธรรมดา-ไซเฟอร์เท็กซ์ที่มีจำนวนมากเพียงพอ ซึ่งทำให้สามารถพิจารณาการแปลงไม่ได้ที่ 32 แต่เพียง 8 รอบเท่านั้น ขั้นตอนที่สองคือ จากผลลัพธ์ของการแปลงรอบ 8 รอบที่ได้รับในขั้นตอนแรก จะมีการสร้างระบบสมการไม่เชิงเส้นขึ้น โดยที่บิตคีย์ไม่เป็นที่รู้จัก ต่อไป ระบบนี้ได้รับการแก้ไขแล้ว (ฟังดูง่าย แต่ในความเป็นจริงเป็นส่วนที่ใช้เวลานานที่สุดของวิธีนี้ เนื่องจากระบบประกอบด้วยสมการที่ไม่เป็นเชิงเส้น)
ตามที่ระบุไว้ข้างต้น ไม่มีที่ใดในงานที่มีคำอธิบายโดยละเอียดและการวิเคราะห์ความซับซ้อนของขั้นตอนที่สองและขั้นตอนหลักในการกำหนดคีย์ มันเป็นความซับซ้อนของขั้นตอนที่สองที่กำหนดความซับซ้อนของวิธีการทั้งหมดโดยรวม ผู้เขียนกลับให้ "ข้อเท็จจริง" ที่มีชื่อเสียงโดยอาศัยการประเมินความเข้มข้นของแรงงานแทน "ข้อเท็จจริง" เหล่านี้กล่าวกันว่าอิงจากผลการทดลอง การวิเคราะห์ "ข้อเท็จจริง" จากงานของ Courtois โดยรวมมีให้ในผลงานของนักเขียนในประเทศ ผู้เขียนงานนี้ตั้งข้อสังเกตว่า "ข้อเท็จจริง" จำนวนมากของกูร์ตัวส์ที่นำเสนอโดยไม่มีหลักฐานใดๆ พบว่าเป็นเท็จในระหว่างการทดสอบเชิงทดลอง ผู้เขียนบทความได้ดำเนินการเพิ่มเติมและดำเนินการวิเคราะห์ความซับซ้อนของขั้นตอนที่สองตาม Courtois โดยใช้อัลกอริธึมและการประมาณการที่มีรากฐานมาอย่างดี การประมาณความซับซ้อนที่เกิดขึ้นแสดงให้เห็นว่าการโจมตีที่นำเสนอนั้นไม่เหมาะสมโดยสิ้นเชิง นอกจากผู้เขียนในประเทศแล้ว ปัญหาใหญ่ที่ Courtois มีกับการประเมินและเหตุผลของวิธีการของเขาก็ถูกบันทึกไว้เช่นกันในงาน
วิธีดิฟเฟอเรนเชียล
ลองพิจารณาวิธีที่สองของ Courtois ซึ่งใช้การวิเคราะห์เชิงอนุพันธ์
วิธีการทั่วไปของการวิเคราะห์เชิงอนุพันธ์นั้นขึ้นอยู่กับการใช้ประโยชน์จากคุณสมบัติของการแมปแบบไม่เชิงเส้นที่ใช้ในการเข้ารหัสแบบดั้งเดิมซึ่งเกี่ยวข้องกับอิทธิพลของค่าคีย์ต่อการพึ่งพาระหว่างความแตกต่างระหว่างคู่ของอินพุตและคู่ของค่าเอาต์พุตของการแมปเหล่านี้ . ให้เราอธิบายแนวคิดหลักของวิธีการวิเคราะห์เชิงอนุพันธ์ของการเข้ารหัสบล็อก โดยทั่วไป บล็อกไซเฟอร์จะแปลงข้อมูลอินพุตเป็นระยะโดยใช้จำนวนที่เรียกว่าการแปลงแบบกลม และการแปลงแบบแต่ละรอบจะไม่ใช้คีย์ทั้งหมด แต่ใช้เพียงบางส่วนเท่านั้น ลองพิจารณารหัสที่ "ถูกตัดทอน" เล็กน้อยซึ่งแตกต่างจากรหัสเดิมตรงที่ไม่มีรอบที่แล้ว สมมติว่ามีความเป็นไปได้ที่จะสร้างว่าการเข้ารหัสข้อความธรรมดาสองข้อความที่แตกต่างกันในตำแหน่งคงที่บางตำแหน่งโดยใช้การเข้ารหัสแบบ "ตัดทอน" มักจะส่งผลให้มีข้อความเข้ารหัสที่แตกต่างกันในตำแหน่งคงที่บางตำแหน่งด้วย คุณสมบัตินี้แสดงให้เห็นว่าการเข้ารหัสที่ "ถูกตัดทอน" มักจะทิ้งการพึ่งพาระหว่างข้อความธรรมดาบางส่วนกับผลลัพธ์ของการเข้ารหัส เพื่อที่จะกู้คืนส่วนหนึ่งของคีย์โดยใช้ข้อบกพร่องที่ชัดเจนนี้ จำเป็นต้องสามารถเข้ารหัสข้อความธรรมดาที่เลือกไว้ล่วงหน้าบนคีย์ที่เราต้องการกู้คืน (ที่เรียกว่า "การโจมตีข้อความธรรมดาที่เลือก") ที่จุดเริ่มต้นของขั้นตอน "การเปิดกุญแจ" ข้อความธรรมดาจำนวนหนึ่งจะถูกสร้างขึ้นแบบสุ่ม ซึ่งต่างกันในตำแหน่งคงที่เดียวกันเหล่านั้น ข้อความทั้งหมดได้รับการเข้ารหัสโดยใช้รหัส "เต็ม" คู่ไซเฟอร์เท็กซ์ที่ได้จะถูกนำมาใช้เพื่อกู้คืนบิตคีย์ที่ใช้ในการแปลงรอบที่แล้ว ดังต่อไปนี้ การใช้ค่าที่เลือกแบบสุ่มของคีย์บิตที่ต้องการ การแปลงที่ผกผันกับการแปลงรอบสุดท้ายจะถูกนำไปใช้กับไซเฟอร์เท็กซ์ทั้งหมด ในความเป็นจริง ถ้าเราเดาค่าที่ต้องการของบิตคีย์ เราจะได้ผลลัพธ์ของการเข้ารหัสที่ "ถูกตัดทอน" และถ้าเราไม่เดา เราจะ "เข้ารหัสข้อมูลมากยิ่งขึ้น" ซึ่งจะลดเพียง การพึ่งพาระหว่างบล็อกที่ระบุไว้ข้างต้น (ความแตกต่างอยู่ในตำแหน่งคงที่บางตำแหน่ง) กล่าวอีกนัยหนึ่งหากในบรรดาผลลัพธ์ของ "การประมวลผลเพิ่มเติม" ของไซเฟอร์เท็กซ์นั้นมีคู่จำนวนมากที่แตกต่างกันในตำแหน่งคงที่ที่เรารู้จักนั่นหมายความว่าเราได้เดาบิตคีย์ที่ต้องการแล้ว มิฉะนั้นจะมีคู่ดังกล่าวน้อยลงอย่างมาก เนื่องจากในแต่ละรอบมีการใช้คีย์เพียงบางส่วนเท่านั้น จึงมีจำนวนบิตที่ค้นหาไม่มาก (นั่นคือ บิตคีย์ที่ใช้ในรอบที่แล้ว) เท่ากับจำนวนบิตใน คีย์เต็มและคุณสามารถเรียงลำดับได้โดยทำตามขั้นตอนข้างต้นซ้ำ ในกรณีนี้เราจะต้องสะดุดกับความหมายที่ถูกต้องสักวันหนึ่งอย่างแน่นอน
จากคำอธิบายข้างต้น สิ่งที่สำคัญที่สุดในวิธีการวิเคราะห์เชิงอนุพันธ์คือจำนวนของตำแหน่งเหล่านั้นในข้อความธรรมดาและข้อความไซเฟอร์เท็กซ์ ซึ่งความแตกต่างมีบทบาทสำคัญในการกู้คืนบิตคีย์ การมีอยู่พื้นฐานของตำแหน่งเหล่านี้ตลอดจนชุดของตัวเลขนั้นขึ้นอยู่กับคุณสมบัติของการแปลงแบบไม่เชิงเส้นที่ใช้ในรหัสบล็อกใด ๆ โดยตรง (โดยปกติแล้ว "ความไม่เชิงเส้น" ทั้งหมดจะกระจุกตัวอยู่ในสิ่งที่เรียกว่า S-box หรือ โหนดทดแทน)
Courtois ใช้วิธีการหาอนุพันธ์แบบดัดแปลงเล็กน้อย โปรดทราบทันทีว่า Courtois ดำเนินการวิเคราะห์ S-boxes ที่แตกต่างจากปัจจุบันและจากที่เสนอใน ISO งานนี้จะให้คุณลักษณะที่แตกต่าง (ตัวเลขที่บล็อกควรแตกต่างกัน) สำหรับรอบจำนวนเล็กน้อย เหตุผลในการขยายคุณสมบัติออกไปอีกรอบก็เป็นไปตาม "ข้อเท็จจริง" ตามปกติ Courtois แสดงอีกครั้งโดยไม่มีอะไรอื่นนอกจากอำนาจของเขา ข้อสันนิษฐานที่ไม่ได้รับการสนับสนุนว่าการเปลี่ยน S-box จะไม่ส่งผลกระทบต่อการต่อต้านของ GOST 28147-89 ต่อการโจมตีของเขา (ในขณะที่ไม่ทราบสาเหตุ S-box จากร่างการทำงานครั้งแรกของ นอกเหนือจากมาตรฐาน ISO/IEC 18033-3 ไม่ได้รับการพิจารณา) การวิเคราะห์ที่ดำเนินการโดยผู้เขียนบทความแสดงให้เห็นว่าแม้ว่าเราจะนำ "ข้อเท็จจริง" ที่ไม่มีมูลของ Courtois เกี่ยวกับความศรัทธาและวิเคราะห์ GOST 28147-89 กับ S-block อื่น ๆ การโจมตีอีกครั้งกลับกลายเป็นว่าไม่ดีไปกว่าการค้นหาที่สมบูรณ์
การวิเคราะห์โดยละเอียดเกี่ยวกับผลงานของ Courtois พร้อมการพิสูจน์รายละเอียดของความไร้เหตุผลของข้อความทั้งหมดเกี่ยวกับการลดลงของการต่อต้านมาตรฐานรัสเซียได้ดำเนินการในงาน [,]
ในขณะเดียวกันแม้แต่ Courtois เองก็ยอมรับว่าการคำนวณขาดความแม่นยำโดยสิ้นเชิง! สไลด์ต่อไปนี้นำมาจากการนำเสนอของ Courtois ในส่วนประกาศสั้นๆ ของ FSE 2012
ควรสังเกตว่างานของ Courtois ก็ถูกวิพากษ์วิจารณ์จากนักวิจัยชาวต่างชาติซ้ำแล้วซ้ำเล่า ตัวอย่างเช่น งานของเขาในการสร้างการโจมตีบนอัลกอริธึมการเข้ารหัสบล็อก AES โดยใช้วิธี XSL มีข้อบกพร่องพื้นฐานเช่นเดียวกับงานในการวิเคราะห์มาตรฐานรัสเซีย: การประมาณความเข้มข้นของแรงงานส่วนใหญ่ปรากฏในข้อความไม่มีมูลความจริงและไม่มีหลักฐานโดยสิ้นเชิง - มีรายละเอียด คำวิจารณ์สามารถพบได้ในการทำงาน นอกจากนี้ Courtois เองก็ยอมรับว่ามีการปฏิเสธอย่างกว้างขวางในการเผยแพร่ผลงานของเขาในการประชุมการเข้ารหัสที่สำคัญและในวารสารที่ได้รับการตรวจสอบโดยผู้ทรงคุณวุฒิ ซึ่งมักจะทำให้เขาเหลือเพียงโอกาสที่จะพูดในส่วนประกาศสั้นๆ ตัวอย่างเช่น คุณสามารถอ่านเกี่ยวกับเรื่องนี้ได้ในส่วนที่ 3 ของงาน ต่อไปนี้เป็นคำพูดบางส่วนจาก Courtois ที่เกี่ยวข้องกับงานของเขา:
- “ฉันคิดว่าผู้ชม Asiacrypt จะไม่รู้สึกว่ามันน่าสนใจ” ผู้ตรวจสอบ Asiacrypt 2011
- “… มีปัญหาใหญ่ ใหญ่ ใหญ่: การโจมตีครั้งนี้ซึ่งเป็นส่วนสนับสนุนหลักของบทความนี้ได้รับการตีพิมพ์แล้วที่ FSE'54 (เป็นบทความที่ดีที่สุดด้วยซ้ำ) …” ผู้ตรวจสอบสำหรับ Crypto 2011
ดังนั้น ส่วนมืออาชีพของชุมชนการเข้ารหัสระหว่างประเทศจึงคำนึงถึงคุณภาพของงานของ Courtois โดยไม่มีข้อสงสัยใด ๆ มากไปกว่าคำพูดของผู้เชี่ยวชาญชาวรัสเซียบางคนเกี่ยวกับความสามารถในการถอดรหัส AES ในราคา 2,100 ซึ่งไม่ได้รับการยืนยันจากการคำนวณที่สอดคล้องกันใด ๆ หรือ “หลักฐาน” ล่าสุดของสมมติฐานสองหน้าเกี่ยวกับความไม่เท่าเทียมกันของคลาสความซับซ้อน P และ NP
การโจมตีโดย Isobe และ Dinur-Dankelman-Shamir
แนวคิดทั่วไปของการโจมตี Isobe () และ Dinur-Dankelman-Shamir (ต่อไปนี้: การโจมตี DDS) () คือการสร้างชุดข้อความธรรมดาแคบบางชุด (ขึ้นอยู่กับคีย์) ซึ่งเป็นการเปลี่ยนแปลงที่เทียบเท่ากับชุดนี้ ซึ่งมี โครงสร้างง่ายกว่าการแปลงการเข้ารหัสเอง ในกรณีของวิธี Isobe นี่คือชุดของบล็อก 64 บิต x โดยที่ F 8 -1 (Swap(F 8 (z))) = z โดยที่ z = F 16 (x) ถึง F 8 ( x) และ F 16 ( x) ระบุ 8 รอบแรกและ 16 รอบแรกของการเข้ารหัส GOST 28147-89 ตามลำดับผ่าน Swap - การดำเนินการของการสลับครึ่งหนึ่งของคำขนาด 64 ไบต์ หากรวมข้อความธรรมดาไว้ในชุดนี้ ผลลัพธ์ของการเปลี่ยนแปลงทั้ง 32 รอบของ GOST 28147-89 จะตรงกับผลลัพธ์ของรอบ 16 รอบ ซึ่งเป็นสิ่งที่ผู้เขียนหาประโยชน์จากการโจมตี ในกรณีของวิธี DDS นี่คือเซตของ x โดยที่ F 8 (x) = x (จุดคงที่ของการแปลง F 8) สำหรับข้อความธรรมดาจากชุดนี้ การแปลง GOST 28147-89 จะทำงานเหมือนกับ 8 รอบล่าสุดทุกประการ ซึ่งทำให้การวิเคราะห์ง่ายขึ้น
ความซับซ้อนของการโจมตี Isobe คือการดำเนินการเข้ารหัส 2,224 ครั้ง การโจมตี DDS คือ 2,192 ครั้ง อย่างไรก็ตาม คำถามทั้งหมดเกี่ยวกับว่าการโจมตี Isobe และ DDS ทำให้เกิดข้อจำกัดใหม่เกี่ยวกับเงื่อนไขในการใช้อัลกอริธึมของเราหรือไม่ จะถูกลบออกโดยการประเมินข้อกำหนดสำหรับปริมาณของเนื้อหาที่จำเป็นในการดำเนินการโจมตีแต่ละครั้ง: วิธี Isobe ต้องใช้ข้อความธรรมดา 2,32 คู่ และไซเฟอร์เท็กซ์และสำหรับวิธี DDS - 2 64 การประมวลผลปริมาณของวัสดุดังกล่าวโดยไม่ต้องเปลี่ยนคีย์เป็นสิ่งที่ยอมรับไม่ได้สำหรับการเข้ารหัสบล็อกใด ๆ ที่มีความยาวบล็อก 64: บนวัสดุเล่ม 2 32 โดยคำนึงถึงปัญหาวันเกิด (ดูตัวอย่าง ) ความน่าจะเป็นที่จะเกิดขึ้น ของการบล็อกซ้ำนั้นใกล้กับ 1/2 ซึ่งจะทำให้ผู้โจมตีสามารถสรุปข้อสรุปบางอย่างเกี่ยวกับข้อความธรรมดาจากไซเฟอร์เท็กซ์โดยไม่ต้องระบุคีย์ การมีข้อความธรรมดาและข้อความเข้ารหัส 2 64 คู่ที่ได้รับในคีย์เดียวทำให้ศัตรูสามารถดำเนินการเข้ารหัสและถอดรหัสโดยไม่ต้องรู้คีย์นี้เลย นี่เป็นเพราะคุณสมบัติเชิงผสมเพียงอย่างเดียว: ศัตรูในกรณีนี้มีตารางการแปลงการเข้ารหัสทั้งหมด สถานการณ์นี้ไม่สามารถยอมรับได้อย่างแน่นอนภายใต้เงื่อนไขการปฏิบัติงานที่สมเหตุสมผล ตัวอย่างเช่นใน CryptoPro CSPมีข้อจำกัดทางเทคนิคเกี่ยวกับปริมาณของเนื้อหาที่เข้ารหัส (ไม่มีการแปลงคีย์) ที่ 4 MB (ดู) ดังนั้นข้อห้ามที่เข้มงวดในการใช้คีย์บนวัสดุที่มีปริมาตรดังกล่าวจึงมีอยู่ในรหัสบล็อกใด ๆ ที่มีความยาวบล็อก 64 บิตดังนั้นการโจมตี Isobe และ DDS จึงไม่ทำให้ขอบเขตการใช้อัลกอริทึม GOST 28147-89 แคบลง ในขณะที่ยังคงรักษาความแข็งแกร่งที่เป็นไปได้สูงสุดไว้ที่ 2,256
แน่นอนว่าควรสังเกตว่านักวิจัย (Isobe และ Dinur-Dankelman-Shamir) ได้แสดงให้เห็นว่าคุณสมบัติบางอย่างของอัลกอริทึม GOST 28147-89 ทำให้สามารถค้นหาเส้นทางการวิเคราะห์ที่ผู้สร้างอัลกอริทึมไม่ได้นำมาพิจารณา รูปแบบที่เรียบง่ายของกำหนดการคีย์ ซึ่งช่วยให้งานการสร้างการใช้งานที่มีประสิทธิภาพง่ายขึ้นอย่างมาก ยังช่วยให้คีย์และข้อความธรรมดาบางกรณีที่หายากสามารถสร้างเพิ่มเติมได้ คำอธิบายง่ายๆการแปลงที่ดำเนินการโดยอัลกอริทึม
งานแสดงให้เห็นว่าคุณสมบัติเชิงลบของอัลกอริทึมสามารถกำจัดได้อย่างง่ายดายด้วยการรักษาคุณลักษณะการปฏิบัติงานไว้อย่างสมบูรณ์ แต่น่าเสียดายที่มันเป็นส่วนสำคัญของอัลกอริทึมในรูปแบบที่ใช้กันทั่วไป
โปรดทราบว่าความประมาทเลินเล่อบางประการในการประมาณความเข้มของแรงงานโดยเฉลี่ยก็มีอยู่ในงานของ Dinur, Dunkelman และ Shamir เช่นกัน ดังนั้น เมื่อสร้างการโจมตี จะไม่มีการให้ความสนใจตามประเด็นต่อไปนี้: สำหรับสัดส่วนที่สำคัญของคีย์ ชุดของข้อความธรรมดา x โดยที่ F 8 (x) = x ว่างเปล่า: อาจไม่มีจุดคงที่ เพื่อการเปลี่ยนแปลง 8 รอบ การมีอยู่ของจุดคงที่ยังขึ้นอยู่กับการเลือกโหนดทดแทนด้วย ดังนั้นการโจมตีนี้ใช้ได้กับโหนดและคีย์ทดแทนบางรายการเท่านั้น
นอกจากนี้ยังควรกล่าวถึงงานอีกชิ้นหนึ่งที่มีการโจมตี GOST 28147-89 ในเดือนกุมภาพันธ์ 2555 เอกสารอิเล็กทรอนิกส์ ePrint ของสมาคมการเข้ารหัสระหว่างประเทศปรากฏขึ้น เวอร์ชันอัปเดตบทความ (ลงวันที่พฤศจิกายน 2554) ซึ่งมีการโจมตีใหม่ใน GOST 28147-89 ลักษณะของการโจมตีที่นำเสนอมีดังนี้ ปริมาตรของวัสดุคือ 2 32 (เช่น Isobe) และความเข้มของแรงงานคือ 2 192 (เช่น DDS) ดังนั้น การโจมตีนี้จึงปรับปรุงการโจมตี DDS ที่บันทึกเวลาในแง่ของปริมาณวัสดุจาก 2 64 เป็น 2 32 เราสังเกตแยกต่างหากว่าผู้เขียนนำเสนอการคำนวณทั้งหมดโดยสุจริตโดยมีเหตุผลสำหรับความซับซ้อนและปริมาณของวัสดุ หลังจากผ่านไป 9 เดือน พบข้อผิดพลาดพื้นฐานในการคำนวณข้างต้น และตั้งแต่เดือนพฤศจิกายน 2555 บทความเวอร์ชันอัปเดตในไฟล์เก็บถาวรอิเล็กทรอนิกส์ไม่มีผลลัพธ์ใด ๆ ที่เกี่ยวข้องกับอัลกอริทึมภายในประเทศอีกต่อไป
การโจมตีโดยสมมติว่าผู้โจมตีรู้ "บางอย่าง" เกี่ยวกับกุญแจ
ในที่สุด เราทราบว่าในวรรณกรรมยังมีงานจำนวนหนึ่ง (ดูตัวอย่าง และ ) ที่อุทิศให้กับการโจมตี GOST 28147-89 ในรูปแบบที่เรียกว่าคีย์ที่เชื่อมโยง รุ่นนี้โดยพื้นฐานแล้วมีข้อสันนิษฐานว่าผู้โจมตีสามารถเข้าถึงการวิเคราะห์ไม่เพียงแต่กับคู่ของข้อความธรรมดาและเข้ารหัสโดยใช้คีย์ที่ต้องการ แต่ยังรวมไปถึงคู่ของข้อความธรรมดาและไซเฟอร์เท็กซ์ที่ได้รับโดยใช้คีย์ (ยังไม่ทราบ) ซึ่งแตกต่างจากคีย์ที่ต้องการในปกติที่รู้จัก วิธี (เช่น ที่ตำแหน่งบิตคงที่) ในแบบจำลองนี้เป็นไปได้จริง ๆ ที่จะได้รับผลลัพธ์ที่น่าสนใจเกี่ยวกับ GOST 28147-89 อย่างไรก็ตามในแบบจำลองนี้สามารถรับผลลัพธ์ที่แข็งแกร่งไม่น้อยเช่นซึ่งใช้กันอย่างแพร่หลายที่สุดในเครือข่ายสมัยใหม่ การใช้งานทั่วไปมาตรฐาน AES (ดูตัวอย่าง) โปรดทราบว่าเงื่อนไขในการโจมตีประเภทนี้เกิดขึ้นเมื่อใช้การเข้ารหัสในโปรโตคอลบางตัว ควรสังเกตว่าผลลัพธ์ประเภทนี้ถึงแม้จะมีความสนใจทางวิชาการอย่างไม่ต้องสงสัยจากมุมมองของการศึกษาคุณสมบัติของการแปลงการเข้ารหัส แต่จริงๆ แล้วไม่เกี่ยวข้องกับการปฏิบัติ ตัวอย่างเช่น เครื่องมือปกป้องข้อมูลการเข้ารหัสทั้งหมดที่ได้รับการรับรองโดย FSB ของรัสเซีย ตรงตามข้อกำหนดที่เข้มงวดที่สุดสำหรับแผนการสร้างคีย์การเข้ารหัส (ดูตัวอย่าง) ตามที่ระบุไว้ในผลการวิเคราะห์ หากมีคีย์ที่เกี่ยวข้อง 18 คีย์ และบล็อกข้อความธรรมดาและไซเฟอร์เท็กซ์ 2 10 คู่ ความซับซ้อนของการเปิดคีย์ส่วนตัวโดยสมบูรณ์ โดยมีความน่าจะเป็นที่จะสำเร็จ 1-10 -4 จริงๆ แล้วคือ 2 26 . อย่างไรก็ตาม หากเป็นไปตามข้อกำหนดข้างต้นสำหรับการพัฒนาเนื้อหาหลัก ความน่าจะเป็นในการค้นหาคีย์ดังกล่าวคือ 2 -4352 นั่นคือ 24,096 เท่าน้อยกว่าหากคุณพยายามเดารหัสลับในการลองครั้งแรก
งานที่เกี่ยวข้องกับโมเดลที่มีคีย์เชื่อมโยงยังรวมถึงงานซึ่งในปี 2010 ทำให้เกิดเสียงดังมากในสิ่งพิมพ์อิเล็กทรอนิกส์ของรัสเซียซึ่งไม่ต้องทนทุกข์ทรมานจากนิสัยในการตรวจสอบเนื้อหาอย่างรอบคอบในการแข่งขันเพื่อหาความรู้สึก ผลลัพธ์ที่นำเสนอไม่ได้รับการสนับสนุนจากการให้เหตุผลที่เข้มงวดใด ๆ แต่มีข้อความดังเกี่ยวกับความเป็นไปได้ของการแฮ็กมาตรฐานของรัฐ สหพันธรัฐรัสเซียบนแล็ปท็อปที่อ่อนแอในเวลาไม่กี่วินาที - โดยทั่วไปแล้วบทความนี้เขียนตามประเพณีที่ดีที่สุดของ Nicolas Courtois แต่ถึงแม้ว่าบทความจะไร้เหตุผลอย่างชัดเจนสำหรับผู้อ่านที่คุ้นเคยกับหลักการพื้นฐานของสิ่งพิมพ์ทางวิทยาศาสตร์ไม่มากก็น้อย แต่ก็สร้างความมั่นใจให้กับสาธารณชนชาวรัสเซียได้อย่างแม่นยำหลังจากงานที่ Rudsky เขียนข้อความที่มีรายละเอียดและละเอียดถี่ถ้วนซึ่งมีการวิเคราะห์ที่ครอบคลุม ของข้อบกพร่องนี้ บทความที่มีชื่ออธิบายตนเองว่า "เกี่ยวกับความสำคัญเชิงปฏิบัติเป็นศูนย์ของงาน" การโจมตีการกู้คืนคีย์ในรหัสบล็อก GOST เต็มรูปแบบพร้อมเวลาและหน่วยความจำเป็นศูนย์ "" ให้เหตุผลว่าความซับซ้อนโดยเฉลี่ยของวิธีการที่ระบุนั้นไม่น้อยกว่าความซับซ้อน ของการค้นหาที่สมบูรณ์
สารตกค้างแห้ง: ความทนทานในทางปฏิบัติคืออะไร?
โดยสรุป เรานำเสนอตารางที่มีข้อมูลเกี่ยวกับผลลัพธ์ทั้งหมดของการโจมตีที่ได้รับการอธิบายและสมเหตุสมผลอย่างเคร่งครัดใน GOST 28147-89 ซึ่งเป็นที่รู้จักในชุมชนการเข้ารหัสระหว่างประเทศ โปรดทราบว่าความซับซ้อนจะได้รับในการดำเนินการเข้ารหัสของอัลกอริทึม GOST 28147-89 และหน่วยความจำและวัสดุจะถูกระบุในบล็อกอัลกอริทึม (64 บิต = 8 ไบต์)
| จู่โจม | ความเข้มของแรงงาน | หน่วยความจำ | วัสดุที่จำเป็น |
| ไอโซเบะ | 2 224 | 2 64 | 2 32 |
| ดินัวร์-ดันเคลมาน-ชามีร์ FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Dinur-Dankelman-Shamir, FP, หน่วยความจำต่ำ | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| ดินัวร์-ดันเคลมาน-ชามีร์, การสะท้อน, 2DMitM | 2 236 | 2 19 | 2 32 |
| ค้นหาให้เสร็จสิ้น | 2 256 | 1 | 4 |
| จำนวนนาโนวินาทีนับตั้งแต่กำเนิดจักรวาล | 2 89 |
แม้จะมีวงจรการวิจัยที่ค่อนข้างใหญ่ในด้านความเสถียรของอัลกอริทึม GOST 28147-89 ช่วงเวลานี้ไม่มีการโจมตีเพียงครั้งเดียวที่สามารถทำได้ภายใต้ข้อกำหนดการปฏิบัติงานที่มีความยาวบล็อก 64 บิต ข้อจำกัดเกี่ยวกับปริมาณของวัสดุที่สามารถประมวลผลบนคีย์เดียวซึ่งเป็นผลมาจากพารามิเตอร์การเข้ารหัส (ความยาวบิตของคีย์ ความยาวบิตของบล็อก) มีความเข้มงวดมากกว่าปริมาณขั้นต่ำที่จำเป็นในการดำเนินการโจมตีที่ทราบในปัจจุบันอย่างมาก ด้วยเหตุนี้ เมื่อเป็นไปตามข้อกำหนดในการปฏิบัติงานที่มีอยู่ ไม่มีวิธีการเข้ารหัสใดที่เสนอจนถึงปัจจุบัน GOST 28147-89 ที่อนุญาตให้กำหนดคีย์ที่มีความเข้มข้นของแรงงานน้อยกว่าการค้นหาอย่างละเอียดถี่ถ้วน
