เครื่องมือสำหรับนักพัฒนาซอฟต์แวร์ · SHA เครื่องคำนวณแฮช
อธิบาย Merkle–Damgård: การก่อสร้างเบื้องหลัง SHA-1 และ SHA-2
· พื้นหลัง
sha-256 การเข้ารหัส เบราว์เซอร์-apis
ฟังก์ชันการบีบอัดขนาดคงที่ไม่สามารถแฮชอินพุตตามอำเภอใจได้ด้วยตัวเอง Merkle–Damgård ล่ามโซ่ไว้ทีละบล็อก โพสต์นี้จะอธิบายการก่อสร้าง แนวคิดที่พิสูจน์ได้ และจุดอ่อนที่มี
อินพุตตามอำเภอใจ เอาต์พุตคงที่ — ปัญหาที่ฟังก์ชันแฮชทุกฟังก์ชันต้องแก้ไขก่อน
ฟังก์ชันแฮชจะต้องแมปอินพุตที่กำหนดเองกับเอาต์พุตคงที่ ข้อความขนาดสามไบต์และข้อความขนาดสามเมกะไบต์จะต้องสร้างเอาต์พุต 256 bits พอดีสำหรับ SHA-256 แฮชจะต้องถูกกำหนดไว้ ดังนั้นอินพุตเดียวกันจะสร้างเอาต์พุตเดียวกันเสมอ ผลลัพธ์จะต้องดูสุ่ม การเปลี่ยนอินพุตบิตเดียวควรเปลี่ยนบิตเอาต์พุตประมาณครึ่งหนึ่ง
ข้อกำหนดเหล่านี้ขัดแย้งกันตั้งแต่แรกเห็น เนื่องจากอัลกอริธึมที่รวดเร็วเพียงตัวเดียวไม่สามารถจัดการข้อความที่มีความยาวตามใจชอบได้ และสร้างเอาต์พุตที่มีความกว้างคงที่สม่ำเสมอ โครงสร้าง Merkle–Damgård แก้ไขปัญหานี้โดยใช้ฟังก์ชันการบีบอัดขนาดคงที่ซ้ำๆ กัน โดยป้อนเอาต์พุตของแต่ละแอปพลิเคชันลงในอินพุตของแอปพลิเคชันถัดไป โครงสร้างนี้ใช้โดย SHA-1 และ SHA-2 ทั้งหมด (SHA-256, SHA-384 และ SHA-512)
ฟังก์ชั่นการบีบอัด - มิกเซอร์ขนาดคงที่ที่รับสถานะและบล็อกแล้วส่งคืนสถานะใหม่
ฟังก์ชันการบีบอัดคือแกนหลักในการเข้ารหัสลับที่ขับเคลื่อนแฮช Merkle–Damgård ใช้สถานะขนาดคงที่ โดยปกติจะเป็น 256 bits สำหรับ SHA-256 หรือ 512 bits สำหรับ SHA-512 และบล็อกอินพุตขนาดคงที่ โดยปกติแล้ว 512 bits สำหรับ SHA-256 หรือ 1024 bits สำหรับ SHA-512 ฟังก์ชันการบีบอัดจะผสมเข้าด้วยกันโดยใช้การดำเนินการระดับบิต การหมุน และการค้นหาตาราง ทำให้เกิดสถานะใหม่ที่มีขนาดเท่ากัน ฟังก์ชันนี้จะต้องทนต่อการชนกัน: การค้นหาคู่ที่แตกต่างกัน (สถานะ บล็อก) สองคู่ที่สร้างเอาต์พุตเดียวกันจะต้องเป็นเรื่องยาก
ฟังก์ชันการบีบอัดนั้นไม่ใช่ฟังก์ชันแฮชที่สมบูรณ์ เนื่องจากไม่ได้จัดการความยาวอินพุตที่กำหนดเอง และไม่ได้จัดการอินพุตแรกซึ่งไม่มีสถานะก่อนหน้าด้วยซ้ำ แต่กลับกลายเป็นสิ่งก่อสร้างที่มีการก่อสร้างขนาดใหญ่ขึ้นแทน ฟังก์ชันการบีบอัดเป็นการดำเนินการเข้ารหัสเพียงอย่างเดียวที่ทำงานซ้ำๆ อย่างอื่นคือการทำบัญชีที่เชื่อมต่อฟังก์ชันนี้กับแฮชแบบเต็ม
การผูกมัดและเวกเตอร์การเริ่มต้น — วิธีที่บล็อกป้อนเข้าหากันจากสถานะเริ่มต้นคงที่
เวกเตอร์การเริ่มต้นคือสถานะเริ่มต้นคงที่ ซึ่งเลือกอย่างระมัดระวังเพื่อหลีกเลี่ยงความสมมาตรหรือจุดอ่อน สำหรับ SHA-256 นั้น IV คือคำ 32 บิตแปดคำที่ได้มาจากเศษส่วนของรากที่สองของจำนวนเฉพาะแปดตัวแรก ค่าเหล่านี้เป็นสิ่งที่กำหนดขึ้นเองได้ ดังนั้นการใช้งานทุกครั้งจึงให้ผลลัพธ์ที่เหมือนกัน บล็อกข้อความแรกผสมกับ IV โดยใช้ฟังก์ชันการบีบอัด ทำให้เกิดสถานะใหม่ บล็อกข้อความที่สองผสมกับสถานะนั้น ทำให้เกิดสถานะใหม่ขึ้นมา และต่อไปเรื่อยๆ ในทุกบล็อกของข้อความ
การผูกมัดนี้เป็นส่วนสำคัญ: ผลลัพธ์ของหนึ่งบล็อกจะขึ้นอยู่กับบล็อกก่อนหน้าทั้งหมด ดังนั้นการเปลี่ยนแปลงบิตใด ๆ ของบล็อกก่อนหน้าจะเปลี่ยนบล็อกต่อ ๆ ไปทั้งหมด เมื่อถึงเวลาที่บล็อกสุดท้ายได้รับการประมวลผล สถานะจะมีข้อมูลเกี่ยวกับทุกบิตของอินพุต การแพดดิ้งเป็นเคล็ดลับที่ทำให้การก่อสร้างนี้ฟังดูดี ข้อความไม่ได้แบ่งออกเป็นบล็อกเท่าๆ กันเสมอไป โครงสร้าง Merkle–Damgård ใช้ MD-strengthening: เติมหนึ่งบิตต่อท้ายข้อความ จากนั้นต่อท้าย 0 จนกระทั่งเหลือบล็อกเกือบเต็ม จากนั้นจึงต่อท้ายความยาวข้อความต้นฉบับ
การเสริมด้วยความยาวของข้อความ — เหตุใดการเสริมความแข็งแกร่งของ MD จึงเป็นสิ่งที่ทำให้การก่อสร้างฟังดูดี
อาร์กิวเมนต์ด้านความปลอดภัยสำหรับ Merkle–Damgård บอกว่าถ้าฟังก์ชันการบีบอัดทนต่อการชนกัน แฮชทั้งหมดก็จะทนต่อการชนกัน การพิสูจน์คือการลดลง: หากคุณพบการชนกันในแฮช คุณสามารถแยกการชนกันในฟังก์ชันการบีบอัดได้ ซึ่งขัดแย้งกับสมมติฐานที่ว่าฟังก์ชันการบีบอัดนั้นชนกันได้ยาก สัญชาตญาณก็คือว่าการชนกันในแฮชจะต้องทำให้เกิดการชนกันในการเรียกฟังก์ชันการบีบอัดรายการใดรายการหนึ่งในที่สุด เนื่องจากสถานะจะถูกยกยอดไปข้างหน้าโดยสมบูรณ์
จุดอ่อนใน Merkle–Damgård ถูกค้นพบเมื่อเวลาผ่านไป แม้ว่าการก่อสร้างขั้นพื้นฐานจะดีก็ตาม ส่วนขยายความยาวคือสิ่งหนึ่ง: ผู้โจมตีที่เห็นส่วนย่อยของข้อความสามารถขยายข้อความและคำนวณส่วนย่อยที่ถูกต้องสำหรับข้อความที่ยาวกว่าโดยไม่ต้องรู้อะไรเกี่ยวกับอินพุต การโจมตีพรีอิมเมจครั้งที่สองนั้นเป็นอีกวิธีหนึ่ง: เมื่อได้รับข้อความ การค้นหาข้อความอื่นที่มีแฮชเดียวกันนั้นง่ายกว่าที่ควรจะเป็นสำหรับข้อความบางประเภท จุดอ่อนเหล่านี้กระตุ้นให้เกิดการออกแบบ SHA-3 ซึ่งใช้แนวทางที่แตกต่างออกไปที่เรียกว่าโครงสร้างแบบฟองน้ำ
การขยายการเข้ารหัสความยาวจะแยกข้อความที่มีเบาะ หลักฐานความปลอดภัยเต็มรูปแบบคือหลักฐานจากพื้นที่เก็บข้อมูลภายนอก
ฟังก์ชันการบีบอัดสำหรับ SHA-256 ใช้สถานะ 256-บิต (แปดคำ 32-บิต) และบล็อก 512-บิต การดำเนินการใช้ 64 รอบ โดยแต่ละรอบจะผสมสถานะกับค่าคงที่และคำจากบล็อก การผสมใช้การดำเนินการระดับบิต: XOR, AND, NOT ใช้การหมุนและการเลื่อนที่ย้ายบิตไปรอบๆ โดยไม่เปลี่ยนบิตที่ตั้งไว้ ใช้การค้นหาตารางที่ให้การผสมแบบไม่เชิงเส้นซึ่ง XOR เพียงอย่างเดียวไม่สามารถทำได้
SHA-512 ใช้โครงสร้างเดียวกันกับ SHA-256 แต่มีการดำเนินการ 64-บิต แทนที่จะเป็นการดำเนินการ 32-บิต สถานะคือ 512 bits (แปดคำ 64 บิต) และขนาดบล็อกคือ 1024 bits ฟังก์ชันการบีบอัดมีการปัดเศษ 80 แทนที่จะเป็น 64 และค่าคงที่และการค้นหาตารางจะแตกต่างกัน สำหรับ SHA-384 ฟังก์ชันสถานะและการบีบอัดจะเหมือนกับ SHA-512 แต่จะมีเอาต์พุตเฉพาะ 384 bits แรกของสถานะสุดท้ายเท่านั้น 128 bits สุดท้ายถูกยกเลิก การตัดทอนนี้คือสาเหตุที่ SHA-384 ทนทานต่อการขยายความยาว
การขยายความยาวเป็นขอบเขตการก่อสร้างที่ได้รับการตรวจสอบแล้ว ละเว้นการอ้างสิทธิ์ multicollision และ SHA-3 แรงจูงใจ
การรักษาความปลอดภัยของแฮช Merkle–Damgård ขึ้นอยู่กับคุณสมบัติหลายประการที่ถือครอง ฟังก์ชั่นการบีบอัดจะต้องต้านทานการชน ดังนั้นการโจมตีโดยตรงจึงไม่สามารถทำได้ รูปแบบการเติมต้องแน่ใจว่าข้อความที่แตกต่างกันจะสร้างรูปแบบการเติมที่แตกต่างกัน ดังนั้นการชนกันในแฮชทุกครั้งจะต้องเกี่ยวข้องกับการชนกันของฟังก์ชันการบีบอัด ขนาดบล็อกและขนาดสถานะต้องมีขนาดใหญ่พอที่จะใช้กำลังดุร้ายไม่ได้ สถานะที่กว้างขึ้นจะขยายพื้นที่การค้นหาทั่วไป แต่บทความนี้ไม่ได้แนบจำนวนการดำเนินการหรือวันที่ความเป็นไปได้โดยไม่มีการสืบค้นแบบอินไลน์และแหล่งที่มาที่ได้รับการตรวจสอบ
หากผู้โจมตีพบจุดอ่อนในฟังก์ชันการบีบอัด หรือหากคอมพิวเตอร์ควอนตัมสามารถใช้งานได้จริงและสามารถค้นหาพื้นที่ที่ไม่มีโครงสร้างในเวลา sqrt(2^n) แทนที่จะเป็น 2^n เวลา ระยะขอบด้านความปลอดภัยก็จะลดลง จุดอ่อนที่เป็นแรงบันดาลใจ SHA-3 ไม่ใช่การหยุดทำงานของฟังก์ชันการบีบอัด แต่เป็นปัญหาการขยายความยาวและช่องโหว่ทางโครงสร้างอื่นๆ โครงสร้างฟองน้ำจะหลีกเลี่ยงสิ่งเหล่านี้โดยไม่เคยเผยแพร่สถานะภายในแบบเต็ม
สิ่งนี้ไม่ครอบคลุม — ฟังก์ชันรอบเฉพาะของ SHA-256 ครอบคลุมอยู่ในโพสต์แยกต่างหาก
วิธีที่โครงสร้าง Merkle–Damgård จัดการกับทุกขนาดอินพุตเป็นผลที่ตามมาในทางปฏิบัติของการออกแบบ แยกข้อความออกเป็นบล็อก 512 บิต วางบล็อกสุดท้าย ประมวลผลทุกบล็อกผ่านฟังก์ชันการบีบอัดตามลำดับ และส่งออกสถานะสุดท้าย สำหรับอินพุตแบบหนึ่งไบต์ การเติมจะสร้างบล็อก 512 บิต (หนึ่งไบต์ของข้อความ การเติมหนึ่งบิต 447 bits ของศูนย์ และ 64 bits สำหรับความยาว) จำนวนการบีบอัดคือจำนวนบล็อก 512 บิต ซึ่งเป็นสัดส่วนกับความยาวของข้อความ
ทุกการแยกย่อย ToolAcre SHA เครื่องคำนวณแฮชที่ผลิตมาจากโครงสร้างนี้ การแยกย่อย 64 อักขระ SHA-256 คือสถานะ 256 บิตสุดท้ายที่พิมพ์ในรูปแบบเลขฐานสิบหก การแยกย่อย 128 อักขระ SHA-512 คือสถานะ 512 บิตสุดท้ายที่พิมพ์ในรูปแบบเลขฐานสิบหก การย่อย 96 อักขระ SHA-384 เป็น 384 bits แรกของสถานะ 512 บิตสุดท้าย ช่องว่างภายในเบื้องหลังช่วยให้แน่ใจว่าทุกข้อความที่เป็นไปได้จะสร้างจำนวนบล็อกที่ถูกต้องและความกว้างของการแยกย่อยที่ถูกต้อง นี่คือโครงสร้าง Merkle–Damgård มาตรฐานที่ทำงานในเบราว์เซอร์
ประเด็นสำคัญ: โครงกระดูกเดียวกันที่อยู่เบื้องหลังอัลกอริธึมทั้งสี่ - ทุกการแยกย่อย ToolAcre SHA เครื่องคำนวณแฮชที่ผลิตมาจากโครงสร้างนี้
การทำความเข้าใจโครงสร้างมีประโยชน์ในการรู้ว่าเหตุใดการย่อยจึงมีความกว้างเท่ากันเสมอ และเหตุใดการเปลี่ยนแปลงอินพุตหนึ่งบิตจึงเปลี่ยนการย่อยทั้งหมด คุณสมบัติการผูกมัดหมายความว่าทุกบิตของอินพุตส่งผลต่อทุกบิตของเอาต์พุตผ่านชุดการดำเนินการผสม การเปลี่ยนแปลงเล็กน้อยในช่วงต้นของข้อความจะเผยแพร่ผ่านการบีบอัดที่ตามมาทั้งหมด ดังนั้นสรุปสุดท้ายจึงแตกต่างไปจากเดิมอย่างสิ้นเชิง คุณสมบัตินี้เรียกว่าเอฟเฟกต์หิมะถล่มและเป็นลายเซ็นของฟังก์ชันแฮชเสียง
โครงสร้าง Merkle–Damgård มีการใช้งานมานานหลายทศวรรษ และเป็นรากฐานของฟังก์ชันแฮชที่มีการใช้งานกันอย่างแพร่หลายมากที่สุด SHA-1 และ SHA-2 สร้างขึ้นจากโครงสร้างนี้ และระบบที่ใช้งานจำนวนมากอาศัยเอาต์พุต การก่อสร้างถูกสร้างขึ้นมากกว่าการทดลอง แต่ประวัติศาสตร์นั้นไม่ได้ทำให้ทุกการใช้งานปลอดภัย การขยายความยาวเป็นขอบเขตหนึ่งที่บันทึกไว้ การทำความเข้าใจโครงสร้างนี้ช่วยให้นักพัฒนาเข้าใจว่าทำไมคุณสมบัติความปลอดภัยบางอย่างจึงถูกระงับ และเหตุใดเวกเตอร์การโจมตีบางอย่างจึงมีอยู่