ความเป็นไปได้สูงแค่ไหนที่แฮชจะชนกันในไฟล์ข้อความ?

เมื่อใช้ก $n$-บิตแฮช ความน่าจะเป็นที่ บังเอิญ การเปลี่ยนแปลงไปตรวจไม่พบเป็นเรื่องเกี่ยวกับ $2^{-n}$ (สำหรับแฮชที่บรรลุเป้าหมายการออกแบบเพียงเล็กน้อย)

หากมีใครใช้เทคนิคนี้หนึ่งครั้งต่อวินาทีเป็นเวลา 100 ปี ด้วยแฮช 128 บิตเช่น MD5 ความน่าจะเป็นนั้นก็คือ $36524\times86400\times2^{-128}\ประมาณ2^{31.6-128}=2^{-96.4}$.

เรารู้จัก 44 หลุมอุกกาบาต บนโลกที่เกิดจากการชนกับเทห์ฟากฟ้าที่มีขนาดใหญ่พอที่จะเป็นผลกระทบครั้งใหญ่ต่ออารยธรรมปัจจุบันของเรา ซึ่งเกิดขึ้นในช่วง 2.3G ปีที่ผ่านมา ดังนั้นความน่าจะเป็นของเหตุการณ์ที่ก่อกวนอารยธรรมภายในกรอบเวลา 100 ปีนี้ อย่างน้อยที่สุด $44\times100/(2.3\times10^9)\ประมาณ2^{-19}$ (และฉันมองโลกในแง่ดีที่นี่: การลบล้างนิวเคลียร์ที่มนุษย์สร้างขึ้นมีความเป็นไปได้มากกว่า) ดังนั้นจึงไม่มีประเด็นใดที่จะต้องกังวลเกี่ยวกับความน่าจะเป็นเท่านั้น $2^{-96.4}$.

แต่ในการเข้ารหัส เราพิจารณา ฝ่ายตรงข้าม ที่พยายามเอาชนะเราอย่างแข็งขัน ถ้าเราใช้แฮช 128 บิต (เช่น MD5) และสร้างไฟล์จำนวนมาก (เช่น $2^{31.6}$ ดังข้างต้นซึ่งแฮชพอดีกับแท่ง USB ขนาด 64GB) และมีศัตรูที่ทรงพลังด้วยประเภทของทรัพยากรที่เสียไปในการขุด bitcoin จากนั้นความเป็นไปได้ที่พวกเขาจะพบไฟล์ที่มีแฮชเดียวกันกับไฟล์ของเรานั้นมีขนาดใหญ่มาก (แม้ว่าจะไม่ใช่ประเด็น คงจะรำคาญ)

อันตรายที่เกิดขึ้นจริงในทันทีจะเกิดขึ้นหากเราถือว่าผู้ไม่หวังดีสามารถเจาะซอฟต์แวร์ที่เราใช้เพื่อบันทึกไฟล์ (เช่น PDF) ของเราได้ และเรายังโง่พอที่จะใช้ MD5 หรือ SHA-1 ซึ่งการต่อต้านการชนกันของคำนำหน้าที่เลือกไว้นั้นเสียหาย ตอนนี้ผู้ไม่หวังดีสามารถสร้างไฟล์ที่มี MD5 หรือ SHA-1 เดียวกันกับของเราได้อย่างง่ายดาย ซึ่งดูเหมือนว่าผู้ไม่หวังดีเห็นว่าเหมาะสมเมื่อดูอย่างไร

เพื่อจุดประสงค์ของฉัน (แค่ตรวจสอบความถูกต้องของข้อมูล) คุณจะแนะนำอะไร

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

กลับไปที่การเข้ารหัสและเป็นแบบจำลองที่เป็นปฏิปักษ์: ควรใช้แฮชที่ไม่เสียหายเช่นเดียวกับตระกูล SHA-2 หรือ SHA-3 SHA-256 มีความปลอดภัยเพียงพอสำหรับอย่างน้อยหนึ่งทศวรรษ แต่ SHA-512 จะคงอยู่ตลอดไป (ในระดับมนุษย์) แม้ว่าเราจะคิดว่าเราเคยได้รับ SHA-512 ก็ตาม คอมพิวเตอร์ควอนตัมที่เกี่ยวข้องกับการเข้ารหัสลับ.

¹ ฉันกำลังพูดถึงพลังงานไฟฟ้าโดยรวมและวงจรรวมที่สูญเสียไป อย่างไรก็ตาม ส่วนใหญ่จะไม่มีไว้สำหรับการแฮชแบบขนานขนาดใหญ่กับ ASIC เช่นเดียวกับการขุด bitcoin มันจะเป็นหน่วยความจำที่รวดเร็วที่จัดระเบียบสำหรับการค้นหา เนื่องจากการประมวลผลแฮช MD5 มีค่าใช้จ่ายต่ำเมื่อเทียบกับการจับคู่กับแฮช $2^{\ประมาณ31.6}$ แฮชเป้าหมาย