ไม่การทำลายคุณสมบัติการชนกันของ SHA-256 ไม่จำเป็นต้องมีการปิด $2^{128}$ ช่องว่าง. เรารู้วิธีการแสดงการชนกันในใดๆ $n$บิตแฮช $H$ กับ $\mathcal O(2^{n/2})$ การประเมินแฮชและ $\mathcal O(n)$ ช่องว่าง.
วิธีการที่เหมาะสมที่ง่ายที่สุดคือ การค้นหาวัฏจักรของฟลอยด์ซึ่งจะแสดงความน่าจะเป็นที่ไม่หายไปสองแบบที่แตกต่างกัน $n$บิต bitstrings $r$ และ $s$ กับ $H(r)=H(s)$ในวงโคจรเป็นจุดเริ่มต้นที่กำหนด $t$ เมื่อวนซ้ำ $H$
- $m\gets\lceil\,2^{n/2+1}\,\rceil$ (เพิ่มขึ้น $+1$ ลดความล้มเหลว)
- $u\gets H(t)$ .
- $r\gets u$; $s\gets H(u)$ .
- ในขณะที่ $r\ne เอส$ :Â (ค้นหาวงจร)
- ถ้า $m=0$ แล้วหยุดด้วยความล้มเหลว (วงโคจรยาว หายาก)
- $m\gets ม-1$ .
- $r\gets H(r)$; $s\gets H(H(s))$ .
- ถ้า $t=s$ แล้วหยุดด้วยความล้มเหลว ($t$ ในวัฏสงสารหายากมาก)
- $s\gets H(s)$ .
- ในขณะที่ $r\ne เอส$ :Â (ออฟเซ็ต $u$ หนึ่งรอบ)
- ในขณะที่ $t\ne ยู$:Â (ค้นหาการชนกัน)
- $r\gets เสื้อ$; $s\gets ยู$ .
- $t\gets H(t)$; $u\gets H(u)$ .
- เอาต์พุต $(ร,ส)$ และหยุดที่ความสำเร็จ
ลองออนไลน์! สำหรับการชนกันของแฮช 24 บิต (ไฟล์ $k=3$ ไบต์ของ SHA-256) โปรดกรุณาเรียกใช้รหัส Python นี้ในเครื่องของคุณหากเพิ่มขึ้น $k$.
วิธีการใช้ว่าวงโคจรของ $t$กำหนดให้เป็น $u$ ถึงโดยการวนซ้ำ $u\gets H(u)$ เริ่มจาก $u=t$มีแนวโน้มที่จะหมุนเวียนภายใน $\mathcal \Theta(2^{n/2})$ ขั้นตอน อัลกอริทึมตรวจพบวงจรถึง ค้นหา $u$ หลังจากผ่านไปหลายก้าวจาก $t$ เป็นความยาวของวัฏจักร จากนั้นเมื่อเข้าสู่วัฏจักร ซึ่งทำให้เกิดการชนกัน สามารถแสดงได้ว่าสำหรับฟังก์ชันสุ่ม $H:\{0,1\}^*\mapsto\{0,1\}^n$ และยกเว้นที่มีขนาดเล็กมาก $n$ความน่าจะเป็นความสำเร็จของอัลกอริทึมนี้จากจุดเริ่มต้นใดๆ $t$ เป็นอย่างน้อย $3/4$ (ความล้มเหลวมีไว้สำหรับวงโคจรที่ยาวเกินไปของ $t$หรือเมื่อไหร่ $t$ เป็นวัฏจักร).
ในกรณีที่ล้มเหลว บ่อยครั้งก็เพียงพอแล้วที่จะเริ่มต้นใหม่จากจุดสุ่มอื่นซึ่งโดยทั่วไปแล้วจะใช้งานได้ดีสำหรับแฮชการเข้ารหัสทั่วไป $H$แต่สำหรับสิ่งเหล่านี้ จุดเริ่มต้นส่วนใหญ่นำไปสู่วัฏจักรที่ใหญ่เกินกว่าจะพบได้ ในกรณีทั่วไป เราต้องการเปลี่ยนไปใช้อัลกอริทึมกับ $H'$ ที่กำหนดโดย $H'(x)=H(F(x))$ สำหรับการฉีดที่คำนวณได้อย่างมีประสิทธิภาพแบบสุ่มอย่างเหมาะสมและกลับด้านได้ $F$ เลือกเมื่อเริ่มต้นอัลกอริทึม นั่นเป็นการแสดงการชนกันของ $H'$ การใช้อัลกอริทึมแสดงการชนกันของ $H$, แต่ $H'$ สามารถมีโครงสร้างวัฏจักรที่แตกต่างกันได้ สำหรับส่วนใหญ่ $n$บิตแฮช $H$ เหมาะสำหรับการใช้เข้ารหัส $F$ สามารถ XOR ด้วยค่าคงที่ $n$-bit bitstring หรือเพิ่มคำนำหน้าหรือ/และต่อท้าย สิ่งนี้ไม่ได้แสดงอยู่ในรหัสจำลองด้านบนและรหัส Python ที่เชื่อมโยง
เป็นไปได้ที่จะกระจายงานบนเครื่องหลายเครื่องที่ทำงานพร้อมกัน โดยแต่ละเครื่องมีหน่วยความจำน้อย สื่อสารได้ปานกลาง และทำงานพิเศษได้พอสมควร ดู Paul C. van Oorschot และ Michael J. Wiener การค้นหาการชนกันแบบขนานด้วยแอปพลิเคชัน Cryptanalytic, ใน วารสารวิทยาการเข้ารหัสลับ, 2542.