Score:2

SHA-256 มีความต้านทานการชนกัน (128-time + 128-space = 256-overall) หรือไม่?

ธง vu

ขั้นแรก เราพิจารณาฟังก์ชันแฮชที่สามารถให้การรักษาความปลอดภัยก่อนอิมเมจ 256 บิตได้ ไม่ใช่อะไรทำนองนั้น SHAKE128<l=256บิต> โดยที่พารามิเตอร์ฟองน้ำมีความสามารถในการรักษาความปลอดภัยเพียง 128 บิตเท่านั้น

เราทราบดีว่าการเข้ารหัสไม่ได้มีเพียงมิติเวลาเท่านั้น แต่ยังมีมิติพื้นที่อีกด้วย กล่าวคือ จำนวนหน่วยความจำที่ใช้งานที่จำเป็นในการดำเนินการอัลกอริทึมการเข้ารหัส ดังนั้นหากเราคาดว่าจะพบการชนกันของ SHA-256 หลังจากนั้นประมาณ $2^{128}$ ความพยายามนี้ในทางทฤษฎีก็หมายความว่ามันต้องการ $2^{128}$ พื้นที่สำหรับเก็บอินพุตการชนกันของผู้สมัคร

นี่เป็นความจริงหรือไม่? นี่หมายความว่า SHA-256 มีความต้านทานการชนโดยรวม 256 บิต เมื่อคำนึงถึงพื้นที่?

vn flag
นอกเหนือจากข้อเท็จจริงที่ว่าคุณไม่ต้องการพื้นที่ $2^{128}$ เพื่อดำเนินการโจมตีแบบปะทะกัน ตามคำตอบที่ยอมรับแล้ว ยังมีความจริงที่ว่า $2^{128} + 2^{128} = 2^{ 129}$ แม้ว่าจะไม่มีการโจมตีหน่วยความจำต่ำ และเรา (ผิดพลาด) นับการใช้ทรัพยากรด้วยวิธีนี้ ก็ยังไม่ถึง $2^{256}$
Score:4
ธง ng

ไม่การทำลายคุณสมบัติการชนกันของ 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$ หนึ่งรอบ)
    • $s=H(s)$; $u=H(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.

gnasher729 avatar
kz flag
นอก crypto บทความที่คุณเชื่อมโยงดูเหมือนจะยากมากที่จะนำไปใช้กับอัลกอริทึมการแยกตัวประกอบของ Pollard-rho เนื่องจากที่นั่นเราไม่ได้มองหา x=y แต่มองหา gcd(x-y, N) > 1
DannyNiu avatar
vu flag
ฉันคิดว่าหากมีการเพิ่มผลการทดลองของอัลกอริทึมของฟลอยด์ในการแปลงที่เล็กลง (เช่น 24 หรือ 32 บิต) มันจะน่าเชื่อถือมากกว่า
fgrieu avatar
ng flag
@DannyNiu: อัลกอริทึมดั้งเดิมผิด อันนี้มาพร้อมกับการสาธิตการทำงาน
gnasher729 avatar
kz flag
อัลกอริทึม Pollard-tho สามารถหาตัวประกอบของตัวเลข 128 บิตได้อย่างง่ายดายในไม่กี่วินาที ซึ่งเกี่ยวข้องกับการค้นหาการชนกันระหว่างตัวเลข 64 บิต โดยปกติจะใช้เวลาประมาณ 2^32 ก้าว
Score:0
ธง kz

ไม่ สามารถพบการชนกันของ 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 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา