ผู้โจมตีถอดรหัสฟังก์ชันแฮชโดยมองหาความเป็นเส้นตรงได้อย่างไร

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

หัวข้อ "ความไม่เป็นเชิงเส้น" ชี้ให้เห็นว่าการทำให้ทุกสมการที่เกี่ยวข้องกับฟังก์ชันแฮชเป็นสมการเชิงเส้นหมายความว่าผู้โจมตีสามารถเข้าใจการใช้งานฟังก์ชันแฮชได้อย่างง่ายดาย

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

เพื่อหลีกเลี่ยงปัญหานี้ คุณต้องทำให้สมการไม่เป็นเชิงเส้นโดยใช้ตัวดำเนินการ AND แฮชทำการเปลี่ยนแปลงและ XOR-ing ได้ทุกประเภท แต่ขั้นตอนที่ไม่ใช่เชิงเส้นนี้คือสิ่งที่ทำให้พวกเขาปลอดภัย

แต่การมีเงื่อนไขที่ไม่ใช่เชิงเส้นนั้นไม่เพียงพอ คุณต้องแน่ใจว่าผู้โจมตีไม่สามารถยกเลิกเงื่อนไขที่ไม่ใช่เชิงเส้นออกจากสมการของคุณได้อย่างมีประสิทธิภาพโดยกำหนดอินพุตบางตัวเป็น 1 หรือ 0 นอกจากนี้ คุณต้องแน่ใจว่าเงื่อนไขจะไม่ถูกยกเลิกหากผู้โจมตีใช้ผลต่างของสมการสองสมการ หากคุณมีสูตร ++ สำหรับสูตรหนึ่งและอีกสูตร ++ สำหรับอีกบิต การเพิ่มทั้งสองจะให้ + ซึ่งตอนนี้เป็นเส้นตรงและอนุญาตให้ผู้โจมตีแก้ไขเพื่อให้ได้ความสัมพันธ์ระหว่างสองบิต ทุกสมการเชิงเส้นอิสระที่ผู้โจมตีสามารถสร้างได้จะลดความปลอดภัยของแฮชของคุณลง 1 บิต

คุณช่วยอธิบายรายละเอียดเพิ่มเติมเกี่ยวกับวิธีการทำงานนี้ได้ไหม เนื่องจากฟังก์ชันแฮชบางตัวใช้งานไม่ได้ คุณจะแสดงสถานการณ์ความเป็นเชิงเส้นบนฟังก์ชันแฮชนั้นได้อย่างไร โดยพื้นฐานแล้ว md5 เป็นตัวอย่าง (ไม่ปลอดภัยด้วยเหตุผลบางประการ) เหตุผลเชิงเส้นนี้ไม่ปลอดภัยหรือไม่ ถ้าเป็นเช่นนั้น หมายความว่าอย่างไรในแง่ของฟังก์ชันแฮช md5 สมการใดที่พบว่ามีลักษณะเป็นเส้นตรง? หาก md5 เป็นตัวอย่างที่ไม่ดี ตัวอย่างที่ดีคืออะไร โดยพื้นฐานแล้ว คุณจะมองหาความเป็นเชิงเส้นในฟังก์ชันแฮชทีละบิตได้อย่างไร มีเทคนิคอะไรบ้างที่จะใช้

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