ในการเข้ารหัสลับฟังก์ชันการบีบอัดแบบทางเดียวคือฟังก์ชันที่แปลงอินพุตความยาวคงที่สองตัวให้เป็นเอาต์พุตความยาวคงที่^{[ 1 ]}การแปลงนี้เป็นแบบ "ทางเดียว"หมายความว่าการคำนวณอินพุตที่บีบอัดเป็นเอาต์พุตนั้นทำได้ยากเมื่อกำหนดเอาต์พุตเฉพาะ ฟังก์ชันการบีบอัดแบบทางเดียวไม่เกี่ยวข้องกับ อัลกอริธึม การบีบอัดข้อมูล แบบดั้งเดิม ซึ่งสามารถผกผันได้อย่างแม่นยำ (การบีบอัดแบบไม่สูญเสีย) หรือโดยประมาณ (การบีบอัดแบบสูญเสีย) ไปยังข้อมูลต้นฉบับ

ตัวอย่างเช่น ฟังก์ชันการบีบอัดแบบทางเดียวถูกนำมาใช้ในการสร้าง Merkle–Damgårdภายในฟังก์ชันแฮชเข้ารหัสลับ

ฟังก์ชันการบีบอัดแบบทางเดียวมักสร้างขึ้นจากรหัสบล็อกวิธีการบางอย่างที่ใช้แปลงรหัสบล็อกปกติให้เป็นฟังก์ชันการบีบอัดแบบทางเดียว ได้แก่Davies–Meyer , Matyas–Meyer–Oseas , Miyaguchi–Preneel (ฟังก์ชันการบีบอัดความยาวบล็อกเดียว) และMDC-2/Meyer–Schilling , MDC-4 , Hirose (ฟังก์ชันการบีบอัดความยาวบล็อกสองเท่า) วิธีการเหล่านี้จะอธิบายรายละเอียดเพิ่มเติมในส่วนถัดไป ( MDC-2ยังเป็นชื่อของฟังก์ชันแฮชที่จดสิทธิบัตรโดยIBM ด้วย )

อีกวิธีหนึ่งคือ2BOW (หรือNBOWโดยทั่วไป) ซึ่งเป็น "ฟังก์ชันแฮชความยาวหลายบล็อกอัตราสูงที่อิงตามการเข้ารหัสบล็อก" ^{[ 2 ]}และโดยทั่วไปจะบรรลุอัตรา (เชิงอะซิมโทติก) ระหว่าง 1 ถึง 2 โดยไม่ขึ้นอยู่กับขนาดของแฮช (โดยมีค่าใช้จ่ายคงที่เล็กน้อยเท่านั้น) วิธีนี้ยังไม่ได้รับการวิเคราะห์ความปลอดภัยอย่างจริงจัง ดังนั้นควรจัดการด้วยความระมัดระวัง

ฟังก์ชันการบีบอัดจะผสมข้อมูลอินพุตสองชุดที่มีความยาวคงที่ และสร้างข้อมูลเอาต์พุตชุดเดียวที่มีความยาวคงที่เท่ากับขนาดของข้อมูลอินพุตชุดใดชุดหนึ่ง กล่าวอีกนัยหนึ่งคือ ฟังก์ชันการบีบอัดจะแปลงข้อมูลอินพุตขนาดใหญ่ที่มีความยาวคงที่ให้เป็นข้อมูลเอาต์พุตที่มีความยาวคงที่และสั้นลง

ตัวอย่างเช่นข้อมูลนำเข้า Aอาจมีขนาด 128 บิตข้อมูลนำเข้า Bก็มีขนาด 128 บิต และถูกบีบอัดรวมกันเป็นข้อมูลส่งออกเดียวที่มีขนาด 128 บิต ซึ่งเทียบเท่ากับการบีบอัดข้อมูลนำเข้าขนาด 256 บิตหนึ่งตัวให้เหลือข้อมูลส่งออกเดียวที่มีขนาด 128 บิต

ฟังก์ชันการบีบอัดบางฟังก์ชันไม่ได้บีบอัดลงครึ่งหนึ่ง แต่บีบอัดด้วยปัจจัยอื่นแทน ตัวอย่างเช่นข้อมูลนำเข้า Aอาจมี 256 บิต และข้อมูลนำเข้า Bมี 128 บิต ซึ่งจะถูกบีบอัดให้เหลือข้อมูลส่งออกเดียวที่มีขนาด 128 บิต นั่นคือ ข้อมูลนำเข้าทั้งหมด 384 บิตจะถูกบีบอัดรวมกันเป็นข้อมูลส่งออก 128 บิต

การผสมสัญญาณทำในลักษณะที่ ทำให้เกิด เอฟเฟกต์แบบลูกโซ่ อย่างสมบูรณ์ กล่าวคือ บิตเอาต์พุตทุกบิตขึ้นอยู่กับบิตอินพุตทุกบิต

ฟังก์ชันทางเดียวคือฟังก์ชันที่คำนวณได้ง่ายแต่หาค่าผกผันได้ยาก ฟังก์ชันการบีบอัดทางเดียว (หรือเรียกว่าฟังก์ชันแฮช) ควรมีคุณสมบัติดังต่อไปนี้:

• คำนวณง่าย: หากคุณมีข้อมูลป้อนเข้า ก็สามารถคำนวณผลลัพธ์ได้อย่างง่ายดาย
• ความต้านทานต่อภาพต้นฉบับ: หากผู้โจมตีรู้เพียงผลลัพธ์ การคำนวณอินพุตควรเป็นไปไม่ได้ กล่าวอีกนัยหนึ่งคือ เมื่อกำหนดผลลัพธ์แล้ว การคำนวณอินพุตเพื่อให้ ได้ ผลลัพธ์ นั้นควรเป็นไปไม่ได้${\displaystyle h}$${\displaystyle m}$${\displaystyle \operatorname {hash} (m)=h}$
• ความต้านทานต่อภาพก่อนหน้าแบบที่สอง: เมื่อกำหนดอินพุตที่มีเอาต์พุตเป็นควรจะเป็นไปไม่ได้ที่จะหาอินพุตอื่นที่มีเอาต์พุตเดียวกันนั่นคือ${\displaystyle m_{1}}$${\displaystyle h}$${\displaystyle m_{2}}$${\displaystyle h}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$
• ความต้านทานต่อการชน:ควรจะยากที่จะหาอินพุตสองชุดที่แตกต่างกันซึ่งบีบอัดแล้วได้เอาต์พุตเดียวกัน กล่าวคือ ผู้โจมตีไม่ควรจะสามารถหาคู่ข้อความใดๆที่ทำให้ ได้ ผลลัพธ์เดียวกัน ได้ เนื่องจากปรากฏการณ์วันเกิด (ดูเพิ่มเติมที่การโจมตีวันเกิด ) มีโอกาส 50% ที่จะพบการชนกันได้ในเวลาประมาณ โดยที่ คือจำนวนบิตในเอาต์พุตของฟังก์ชันแฮช ดังนั้น การโจมตีฟังก์ชันแฮชจึงไม่ควรจะสามารถหาการชนกันได้ด้วยการ ทำงานที่น้อยกว่าประมาณ${\displaystyle m_{1}\neq m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{n/2}}$${\displaystyle n}$${\displaystyle 2^{n/2}}$

ตามหลักการแล้ว เราอยากให้ "ความเป็นไปไม่ได้" ในการต้านทานภาพต้นฉบับและการต้านทานภาพต้นฉบับลำดับที่สอง หมายถึงงานที่มีระยะเวลาประมาณ โดยที่คือจำนวนบิตในผลลัพธ์ของฟังก์ชันแฮช อย่างไรก็ตาม โดยเฉพาะอย่างยิ่งสำหรับการต้านทานภาพต้นฉบับลำดับที่สอง นี่เป็นปัญหาที่ยากลำบาก ${\displaystyle 2^{n}}$${\displaystyle n}$

การใช้งานทั่วไปของฟังก์ชันการบีบอัดทางเดียวคือการสร้าง Merkle–Damgård ภายในฟังก์ชันแฮชการเข้ารหัส ฟังก์ชันแฮชที่ใช้กันอย่างแพร่หลายที่สุด รวมถึงMD5 , SHA-1 (ซึ่งเลิกใช้แล้ว^{[ 3 ]} ) และSHA-2ใช้การสร้างนี้

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

เมื่อมีการใช้การเติมความยาว (เรียกอีกอย่างว่าการเสริมความแข็งแกร่งของ MD) การโจมตีจะไม่สามารถค้นหาการชนกันได้เร็วกว่าปรากฏการณ์วันเกิด ( โดยที่ขนาดบล็อกเป็นบิต) หากฟังก์ชันที่ใช้มีความทนทานต่อการชนกัน^{[ 4 ] [ 5 ]}ดังนั้น การสร้างแฮช Merkle–Damgård จึงลดปัญหาการค้นหาฟังก์ชันแฮชที่เหมาะสมลงเหลือเพียงการค้นหาฟังก์ชันการบีบอัดที่เหมาะสม ${\displaystyle 2^{n/2}}$${\displaystyle n}$${\displaystyle f}$

การโจมตีภาพก่อนหน้าครั้งที่สอง (เมื่อได้รับข้อความผู้โจมตีจะพบข้อความอื่นที่ตรงตามเงื่อนไข) สามารถทำได้ตาม Kelsey และ Schneier ^{[ 6 ]}สำหรับข้อความบล็อกข้อความในเวลาความซับซ้อนของการโจมตีนี้จะถึงค่าต่ำสุดสำหรับข้อความยาวเมื่อและเข้าใกล้เมื่อข้อความสั้น ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{3n/4+2}}$${\displaystyle k=2^{n/4}}$${\displaystyle 2^{n}}$

ฟังก์ชันการบีบอัดแบบทางเดียวมักสร้างขึ้นจากรหัสบล็อก

การเข้ารหัสแบบบล็อก (เช่นเดียวกับฟังก์ชันการบีบอัดแบบทางเดียว) รับอินพุตสองชุดที่มีขนาดคงที่ ( กุญแจและข้อความต้นฉบับ ) และส่งคืนเอาต์พุตเดียว ( ข้อความที่เข้ารหัสแล้ว ) ซึ่งมีขนาดเท่ากับข้อความต้นฉบับที่ป้อนเข้ามา

อย่างไรก็ตาม การเข้ารหัสแบบบล็อกสมัยใหม่นั้นเป็นแบบทางเดียวเพียงบางส่วนเท่านั้น กล่าวคือ เมื่อมีข้อความต้นฉบับและข้อความที่เข้ารหัสแล้ว การหาคีย์ที่สามารถเข้ารหัสข้อความต้นฉบับให้เป็นข้อความที่เข้ารหัสได้นั้นเป็นไปไม่ได้ แต่เมื่อมีข้อความที่เข้ารหัสและคีย์แล้ว ก็สามารถหาข้อความต้นฉบับที่ตรงกันได้ง่ายๆ โดยใช้ฟังก์ชันการถอดรหัสของการเข้ารหัสแบบบล็อก ดังนั้น เพื่อเปลี่ยนการเข้ารหัสแบบบล็อกให้เป็นฟังก์ชันการบีบอัดแบบทางเดียว จึงต้องเพิ่มการดำเนินการพิเศษบางอย่างเข้าไป

วิธีการบางอย่างในการแปลงการเข้ารหัสแบบบล็อกปกติให้เป็นฟังก์ชันการบีบอัดแบบทางเดียว ได้แก่ Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (ฟังก์ชันการบีบอัดความยาวบล็อกเดียว) และ MDC-2, MDC-4, Hirose (ฟังก์ชันการบีบอัดความยาวบล็อกสองเท่า)

ฟังก์ชันการบีบอัดข้อมูลที่มีความยาวบล็อกเดียวจะให้ผลลัพธ์เป็นจำนวนบิตเท่ากับจำนวนบิตที่ประมวลผลโดยการเข้ารหัสแบบบล็อกพื้นฐาน ดังนั้น ฟังก์ชันการบีบอัดข้อมูลที่มีความยาวบล็อกสองเท่าจึงให้ผลลัพธ์เป็นจำนวนบิตเป็นสองเท่า

สมมติว่าการเข้ารหัสแบบบล็อกมีขนาดบล็อก 128 บิต วิธีการเข้ารหัสแบบความยาวบล็อกเดียวจะสร้างฟังก์ชันแฮชที่มีขนาดบล็อก 128 บิตและให้ค่าแฮชขนาด 128 บิต ในขณะที่วิธีการเข้ารหัสแบบความยาวบล็อกสองเท่าจะสร้างค่าแฮชที่มีขนาดเป็นสองเท่าของขนาดบล็อกของการเข้ารหัสแบบบล็อกที่ใช้ ดังนั้นการเข้ารหัสแบบบล็อก 128 บิตจึงสามารถแปลงเป็นฟังก์ชันแฮชขนาด 256 บิตได้

จากนั้นจึงนำวิธีการเหล่านี้ไปใช้ภายในโครงสร้าง Merkle–Damgård เพื่อสร้างฟังก์ชันแฮชจริง วิธีการเหล่านี้จะอธิบายโดยละเอียดในส่วนถัดไป

การใช้การเข้ารหัสแบบบล็อกเพื่อสร้างฟังก์ชันการบีบอัดแบบทางเดียวสำหรับฟังก์ชันแฮชมักจะช้ากว่าการใช้ฟังก์ชันการบีบอัดแบบทางเดียวที่ออกแบบมาเป็นพิเศษในฟังก์ชันแฮช เนื่องจากโครงสร้างที่ปลอดภัยที่รู้จักทั้งหมดจะทำการกำหนดตารางคีย์สำหรับแต่ละบล็อกของข้อความ Black, Cochran และ Shrimpton ได้แสดงให้เห็นว่าเป็นไปไม่ได้ที่จะสร้างฟังก์ชันการบีบอัดแบบทางเดียวที่เรียกใช้การเข้ารหัสแบบบล็อกเพียงครั้งเดียวด้วยคีย์คงที่^{[ 7 ]}ในทางปฏิบัติ ความเร็วที่เหมาะสมจะเกิดขึ้นได้หากการกำหนดตารางคีย์ของการเข้ารหัสแบบบล็อกที่เลือกไม่ใช่การดำเนินการที่หนักเกินไป

แต่ในบางกรณี การใช้การเข้ารหัสแบบบล็อกเพียงครั้งเดียวจะง่ายกว่า เพราะสามารถใช้ได้ทั้งสำหรับการเข้ารหัสแบบบล็อกและฟังก์ชันแฮช นอกจากนี้ยังช่วยประหยัด พื้นที่ โค้ดในระบบฝังตัว ขนาดเล็กมาก เช่นสมาร์ทการ์ดหรืออุปกรณ์ในรถยนต์หรือเครื่องจักรอื่นๆ

ดังนั้น อัตราแฮชหรืออัตราการประมวลผลจึงให้ภาพรวมของประสิทธิภาพของฟังก์ชันแฮชโดยอิงจากฟังก์ชันการบีบอัดที่กำหนด อัตราของฟังก์ชันแฮชแบบวนซ้ำแสดงถึงอัตราส่วนระหว่างจำนวนการดำเนินการเข้ารหัสบล็อกและผลลัพธ์ กล่าวคือ อัตราแสดงถึงอัตราส่วนระหว่างจำนวนบิตที่ประมวลผลของอินพุตความยาวบิตเอาต์พุตของการเข้ารหัสบล็อก และการดำเนินการเข้ารหัสบล็อกที่จำเป็นในการสร้างบิตเอาต์พุตเหล่านี้ โดยทั่วไป การใช้การดำเนินการเข้ารหัสบล็อกน้อยลงจะส่งผลให้ประสิทธิภาพโดยรวมของฟังก์ชันแฮชทั้งหมดดีขึ้น แต่ก็อาจทำให้ค่าแฮชเล็กลงซึ่งอาจไม่เป็นที่ต้องการ อัตราแสดงด้วยสูตร: ${\displaystyle m}$${\displaystyle n}$${\displaystyle s}$${\displaystyle n}$

${\displaystyle R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}}$

ฟังก์ชันแฮชจะถือว่าปลอดภัยได้ก็ต่อเมื่อเป็นไปตามเงื่อนไขอย่างน้อยดังต่อไปนี้:

• การเข้ารหัสแบบบล็อกไม่มีคุณสมบัติพิเศษใด ๆ ที่แตกต่างจากการเข้ารหัสในอุดมคติ เช่น กุญแจที่อ่อนแอ หรือกุญแจที่นำไปสู่การเข้ารหัสที่เหมือนกันหรือเกี่ยวข้องกัน (จุดคงที่หรือการชนกันของกุญแจ)
• ขนาดแฮชที่ได้นั้นใหญ่พอแล้ว ตามทฤษฎีการโจมตีแบบวันเกิดระดับความปลอดภัยที่^2⁸⁰ (ซึ่งโดยทั่วไปถือว่าคำนวณได้ยากในปัจจุบัน) ถือเป็นระดับที่พึงประสงค์ ดังนั้นขนาดแฮชควรมีอย่างน้อย 160 บิต
• บล็อกสุดท้ายจะถูกเติมความยาวอย่างเหมาะสมก่อนทำการแฮช (ดูโครงสร้าง Merkle–Damgård ) การเติมความยาวมักจะถูกนำไปใช้และจัดการภายในโดยฟังก์ชันแฮชเฉพาะทาง เช่นSHA-1เป็นต้น

โครงสร้างที่นำเสนอต่อไปนี้: Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel และ Hirose ได้รับการพิสูจน์แล้วว่ามีความปลอดภัยภายใต้การวิเคราะห์แบบกล่องดำ^{[ 8 ] [ 9 ]}เป้าหมายคือการแสดงให้เห็นว่าการโจมตีใดๆ ที่สามารถพบได้นั้นมีประสิทธิภาพสูงสุดเท่ากับการโจมตีแบบวันเกิดภายใต้สมมติฐานบางประการ แบบจำลองกล่องดำสมมติว่ามีการใช้การเข้ารหัสแบบบล็อกที่เลือกแบบสุ่มจากชุดที่มีการเข้ารหัสแบบบล็อกที่เหมาะสมทั้งหมด ในแบบจำลองนี้ ผู้โจมตีสามารถเข้ารหัสและถอดรหัสบล็อกใดๆ ได้อย่างอิสระ แต่ไม่สามารถเข้าถึงการใช้งานการเข้ารหัสแบบบล็อกได้ ฟังก์ชันการเข้ารหัสและการถอดรหัสแสดงโดยออราเคิลที่รับคู่ของข้อความธรรมดาและกุญแจ หรือข้อความที่เข้ารหัสและกุญแจ จากนั้นออราเคิลจะตอบกลับด้วยข้อความธรรมดาหรือข้อความที่เข้ารหัสที่เลือกแบบสุ่ม หากคู่ดังกล่าวถูกขอเป็นครั้งแรก ทั้งสองใช้ตารางร่วมกันสำหรับสามสิ่งนี้ ซึ่งเป็นคู่จากคำถามและการตอบกลับที่สอดคล้องกัน และส่งคืนบันทึก หากได้รับคำถามเป็นครั้งที่สอง สำหรับการพิสูจน์นั้น มีอัลกอริธึมการค้นหาการชนกันที่ทำการสอบถามไปยังออราเคิลแบบสุ่ม อัลกอริธึมจะส่งคืนค่า 1 หากการตอบกลับสองครั้งส่งผลให้เกิดการชนกันที่เกี่ยวข้องกับฟังก์ชันแฮชที่สร้างขึ้นจากฟังก์ชันการบีบอัดที่ใช้การเข้ารหัสแบบบล็อกนี้ (0 ในกรณีอื่น ๆ) ความน่าจะเป็นที่อัลกอริธึมจะส่งคืนค่า 1 ขึ้นอยู่กับจำนวนการสอบถาม ซึ่งเป็นตัวกำหนดระดับความปลอดภัย

ฟังก์ชันการบีบอัดแบบบล็อกเดียวของ Davies–Meyer จะป้อนแต่ละบล็อกของข้อความ ( ) เป็นกุญแจให้กับการเข้ารหัสแบบบล็อก โดยจะป้อนค่าแฮชก่อนหน้า ( ) เป็นข้อความธรรมดาที่จะถูกเข้ารหัส จากนั้นข้อความที่เข้ารหัสแล้วจะถูกXOR (⊕) กับค่าแฮชก่อนหน้า ( ) เพื่อสร้างค่าแฮชถัดไป ( ) ในรอบแรก หากไม่มีค่าแฮชก่อนหน้า จะใช้ค่าเริ่มต้นคงที่ที่กำหนดไว้ล่วงหน้า ( ) ${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i}}$${\displaystyle H_{0}}$

ในทางคณิตศาสตร์สามารถอธิบายสมการ Davies–Meyer ได้ดังนี้:

${\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}}$

โครงการนี้มีอัตรา (k คือขนาดของคีย์):

${\displaystyle R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}}$

หากการเข้ารหัสแบบบล็อกใช้คีย์ขนาด 256 บิต ตัวอย่างเช่น บล็อกข้อความแต่ละบล็อก ( ) จะเป็นส่วนย่อยของข้อความขนาด 256 บิต หากการเข้ารหัสแบบบล็อกเดียวกันใช้ขนาดบล็อก 128 บิต ค่าแฮชขาเข้าและขาออกในแต่ละรอบจะมีขนาด 128 บิต ${\displaystyle m_{i}}$

วิธีการนี้สามารถปรับเปลี่ยนได้ โดยแทนที่การดำเนินการ XOR ด้วยการดำเนินการกลุ่มอื่นๆ เช่น การบวกจำนวนเต็ม 32 บิตที่ไม่มีเครื่องหมาย

คุณสมบัติที่โดดเด่นของโครงสร้าง Davies–Meyer คือ แม้ว่าการเข้ารหัสบล็อกพื้นฐานจะปลอดภัยอย่างสมบูรณ์ ก็ยังสามารถคำนวณจุดคงที่สำหรับโครงสร้างได้: สำหรับค่าใดๆ ก็ตามสามารถหาค่าของ ได้เช่นนั้น: เพียงแค่ต้องตั้งค่า[ ^{10 ] นี่}เป็นคุณสมบัติที่ฟังก์ชันสุ่มไม่มีอย่างแน่นอน จนถึงขณะนี้ยังไม่มีการโจมตีในทางปฏิบัติใดๆ ที่อิงตามคุณสมบัตินี้ แต่ควรตระหนักถึง "คุณลักษณะ" นี้ จุดคงที่สามารถใช้ในการโจมตีแบบ preimage ครั้งที่สอง (เมื่อกำหนดข้อความผู้โจมตีจะหาข้อความอื่นที่ตรงตามเงื่อนไข) ของ Kelsey และ Schneier ^{[ 6 ]}สำหรับข้อความบล็อก -ข้อความ ในเวลาหากโครงสร้างไม่อนุญาตให้สร้างจุดคงที่ได้ง่าย (เช่น Matyas–Meyer–Oseas หรือ Miyaguchi–Preneel) การโจมตีนี้สามารถทำได้ในเวลา ในทั้งสองกรณี ความซับซ้อนจะสูงกว่าแต่ต่ำกว่าเมื่อข้อความยาว และเมื่อข้อความสั้นลง ความซับซ้อนของการโจมตีจะเข้าใกล้ ${\displaystyle m}$${\displaystyle h}$${\displaystyle E_{m}(h)\oplus h=h}$${\displaystyle h=E_{m}^{-1}(0)}$${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle 3\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

ความปลอดภัยของการสร้าง Davies–Meyer ใน Ideal Cipher Model ได้รับการพิสูจน์ครั้งแรกโดย R. Winternitz ^{[ 11 ]}

ฟังก์ชันการบีบอัดทางเดียวความยาวบล็อกเดียวของ Matyas–Meyer–Oseas สามารถพิจารณาได้ว่าเป็นคู่ตรงข้าม (ตรงกันข้าม) ของ Davies–Meyer

โดยจะป้อนแต่ละบล็อกของข้อความ ( ) เป็นข้อความธรรมดาที่จะถูกเข้ารหัส ข้อความที่เข้ารหัสแล้วจะถูก XOR (⊕) กับบล็อกข้อความเดียวกัน ( ) เพื่อสร้างค่าแฮชถัดไป ( ) ค่าแฮชก่อนหน้า ( ) จะถูกป้อนเป็นกุญแจสำหรับการเข้ารหัสแบบบล็อก ในรอบแรกหากไม่มีค่าแฮชก่อนหน้า จะใช้ค่าเริ่มต้นคงที่ที่กำหนดไว้ล่วงหน้า ( ) ${\displaystyle m_{i}}$${\displaystyle m_{i}}$${\displaystyle H_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{0}}$

หากการเข้ารหัสแบบบล็อกมีขนาดบล็อกและขนาดคีย์ที่แตกต่างกัน ค่าแฮช ( ) จะมีขนาดไม่ถูกต้องสำหรับการใช้งานเป็นคีย์ การเข้ารหัสอาจมีข้อกำหนดพิเศษอื่นๆ เกี่ยวกับคีย์ด้วย จากนั้นค่าแฮชจะถูกป้อนผ่านฟังก์ชันเพื่อแปลง/เติมให้พอดีกับขนาดคีย์สำหรับการเข้ารหัสก่อน ${\displaystyle H_{i-1}}$${\displaystyle g}$

ในสัญลักษณ์ทางคณิตศาสตร์ Matyas–Meyer–Oseas สามารถอธิบายได้ดังนี้:

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}$

โครงการนี้มีอัตราดังนี้:

${\displaystyle R_{MMO}={\frac {n}{1\cdot n}}=1}$

การโจมตีภาพก่อนหน้าครั้งที่สอง (เมื่อได้รับข้อความผู้โจมตีจะพบข้อความอื่นที่ตรงตามเงื่อนไข) สามารถทำได้ตาม Kelsey และ Schneier ^{[ 6 ]}สำหรับข้อความบล็อกข้อความในเวลาความซับซ้อนจะสูงกว่าแต่ต่ำกว่าเมื่อข้อความยาว และเมื่อข้อความสั้นลง ความซับซ้อนของการโจมตีจะเข้าใกล้ ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

ฟังก์ชันการบีบอัดทางเดียวความยาวบล็อกเดียวของ Miyaguchi–Preneel เป็นรูปแบบที่ขยายเพิ่มเติมของ Matyas–Meyer–Oseas ซึ่งได้รับการเสนอโดยอิสระจากShoji MiyaguchiและBart Preneel

โดยจะป้อนแต่ละบล็อกของข้อความ ( ) เป็นข้อความธรรมดาที่จะถูกเข้ารหัส ข้อความที่เข้ารหัสแล้วจะถูก XOR (⊕) กับบล็อกข้อความเดียวกัน ( ) จากนั้นจึง XOR กับค่าแฮชก่อนหน้า ( ) เพื่อสร้างค่าแฮชถัดไป ( ) ค่าแฮชก่อนหน้า ( ) จะถูกป้อนเป็นกุญแจสำหรับการเข้ารหัสแบบบล็อก ในรอบแรกหากไม่มีค่าแฮชก่อนหน้า จะใช้ค่าเริ่มต้นคงที่ที่กำหนดไว้ล่วงหน้า ( ) ${\displaystyle m_{i}}$${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{0}}$

หากการเข้ารหัสแบบบล็อกมีขนาดบล็อกและขนาดคีย์ที่แตกต่างกัน ค่าแฮช ( ) จะมีขนาดไม่ถูกต้องสำหรับการใช้งานเป็นคีย์ การเข้ารหัสอาจมีข้อกำหนดพิเศษอื่นๆ เกี่ยวกับคีย์ด้วย จากนั้นค่าแฮชจะถูกป้อนผ่านฟังก์ชันเพื่อแปลง/เติมให้พอดีกับขนาดคีย์สำหรับการเข้ารหัสก่อน ${\displaystyle H_{i-1}}$${\displaystyle g}$

ในทางคณิตศาสตร์ สามารถอธิบาย Miyaguchi–Preneel ได้ดังนี้:

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}$

โครงการนี้มีอัตราดังนี้:

${\displaystyle R_{MP}={\frac {n}{1\cdot n}}=1}$

บทบาทของและอาจสลับกันได้ ทำให้ถูกเข้ารหัสภายใต้กุญแจซึ่งทำให้วิธีการนี้เป็นส่วนขยายของ Davies–Meyer แทน ${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i-1}}$${\displaystyle m_{i}}$

การโจมตีภาพก่อนหน้าครั้งที่สอง (เมื่อได้รับข้อความผู้โจมตีจะพบข้อความอื่นที่ตรงตามเงื่อนไข) สามารถทำได้ตาม Kelsey และ Schneier ^{[ 6 ]}สำหรับข้อความบล็อกข้อความในเวลาความซับซ้อนจะสูงกว่าแต่ต่ำกว่าเมื่อข้อความยาว และเมื่อข้อความสั้นลง ความซับซ้อนของการโจมตีจะเข้าใกล้ ${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

ฟังก์ชันการบีบอัดทางเดียวความยาวบล็อกสองเท่า ของ Hirose ^{[ 9 ]}ประกอบด้วยการเข้ารหัสบล็อกบวกกับการเรียงสับเปลี่ยน ฟังก์ชันนี้ได้รับการเสนอโดย Shoichi Hirose ในปี 2549 และอิงตามผลงาน^{[ 12 ]}ของMridul Nandi ${\displaystyle p}$

มันใช้การเข้ารหัสแบบบล็อกที่มีความยาวของคีย์มากกว่าความยาวของบล็อกและสร้างค่าแฮชที่มีขนาดตัวอย่างเช่นตัวเลือกใด ๆ ของ AESที่มีคีย์ 192 หรือ 256 บิต (และบล็อก 128 บิต) ${\displaystyle k}$${\displaystyle n}$${\displaystyle 2n}$

แต่ละรอบจะรับส่วนหนึ่งของข้อความที่มีความยาวเป็นบิต และใช้ส่วนนั้นเพื่ออัปเดตค่า สถานะสองบิตและ${\displaystyle m_{i}}$${\displaystyle kn}$${\displaystyle n}$${\displaystyle G}$${\displaystyle H}$

ขั้นแรกนำมาต่อกันเพื่อสร้างคีย์จากนั้นค่าฟีดแบ็กทั้งสองจะได้รับการอัปเดตตามลำดับดังนี้: ${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle K_{i}}$

• ${\displaystyle G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}}$
• ${\displaystyle H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})}$

${\displaystyle p(G_{i-1})}$คือการเรียงสับเปลี่ยนแบบไม่มีจุดคงที่โดยพลการบนค่าบิต ซึ่งโดยทั่วไปจะกำหนดเป็นสำหรับค่าคงที่ที่ไม่เป็นศูนย์โดยพลการ(การเลือกเลข 1 ทั้งหมดอาจสะดวกกว่า) ${\displaystyle n}$${\displaystyle p(x)=x\oplus c}$${\displaystyle c}$

การเข้ารหัสแต่ละครั้งมีลักษณะคล้ายกับการสร้างแบบ Davies–Meyer มาตรฐาน ข้อดีของวิธีการนี้เมื่อเทียบกับวิธีการความยาวบล็อกสองเท่าอื่นๆ ที่เสนอมาคือ การเข้ารหัสทั้งสองใช้กุญแจเดียวกัน ดังนั้นจึงสามารถแบ่งปันความพยายามในการกำหนดตารางเวลากุญแจได้

ผลลัพธ์สุดท้ายคือ. แผนการนี้มีอัตราที่สัมพันธ์กับการเข้ารหัสข้อความด้วยรหัสลับ ${\displaystyle H_{t}||G_{t}}$${\textstyle R_{Hirose}={\frac {k-n}{2n}}}$

นอกจากนี้ ฮิโรเสะยังได้เสนอข้อพิสูจน์ในแบบจำลองการเข้ารหัสในอุดมคติอีกด้วย

โครงสร้างฟองน้ำสามารถใช้สร้างฟังก์ชันการบีบอัดทางเดียวได้^{[ 3 ]}

• Whirlpool — ฟังก์ชันแฮชเข้ารหัสลับที่สร้างขึ้นโดยใช้โครงสร้าง Miyaguchi–Preneel และการเข้ารหัสแบบบล็อกที่คล้ายกับSquareและAES
• CBC-MAC , OMACและPMAC — วิธีการแปลงรหัสบล็อกให้เป็นรหัสตรวจสอบความถูกต้องของข้อความ (MAC)