การโจมตีแบบวันเกิดและการชนกัน

ในกลุ่มคน 23 คน ความน่าจะเป็นที่คนสองคนมีวันเกิดตรงกันมีค่ามากกว่า 50% หากมี 70 คน ค่านี้จะมากกว่า 99.9% ในทางคณิตศาสตร์ สำหรับเซตขนาด N ความน่าจะเป็นที่จะเกิดการชนกันจะเกิน 50% หลังสุ่มตัวอย่างประมาณ √N รายการ นี่คือขอบเขตวันเกิด

สำหรับฟังก์ชันแฮชขนาด n บิต จะพบการชนกัน (H(m1) = H(m2), m1 ≠ m2) ได้จากการทดลองสุ่มประมาณ 2^{n/2} ครั้ง สำหรับ SHA-256 (256 บิต) การหาการชนกันต้องใช้การคำนวณประมาณ 2^{128} ครั้ง ซึ่งทำไม่ได้ในทางปฏิบัติ สำหรับ MD5 (128 บิต) ต้องใช้ประมาณ 2^{64} ครั้ง ซึ่งเริ่มมีความเป็นไปได้

การค้นหาการชนกันทั่วไป: สร้างข้อความสุ่มจำนวน 2^{n/2} รายการ คำนวณแฮช เรียงตามค่าแฮช แล้วค้นหารายการซ้ำ ใช้หน่วยความจำ O(2^{n/2}) อัลกอริทึม Rho (การค้นหาวงจรของ Floyd) ลดการใช้หน่วยความจำเหลือ O(1) โดยใช้เวลาเท่าเดิม การค้นหาการชนกันแบบขนานของ van Oorschot-Wiener ช่วยลดเวลาได้ด้วยฮาร์ดแวร์

Wang และคณะพบการชนกันของ MD5 ที่ใช้งานได้จริงในปี 2004 โดยใช้การวิเคราะห์รหัสลับเชิงผลต่าง ไม่ใช่การโจมตีแบบวันเกิด ข้อความขนาด 1024 บิตสองรายการที่แตกต่างกันสามารถมีแฮช MD5 เหมือนกันได้ภายในไม่กี่วินาที การชนกันแบบเลือกคำนำหน้าและ Hertzbleed ทำให้สร้างการชนกันของใบรับรองได้ MD5 ถูกทำลายอย่างสมบูรณ์ในด้านความต้านทานต่อการชนกัน

วิธีที่มีประสิทธิภาพยิ่งกว่า: เมื่อกำหนดคำนำหน้าสองค่าโดยพลการ P1, P2 ให้ค้นหาส่วนต่อท้าย S1, S2 ที่ทำให้ H(P1||S1) = H(P2||S2) Stevens และคณะพบการชนกันของ MD5 แบบเลือกคำนำหน้าในปี 2017 วิธีนี้ใช้สร้างใบรับรอง CA ที่เป็นอันตรายพร้อมลายเซ็น MD5 ที่ถูกต้อง และทำให้เลิกใช้ MD5 กับใบรับรอง

SHAttered ของ Google ในปี 2017 เป็นการชนกันของ SHA-1 ที่ใช้งานได้จริงครั้งแรก ไฟล์ PDF สองไฟล์ที่แตกต่างกันมีแฮช SHA-1 เหมือนกัน ต้องใช้การบีบอัด SHA-1 จำนวน 2^{63.1} ครั้ง ซึ่งเทียบเท่ากับเวลา 6,500 ปีของ CPU และ 110 ปีของ GPU มีค่าใช้จ่ายประมาณ 110,000 ดอลลาร์สหรัฐ เบราว์เซอร์ยกเลิกการรองรับใบรับรอง SHA-1 ในปี 2017

สำหรับฟังก์ชันแฮชแบบ Merkle-Damgard (MD5, SHA-1, SHA-2) หากทราบ H(m) ก็สามารถคำนวณ H(m||padding||m') ได้โดยไม่ต้องทราบ m ซึ่งทำลายการสร้าง MAC เช่น H(secret||message) วิธีแก้คือใช้ HMAC (ซึ่งใช้ข้อมูลเติมเต็มด้านในและด้านนอก) หรือ SHA-3 (โครงสร้าง sponge ซึ่งไม่เสี่ยงต่อการขยายความยาว)

ความต้านทานการชนกัน: ค้นหาข้อความสองข้อความที่แตกต่างกันแต่มีค่าแฮชเดียวกัน (ใช้ความพยายาม 2^{n/2}) ความต้านทานการหาอินพุตต้นทางที่สอง: เมื่อกำหนด m ให้ค้นหา m' ≠ m ที่มีค่าแฮชเดียวกัน (ใช้ความพยายาม 2^n) ความต้านทานการหาอินพุตต้นทาง: ค้นหาข้อความใด ๆ ที่ให้ค่าแฮชที่กำหนด (ใช้ความพยายาม 2^n) การต้านทานการชนกันอ่อนแอที่สุดเสมอ

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

Joux (2004): สำหรับแฮชแบบ Merkle-Damgard การค้นหาการชนกันของ 2^k ข้อความ (ข้อความ 2^k รายการที่มีค่าแฮชเดียวกัน) ใช้ความพยายามเพียง k เท่าของการค้นหาการชนกันครั้งเดียว ไม่ใช่ 2^k เท่า ซึ่งทำให้ช่องโหว่ในแฮชที่นำมาต่อกันทวีความรุนแรงขึ้น (H1(m)||H2(m) ไม่ได้แข็งแกร่งอย่างที่คิด)

ใช้ SHA-256 หรือ SHA-3 สำหรับการแฮชที่ต้านทานการชนกัน หลีกเลี่ยง MD5 และ SHA-1 เพื่อวัตถุประสงค์ด้านความปลอดภัยทุกกรณี สำหรับ MAC ให้ใช้ HMAC-SHA-256 หรือ HMAC-SHA-3 สำหรับการแฮชรหัสผ่าน ให้ใช้ Argon2 (ไม่ใช่ SHA-2 โดยตรง) ใช้ SHA-3 เสมอเมื่อต้องการการต้านทานการขยายความยาว

ต้องคำนวณค่าแฮชประมาณกี่ครั้งจึงจะค้นหาการชนกันในฟังก์ชันแฮชขนาด n บิตได้

การโจมตีแบบวันเกิดค้นหาการชนกันของค่าแฮชได้ด้วยความพยายาม 2^{n/2} MD5 มีการชนกันแบบคำนำหน้าที่เลือกได้ในทางปฏิบัติ และ SHA-1 ถูกทำลายได้ในปี 2017 การโจมตีแบบขยายความยาวทำลาย MAC แบบ H(key||msg) ที่สร้างอย่างไร้การป้องกัน ใช้ SHA-256 หรือ SHA-3 และใช้ HMAC สำหรับการยืนยันข้อความ ถัดไป: การโจมตีแบบพบกันตรงกลาง