เครื่องมือสำหรับนักพัฒนาซอฟต์แวร์ · SHA เครื่องคำนวณแฮช
เอฟเฟกต์หิมะถล่ม: เหตุใดอักขระที่มีการเปลี่ยนแปลงจึงเขียนแฮช SHA ใหม่
· มันทำงานอย่างไร
sha-256 การเข้ารหัส ความปลอดภัย การตรวจสอบ
เปลี่ยนตัวอักษรหนึ่งตัวและบิตเอาต์พุตประมาณครึ่งหนึ่งจะพลิก โพสต์นี้จะอธิบายคุณสมบัติของหิมะถล่ม เหตุใดจึงจำเป็นสำหรับการตรวจจับการงัดแงะ และวิธีที่ SHA-2 บรรลุเป้าหมายดังกล่าว
คาดว่าแฮชจะเปลี่ยนไปเล็กน้อย - สัญชาตญาณที่คนส่วนใหญ่นำมาและเหตุใดการออกแบบจึงจงใจทำลายมัน
คนส่วนใหญ่คาดหวังว่าอินพุตที่คล้ายคลึงกันจะสร้างเอาต์พุตที่คล้ายคลึงกัน เปลี่ยนอักขระหนึ่งตัวในไฟล์และการสรุปควรเปลี่ยนแปลงเล็กน้อย แต่แฮชที่เข้ารหัสลับได้รับการออกแบบมาให้ทำสิ่งที่ตรงกันข้าม: การเปลี่ยนแปลงบิตเดียวในอินพุตควรพลิกบิตเอาต์พุตประมาณครึ่งหนึ่งอย่างคาดเดาไม่ได้ คุณสมบัตินี้เรียกว่าปรากฏการณ์หิมะถล่มและเป็นการกระทำโดยเจตนา การออกแบบนี้มีจุดประสงค์เฉพาะ: การตรวจจับการงัดแงะ
เอฟเฟกต์หิมะถล่มคือสาเหตุที่ "เกือบจะตรงกัน" จึงไม่ใช่แนวคิดในโลกแห่งการแฮช แฮชตรงกันทุกประการหรือไม่ตรงกัน ไม่มีคำว่า "ใกล้พอ" คุณสมบัตินี้ทำให้การแฮชมีประโยชน์สำหรับการตรวจสอบความสมบูรณ์และการจัดการเนื้อหา และทำให้อัลกอริธึมการแฮชที่ไม่รัดกุมไม่สามารถใช้งานได้เพื่อจุดประสงค์ด้านความปลอดภัย
หิมะถล่มหมายถึงการแพร่กระจายเอาต์พุตในวงกว้าง บทความนี้ไม่มีการอ้างสิทธิ์ความน่าจะเป็นที่แน่นอนโดยไม่มีแหล่งที่มา
อย่างเป็นทางการ เอฟเฟกต์หิมะถล่มหมายความว่าสำหรับอินพุตสองตัวที่แตกต่างกันในบิตเดียว การแยกย่อยเอาต์พุตควรแตกต่างกันประมาณ 50% ของบิตเหล่านั้น สำหรับ SHA-256 (256 bits ของเอาต์พุต) การเปลี่ยนบิตอินพุตหนึ่งบิตควรพลิกบิตเอาต์พุต 128 ประมาณ ผลที่ได้ไม่แน่นอน มันเป็นคุณสมบัติทางสถิติ แต่มันมีความแข็งแกร่ง: ในทางปฏิบัติ ทุกบิตของอินพุตจะถูกผสมอย่างละเอียดกับทุกบิตของเอาท์พุต
ทำไมประมาณครึ่งหนึ่ง? เนื่องจากเอาต์พุตสุ่มอย่างแท้จริงจะแตกต่างจากเอาต์พุตสุ่มอื่นโดยเฉลี่ยเพียงครึ่งหนึ่งของบิต (ตามหลักการรูนกพิราบและสถิติพื้นฐาน) ฟังก์ชันแฮชที่ดีจะใกล้เคียงกับความสุ่ม มันสร้างผลลัพธ์ที่ดูเหมือนจะไม่มีรูปแบบที่มองเห็นได้ บิตที่พลิกโดยเฉลี่ยครึ่งหนึ่งคือจุดเด่นของการสุ่ม หากแฮชพลิก 10% ของบิตเท่านั้น ผู้โจมตีสามารถค้นหารูปแบบและใช้ประโยชน์จากมันได้
เหตุใดจึงจำเป็นต้องมีการตรวจจับการงัดแงะ — การแก้ไขเอกสารเพียงเล็กน้อยจะต้องไม่สร้างแฮชที่เกือบจะเหมือนกันจนการดูอย่างรวดเร็วจะยอมรับได้
การตรวจจับการงัดแงะอาศัยหิมะถล่ม หากคุณดาวน์โหลดไฟล์และคำนวณ SHA-256 การแยกย่อยที่คาดไว้คือ ba7816... (เป็นตัวอย่าง) ผู้โจมตีแก้ไขไฟล์โดยเปลี่ยนหนึ่งไบต์ การแยกย่อยใหม่เปลี่ยนจาก ba7816... เป็น 3d4e92... (แตกต่างอย่างสิ้นเชิง) เมื่อคุณตรวจสอบไฟล์กับไดเจสต์ที่คาดไว้ ความไม่ตรงกันจะเกิดขึ้นทันทีและเป็นผลรวม ไม่มีที่ว่างสำหรับการตีความที่ผิด: ไฟล์ถูกแก้ไข
หากไม่มีหิมะถล่ม ผู้โจมตีสามารถเปลี่ยนไบต์ได้และข้อมูลย่อยอาจเปลี่ยนเพียงเล็กน้อยเป็น ba7817... (เลขฐานสิบหกต่างกันหนึ่งหลัก) การเปรียบเทียบแบบทั่วไปอาจทำให้พลาดความแตกต่าง ผู้โจมตีสามารถค้นหาอินพุตที่สร้างไดเจสต์ที่ขึ้นต้นด้วย ba78 โดยอ้างว่าไฟล์นั้นเป็นของแท้ Avalanche ทำให้สิ่งนี้มีราคาแพงมาก: ในการค้นหาอินพุตสองตัวที่การแยกย่อยเริ่มต้นด้วยเลขฐานสิบหกสี่หลักที่เหมือนกันนั้นจะต้องดำเนินการมากกว่าที่การออกแบบจะอนุญาต
การเปลี่ยนแปลงของการกระจายของรอบ - การหมุน การบวก และฟังก์ชันที่ไม่ใช่เชิงเส้นที่มีอิทธิพลหนึ่งบิตทั่วทั้งสถานะ
รอบใน SHA-256 (และรอบใน SHA-512) ได้รับการออกแบบมาเพื่อกระจายการเปลี่ยนแปลง แต่ละรอบจะผสมข้อมูลโดยใช้ฟังก์ชันที่ไม่ใช่เชิงเส้น (เลือก ส่วนใหญ่) และการหมุน การเปลี่ยนแปลงอินพุตเพียงบิตเดียวจะเข้าสู่กำหนดเวลาข้อความและเผยแพร่เป็นรอบ การหมุนจะเปลี่ยนตำแหน่งบิต ฟังก์ชันที่ไม่ใช่เชิงเส้นจะซ่อนอิทธิพลของบิต: การเปลี่ยนบิตควบคุมในการดำเนินการเลือกสามารถพลิกบิตเอาท์พุตใดๆ ได้ ขึ้นอยู่กับข้อมูลที่เลือก
ค่าคงที่แฮชเริ่มต้น ค่าคงที่กำหนดการข้อความ จำนวนการหมุน และจำนวนรอบถูกเลือกทั้งหมดเพื่อเพิ่มเอฟเฟกต์หิมะถล่มให้สูงสุด ตัวเลขเหล่านี้ไม่ได้กำหนดขึ้นเอง มาจากข้อกำหนด SHA-2 และได้รับการเข้ารหัสอย่างกว้างขวาง การเปลี่ยนแปลงค่าคงที่หรือการนับรอบจะทำให้เกิดอัลกอริธึมที่แตกต่างออกไป (อาจเป็นอัลกอริธึมที่อ่อนกว่า)
ตัวอย่างการทำงาน — แฮชอินพุตสองตัวที่แตกต่างกันไปตามอักขระหนึ่งตัว และเปรียบเทียบการแยกย่อยทีละบิต
การทดสอบหิมะถล่มนั้นตรงไปตรงมา แฮชอินพุต abc และจดบันทึกย่อ จากนั้นแฮช abc ตามด้วยช่องว่าง หรือแทนที่อักขระหนึ่งตัวด้วยอย่างอื่น: abd เปรียบเทียบเอาต์พุตฐานสิบหก สำหรับ SHA-256 ประมาณครึ่งหนึ่งของเลขฐานสิบหก 64 จะแตกต่างกัน นับพวกเขา เวกเตอร์ทดสอบจากโพสต์ ToolAcre: abc สร้าง ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad สตริงว่างสร้าง e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 การย่อยเหล่านั้นไม่มีเลขฐานสิบหกเหมือนกัน
ลองใช้เครื่องคิดเลข ToolAcre ด้วยอินพุตใดก็ได้ แฮชประโยค จากนั้นเปลี่ยนตัวอักษรหนึ่งตัวแล้วแฮชอีกครั้ง นับเลขฐานสิบหกที่แตกต่างกัน คุณจะพบว่าประมาณครึ่งหนึ่ง (32 จาก 64 ในกรณีส่วนใหญ่) แตกต่างกัน นี่คือเอฟเฟกต์หิมะถล่มในการดำเนินการ มันเป็นคุณสมบัติของการออกแบบอัลกอริทึม ไม่ใช่ความบังเอิญ
Avalanche ไม่ได้ให้การค้นหาที่คล้ายคลึงกันหรือโดยตัวมันเองสามารถวัดปริมาณความต้านทานการชนได้
Avalanche ไม่ได้สร้างการค้นหาความคล้ายคลึงหรือการจับคู่โดยประมาณ หากคุณมีไดเจสต์ ba7816... และต้องการค้นหาไดเจสต์ที่คล้ายกัน คุณไม่มีทางลัด คุณต้องเดาหรือป้อนข้อมูลของผู้สมัครแบบดุร้าย แฮชแต่ละรายการ และตรวจสอบการจับคู่ที่ตรงกันทุกประการ เอฟเฟกต์หิมะถล่มทำให้ทุกการคาดเดามีโอกาสเท่าๆ กันที่จะให้ผลลัพธ์ที่เหมือนหรือแตกต่างไปจากเดิมอย่างสิ้นเชิง อัลกอริธึมการแฮชบางอย่าง (เรียกว่าการแฮชแบบไวต่อพื้นที่) ได้รับการออกแบบมาเพื่อรักษาความคล้ายคลึงกัน มีประโยชน์สำหรับการตรวจจับและการจัดกลุ่มที่เกือบจะซ้ำซ้อน แต่ไม่ใช่แฮชที่เข้ารหัส
Avalanche ไม่ได้ป้องกันการค้นหาการชนกันที่กำหนดอีกด้วย นักเข้ารหัสยังสามารถค้นหาอินพุตที่แตกต่างกันสองรายการที่สร้างข้อมูลย่อยเดียวกันได้ แต่พื้นที่การค้นหานั้นมีขนาดใหญ่มาก การค้นหาการชนกันที่กำหนดเป็นคำถามที่แตกต่างจากการแพร่กระจายของภาพ บทความนี้ไม่ได้อ้างอิงตัวเลขหรือไทม์ไลน์ของฮาร์ดแวร์ตามวันเกิดเนื่องจากไม่ได้ระบุไว้ในที่นี้ ขอบเขตในการป้องกันก็คือ หิมะถล่มเพียงอย่างเดียวไม่สามารถพิสูจน์หรือวัดปริมาณความต้านทานการชนได้
ประเด็นสำคัญ: ไม่มีพลาดเลย — ลองใช้การทดสอบหนึ่งอักขระในเครื่องคำนวณแฮช ToolAcre SHA และดูการเปลี่ยนแปลงสรุปทั้งหมด
เครื่องคำนวณแฮช ToolAcre SHA รันอัลกอริทึม SHA ผ่านการใช้ Web Crypto ของเบราว์เซอร์ คุณสามารถใช้มันเพื่อตรวจสอบหิมะถล่มได้ด้วยตัวเอง ความแม่นยำทุกบิตในอัลกอริธึมจะป้อนเข้าสู่เอาต์พุต และการใช้งาน Web Crypto ได้รับการตรวจสอบและดูแลรักษาโดยผู้จำหน่ายเบราว์เซอร์ คุณกำลังเห็นอัลกอริธึมจริงทำงานบนอินพุตจริง คุณสมบัติที่ขัดกับสัญชาตญาณที่การเปลี่ยนแปลงอักขระหนึ่งตัวเขียนการย่อยทั้งหมดใหม่ไม่ใช่ข้อบกพร่อง มันเป็นคุณสมบัติที่ทำให้การแฮชทำงาน
เมื่อคุณใช้แฮชในการตรวจสอบความสมบูรณ์ คุณจะต้องพึ่งพาหิมะถล่ม เมื่อคุณใช้เพื่อระบุที่อยู่เนื้อหา (เช่น การสรุปอิมเมจคอนเทนเนอร์) คุณจะต้องขึ้นอยู่กับคุณสมบัติที่ว่าการเปลี่ยนแปลงเล็กๆ น้อยๆ ทำให้เกิดการสรุปที่แตกต่างกันอย่างมากมาย เมื่อคุณใช้ในลายเซ็นดิจิทัล (โดยที่ลายเซ็นถูกคำนวณบนแฮชของข้อความ) เอฟเฟกต์หิมะถล่มช่วยให้มั่นใจได้ว่าการดัดแปลงข้อความจะทำให้เกิดการเปลี่ยนแปลงที่ตรวจพบได้ คุณสมบัตินี้เป็นรากฐานของการรักษาความปลอดภัยแบบแฮช