กระดาษแตกของ Google (การชนกันครั้งแรกสำหรับ SHA-1 แบบเต็ม) หมายถึงการสร้างไฟล์ใหม่ที่มีแฮชเดียวกันกับไฟล์ต้นฉบับหรือไม่

ฉันมีแหล่งข้อมูล A และแฮช H(A) ของ A นี้ เป็นไปได้ไหมที่เอกสารที่เสียหายของ Google จะสร้างข้อมูล B ใหม่ที่ส่งออก H(A) นี้

++ ฉันเข้าใจว่าเนื้อหาของเอกสารนี้เป็นการเสริมบล็อกข้อความสองบล็อกเพื่อให้ CV สุดท้ายเหมือนกัน วิธีการที่ฉันคิดคือสามารถหา M2(2) ของ "Dummy File" ได้อย่างถูกต้องหรือไม่ เพื่อให้ CV2 ของ "Original File" และ "DummyFile" แสดงผลเหมือนกับวิธีที่ 1 ในรูปภาพ หรือสร้างเฉพาะ CV2 ที่เหมือนกัน ในวิธีที่ 2 ผ่านการค้นหา M1(2), M2(2) ใหม่

บล็อกข้อความขนาด 64 ไบต์เป็นข้อมูลที่ไม่มีความหมาย ดังนั้นจึงไม่ต้องเปิดไฟล์ตามปกติ

รูปแบบของไฟล์ไม่จำกัดเฉพาะ PDF

ไม่ สิ่งที่คุณอธิบายจะเป็น การโจมตีด้วยภาพล่วงหน้าครั้งที่สองในขณะที่ทีม Google สร้างการโจมตีแบบปะทะกัน ใน SHAttered กระดาษ "การชนกันเต็มรูปแบบครั้งแรกบน SHA1" โดย Mark Stevens และคณะ โดยที่สถานะเหล่านั้นถูกยกมาในวิธีที่ 1 ของคุณ ผู้เขียนสามารถเลือกได้พร้อมกันก่อน $M_1^{(1)}$ และ $M_1^{(2)}$ สร้างความปั่นป่วนเล็กน้อยให้กับสิ่งหนึ่งสิ่งใดจนกว่าจะมีค่าใกล้เคียงกัน $CV_1^{(1)}$ และ $CV_1^{(2)}$ ถูกผลิตขึ้น ในสถานการณ์ของคุณ $M_1^{(1)}$ จะได้รับการแก้ไขและเท่านั้น $M_1^{(2)}$ สามารถปรับเปลี่ยนได้ทำให้หาตัวปิดยากขึ้นมาก $CV_1$ ค่า ในทำนองเดียวกัน ในขั้นตอนที่สอง นักวิจัยสามารถรบกวนทั้งสองอย่างได้ $M_2^{(1)}$ และ $M_2^{(2)}$ เพื่อค้นหาการปะทะกันทั้งหมด แต่ในสถานการณ์ของคุณ ผู้โจมตีจะสามารถปรับเปลี่ยนได้เท่านั้น $M_2^{(2)}$.

ความแตกต่างของความยากของความท้าทายเหล่านี้คือการค้นหาภาพพรีอิมเมจที่สองสำหรับ SHA1 ยังคงต้องใช้เวลาโดยประมาณ $2^{160}$ การประเมินฟังก์ชันแฮช มันเหมือนกับความแตกต่างระหว่าง ความน่าจะเป็นที่จะพบคนสองคนในห้องที่มีวันเกิดเดียวกัน และ ความน่าจะเป็นที่จะพบคนในห้องที่มีวันเกิดเดียวกันกับคุณ.

ผลงานล่าสุด ("SHA1 เป็นความโกลาหล" โดย Leurent และ Peyrin) แสดงว่า มันเป็นไปได้ เพื่อให้ผู้โจมตีใช้ไฟล์โดยอำเภอใจและเพิ่มข้อมูลที่พวกเขาควบคุมทั้งไฟล์ของคุณและของพวกเขาในลักษณะที่จะสร้างค่า SHA1 เดียวกันสำหรับทั้งสองไฟล์ สิ่งนี้เรียกว่า เลือกคำนำหน้าการชนกัน และยังเป็นหลักฐานที่ชัดเจนยิ่งขึ้นว่า SHA1 จำเป็นต้องเลิกใช้

หมายเหตุ: ตารางค่าไบต์ของคุณติดป้ายกำกับทั้งซ้ายและขวาเป็น $M_1^{(2)}$ และฉันได้กลับไปใช้สัญกรณ์ของกระดาษที่แตกแล้ว ฉันไม่แน่ใจแหล่งที่มาของตารางที่สองของคุณ

การโจมตีแบบแตกจะค้นหาไฟล์/ข้อความ B อื่นที่มีแฮช SHA-1 เหมือนกันกับไฟล์/ข้อความ A แต่เฉพาะในกรณีที่บางส่วนของข้อมูลใน A มีลักษณะเฉพาะที่จะไม่เกิดขึ้นโดยบังเอิญ สำหรับรูปแบบไฟล์/ความหมายของข้อมูลส่วนใหญ่ สิ่งนั้นยังคงอนุญาตให้โจมตีโดยฝ่ายตรงข้ามซึ่งไม่สามารถเปลี่ยนแปลงความหมาย/รูปลักษณ์/เอฟเฟกต์ของ A ได้ แต่อาจส่งผลต่อเนื้อหาไบนารีของ A ได้เล็กน้อย

ฉันมีแหล่งข้อมูล A และแฮช H(A) ของ A นี้ เป็นไปได้ไหมที่เอกสารที่เสียหายของ Google จะสร้างข้อมูล B ใหม่ที่ส่งออก H(A) นี้

คำตอบขึ้นอยู่กับข้อมูล A ซึ่งขึ้นอยู่กับวิธีการหาหรือผลิต A ซึ่งคำถามไม่ได้ระบุหรืออนุญาตให้เดา

1. ใช่โดยไม่ต้องพยายามคำนวณ ถ้า A เริ่มต้นด้วยหนึ่งในสองค่าเฉพาะ 320 ไบต์ที่การโจมตีแบบ Shattered มอบให้ เราสามารถแทนที่อันหนึ่งด้วยอันอื่นเพื่อสร้าง B ด้วยแฮช SHA-1 เดียวกัน สามารถใช้ (เหนือสิ่งอื่นใด) เพื่อสร้างไฟล์ PDF ที่ถูกต้องที่แตกต่างกันสองไฟล์ได้อย่างง่ายดาย โดยมีเนื้อหาไบต์ที่แตกต่างกันเล็กน้อยและรูปลักษณ์ที่แตกต่างกันโดยสิ้นเชิง
2. ไม่ถ้า A น้อยกว่าประมาณ 125 ไบต์ เมื่อยึดติดกับเมธอดใน Shattered paper แม้ว่าจะใช้ความพยายามในการคำนวณก็ตาม แต่เราต้องลดขีดจำกัดนั้นลงเหลือประมาณ 19 ไบต์หากเราเปลี่ยนวิธีการและยอมรับความพยายามในการคำนวณที่เพิ่มขึ้นโดยปัจจัยเล็กน้อย (ประมาณ 250,000) เป็นประมาณ $2^{81}$ แฮช SHA-1
3. ใช่ด้วยความพยายามในการคำนวณของ Shattered หากฝ่ายตรงข้ามสามารถเลือก 128 ไบต์แรกของ A ได้ นั่นยังคงเป็นการโจมตีแบบ Shattered แต่ต้องใช้งานขนาดใหญ่ เราสามารถลดขีด จำกัด นั้นลงเหลือ 64 ไบต์ได้หากเรายอมรับความพยายามในการคำนวณที่เพิ่มขึ้นของจุดก่อนหน้า
4. ใช่เป็นส่วนขยายของ 3 ถ้าฝ่ายตรงข้ามรู้ก่อน $n$ ไบต์ของ A และสามารถเลือกต่อไปได้ $128+(-n\bmod 64)$ ไบต์ และเราต้องลดระดับลงเป็น $64+(-n\bmod 64)$ ไบต์ด้วยความพยายามในการคำนวณที่เพิ่มขึ้น สิ่งนี้สามารถขยายเพิ่มเติมไปยังฝ่ายตรงข้ามที่เลือกข้อมูลประมาณ 20 ไบต์ในครั้งแรก $64\,f$ ไบต์ของ A ที่มีความรู้ในส่วนนั้นของ A และงานที่เพิ่มขึ้นอีกโดยปัจจัยที่ไม่เกิน $f$.
5. ใช่จากผลที่ตามมาของ 4 ถ้า A ถูกเตรียมไว้ในลักษณะที่อยู่ภายใต้การควบคุมของศัตรู เช่น ถ้า A เป็นเอกสาร PDF, รูปภาพ PNG, รูปภาพ "ISO" ของ CD/DVD หรืออาจเป็นไฟล์ปฏิบัติการที่จัดทำขึ้นโดยใช้เครื่องมือที่สร้างขึ้นโดยฝ่ายตรงข้าม สำหรับใบรับรองดิจิทัล โปรดดูที่ คำถามนี้.
6. ไม่ถ้า A ผ่านการทดสอบที่จัดทำโดยผู้เขียน Shattered และเรายึดตามวิธีการโจมตีของพวกเขา แต่การทดสอบของพวกเขาไม่สามารถป้องกันการโจมตีอื่น ๆ ที่มีต้นทุนใกล้เคียงกัน และไม่มีการทดสอบใดที่สามารถป้องกันการโจมตีที่มีต้นทุนเพิ่มขึ้นเล็กน้อย
7. ไม่หากมีอย่างน้อย 64 บิตของเอนโทรปีใน 64 ไบต์แรกของ A ที่ไม่รู้จักสำหรับฝ่ายตรงข้ามในเวลาที่ฝ่ายตรงข้ามสามารถมีอิทธิพลต่อ A สำหรับความพยายามในการคำนวณใด ๆ ที่เป็นไปได้ ซึ่งรวมถึงใบรับรอง A แบบสุ่มและใบรับรองดิจิทัลที่ออกโดยผู้ออกใบรับรองโดยใช้การป้องกันง่ายๆ โดยใช้หมายเลขซีเรียลแบบสุ่มที่จุดเริ่มต้นของใบรับรอง

ฉันต้องการตรวจสอบให้แน่ใจว่ารูปแบบของไฟล์ไม่จำกัดเฉพาะ PDF

การโจมตีและส่วนขยายของ The Shattered ไม่จำกัดเฉพาะ PDF โปรดดู 3/4/5 สามารถพกพา (กับงานบางอย่าง) ด้วยรูปแบบไฟล์ใดก็ได้โดยไม่ต้องตรวจสอบความซ้ำซ้อนภายใน นั่นคือส่วนใหญ่ นอกจากนี้ คำนำหน้าอะนาล็อกเป็น 1 (ซึ่งเชี่ยวชาญสำหรับการปลอมแปลง PDF ราคาไม่แพง) สามารถประดิษฐ์ได้หลายรูปแบบ รวมทั้ง JPEG, PNG, GIF, MP4, JPEG2000, Portable Excutable format และอื่นๆ อีกมากมาย โดยมีงานขนาดใหญ่แต่ทำได้เท่านั้น ครั้งหนึ่ง. คำนำหน้าของ 1 ใช้ได้กับรูปแบบไฟล์ที่มีอยู่บางรูปแบบ เช่น เสียงและวิดีโอสำหรับผู้เล่นที่ข้ามผ่านสิ่งที่พวกเขาไม่รู้จัก (เนื่องจากคำถามไม่ได้ถามว่า A และ B ที่แตกต่างกันมีพฤติกรรมต่างกัน นั่นคงเป็นเรื่องยากที่จะบรรลุด้วยคำนำหน้า 1 สำหรับบางสิ่งที่ไม่ใช่ PDF และผู้เล่นมาตรฐานไม่ สร้างขึ้นเพื่อจุดประสงค์)

หากมีข้อสงสัย: ปลอดภัยไว้ก่อนดีกว่า สันนิษฐานว่าใช่ การโจมตีเป็นไปได้ และใช้แฮชที่ต่อเนื่องและกว้างกว่า SHA-1 อย่างเห็นได้ชัด

(หลักการ) ของกระดาษคือการเติมเต็มบล็อกข้อความสองบล็อก

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

การโจมตีที่ใช้กับ A ตามอำเภอใจจะเป็นการโจมตีแบบพรีอิมเมจ (วินาที) การโจมตีดังกล่าวไม่เป็นที่รู้จักสำหรับ SHA-1