การโจมตีแบบเดารหัสทุกความเป็นไปได้ทำงานอย่างไร

การโจมตีแบบลองครบทุกค่ากับรหัสเข้ารหัสจะลองคีย์ที่เป็นไปได้ทุกค่าจนกว่าจะพบคีย์ที่ถูกต้อง สำหรับคีย์ขนาด n บิต จะมีคีย์ที่เป็นไปได้ 2^n ค่า คีย์ขนาด 3 บิตมีความเป็นไปได้เพียง 8 ค่า ส่วนคีย์ขนาด 56 บิตมีมากกว่า 72 ควอดริลเลียนค่า การป้องกันพื้นฐานจากการลองครบทุกค่าคือการเลือกคีย์ให้มีขนาดใหญ่พอจนการค้นหาครบทุกค่าไม่สามารถคำนวณให้เสร็จได้จริงภายในกรอบเวลาที่มีความหมาย

DES (มาตรฐานการเข้ารหัสข้อมูล) ใช้คีย์ขนาด 56 บิต ทำให้มีพื้นที่คีย์ประมาณ 7.2 * 10^16 ค่า ในปี 1977 ตัวเลขนี้ดูมหาศาล แต่ในปี 1998 เครื่องดีปแคร็กของ EFF สามารถถอด DES ได้ภายใน 56 ชั่วโมงด้วยงบประมาณ 250,000 ดอลลาร์ ในปี 2006 คลัสเตอร์เฉพาะทางสามารถถอด DES ได้ภายในเวลาไม่ถึง 9 วันด้วยค่าใช้จ่ายต่ำกว่า 10,000 ดอลลาร์ บทเรียนมีความชัดเจนว่า 56 บิตไม่ใช่การรักษาความปลอดภัยที่เพียงพออีกต่อไปเมื่อต้องรับมือกับผู้โจมตีที่มีแรงจูงใจ

เออีเอส-128 ใช้คีย์ขนาด 128 บิต ทำให้มีคีย์ที่เป็นไปได้ 2^128 ค่า หรือประมาณ 3.4 * 10^38 ค่า หากอะตอมทุกอะตอมในจักรวาลที่สังเกตได้เป็นคอมพิวเตอร์ที่ทดสอบคีย์หนึ่งพันล้านค่าต่อวินาทีมาตั้งแต่บิกแบง การค้นหาก็ยังห่างไกลจากการเสร็จสิ้น แม้จะมีฮาร์ดแวร์ในอนาคตที่เร็วขึ้นแบบเลขชี้กำลัง คีย์ขนาด 128 บิตก็คาดว่าจะยังคงปลอดภัยจากการลองครบทุกค่าแบบดั้งเดิมไปอีกนานในอนาคตที่คาดการณ์ได้

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

GPU สมัยใหม่มีแกนประมวลผลแบบขนานหลายพันแกน ซึ่งปรับให้เหมาะกับการคำนวณเลขทศนิยม แฮชแคต ซึ่งเป็นเครื่องมือถอดรหัสแฮชด้วย GPU ชั้นนำ สามารถทดสอบแฮชเอ็มดีไฟฟ์ได้มากกว่า 100,000 ล้านรายการต่อวินาทีบน GPU ระดับสูงเพียงหนึ่งตัว ชุดเครื่องที่มี GPU แปดตัวสามารถทดสอบรหัสที่เป็นไปได้มากกว่า 800,000 ล้านรายการต่อวินาที ความเร็วนี้ทำให้รหัสผ่านที่เลือกมาไม่ดีและฟังก์ชันแฮชที่อ่อนแอเสี่ยงต่อการถอดรหัสแบบออฟไลน์อย่างรวดเร็ว

วงจรรวมเฉพาะงานคือชิปที่ออกแบบมาเพื่อการคำนวณเพียงอย่างเดียว นักขุดบิตคอยน์ใช้วงจรรวมเฉพาะงานที่คำนวณแฮช SHA-256 ได้ด้วยอัตราหลายสิบเทราแฮชต่อวินาที ซึ่งเร็วกว่าทุก GPU อย่างมาก แม้ว่าวงจรรวมเฉพาะงานสำหรับบิตคอยน์จะคำนวณการทำงานที่แตกต่างจากการถอดรหัสรหัสผ่าน แต่หลักการยังเหมือนกัน นั่นคือฮาร์ดแวร์ที่สร้างมาเฉพาะงานให้ความเร็วเพิ่มขึ้นหลายระดับขนาดเมื่อเทียบกับฮาร์ดแวร์อเนกประสงค์สำหรับการคำนวณด้านการเข้ารหัสลับบางประเภท

กฎของมัวร์ระบุว่าความหนาแน่นของทรานซิสเตอร์เพิ่มขึ้นเป็นสองเท่าโดยประมาณทุกสองปี ซึ่งในอดีตทำให้กำลังประมวลผลเพิ่มขึ้นในระดับใกล้เคียงกัน ความยาวคีย์ที่ถือว่าปลอดภัยในปัจจุบันต้องยังคงปลอดภัยได้ตลอดหลายทศวรรษของการพัฒนาฮาร์ดแวร์ในอนาคต ดังนั้นคำแนะนำด้านความปลอดภัยจึงเผื่อระยะปลอดภัยไว้มาก เออีเอส-128 จะต้องมีความเร็วในการคำนวณเพิ่มขึ้น 2^64 เท่าจึงจะเสี่ยงต่อการลองคีย์ทุกความเป็นไปได้แบบดั้งเดิม ซึ่งไกลเกินกว่าการคาดการณ์ตามกฎของมัวร์ที่มีความเป็นไปได้ใด ๆ

NIST SP 800-57 กำหนดระดับความปลอดภัยสำหรับอัลกอริทึมการเข้ารหัสลับ ความปลอดภัยระดับ 112 บิตเป็นขั้นต่ำในปัจจุบันสำหรับระบบใหม่ แนะนำให้ใช้ความปลอดภัยระดับ 128 บิตเพื่อการป้องกันระยะยาว คีย์สมมาตรขนาด 256 บิตให้ระยะเผื่อความปลอดภัยที่สูงกว่าภัยคุกคามจากการประมวลผลแบบดั้งเดิมที่คาดการณ์ได้ในปัจจุบัน NIST ไม่แนะนำระดับความปลอดภัย 80 บิตหรือต่ำกว่า เนื่องจากถือว่าไม่เพียงพอสำหรับแอปพลิเคชันใหม่ใด ๆ

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

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

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

อัลกอริทึมควอนตัมของโกรเวอร์ส่งผลต่อระดับความปลอดภัยที่มีผลจริงของเออีเอส-128 อย่างไร

การลองทุกความเป็นไปได้จะทดสอบคีย์ที่เป็นไปได้ทุกคีย์ ระบบจะปลอดภัยได้ก็ต่อเมื่อมีพื้นที่คีย์ใหญ่เกินกว่าจะไล่ตรวจสอบได้ในทางปฏิบัติ DES ขนาด 56 บิตถูกทำลายได้ในปี 1998 เออีเอส-128 ที่มีคีย์ 2^128 แบบไม่สามารถโจมตีด้วยคอมพิวเตอร์แบบดั้งเดิมได้ในทางปฏิบัติ คลัสเตอร์ GPU สามารถถอดรหัสแฮชแบบออฟไลน์ได้หลายแสนล้านรายการต่อวินาที อัลกอริทึมควอนตัมของโกรเวอร์ลดจำนวนบิตความปลอดภัยลงครึ่งหนึ่ง จึงต้องใช้คีย์ขนาด 256 บิตเพื่อให้มีความปลอดภัยหลังควอนตัมระดับ 128 บิต NIST แนะนำความปลอดภัยขั้นต่ำระดับ 128 บิตสำหรับระบบใหม่