Score:2

วิธีที่มีประสิทธิภาพมากขึ้นของการแฮชซ้ำ

ธง sk

ต่อไปนี้คือวิธีที่เป็นไปได้ในการแฮชการเข้ารหัสลับแบบวนซ้ำให้เร็วเป็นสองเท่าของวิธีปกติ

กำหนดฟังก์ชั่นการบีบอัด $f: \{0,1\}^{a+b} \rightarrow \{0,1\}^b$. สมมติว่าข้อความมีความยาว $4a$ บิตหลังจากการเติม โดยปกติบล็อกข้อความทั้งสี่จะถูกแทรกลงในบล็อกข้อมูล $x_i \ใน \{0,1\}^b$:

$$ ม = m_0 \| m_1 \| m_2 \| m_3; \; |m_i| = ก $$ $$ x_{i+1} = ฉ(x_i \| m_i); \; ผม=0,1,2,3; \; x_0 = IV $$ $$ ชั่วโมง = x_4 $$ แนวคิดแรกในการแฮชให้เร็วขึ้นคือการลดความซับซ้อนของฟังก์ชันการบีบอัด เช่น ช. แทนที่ $f$ โดยฟังก์ชัน $g$ ที่สร้างคล้ายๆ กัน แต่ใช้อย่างเดียว $\frac 1 4$ ของรอบภายใน. คำนวณ $x_4$ เหมือนด้านบนโดยใช้ $g$ แทน $f$ และปิดท้ายโดย $h=p(x_4)$, ที่ไหน $p$ เป็นฟังก์ชันสุ่มเทียมที่ไม่อนุญาตให้คำนวณ $x_4$ จากแฮช $h$.

ฉันคิดว่าสิ่งนี้อาจปลอดภัยจากพรีอิมเมจ แต่ไม่ใช่การโจมตีแบบชนกัน เนื่องจากมีความสัมพันธ์กันมากเกินไป $x_i$ และ $x_{i+1}$อนุญาตให้สร้างบล็อกข้อความ $m_i, \overline m_i, m_{i+1}, \overline m_{i+1}$ ดังนั้น $$g(g(x_i\|m_i)\|m_{i+1})=g(g(x_i\|\overline m_i)\|\overline m_{i+1})$$ แนวคิดคือการแทรกแต่ละบล็อกข้อความสองครั้ง:

$$ x_{i+1} = g(x_i \| m_{i \bmod 4}); \; ฉัน=0,...,7 $$ $$ ชั่วโมง = x_8 $$ ขณะนี้มีการโทรอย่างน้อยห้าสาย $g$ ระหว่างการฉีดของสองบล็อกที่แตกต่างกัน $m_i, m_j$. ตัวอย่างเช่น $m_2$ จะถูกแฮชเมื่อ $i=2$ และ $m_3$ เมื่อไร $i=7$ดังนั้นจึงไม่ควรมีความสัมพันธ์ที่หาประโยชน์ได้ระหว่าง $x_2$ และ $x_7$. แต่รูปแบบนี้ใช้เท่านั้น $\frac 1 2$ รอบทั้งหมดเมื่อเทียบกับวิธีปกติ

สิ่งนี้จะปลอดภัยหรือไม่ เมื่อพิจารณาจากจำนวนรอบของ $f$ เพียงพอที่จะทำให้วิธีธรรมดาปลอดภัยหรือไม่?

Score:2
ธง my

ต่อไปนี้เป็นวิธีการหนึ่งที่ชัดเจนในการพยายามค้นหาการชนกัน:

  • ค้นหาคู่ $m_1, \โอเวอร์ไลน์{m_1}$ ด้วยคุณสมบัติที่ว่า $g(x \| m_1) = g(x \| \overline{m_1})$ สำหรับส่วนที่ไม่สำคัญของ $x$. กำหนดว่า $g$ มีจำนวนรอบลดลง อาจทำได้

  • ตอนนี้เริ่มต้นด้วยการแก้ไข $x_i$ (ตรงกับคำนำหน้าข้อความที่รู้จัก) และค้นหา $m_0$ เซนต์. $g(x_i \| m_0)$ เป็นหนึ่งในพรีอิมเมจที่ชนกันของ $m_1, \โอเวอร์ไลน์{m_1}$.

  • เรียก $g(g(x_0 \| m_0) \| m_1)$ มูลค่า $x_2$; ค้นหา $m_2, m_3$ คู่กันขนาดนั้น $g(g(g(x_2 \| m_2) \| m_3) \| m_0)$ ก็เป็นคู่ชนกัน

หากเราพบสิ่งนั้น ข้อความจะบล็อก $(m_0, m_1, m_2, m_3)$ และ $(m_0, \overline{m_1}, m_2, m_3$) ชนกันเมื่อเพิ่มคำนำหน้าข้อความ

สิ่งนี้ทำได้แค่ไหน? ขึ้นอยู่กับความเป็นไปได้ของขั้นตอนแรก (และความน่าจะเป็นของการสุ่ม $x$ ค่าเป็นพรีอิมเมจชนกัน) - ถ้าเราสามารถหาความน่าจะเป็นของการชนพรีอิมเมจได้ถึง $2^{-N}$จากนั้นปริมาณของความพยายามที่ใช้โดยขั้นตอนที่เหลือจะเป็นค่าที่คาดไว้ $2^{N+1}$ งาน...

ThomasM avatar
sk flag
การโจมตีนี้สามารถขัดขวางได้โดยการป้อนหมายเลขการวนซ้ำในแต่ละขั้นตอนการบีบอัด: $x_{i+1}=g(x_i \| m_{i \bmod 4}, i)$

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา