คุณสมบัติของฟังก์ชันแฮชคืออะไร?

จากมุมมองการเข้ารหัส ฟังก์ชันแฮชที่มีเอาต์พุตขนาดคงที่:

• ต้องเป็นฟังก์ชันเชิงกำหนด: อินพุตเดียวกันต้องสร้างเอาต์พุตเดียวกันเสมอ
• ต้องยอมรับข้อความอินพุตในชุดอินพุตแบบกว้าง ตามหลักการแล้วควรเป็น bitstring ตามอำเภอใจ แต่บ่อยครั้งเป็น bytestings หรือ character strings ตามอำเภอใจ อาจมีบางขนาด
• คัดแยกพิเศษ (เช่น คีย์ หรือ ความลับ หรือ สุ่ม) ต้องเป็นสาธารณะ: ทุกขั้นตอนและค่าคงที่ที่จำเป็นสำหรับการคำนวณเอาต์พุตสำหรับอินพุตที่กำหนดใดๆ นั้นเป็นที่รู้จักสำหรับทุกคน
• ต้องคำนวณผลลัพธ์เป็นพหุนามตามเวลาด้วยขนาดอินพุต ซึ่งควรเป็นเวลาเชิงเส้นโดยประมาณกับขนาดอินพุต
• ควรมี ต้านทานการชน: เป็นไปไม่ได้ในทางคำนวณที่จะแสดงสองข้อความที่แตกต่างกันด้วยเอาต์พุตเดียวกัน (คุณสมบัตินี้หมายถึง ความต้านทานพรีอิมเมจที่สองซึ่งเป็นอินพุตแบบสุ่ม เป็นไปไม่ได้ในทางคำนวณที่จะหาอินพุตอื่นที่ให้เอาต์พุตเดียวกัน) สังเกตว่าถ้ามี $n$ ผลลัพธ์ที่เป็นไปได้ มีการโจมตีแบบทั่วไปที่ทำลายการต้านทานการชนด้วย $\sqrtn$ การประเมินการทำงานจึงหมายถึงการต้านทานการชน $n$ มีขนาดใหญ่ (พูดอย่างน้อย $2^{192}$ ทุกวันนี้); หากไม่เป็นเช่นนั้น คำจำกัดความของการต้านทานการชนจะต้องคลายเป็น: วิธีที่ดีที่สุดในการแสดงข้อความสองข้อความที่แตกต่างกันด้วยเอาต์พุตเดียวกันคือการโจมตีทั่วไป
• ควรมี (ครั้งแรก) ความต้านทานพรีอิมเมจ: ให้เอาต์พุตสำหรับอินพุตที่ไม่รู้จักแบบสุ่ม เป็นไปไม่ได้ในทางคำนวณที่จะค้นหาอินพุตนั้น (หรืออินพุตอื่นที่มีเอาต์พุตเดียวกัน) ง่ายกว่าการลองอินพุต สังเกตว่าถ้ามี $n$ ผลลัพธ์ที่เป็นไปได้ มีการโจมตีทั่วไปที่ทำลายการต่อต้านพรีอิมเมจด้วยประมาณ $n$ การประเมินฟังก์ชัน ดังนั้นการต้านทานพรีอิมเมจจึงเป็นนัย $n$ มีขนาดใหญ่ (พูดอย่างน้อย $2^{96}$ ทุกวันนี้); หากไม่เป็นเช่นนั้น คำจำกัดความของความต้านทานต่อพรีอิมเมจจะต้องคลายลง

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

• สำหรับอินพุตสุ่มที่ไม่รู้จักซึ่งมีลักษณะตามธรรมชาติใดๆ (นั่นคือ ไม่ขึ้นกับคำจำกัดความของฟังก์ชันแฮช ตัวอย่างเช่น อินพุตที่ประกอบด้วยทศนิยม 40 หลักซึ่งผลรวมหารด้วย 10 ลงตัว) เอาต์พุตควรแยกไม่ออกจากการคำนวณจากการสุ่มแบบสม่ำเสมอใน ชุดเอาต์พุต
• ความต้านทานต่อการโจมตีแบบขยายความยาว: ให้เอาต์พุตสำหรับอินพุตที่ไม่รู้จัก $M$ไม่ควรคำนวณเอาต์พุตสำหรับอินพุตส่วนขยายของ $M$ (นั่นคือ $M\mathbin\|E$ เผื่อไม่ว่าง $E$) ง่ายกว่าโดยการค้นหา $M$ โดยลองอินพุต ขอให้สังเกตว่าแฮชทั่วไปเช่น SHA-256 ไม่มีคุณสมบัตินั้นในภายหลัง