การแฮชหลายครั้งจะมากขึ้น น้อยลง หรือปลอดภัยเทียบเท่ากับการแฮชครั้งเดียว

การแฮชหลายครั้งจะมากขึ้น น้อยลง หรือปลอดภัยเทียบเท่ากับการแฮชครั้งเดียวหรือไม่

ล้างคำถามนี้:

• ฉันเห็นการอ้างสิทธิ์นี้:
  • รายการ: อย่าทำสิ่งนี้: hash = sha512(รหัสผ่าน + เกลือ); สำหรับ (i = 0; i <1,000; i++) { hash = sha512(hash); // <-- อย่าทำแบบนี้! } แต่ถ้าคุณกำลังจะแฮชสองเท่าให้ทำสิ่งนี้ แฮช = sha512 (รหัสผ่าน + เกลือ); สำหรับ (i = 0; i <1,000; i++) { hash = sha512(hash + รหัสผ่าน + เกลือ); }
  • ดู: https://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms/4948393#4948393
• สำหรับฉันแล้ว ดูเหมือนว่าคุณกำลังพยายามทำ rehashing เพื่อทำให้การโจมตีของเดรัจฉานช้าลง
• แม้ว่าปัญหาวันเกิดอาจนำไปใช้กับการแฮชหลายครั้ง แต่ดูเหมือนว่าจะใช้ได้กับตัวอย่างแรก (ซึ่งบุคคลนั้นระบุว่า "อย่าทำสิ่งนี้") เช่นเดียวกับตัวอย่างที่สอง (ซึ่งบุคคลนั้นรู้สึกสบายใจมากกว่า)
• ในทั้งสองตัวอย่าง เมื่อพบการชนกัน การรีแฮชที่จุดนั้นถือเป็นสิ่งที่สงสัย (เนื่องจากจะสร้างผลลัพธ์เดียวกันระหว่างการแฮชและการชนกัน)
• สถานการณ์เฉพาะสำหรับคำถามนี้คือ: ตัวอย่างของบุคคลที่ฉันให้ไว้ในคำถามของฉันข้างต้นถูกต้องในการยืนยันหรือไม่ - ตัวอย่างที่ 2 จะทำให้การชนกัน ซึ่งพูดตามความน่าจะเป็น เกิดขึ้นน้อยลงหรือไม่

สิ่งที่ฉันกำลังมองหาในคำตอบ:

• นี่ไม่ใช่สาขาความเชี่ยวชาญของฉัน (ซึ่งเป็นเหตุผลที่ฉันถามที่นี่ ความเชี่ยวชาญของคุณอยู่ที่ไหน) โปรดอย่าลังเลที่จะแก้ไขความเข้าใจผิดและสมมติฐานที่เป็นปัญหาของฉัน
• ฉันสนใจทั้งคำอธิบายทางเทคนิคโดยละเอียดตราบเท่าที่มีคำอธิบายขั้นตอนของคนธรรมดาและโดยเฉพาะอย่างยิ่งบทสรุป (โดยเน้นที่คำอธิบายของคนธรรมดา)
• ฉันกำลังถามในทางทฤษฎีเกี่ยวกับฟังก์ชันการแฮชทางเดียวทั้งหมด (หากมีความแตกต่างระหว่างอัลกอริธึมการแฮชประเภทต่างๆ ในวงกว้าง โปรดอย่าลังเลที่จะชี้ให้เห็นถึงสิ่งเหล่านั้นโดยทั่วๆ ไป ในขณะที่เข้าใจว่าความหมายของคำตอบของคุณจะถูกนำไปใช้กับอัลกอริทึมการแฮชที่คล้ายกัน เป็น SHA-2, SHA-3 หรือ bcrypt)
• ฉันได้ตรวจสอบคำถามและคำตอบของ crypto.stackexchange.com ที่แตกต่างกัน 10 ข้อซึ่งดูเหมือนจะคล้ายกับคำถามนี้มาก แต่ไม่ว่าจะจัดการกับกรณีการใช้งานเฉพาะที่สร้างคำตอบให้กับกรณีการใช้งาน หรือพวกเขาให้ข้อพิสูจน์ทางทฤษฎีโดยไม่ต้องอธิบายในคนธรรมดา เงื่อนไขว่าข้อพิสูจน์ของพวกเขากำลังทำอะไรอยู่จริง ๆ และบทสรุปของคนธรรมดาต่อคำตอบของพวกเขา
  • สำหรับจุดประสงค์ของคำถามนี้ สมมติว่าแคลคูลัสของฉันไม่เสมอกัน และโดยทั่วไปฉันอ่านตัวแปรทางคณิตศาสตร์ที่ใช้ในวิทยาการเข้ารหัสลับไม่ได้ แต่สมมติว่าฉันทำตามพีชคณิตได้และสามารถปัดฝุ่นแคลคูลัสของฉันได้ ถ้าคุณบอกฉันว่าตัวแปรอะไร ย่อมาจาก (หรือลิงค์ไปยังคำอธิบายของพวกเขา)

ขอขอบคุณล่วงหน้าสำหรับความช่วยเหลือของคุณเกี่ยวกับคำถามนี้

ตัวอย่างของบุคคลที่ฉันให้ไว้ในคำถามข้างต้นถูกต้องในการยืนยันหรือไม่ - ตัวอย่างที่ 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) และหากไม่เป็นที่พึงปรารถนา ก็สมเหตุสมผลที่จะแฮชใหม่เมื่อผลลัพธ์ของแฮชออกมา (ซึ่งไม่จำเป็นต้องจัดเก็บข้อความสองครั้ง)

นี่คือคำอธิบายที่เข้าใจได้ง่าย (เมื่อเทียบกับความเข้มงวด):

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

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

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

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

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

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

หวังว่าจะมีใครแสดงสิ่งนี้ได้อย่างเข้มงวดมากขึ้นโดยใช้ทฤษฎีบทของพีชคณิตนามธรรม และคุณสมบัติของกลุ่มแฮช LSR ตั้งตารอ.ขอบคุณสำหรับคำถาม