การแฮชแบบเรียกซ้ำเป็นวัฏจักรหรือไม่?

ถ้าฉันป้อนเอาต์พุตของ H กลับเข้าไปใน H มันจะครอบคลุมพื้นที่เอาต์พุตทั้งหมดของ H ก่อนที่จะทำซ้ำหรือไม่

พิจารณาสถานการณ์ต่อไปนี้:

ก=1;
ในขณะที่(){
   ก=ซ(ก);
   พิมพ์(A)
}

จะมีรอบสั้น ๆ หรือไม่? เช่น. มีค่าของ A ที่ H(A) = A (รอบละ 1) ค่าของ A โดยที่ H(A) = B และ H(B) = A (รอบที่ 2)

มีวิธีพิสูจน์หรือไม่ว่าไม่มีรอบดังกล่าวสำหรับแฮชที่กำหนด หรือกำหนดขอบเขตล่างให้กับรอบที่สั้นที่สุด

Douglas Hofstadter ในหนังสือเล่มหนึ่งของเขา (Either "The Mind's I" or "Metamathematical Themas" I think) มีประโยคหนึ่งว่า

ประโยคนี้มีหนึ่ง 'a' หนึ่ง 'b' ...

ปัญหาคือการหาค่าที่ทำให้เป็นจริง หากคุณแค่นับการครอบตัดปัจจุบัน และแก้ไขประโยค และทำซ้ำ ประโยคจะบรรจบกับข้อความจริงอย่างรวดเร็ว

สิ่งนี้เชื่อมต่อกับการเข้ารหัสอย่างไร

ฉันสงสัย แต่ยังไม่ได้แสดงให้เห็นว่า 'ตัวดึงดูดที่แปลกประหลาด' ข้างต้นนั้นค่อนข้างไม่มีกฎเกณฑ์

{ข้อความทั้งหมดของสงครามและสันติภาพ} ข้อความนี้มี...

จะมาบรรจบกันในคำสั่งที่ถูกต้องด้วย

พิจารณาแฮช H สมมติว่ามีรอบสั้นๆ ของ H จะมีรอบของ (D+H) ด้วยหรือไม่ โดยที่ D เป็นก้อนข้อมูลโดยพลการ จะยาวเท่ากันไหม? (ฉันไม่เห็นเหตุผลที่ดีว่าทำไมพวกเขาควรจะเป็น)

หากเศษส่วนของแฮชที่ประเมินค่าได้เป็นสมาชิกของวงจรสั้น (สำหรับค่าสั้นบางค่า: 1 ล้าน? 1 พันล้าน?) แสดงว่ามีช่องโหว่ดังต่อไปนี้:

เอาไฟล์ D.

• แก้ไข D เพื่อให้เหมาะกับวัตถุประสงค์ของคุณ ส่วนหนึ่งของกระบวนการนี้ควรจะสั้นลงตามความยาว (ค่าแฮช) เรียกไฟล์นี้ว่า D'

+ ยืนหรือเชื่อม

• คำนวณ A = H(D)
• คำนวณ A2 = H(A+D')
• คำนวณ A3 = H(A2+D')

ถ้า A เป็นวงกลม คุณจะไปถึง A_n บางตัวซึ่งการวนซ้ำครั้งต่อไปจะทำให้เกิด A

• แทนที่ไฟล์ D ด้วย A_n+D'

ในแง่ของความปลอดภัย เราจำเป็นต้องรู้ว่าความน่าจะเป็นของ A ที่กำหนดจะเป็นวัฏจักรในเวลาที่เหมาะสมเท่าใด แน่นอนว่าความสมเหตุสมผลขึ้นอยู่กับความสำคัญของเอกสาร แต่ถ้าคุณสามารถแสดงให้เห็นว่ามีความเป็นไปได้น้อยมากที่จะพบวัฏจักรต่ำกว่า 10^15 หรือมากกว่านั้น แสดงว่าการโจมตีแบบนี้ใช้ไม่ได้ หากมีโอกาส 2% ที่แฮชที่กำหนดเป็นวงจรในการวนซ้ำน้อยกว่าหนึ่งล้านครั้ง แสดงว่าอาจเกิดปัญหาขึ้นได้

เมื่อศึกษาปัญหาดังกล่าว นักเข้ารหัสจะเลียนแบบแฮชการเข้ารหัส $H$ ถึง ก ฟังก์ชั่นสุ่ม หรือ ออราเคิลแบบสุ่ม (หรือ การทำแผนที่แบบสุ่ม แม้ว่ามันจะเก่าไปหน่อย) ที่ทำซ้ำ ความน่าจะเป็นจะคำนวณผ่านชุดแฮชที่เป็นไปได้ทั้งหมด นั่นเป็นการประมาณค่า แต่ถ้าผลลัพธ์จริงแตกต่างกันอย่างชัดเจน นั่นจะเป็นวิธีแยกแยะแฮชจากฟังก์ชันสุ่ม ดังนั้นการแบ่งแฮชตามคำจำกัดความสมัยใหม่ ดังนั้น การประมาณค่าดังกล่าวจึงน่าพอใจ และยิ่งมีแฮชการเข้ารหัสที่ไม่ขาดตอนก็ยิ่งดี

จะมีรอบสั้น ๆ หรือไม่?

มีแนวโน้มและยิ่งเมื่อเราคลายคำจำกัดความสั้นๆ แต่ (ยกเว้นแฮชขนาดเล็กมาก) ไม่น่าเป็นไปได้ที่รอบสั้นๆ จะไปถึงจากจุดเริ่มต้นแบบสุ่ม $A$; และ (สำหรับแฮชการเข้ารหัสมาตรฐานที่มีเอาต์พุตขนาดใหญ่พอที่จะป้องกันการชนกัน) ไม่น่าเป็นไปได้ที่เราจะแสดงวัฏจักรใดๆ โดยไม่คำนึงว่าขนาดของมันจะเป็นอย่างไร

มีค่าของ $A$ ดังนั้น $H(A)=A$ (รอบ 1)

หากชุดปลายทางของแฮชมีขนาด $n$ (ที่ไหน $n=2^b$ สำหรับ $ข$-บิตแฮช เช่น $n=2^{256}$ สำหรับ SHA-256) จากนั้นความน่าจะเป็นที่มีวัฏจักรขนาด 1 จะถูกคำนวณอย่างง่ายโดยเป็นส่วนเติมเต็มของความน่าจะเป็นที่ไม่มี $n$ ชี้แฮชไปที่ตัวเองนั่นคือ $p_1(n)=1-(1-1/n)^n$. นี้เริ่มต้นจาก $p_1(1)=1$, $p_1(2)=3/4=0.75$, $p_1(3)=19/27\ประมาณ0.7037$, และ $p_1$ มาบรรจบกันอย่างรวดเร็ว $1-1/e\ประมาณ0.6321$.

ดังนั้นจึงมีความเป็นไปได้ > 63.2% ที่จะมีวงจรขนาด 1 ในแฮชการเข้ารหัสที่ระบุ เช่น SHA-256, SHA-384 หรือ SHA-512 และเราไม่สามารถบอกได้ดีกว่าสำหรับแฮชเหล่านี้

ฉันไม่รู้วิธีทำเช่นเดียวกันสำหรับไซเคิลขนาด 2 แต่ไม่ต้องสงสัยเลยว่ามันเป็นไปได้ และความน่าจะเป็นก็มากสำหรับ $n\ge2$.

เป็นไปได้ที่จะคำนวณค่าที่คาดหวังของลักษณะต่างๆ ของวงจรสำหรับฟังก์ชัน/แฮชแบบสุ่มที่วนซ้ำ โดยเฉพาะอย่างยิ่งสำหรับขนาดใหญ่ $n$จำนวนขั้นที่คาดไว้ก่อนที่จะถึงค่าก่อนหน้าที่เริ่มต้นจากจุดสุ่มคือ $\ประมาณ\sqrt{\pi\,n/2}$และระยะเวลาที่คาดไว้ของรอบถึงครึ่งหนึ่ง การอ้างอิงแบบคลาสสิกคือ Philippe Flajolet และ Andrew M. Odlyzko สถิติการทำแผนที่แบบสุ่ม, ใน การดำเนินการของ Eurocrypt 1989, และ รายงานการวิจัย RR-1114, INRIA, 1989.

มีวิธีพิสูจน์หรือไม่ว่าไม่มีรอบดังกล่าวสำหรับแฮชที่กำหนด หรือกำหนดขอบเขตล่างให้กับรอบที่สั้นที่สุด

ไม่สำหรับแฮชการเข้ารหัสลับที่ไม่เสียหายซึ่งมีขนาดเอาต์พุตที่ใหญ่พอที่จะป้องกันการชนกันได้ (นั่นคือ $\sqrtn$ มีขนาดใหญ่จนไม่สามารถคำนวณจำนวนแฮชนี้ได้) เช่น แฮชที่ไม่ขาดตอน 256 บิตหรือกว้างกว่านั้น ในส่วนของคำถามที่ถามว่าเป็นไปได้ไหมที่จะพิสูจน์ว่าไม่มีวัฏจักรดังกล่าวอยู่ เราจำเป็นต้องคำนวณด้วยซ้ำ $n$ แฮช (จนถึงครั้งสุดท้ายเราไม่สามารถแน่ใจได้ว่าไม่มีวงจรขนาด 1) ดังนั้นแฮช 128 บิตหรือกว้างกว่าที่ไม่เสียหายจะทำได้

ดังนั้น (การสร้างซ้ำของ Douglas Hofstadter) เชื่อมต่อกับการเข้ารหัสอย่างไร

มีการใช้เทคนิคที่คล้ายกันในการโจมตีระบบเข้ารหัสลับบางระบบ เราสร้างฟังก์ชัน วนซ้ำจนกว่าจะพบวัฏจักร (ซึ่งสั้นมาก ไม่งั้นหาไม่เจอ) และจุดเริ่มต้นในวัฏจักรทำให้เกิดการชนกัน และการชนกันแก้ปัญหาเพราะฟังก์ชันถูกสร้างขึ้นด้วยความชัดเจนนั้น วัตถุประสงค์. นั่นคือหัวใจของ โรของพอลลาร์ด วิธีการแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่อง ซึ่งเป็นการโจมตีทางทฤษฎีที่ดีที่สุดสำหรับปัญหานี้ในบางกลุ่มที่ใช้ในการเข้ารหัส

โปรดสังเกตว่าทั้งฟังก์ชันในข้างต้นหรือฟังก์ชันที่สร้างโดย Douglas Hofstadter ไม่ถือเป็นแฮชการเข้ารหัสที่ปลอดภัย เป็นเพราะพวกเขาไม่สามารถหาวัฏจักรและแก้ปัญหาได้