ความแตกต่างของการโจมตีในฟังก์ชันแฮชคืออะไร? เราจะโจมตีอัลกอริทึม SHA ได้อย่างไรและจะได้อะไร

ปัจจุบัน ฉันได้รับมอบหมายให้โจมตี SHA-1 เวอร์ชันย่อ เรากำลังพยายามบรรลุอะไร เราจะโจมตีมันได้อย่างไร?

อย่างไรก็ตาม คำตอบนั้นไม่ง่ายเลย จุดเริ่มต้นที่ดีคือ กระดาษของ Florent Chabaud และ Antoine Joux เรื่อง SHA-0 และ SHA-1

• การชนกันของความแตกต่างใน SHA-0, คริปโต 1998.

บทนำง่ายๆ

ใน MD4, SHA-0, SHA-1 และ SHA-2 มีฟังก์ชันการบีบอัด $$C:\{0,1\}^\ell \to :\{0,1\}^n$$ ที่ไหน $n$ คือขนาดเอาต์พุตและ $\ell$ คือความยาวของบล็อกในการประมวลผล

ฟังก์ชั่นการบีบอัด $C$ สามารถดูได้ว่าเป็นรหัสบล็อกโดยที่คีย์คือข้อความ สิ่งนี้มีความหมายเนื่องจากส่วนเดียวคืออินพุตและ SHACAL ถูกเรียกว่า block cipher ของ SHA-1 และเรียก SHACAL-2 สำหรับ SHA-2 ในทำนองเดียวกัน

ตอนนี้ เรามีรหัสบล็อก และเรามีอินพุต ( ค่าเริ่มต้น $H_i$s และค่าเอาต์พุต ( แฮช - ไดเจสต์) เราต้องหากุญแจ หากเราสามารถหากุญแจได้ เราก็มีภาพก่อนการโจมตีและการชนกัน สิ่งนี้อาจนำไปสู่การพิจารณาว่าเรากำลังโจมตีในลักษณะของการโจมตีแบบแยกส่วน ไม่ใช่ทั้งหมด แต่ในลักษณะเดียวกัน

ผู้เขียนเริ่มด้วย SHA-1 (SHI1) ที่อ่อนแอลงก่อน โดยที่ไม่พิจารณาการขยายอินพุตและ ADD จะถูกแปลงเป็น X หรือเพื่อให้ไม่มีส่วนที่ไม่เป็นเชิงเส้น ด้วยการรบกวนบิตเดียวและการแก้ไขอินพุต พวกเขาแสดงให้เห็นว่าพบการชนกันของหน้ากาก

ต่อมา ADD เดียวที่แปลงเป็น X-หรือ (SHI2) เพื่อขยายการโจมตี พวกเขาพบว่าก หน้ากากที่แตกต่างกัน $\คณิตศาสตร์แคล{M}$ ที่สามารถใช้กับข้อความธรรมดา (อินพุต) เพื่อค้นหาการชนกัน

   ดูการชนกันแบบสุ่ม (h, บล็อก):
      m = ramdom_message (1 บล็อก)
      ชั่วโมง = แฮช(เมตร)
      m' = หน้ากาก (ม.)
      h' = แฮช (m')
      ถ้า h=h':
         กลับ (ม.)
      อื่น: 
         กลับ -1

    ในขณะที่ (1):
        ความสำเร็จดูการชนกันแบบสุ่ม (SHA-1, 512)
        ถ้าสำเร็จ != -1:
            พิมพ์("คู่ชนกันคือ - ", m, mask(m))

ความสำเร็จของการโจมตีคือโอกาสสำเร็จของหน้ากาก $\คณิตศาสตร์แคล{M}$ เพื่อแนะนำการชนกัน หากโอกาสสำเร็จของหน้ากากคือ $1/ตัน$ แล้วรอบ ๆ $c\cdott$ สุ่มคู่หนึ่งจะพบการชนกัน

หลังจากนั้น พวกเขาดู SHA-0 และ SHA-1 จริงเพื่อหาหน้ากากดังกล่าว พวกเขาพบหนึ่งสำหรับ SHA-0 ด้วย $2^{61}$- เวลาที่ซับซ้อน หน้ากากที่พวกเขาพบสำหรับ SHA-1 นั้นไม่มีความซับซ้อนที่ดีไปกว่าการชนกันทั่วไป นั่นคือมันมีความซับซ้อน $> 2^{80}$.

บทความนี้เขียนขึ้นอย่างดีตั้งแต่การทำความเข้าใจการโจมตีจากฟังก์ชันการบีบอัดระดับต่ำ (ไม่มีส่วนที่ไม่ใช่เชิงเส้น) ไปจนถึงฟังก์ชันระดับสูงที่มีความไม่เชิงเส้น

และมีความเป็นไปได้สูงที่ NSA จะรู้เรื่องนี้ ดังนั้นพวกเขาจึงแก้ไขการขยายอินพุตของ SHA-0 บน SHA-1 ด้วยการแนะนำการหมุนเวียน

ทำไมมันถึงเป็นอันตราย

พิจารณากรณีที่ SHA-1 เสีย เรามีบล็อกคำนำหน้า $พี$ และส่วนต่อท้ายบล็อก $S$ และเรากำลังมองหาการปะทะกัน

$$แฮช(P\mathbin\| m \mathbin\|S) = แฮช(P\mathbin\| m' \mathbin\|S)$$

หากเราสามารถหาหน้ากากดิฟเฟอเรนเชียลที่ดีได้ $\คณิตศาสตร์แคล{M}$ ด้วยความน่าจะเป็นที่ดี เราจึงสามารถโจมตีบล็อกได้ $m$. หากส่วนของไฟล์เป็นส่วนหนึ่งของความซ้ำซ้อนเช่นเดียวกับในไฟล์ PDF คุณสามารถสร้าง PDF สองไฟล์ที่มีค่าแฮชเหมือนกันได้ อันตรายจริง ๆ ต้องใช้มากกว่านี้แน่นอน การเปลี่ยนแปลงใน $m'$ มีข้อได้เปรียบสำหรับผู้ลงนาม นี้สามารถทำได้เช่นกัน