ตัวอย่างของบุคคลที่ฉันให้ไว้ในคำถามข้างต้นถูกต้องในการยืนยันหรือไม่ - ตัวอย่างที่ 2 จะทำให้การชนกัน พูดตามความน่าจะเป็น เกิดขึ้นน้อยลงหรือไม่
มีการยืนยันหลายอย่าง ที่นั่น:
การยืนยันอย่างหนึ่งคือฟังก์ชัน 1 ของ รหัสผ่าน + เกลือ
ยอม กัญชา
ที่กำหนดโดย
แฮช = sha512 (รหัสผ่าน + เกลือ);
สำหรับ (i = 0; i <1,000; i++) {
แฮช = sha512(แฮช); // <-- อย่าทำแบบนี้!
}
มีโอกาสชนกันมากกว่าฟังก์ชัน 2 ของ รหัสผ่าน + เกลือ
ยอม กัญชา
ที่กำหนดโดย
แฮช = sha512 (รหัสผ่าน + เกลือ);
สำหรับ (i = 0; i <1,000; i++) {
แฮช = sha512(แฮช + รหัสผ่าน + เกลือ);
}
ซึ่งถูกต้องในทางทฤษฎี และในทางปฏิบัติสามารถสังเกตได้สำหรับแฮชแคบๆ เช่น 80 บิต
วิธีหนึ่งในการดูก็คือ
- ชุดเอาต์พุตของฟังก์ชันสุ่มคงที่ $H$ ย้ำ $n$ เวลามีแนวโน้มที่จะแคบลงเช่น $n$ เติบโต (อาร์กิวเมนต์: มันไม่สามารถเพิ่มขึ้นเมื่อ $n$ ทำ และผลลัพธ์ที่แคบลงจากการชนกันของแฮชที่วนซ้ำ ที่นี่ SHA-512);
- ความน่าจะเป็นของการชนกันของฟังก์ชันสุ่มสำหรับอินพุตที่แตกต่างกันแบบสุ่มสองตัวคือค่าผกผันของขนาดของชุดเอาต์พุต
ดังนั้นจึงเป็นที่เข้าใจได้ (แม้ว่าจะวนซ้ำฟังก์ชันสุ่ม $n$ ครั้งอาจให้ฟังก์ชันสุ่มไม่มากเท่าสิ่งที่เหลืออยู่ของชุดเอาต์พุต) ที่ความน่าจะเป็นของการชนกันของ $H^n(x)$ สำหรับความแตกต่างแบบสุ่มสองรายการ $x$ เพิ่มขึ้นด้วย $n$.
ที่จำกัดการต้านทานการชนกันของฟังก์ชัน 1 ซึ่ง สำหรับ
วนซ้ำ $H: h\mapsto\operatorname{SHA-512}(h)$. ในขณะที่ 2 ฟังก์ชันวนซ้ำจะเปลี่ยนเมื่ออินพุต รหัสผ่าน + เกลือ
การเปลี่ยนแปลง ดังนั้นชุดเอาต์พุตจึงหดตัวด้วย $n$ ขึ้นอยู่กับอินพุตนั้น ภายใต้แบบจำลองของแฮชเป็นฟังก์ชันสุ่ม 2 ยังเป็นฟังก์ชันสุ่มที่อาจเข้าถึงค่าเต็มได้ และความน่าจะเป็นของการชนกันของอินพุตที่แตกต่างกัน รหัสผ่าน + เกลือ
ไม่เพิ่มขึ้นตาม $n$ ทำ.
มีการยืนยันว่าด้วยเหตุผลนี้ในทางปฏิบัติเราควรใช้ 2 มากกว่า 1 และนั่นไม่ถูกต้องด้วยเหตุผลหลายประการ:
- อย่างน้อยสำหรับแฮชใดๆ ที่ต้านทานการชน เช่นเดียวกับ SHA-512 เราไม่จำเป็นต้องกังวลเกี่ยวกับการชนหรือรอบเลย
- ในบริบท (แอปพลิเคชันแฮชรหัสผ่าน) ต้านทานการชน ของฟังก์ชันวนซ้ำโดยรวมไม่ใช่ปัญหา ความต้านทานพรีอิมเมจ เป็น. และแม้แต่สำหรับ SHA-1 ซึ่งไม่ทนต่อการชนและมีความสมจริงใดๆ $n$เราไม่ต้องกังวลว่าการแตก 1 จะต้องมีการประเมินแฮชน้อยกว่าการแตก 2 อย่างมาก รวมถึงการคำนวณล่วงหน้าที่เหมือนจริง
ข้อดีของข้อ 2 คือ: ใช้งานในฮาร์ดแวร์ได้ยากกว่าเล็กน้อย เนื่องจากฮาร์ดแวร์ต้องใช้รหัสผ่านและเกลือในการวนซ้ำแต่ละครั้ง ซึ่งจะต้องเก็บไว้ ASICs เพื่อเร่งความเร็ว 2 จะซับซ้อนกว่า 1 นั่นคือเหตุผลเดียวที่ฉันเห็นว่า 2 แย่น้อยกว่า 1 ในทางปฏิบัติ มันยังคงไม่ดีเพราะ $n=1,000$ การวนซ้ำไม่ได้ช้าเพียงพอเมื่อเผชิญกับ ASIC หรือ GPU ที่ทำการค้นหารหัสผ่าน และเนื่องจากสิ่งทั้งหมดไม่ได้ใช้หน่วยความจำดังนั้นจึงสูญเสียการป้องกันพิเศษจากการค้นหารหัสผ่านที่ดุร้ายซึ่งแฮชรหัสผ่านหน่วยความจำที่ทันสมัย (เช่น เข้ารหัส หรือ อาร์กอน2) ให้.
การแฮชหลายครั้งจะปลอดภัยกว่าการแฮชครั้งเดียว
สิ่งนี้ขึ้นอยู่กับวัตถุประสงค์เป็นหลัก ซึ่งกำหนดแฮชที่จะใช้
- หากเรากำลังแฮชเพื่อจุดประสงค์ของ การยืดที่สำคัญซึ่งโดยทั่วไปแล้วคือเมื่อแฮชรหัสผ่านหรือข้อความรหัสผ่าน ใช่: ความปลอดภัยจากการค้นหาแบบเดรัจฉานบังคับจะเพิ่มขึ้นเป็นเส้นตรงตามจำนวนรอบ แต่อีกครั้ง เราควรใช้แฮชรหัสผ่านหน่วยความจำสำหรับการใช้เวลาเท่ากัน แม้แต่ของล้าสมัย เข้ารหัส จะให้ความปลอดภัยมากกว่าสิ่งก่อสร้างที่วนซ้ำแฮชอย่างเดียว เช่น PBKDF2 หรือฟังก์ชัน 1 และ 2 ซึ่งเป็นธรรมดาที่ไม่แนะนำในยุคของ ASIC, FPGA และ GPU สำหรับ แคร็กรหัสผ่าน.
- หากเรากำลังแฮชมากกว่าหนึ่งครั้งเพื่อเสริมกำลังฟังก์ชันแฮชการเข้ารหัสบางอย่างที่มีข้อบกพร่อง (เช่น ความต้านทานการชนกันนั้นพัง) เป็นไปได้ว่าใช่ เช่น. ฟังก์ชัน 2 (ด้วย
รหัสผ่าน + เกลือ
แทนที่ด้วยข้อความเพื่อแฮช) จะแก้ไขข้อบกพร่องด้านความปลอดภัยที่รู้จักทั้งหมดของ นพ.5 หรือ SHA-1 นอกเหนือจากความกว้างเอาต์พุต แม้ว่าเราจะสร้างรอบพิเศษเพียงรอบเดียวแทนที่จะเป็น 1,000 รอบ อย่างไรก็ตาม ประสิทธิภาพและความสามารถในการใช้งานนั้นมีราคาสูง เนื่องจากเราจำเป็นต้องแฮชข้อความสองครั้ง ดังนั้นในบางกรณีจึงเก็บข้อความนั้นไว้
- สำหรับวัตถุประสงค์ในการเข้ารหัสอื่น ๆ รวมถึงลายเซ็นและที่มาของคีย์จากไวด์คีย์โดยใช้แฮชสมัยใหม่ ไม่ เราสามารถใช้ SHA-2 หรือ SHA-3 (เพื่อตั้งชื่อในคำถาม) เพื่อวัตถุประสงค์เหล่านี้ การแฮชแบบวนซ้ำไม่จำเป็น และยังสามารถลดความต้านทานการชนได้เล็กน้อย (หากดำเนินการตามข้อ 1) โดยมีข้อยกเว้นประการหนึ่ง: หากการแฮชมี คุณสมบัติการขยายความยาว (เช่น SHA-2 มี แต่ไม่มี SHA-3) และหากไม่เป็นที่พึงปรารถนา ก็สมเหตุสมผลที่จะแฮชใหม่เมื่อผลลัพธ์ของแฮชออกมา (ซึ่งไม่จำเป็นต้องจัดเก็บข้อความสองครั้ง)