ฉันเข้าใจว่าทำไมเราต้องการฟังก์ชันแฮชให้เร็วพอสำหรับการประมวลผล แต่ช้าพอสำหรับความปลอดภัย แต่ฉันไม่เข้าใจว่าทำไมฟังก์ชันแฮชที่เร็วมากสามารถทำให้เกิดการชนกันได้ ฉันเดาว่าฟังก์ชันแฮชที่รวดเร็วมากจะสร้างบิตจำนวนเล็กน้อยเป็นเอาต์พุต ดังนั้นนั่นจึงหมายถึงความน่าจะเป็นของการชนกันที่สูงขึ้น มีคนแก้ไขฉันได้ไหม
ในแอปพลิเคชันส่วนใหญ่ เป็นที่พึงปรารถนาว่าฟังก์ชันแฮชจะต้องทำงานเร็ว และจะไม่มีปัญหาหากทำงานเร็วเป็นพิเศษ (กล่าวคือ เร็วที่สุดเท่าที่อินพุตในหน่วยความจำแคชสามารถเข้าถึง CPU ได้) ถ้า นั่นไม่ใช่ค่าใช้จ่ายในการรักษาความปลอดภัย ซึ่งรวมถึงการใช้งานในลายเซ็น การเติมการเข้ารหัส การสร้างบล็อกรหัส
ในการสมัครทำ การยืดที่สำคัญรวมถึงการควบคุมการเข้าถึงด้วยรหัสผ่าน หรือการได้รับคีย์การเข้ารหัสแบบสมมาตรจากวลีรหัสผ่าน ควรมีฟังก์ชันแฮชที่ช้า แม่นยำยิ่งขึ้น พารามิเตอร์ควรควบคุมระยะเวลา และต้นทุนการคำนวณต่อแฮชสำหรับฝ่ายตรงข้ามไม่ควรต่ำกว่าสำหรับผู้ใช้ที่ถูกต้อง¹ ในแอปพลิเคชันดังกล่าว เมื่อเราจัดการกับการแฮชช้าลงด้วยปัจจัยของ $ค$ สำหรับศัตรู เราได้รับเทียบเท่ากับ $\log_2(c)$ บิตเพิ่มเติมเกี่ยวกับเอนโทรปีในการป้อนรหัสผ่าน/ข้อความรหัสผ่าน ตัวอย่างเช่น เมื่อเราเพิ่มต้นทุนหนึ่งพัน (สำหรับ $c\ประมาณ 2^{10}$ ) สำหรับการโจมตีการถอดรหัสรหัสผ่าน เราได้รับความปลอดภัยเทียบเท่ากับการเพิ่มทศนิยมสามหลักต่อท้ายรหัสผ่านโดยไม่จำเป็นต้องจำ
การพิจารณาความเร็วนั้นแตกต่างอย่างมากจากการต้านทานการชนกัน (นั่นคือ เป็นไปไม่ได้ในทางปฏิบัติที่จะแสดงข้อความสองข้อความที่มีแฮชเดียวกัน) สำหรับการต้านทานการชนเพื่อถือเป็นสิ่งจำเป็น (ไม่เพียงพอ)
¹ วิธีที่ดีที่สุดที่เราต้องทำให้สำเร็จคือการสร้างแฮช หน่วยความจำยากนั่นคือการประเมินควรต้องมีการเข้าถึงหน่วยความจำจำนวนมากในหน่วยความจำจำนวนมากที่ทุ่มเทให้กับการใช้งานนั้นในระหว่างการประเมินทั้งหมด ฟังก์ชั่นดังกล่าวรวมถึงความทันสมัย อาร์กอน2, เข้ารหัสและในระดับหนึ่งล้าสมัย เข้ารหัสแต่ก็ไม่เลวตรง PBKDF2 (ซึ่งเป็นหายนะเพราะใช้ RAM ต่ำทำให้ได้เปรียบคู่แข่งด้วย ASIC, FPGA หรือ GPU เมื่อเทียบกับผู้ใช้ส่วนใหญ่ที่ใช้ CPU)
² ดูของ Paul C. van Oorschot และ Michael J. Wiener การค้นหาการชนกันแบบขนานด้วยแอปพลิเคชัน Cryptanalytic, ใน วารสารวิทยาการเข้ารหัสลับ, 2542.
³ ดู Florian Mendel, Tomislav Nad และ Martin Schläffer's การปรับปรุงการชนในพื้นที่: การโจมตีใหม่บน SHA-256 ที่ลดลง, ใน การดำเนินการของ Eurocrypt 2013
คำตอบที่ยอมรับในปัจจุบันนั้นดี แต่ฉันต้องการเพิ่มบางอย่าง "ความปลอดภัย" เป็นคำกว้างๆ ในบริบทนี้ และคุณควรถามว่าคุณต้องการป้องกันภัยคุกคามใด ในการอภิปรายส่วนใหญ่ "การปะทะกัน" เป็นเรื่องเกี่ยวกับการค้นหาอินพุตที่แตกต่างกันซึ่งมีเอาต์พุตที่เหมือนกันแต่สำหรับกรณีรหัสผ่าน "แฮชเร็ว" เป็นปัญหาสำหรับการบังคับเดรัจฉานแบบเก่าธรรมดา ด้วยแฮชที่รวดเร็ว ผู้โจมตีจึงสามารถโจมตีพจนานุกรมได้หลายอินพุตที่เป็นไปได้โดยมองหาการจับคู่กับแฮช
ไม่ใช่กรณีของ "แฮชเร็ว == เอาต์พุตน้อยเกินไป" ตามที่ OP ถาม เป็นเพียงว่าหากแฮชเร็วเกินไป การค้นหาอินพุตดั้งเดิม (ไม่ใช่การชนกัน) ก็ง่ายเช่นกัน ซึ่งทำให้ไม่ปลอดภัย
ให้ฟังก์ชันแฮชที่สามารถปรับแต่งสำหรับ "ความเร็ว" (การวนซ้ำ บางที) เพิ่มความเร็วที่มันแฮชไม่ได้ สร้าง การชนกันมากขึ้น ปัญหาด้านความปลอดภัยของแฮชที่เร็วเกินไปคือเมื่อกำหนดจำนวน X ของเวลา แฮชที่เร็วกว่าจะสร้างเอาต์พุตในปริมาณที่มากขึ้น ดังนั้นผู้โจมตีจึงมีโอกาสสูงที่จะ การหา การชนกัน
OP ได้แนวคิดมาจาก โพสต์ YouTube ที่โต้แย้งเกี่ยวกับ MD5
นี่คือข้อโต้แย้งง่ายๆ ถ้าใครดูวิดีโอ
ความเร็วไม่ได้หมายความว่าฟังก์ชันแฮชไม่ปลอดภัย แต่การออกแบบทำให้ปลอดภัย.
ในช่วงหลายปีที่ผ่านมา ผู้วิจัยพบจุดอ่อนในการออกแบบ MD5 และปรับปรุงเมื่อเวลาผ่านไป เมื่อ MD5 เปิดตัวในปี 1992 การโจมตีก็เริ่มต้นขึ้น และในปี 2010 Xie และ Dengguo Feng ได้ประกาศ การชนกันของ MD5 บล็อกเดียว (512 บิต) ที่เผยแพร่ครั้งแรก. แน่นอน การปรับปรุง CPU และวงจรของมันช่วยให้การโจมตีเร็วขึ้น อย่างไรก็ตาม การสนับสนุนหลักคือวิธีการโจมตี พิจารณาว่าการโจมตีแบบชนกันทั่วไป (การโจมตีวันเกิด) จำเป็นต้องใช้ $2^{64}$ MD5 แฮชที่มีโอกาสสำเร็จ 1/2 แม้กระทั่งทุกวันนี้ CPU ธรรมดายังทำไม่ได้ $2^{64}$ ใน ได้เวลาอันสมควร. ในทางกลับกัน เรามีการปะทะกันในทันทีสำหรับ MD5 ดูคอร์กามิ.
ในทางกลับกัน Blake2 คือ a ฟังก์ชันแฮชที่รวดเร็วมากเร็วกว่า MD5 และ SHA-1 และไม่มีการโจมตีแบบขยายความยาวเนื่องจากใช้ไฟล์ โครงสร้างไฮฟาแก้ไขการออกแบบ MD มันเร็วกว่า MD5 และปลอดภัย อย่างน้อยก็ในลักษณะที่คาดการณ์ได้ ขนาดเอาต์พุตมีความปลอดภัยเพียงพอสำหรับการโจมตีแบบขนานขนาดใหญ่หรือแม้แต่สำหรับ อัลกอริทึมการค้นหาควอนตัมของโกรเวอร์. ชุดเบลคตอนนี้มี เบลค3, มันเป็นแฮชแบบขนานและ เร็วมาก.
สิ่งสำคัญเกี่ยวกับความเร็วและความสัมพันธ์กับความปลอดภัยคือขนาดสรุป การโจมตีทั่วไปสำหรับการโจมตีก่อนภาพ การโจมตีภาพก่อนภาพรอง และการชนทั่วไปคือ $2^n$,$2^n$, และ $2^{n/2}$ตามลำดับ หากคุณมีเอาต์พุต 256 หรือ 512 บิต คุณก็ไม่มีปัญหาเกี่ยวกับการโจมตีทั่วไป โปรดจำไว้ว่า พื้นที่ป้อนข้อมูลสั้น เป็นปัญหาสำหรับการโจมตีด้วยภาพล่วงหน้า และ HMAC ได้รับคำแนะนำ
PS: การแฮชรหัสผ่าน (ไม่จำเป็นต้องมีการต้านทานการชนกัน) ซึ่งเราต้องการความเร็วที่ควบคุมได้ ความแข็งของหน่วยความจำและจำนวนเธรดของฟังก์ชันแฮชรหัสผ่าน เราควรอ่านคำถามที่เป็นที่ยอมรับจากไซต์ที่เคารพของเรา ความปลอดภัยของข้อมูล. อีกด้วย, กระดาษอาร์กอน2ผู้ชนะการแข่งขันการแฮชรหัสผ่านประจำปี 2015 เป็นตัวเลือกที่ดีในการอ่าน
หมายเหตุสุดท้าย: เราควรกำหนดปัญหาอย่างรอบคอบเพื่อให้สามารถบรรลุการออกแบบที่ปลอดภัย ไม่มีความปลอดภัยที่แท้จริงหากคุณไม่ทราบความเสี่ยงของคุณ
ลองพิจารณาการใช้แฮชเพื่อป้องกันรหัสผ่าน และยกตัวอย่างสองสามตัวอย่าง
กรณีแรก: เรามีฟังก์ชันแฮชที่ใช้ 1 วินาที เพื่อดำเนินการบนคอมพิวเตอร์ที่ใช้งานทั่วไป หากผู้โจมตีสามารถเข้าถึงคอมพิวเตอร์ 1 ล้านเครื่อง (เช่น ผ่านบ็อตเน็ต) พวกเขาสามารถพยายาม 1 ล้านครั้งต่อวินาที หรือ 86 พันล้านครั้งต่อวัน แต่รหัสผ่าน 8 อักขระที่ใช้ตัวเลขบน ล่าง ตัวเลขและสัญลักษณ์มีค่าเอนโทรปีประมาณ 50 บิต ดังนั้นประสิทธิภาพปัจจุบันจะยังคงใช้เวลาประมาณ 18 ปี เพื่อแคร็กรหัสผ่านนั้น แม้ว่าจะมีบอตเน็ตจำนวนมหาศาลก็ตาม (แน่นอนว่าในอีก 18 ปีข้างหน้า สิ่งต่างๆ คงจะเร็วขึ้นมากทีเดียว ดังนั้นมันจะสั้นกว่านั้น แต่ก็ยังอยู่) กรณีที่เลวร้ายที่สุดจะใช้เวลา 36 ปี
กรณีที่สอง: เรามีฟังก์ชันแฮชที่ใช้ 1 ไมโครวินาที เพื่อดำเนินการ ผู้โจมตีรายเดียวกันที่ใช้บ็อตเน็ตคอมพิวเตอร์เครื่องเดียวกันหลายล้านเครื่องสามารถพยายามได้มากกว่าหนึ่งล้านครั้งต่อวินาที ตอนนี้ใช้เวลา 1125 วินาที (น้อยกว่า 20 นาที) เพื่อลองใช้รหัสผ่าน 8 อักขระที่เป็นไปได้ประมาณ 2^50 ตัว โดยเฉลี่ยประมาณครึ่งเวลา
หากคุณคิดว่าบ็อตเน็ตที่มีคอมพิวเตอร์หนึ่งล้านเครื่องเป็นเรื่องเพ้อฝัน คิดอีกครั้ง.
ดังนั้นมันจึงไม่ใช่เรื่องของการทำให้เกิดการชนกันมากขึ้น (สำหรับฟังก์ชันแฮชที่เหมาะสม สิ่งนี้จะเชื่อมโยงโดยตรงกับขนาดของเอาต์พุต ไม่ใช่ความเร็วของแฮช) แต่เป็นเรื่องของความสามารถในการค้นหาการชนกัน (หรือจริงๆ แล้ว ต้นฉบับ อินพุต แต่คุณไม่จำเป็นต้องรู้) เอาชนะจุดประสงค์ของแฮช
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
