What is Hash Collision?

Hash Collision คือเมื่อข้อมูลสองชุดที่ต่างกันสร้างผลลัพธ์ hash ที่เหมือนกันเป๊ะ ลองนึกถึงกุญแจสองดอกที่เปิดล็อกดิจิทัลแบบเดียวกันได้ ความหายาก แต่ถ้ามาเจอกับอัลกอริทึมที่ผิดพลาด ก็กลายเป็นเรื่องราวได้

Myth

“หากมีการชนกันหนึ่งครั้งก็เหมือนทุกอย่างพังทลาย” ไม่ใช่ทั้งหมดแบบนั้น นักอัลกอริทึมที่เข้มแข็งถูกออกแบบมาให้ Hash Collision ที่ใช้งานได้จริงน้อยมาก และระบบสมัยใหม่มีชั้นเพิ่มเติมเพื่อไม่ให้จุดบกพร่องเดียวทำให้บ้านล่มสลาย

How Hash Collision works

คิดว่า hash เป็นป้ายชื่อขนาดเล็กสำหรับข้อมูลขนาดใหญ่ นี่คือทัวร์สั้นๆ จาก input ถึง oops.

Input: คุณเริ่มด้วยข้อความ ใดก็ได้ ไฟล์ หรือธุรกรรม
Hash: ฟังก์ชันจากครอบครัว cryptographic hash functions เปลี่ยน input นั้นให้เป็นสตริงความยาวคงที่
Clash: เนื่องจากผลลัพธ์มีจำกัด แต่ input มีไม่จำกัด สอง input ที่ต่างกันอาจ map ไปยัง output เดียวกัน
Attack: ภัยคุกคามร้ายแรงคือเมื่อคนร้ายสามารถออกแบบสอง input ที่ต่างกันให้ชนกัน จากนั้นสลับทีละอันกับอีกอัน
Defense: อัลกอริทึมที่ดีทำให้การค้นหานั้นมีค่าใช้จ่ายเชิงคอมพิวเตอร์สูงมาก ดังนั้นการเดาแบบสุ่มจึงเปลืองเวลาและเงิน

ใช่ นี่คือแนวคิด

Why Hash Collision Matters

ทำไมคุณควรแคร์เกี่ยวกับมุมมืดๆ ของคณิตศาสตร์และโค้ดนี้?

Benefit: ความทนทานที่แข็งแกร่งทำให้ labels ของข้อมูลของคุณไม่ซ้ำซ้อน ซึ่งหมายถึงช่องว่างน้อยลงสำหรับเทคนิคลับๆ
Perspective: การชนกันเป็นภัยคุกคามความสมบูรณ์ของสิ่งต่างๆ เช่น blockchain technology, การอัปเดตซอฟต์แวร์, และการตรวจสอบไฟล์
Relevance: คุณจะพบมันใน wallets, exchanges, proofs, และ audit tools ที่เชื่อมั่นในการ equality ของ hash

Tip

เมื่อมีตัวเลือกนั้น เลือก schemes ที่ stack defenses เหมือน Double Hashing, และยึดอัลกอริทึมที่ผ่านการทบทวนอย่างกว้างขวางที่มี output ยาว

Key Characteristics of Hash Collision

อะไรที่ทำให้ปรากฏการณ์นี้โดดเด่นและน่าจดจำ:

Inevitable: ด้วย outputs ที่จำกัดและ inputs ที่ไร้ขอบเขต คู่ใดคู่หนึ่งจะชนกันตามหลัก pigeonhole principle
Hard: สำหรับ hash สมัยใหม่ การค้นหาการชนแบบตั้งใจถูกออกแบบให้ต้องใช้งานเชิงคอมพิวเตอร์อย่างทรหด
Signatures: หลาย digital signatures ลงนาม hash ดังนั้นการต้านทานการชนกันจะปกป้องผู้เซ็นจากข้อความหลอกลวง

How is Hash Collision calculated?

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

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

ตัวอย่าง: หาก k เท่ากับ 256 จำนวนการลองที่ต้องใช้มีขนาดมหาศาล นี่คือเหตุผลที่การ brute forcing ไปยังการชนจึงไม่ใช่งานในวันหยุด

Variations

รสชาติที่แตกต่างกันปรากฏในงานวิจัยและการโจมตี:

Collision: input สองตัวที่แตกต่างกันร่วมกันมี hash เหมือนกัน
Second: ให้ input หนึ่งอัน หาอันอื่นที่ตรงกับ hash ของมัน
Preimage: ให้ hash หา input ใดๆ ที่ map ไปหามัน
Prefix: collision ของ prefix ที่เลือกสร้างข้อความสองข้อความที่มีจุดเริ่มต้นที่เลือกต่างกันแต่ลงท้ายด้วย hash เดียวกัน

Reminder

SHA two five six ไม่มี collision แบบสาธารณะและใช้งานจริง หากมีคนอ้างว่าเจอ ให้รอ peer review และผลการทดสอบก่อนจะ panic หรือ celebrate

Example

หากผู้โจมตีสามารถสร้างธุรกรรมสองรายการที่มี txid เดียวกัน พวกเขาอาจพยายามกลอุบาย Double Spending โดยสลับคู่ฝาแฝดหลังจากที่คุณเซ็น

Fun Fact

การชน MD5 ถูกแสดงให้เห็นหลายสิบปีก่อน และโครงการ SHAttered ได้สร้างการชน SHA หนึ่งชนกับ PDF สองฉบับที่ต่างกัน ซึ่งเป็นจุดเดือดที่ผลักดIndustry ให้งานยุติมัน

Wrap-Up

ในประโยคเดียว Hash Collision คือกรณีหายากที่ข้อมูลสองชุดแบ่งปัน fingerprint ดิจิทัลหนึ่งชุด และ crypto สมัยใหม่ทำงานอย่างหนักเพื่อให้เรื่องนี้ไม่กลายเป็นแค่ trivia

Hash Collision