DES ถูกถอดรหัสได้อย่างไร

DES มีคีย์ที่เป็นไปได้ 2^56 ค่า หรือประมาณ 72 พันล้านล้านค่า (72,057,594,037,927,936 ค่า) แม้ตัวเลขนี้ฟังดูมหาศาล แต่ก็เป็นพื้นที่ที่มีขอบเขตจำกัดและสามารถค้นหาอย่างเป็นระบบได้หากมีกำลังประมวลผลเพียงพอ

การค้นหาคีย์จนหมด (การลองทุกค่า) ต้องทดสอบพื้นที่คีย์โดยเฉลี่ยครึ่งหนึ่งก่อนจะพบคีย์ที่ถูกต้อง สำหรับ DES หมายถึงการถอดรหัสเพื่อทดลองประมาณ 2^55 ครั้ง โดยแต่ละครั้งใช้การดำเนินการเพียงไม่กี่ขั้นบนฮาร์ดแวร์สมัยใหม่

ในปี 1997 บริษัทความปลอดภัยข้อมูลอาร์เอสเอเสนอรางวัล 10,000 ดอลลาร์สำหรับผู้ที่ถอดข้อความที่เข้ารหัสด้วย DES ได้ ร็อก เวอร์เซอร์ประสานงานความพยายามด้านการประมวลผลแบบกระจายผ่านคอมพิวเตอร์ที่เชื่อมต่ออินเทอร์เน็ตหลายหมื่นเครื่อง

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

มูลนิธิแนวหน้าอิเล็กทรอนิกส์ EFF สร้างดีปแคร็กด้วยงบประมาณ 250,000 ดอลลาร์ในปี 1998 เครื่องนี้ประกอบด้วยวงจรรวมเฉพาะงาน 1,856 ชุด แต่ละชุดสามารถทดสอบคีย์ DES ได้ 2.5 ล้านค่าต่อวินาที ทำให้ดีปแคร็กมีอัตรารวมมากกว่า 90,000 ล้านค่าต่อวินาที

โดยเฉลี่ยแล้ว ดีปแคร็กสามารถค้นหาพื้นที่คีย์ DES ทั้งหมดจนหมดได้ภายในประมาณ 9 วัน นี่เป็นหลักฐานว่าผู้โจมตีที่มุ่งมั่นและลงทุน 250,000 ดอลลาร์สามารถทำลาย DES ได้ภายในเวลาไม่ถึงสองสัปดาห์

ในโจทย์ท้าทาย DES II-1 (กุมภาพันธ์ 1998) ดีปแคร็กทำงานร่วมกับเครือข่ายการประมวลผลอาสาสมัครของ distributed.net และทำลาย DES ได้ภายในเวลาเพียง 39 วัน ส่วนโจทย์ท้าทาย II-2 (กรกฎาคม 1998) ถูกทำลายภายใน 56 ชั่วโมง

การปรับปรุงอย่างรวดเร็วจาก 96 วันเหลือ 56 ชั่วโมงภายในเวลาเพียงหนึ่งปี แสดงให้เห็นว่าการพัฒนาฮาร์ดแวร์และการประสานงานที่ดีขึ้นสามารถเร่งการโจมตีแบบลองทุกค่าได้รวดเร็วเพียงใด

ในเดือนมกราคม 1999 ดีปแคร็กของ EFF ทำงานร่วมกับ distributed.net และทำลายโจทย์ท้าทาย DES III ได้ภายในเวลาเพียง 22 ชั่วโมง 15 นาที พร้อมคว้ารางวัล 10,000 ดอลลาร์จากบริษัทความปลอดภัยอาร์เอสเอ

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

Distributed.net จัดความพยายามด้านการประมวลผลโดยอาสาสมัคร โดยผู้ใช้อินเทอร์เน็ตทั่วไปบริจาคเวลาการประมวลผลของ CPU ให้กับโจทย์ท้าทาย DES ในช่วงที่มีผู้เข้าร่วมสูงสุด มีคอมพิวเตอร์หลายแสนเครื่องเข้าร่วม

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

การค้นหาคีย์จนหมดใช้ได้ผลเพราะการถอดรหัส DES แต่ละครั้งทำได้รวดเร็ว (ระดับไมโครวินาทีบนฮาร์ดแวร์) และเป็นอิสระต่อกัน ไม่มีการพึ่งพาระหว่างการทดสอบคีย์ N กับคีย์ N+1 ดังนั้นการค้นหาจึงสามารถแบ่งทำงานแบบขนานได้อย่างสมบูรณ์บนเครื่องจำนวนเท่าใดก็ได้

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

Eli Biham และ Adi Shamir เผยแพร่การวิเคราะห์รหัสเชิงผลต่างในปี 1990 ซึ่งเป็นเทคนิคที่ใช้ประโยชน์จากวิธีที่ความแตกต่างในคู่ข้อมูลนำเข้าแพร่ผ่านรอบต่าง ๆ ของรหัสลับ สำหรับ DES เทคนิคนี้ต้องใช้ข้อความธรรมดาที่เลือกประมาณ 2^47 ข้อความตามทฤษฎี

ภายหลังมีการเปิดเผยว่ากล่อง S ของ DES ได้รับการออกแบบโดยคำนึงถึงการต้านทานการวิเคราะห์รหัสเชิงผลต่าง ซึ่งบ่งชี้ว่า NSA รู้จักเทคนิคนี้ตั้งแต่ทศวรรษ 1970 การโจมตีนี้น่าประทับใจในทางทฤษฎี แต่ในทางปฏิบัติด้อยกว่าการลองทุกคีย์ด้วยฮาร์ดแวร์

Mitsuru Matsui เผยแพร่การวิเคราะห์รหัสเชิงเส้นในปี 1993 โดยต้องใช้ข้อความธรรมดาที่ทราบ 2^43 ข้อความเพื่อโจมตี DES เขานำการโจมตีนี้ไปใช้งานจริงและทำลาย DES ได้ในการทดลองในปี 1994 ซึ่งยืนยันการวิเคราะห์ทางทฤษฎี

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

การวิเคราะห์รหัสเชิงผลต่างได้รับการเผยแพร่ในปี 1990 แต่ต้องใช้ข้อความธรรมดาที่เลือก ซึ่งไม่สะดวกในสถานการณ์จริงส่วนใหญ่ ส่วนการวิเคราะห์รหัสเชิงเส้นได้รับการเผยแพร่ในปี 1993 และใช้ข้อความธรรมดาที่ทราบได้ แต่ต้องใช้ถึง 2^43 ข้อความ

การลองทุกค่าด้วยฮาร์ดแวร์ (ดีปแคร็ก) ทำลาย DES ได้ภายใน 22 ชั่วโมงในปี 1999 ในทางปฏิบัติ การโจมตีด้วยฮาร์ดแวร์สร้างความเสียหายรุนแรงกว่าความก้าวหน้าด้านการวิเคราะห์รหัสลับเชิงทฤษฎี เพราะไม่ต้องใช้คู่ข้อความธรรมดาและข้อความเข้ารหัสแบบพิเศษใด ๆ เลย

การทำลาย DES ที่เปิดเผยต่อสาธารณะและมีเอกสารยืนยันส่งผลต่อนโยบายในทันที NIST เริ่มกระบวนการประกวดคัดเลือกเออีเอสในปี 1997 ซึ่งเป็นปีเดียวกับที่โจทย์ท้าทาย DES I ประสบความสำเร็จ การประกวดนี้ออกแบบมาโดยเฉพาะเพื่อหลีกเลี่ยงจุดอ่อนของกระบวนการทำให้ DES เป็นมาตรฐาน

ธนาคารและหน่วยงานรัฐบาลเริ่มเปลี่ยนไปใช้ DES สามชั้นเป็นมาตรการชั่วคราวระหว่างการพัฒนาเออีเอส เส้นเวลาการทำลาย DES เป็นตัวกำหนดโดยตรงถึงความเร่งด่วนและกรอบเวลาของความพยายามนำเออีเอสมาใช้

DES ถูกทำลายได้เร็วขึ้นเรื่อย ๆ ได้แก่ 96 วันในปี 1997, 56 ชั่วโมงในปี 1998 และ 22 ชั่วโมงในปี 1999 ดีปแคร็กมูลค่า 250,000 ดอลลาร์ของ EFF ใช้วงจรรวมเฉพาะงานเพื่อทดสอบคีย์ 90,000 ล้านค่าต่อวินาที

ทั้งการวิเคราะห์รหัสเชิงผลต่าง (ใช้ข้อความธรรมดาที่เลือก 2^47 ข้อความ) และการวิเคราะห์รหัสเชิงเส้น (ใช้ข้อความธรรมดาที่ทราบ 2^43 ข้อความ) สามารถทำลาย DES ได้ในทางทฤษฎีเช่นกัน แต่การลองทุกค่าด้วยฮาร์ดแวร์เป็นวิธีที่ทำลาย DES ได้จริง การทำลายภายใน 22 ชั่วโมงยุติการใช้งาน DES ในฐานะรหัสลับที่ยังเหมาะสมต่อการใช้งาน