ความสำคัญของการชนกันของฟังก์ชันแฮช

สมมติว่าพบการชนกันในฟังก์ชันแฮช ดังนั้น H(x1) = H(x2)

อย่างไรก็ตาม x1 และ x2 เป็นทั้งชุดของบิตที่ดูเหมือน 'สุ่ม' ซึ่งไม่สื่อข้อความที่เชื่อมโยงกัน และไม่สามารถตีความในลักษณะที่สอดคล้องกันได้

การชนกันนี้ทำให้ฟังก์ชันแฮช H ไม่ปลอดภัยหรือไม่? ถ้าเป็นเช่นนั้นจะใช้ประโยชน์ได้อย่างไร แม้ว่าการชนกันที่ทราบจะไม่สื่อถึงข้อความที่สอดคล้องกัน ขอบใจ

ฉันชอบคิดว่าการเข้ารหัสเป็นโครงสร้างพื้นฐาน เราควรพยายามพัฒนาโครงสร้างพื้นฐานที่ลดจำนวนคำเตือนในการใช้งานให้น้อยที่สุดไม่ใช่หน้าที่ของการเข้ารหัสที่จะกำหนดว่าข้อความใดที่ "มีความหมาย" ในแอปพลิเคชันของคุณ คุณสามารถดูการชนที่เฉพาะเจาะจง $m_1, m_2$ และพูดด้วยความมั่นใจว่า ไม่ การประยุกต์ใช้ฟังก์ชันแฮชจะ เคย กำหนดความหมายให้กับสิ่งเหล่านี้ $m_1$ และ $m_2$?

ฟังก์ชันแฮชใดที่คุณควรใช้ ฟังก์ชันที่มีการรับประกัน "หายาก ใดๆ การชนกัน" หรือแบบที่มีการรับประกัน "เป็นการยากที่จะหาการชนกัน ยกเว้นบางครั้งในสตริงที่เป็น JPG ของเจอร์บิลและไฟล์ gzip ของเชคสเปียร์" ฉันไม่อยากขับรถที่มีสติกเกอร์เตือนว่า "รถอาจระเบิดถ้า คุณกำลังขับรถด้วยความเร็ว 88.1 ไมล์ต่อชั่วโมงโดยเปิดไฟเลี้ยวซ้ายและวิทยุปรับเป็น 88.1 FM แม้ว่าคำเตือนนั้นจะแคบลงก็ตาม และฉันจะไม่ทำ 3 อย่างพร้อมกัน

นั่นเป็นเหตุผลที่คำจำกัดความความปลอดภัยการเข้ารหัสพิจารณาการชนกัน ใดๆ สองข้อความที่ตอบสนอง $H(x_1) = H(x_2)$, การปลอมแปลงลายเซ็นบน ใดๆ ข้อความคือการโจมตี การเข้ารหัสของ ใดๆ ข้อความธรรมดาควรมีลักษณะที่แยกไม่ออก ฯลฯ หากคุณต้องการใช้การเข้ารหัสของคุณ ตรวจสอบให้แน่ใจว่าคุณพยายามรับประกันความปลอดภัยที่ทำให้ ทุกคน สบายใจ

เหตุผลประการที่สองที่ต้องกังวลเกี่ยวกับการชนกันแบบ "ไม่มีโครงสร้าง" $H$คือเมื่อพบแล้ว มักจะต้องใช้เวลาก่อนที่เทคนิคจะขยายออกไปเพื่อค้นหาการชนกันแบบ "มีโครงสร้าง" ตัวอย่างเช่น การค้นหาการชนที่มีโครงสร้างในฟังก์ชันสุ่ม (โดยใช้การโจมตีแบบคลาสสิกของ Yuval Collision Attack) มีความยากพอๆ กับการค้นหาการชนที่ไม่มีโครงสร้าง (โดยใช้กำลังเดรัจฉานมาตรฐานและขอบเขตวันเกิด)

H จะไม่ปลอดภัยหากได้รับ x1 ซึ่งเป็นไปได้ทางอัลกอริทึมที่จะได้รับ x2 ที่แตกต่างกันด้วยแฮชเดียวกัน เนื่องจากพื้นที่แฮชมีขนาดเล็กกว่าพื้นที่ข้อมูลมาก จึงมีโอกาสเกิดการชนกันได้เสมอ คำถามคือเราจะหามันเจอได้หรือไม่

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

ตอนนี้ให้พิจารณาว่าแม้สำหรับ SHA256 (อาจเป็นฟังก์ชันแฮชที่ได้รับการประเมินมากที่สุดตลอดกาล) ฉันก็ยังประมาณว่า น้อยกว่า $2^{90}$ เอาต์พุต ได้รับการคำนวณแล้ว (และค่าเหล่านั้นส่วนใหญ่ถูกละทิ้ง) สำหรับฟังก์ชันแฮชที่สร้างเอาต์พุต 256 บิตอย่างสม่ำเสมอโดยการสุ่มเพื่อให้เกิดการชนกัน $2^{90}$ ผลลัพธ์คือ เกี่ยวกับ ก $2^{-77}$ เหตุการณ์. เราจะต้องสรุปได้ว่า SHA256 ไม่ทำงานอย่างที่เราหวังไว้หรือว่าเราโชคร้ายอย่างเหลือเชื่อ (และไม่มีใครโชคร้ายขนาดนั้น)

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