ขั้นแรก เราพิจารณาฟังก์ชันแฮชที่สามารถให้การรักษาความปลอดภัยก่อนอิมเมจ 256 บิตได้ ไม่ใช่อะไรทำนองนั้น SHAKE128<l=256บิต> โดยที่พารามิเตอร์ฟองน้ำมีความสามารถในการรักษาความปลอดภัยเพียง 128 บิตเท่านั้น
เราทราบดีว่าการเข้ารหัสไม่ได้มีเพียงมิติเวลาเท่านั้น แต่ยังมีมิติพื้นที่อีกด้วย กล่าวคือ จำนวนหน่วยความจำที่ใช้งานที่จำเป็นในการดำเนินการอัลกอริทึมการเข้ารหัส ดังนั้นหากเราคาดว่าจะพบการชนกันของ SHA-256 หลังจากนั้นประมาณ $2^{128}$ ความพยายามนี้ในทางทฤษฎีก็หมายความว่ามันต้องการ $2^{128}$ พื้นที่สำหรับเก็บอินพุตการชนกันของผู้สมัคร
นี่เป็นความจริงหรือไม่? นี่หมายความว่า SHA-256 มีความต้านทานการชนโดยรวม 256 บิต เมื่อคำนึงถึงพื้นที่?
ไม่การทำลายคุณสมบัติการชนกันของ SHA-256 ไม่จำเป็นต้องมีการปิด $2^{128}$ ช่องว่าง. เรารู้วิธีการแสดงการชนกันในใดๆ $n$บิตแฮช $H$ กับ $\mathcal O(2^{n/2})$ การประเมินแฮชและ $\mathcal O(n)$ ช่องว่าง.
วิธีการที่เหมาะสมที่ง่ายที่สุดคือ การค้นหาวัฏจักรของฟลอยด์ซึ่งจะแสดงความน่าจะเป็นที่ไม่หายไปสองแบบที่แตกต่างกัน $n$บิต bitstrings $r$ และ $s$ กับ $H(r)=H(s)$ในวงโคจรเป็นจุดเริ่มต้นที่กำหนด $t$ เมื่อวนซ้ำ $H$
ลองออนไลน์! สำหรับการชนกันของแฮช 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.
ไม่ สามารถพบการชนกันของ SHA-256 ได้โดยแทบไม่มีที่ว่างเลย
เคล็ดลับคือคุณไม่ต้องคำนวณ เช่น H(1), H(2), H(3) เป็นต้น ซึ่งจำเป็นต้องเก็บผลลัพธ์ทั้งหมดไว้ในตาราง แต่เราให้ x0 = ค่าบางอย่าง x1 = H(x0), x2 = H(x1) และอื่นๆ จากนั้นเราเปรียบเทียบ x1 และ x2, x2 และ x4, x3 และ x6, xk และ x2k และนี่จะพบการชนกันในประมาณ 2^128 ขั้นโดยไม่มีที่เก็บข้อมูล
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
