ฟังก์ชันแฮชย้อนกลับทำให้ความเป็นไปได้เพิ่มขึ้นแบบทวีคูณ แต่อินพุตมีจำนวนจำกัด ยังไง?

เมื่อพยายามย้อนกลับฟังก์ชันแฮช จะมีการสูญเสีย เช่น

ก+ข=ค
ให้ c=5 ลองกลับไปที่ a,b (ขั้นตอนก่อนหน้า)
(ก,ข)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)

แต่เมื่อพิจารณาจากคู่ (a,b) ใด ๆ เราจะได้ c=5 ในขั้นตอนต่อไป และแต่ละคู่เหล่านี้มีการเพิ่มขึ้นแบบเอกซ์โปเนนเชียลแบบเดียวกันที่ใช้เมื่อย้อนกลับ ดังนั้น ดูเหมือนว่าทุก ๆ ก้าวที่คุณถอยหลังจะเพิ่มจำนวนค่าที่เป็นไปได้ซึ่งนำไปสู่ ​​c=5 แบบทวีคูณ

นอกจากนี้ ไม่มีสองสาขาที่สามารถรวมกันใหม่ได้เมื่อย้อนกลับ เนื่องจากจะต้องแยกหนึ่ง (a,b,c) ออกเป็นสองส่วนที่เป็นไปได้ (a,b,c) ซึ่งเป็นการสุ่มที่ไม่ได้กำหนดและเป็นไปไม่ได้ในการแฮช

ปัญหาคือ มีจำนวนอินพุตจำกัด และค่าที่เป็นไปได้ (a,b,c) เป็นจำนวนจำกัด ดูเหมือนเป็นความขัดแย้ง และทางออกเดียวที่ฉันพบคือบางเส้นทางเป็นทางตัน เช่น ((a,b,c)!=เป็นไปได้ที่จะทำจากสิ่งอื่น (a,b,c)). แต่ฉันไม่คิดว่ามี (a,b,c) อยู่ ดังนั้นฉันอาจมีวิธีแก้ปัญหาผิดหรือเปล่า

ฟังก์ชันแฮชย้อนกลับทำให้ความเป็นไปได้เพิ่มขึ้นแบบทวีคูณ แต่อินพุตมีจำนวนจำกัด ยังไง?

ค่อนข้างเป็นไปตามที่เราคาดไว้ (เรื่องสั้น); การไม่รู้จักแต่ละครั้งจะเพิ่มความเป็นไปได้ 2 ดังนั้นคุณจะได้รับเลขชี้กำลัง - คุณอาจคิดว่าตารางความจริงเพื่อดูสิ่งนั้น มีอินพุตจำกัดสำหรับ SHA-256 เนื่องจากกฎการเติม นั่นคือ $2^{128}-1$. ข้อมูลที่คุณป้อนอาจไม่มากแต่ยังมีขอบเขตจำกัด

การย้อนกลับการดำเนินการแฮช SHA-256 ด้วยการแก้สมการ ( เราเรียกสิ่งนี้ว่า การโจมตีทางพีชคณิต) แทบจะเป็นไปไม่ได้เนื่องจากคุณต้องแก้ปัญหาการคำนวณสัญลักษณ์ (SAT) และ 3SAT คือ NP-Complete ไม่มีการรับประกันว่าทุกอินสแตนซ์ของ SHA-256 จะยาก. เมื่อเราพิจารณาว่าการโจมตีเชิงพีชคณิตของ AES (เอ็กซ์เอสแอล) ไม่เร็วกว่ากำลังเดรัจฉาน ฉันคาดหวังว่า SHA-256 รอบที่ 64 จะยากต่อการเข้ารหัสด้วยการโจมตีเชิงพีชคณิต นี่ยังไม่ได้หมายความว่าสำหรับค่าแฮชบางค่าอินสแตนซ์ก็จะยากเช่นกัน

แม้แต่พื้นที่อินพุต 64 บิต ฉันคาดว่าพีชคณิตจะยากกว่าการค้นหาพื้นที่อินพุต 64 บิตเพื่อค้นหาภาพก่อนหน้าของเอาต์พุตแฮชที่กำหนด

ในการคำนวณของคุณ คุณกำลังกำจัดความเป็นไปได้บางอย่างของตัวแปร นี่คือสิ่งที่เราคาดหวัง อย่างไรก็ตาม 64 รอบของการเข้ารหัสบล็อกภายในของ SHA-256 ชื่อ SHACAL2 จะไม่อนุญาตให้คุณดำเนินการมากนัก นี่ไม่ใช่วิธีที่จะ โจมตี SHA-256.

หนังสือกวี; การเข้ารหัสลับเกี่ยวกับพีชคณิต เป็นจุดเริ่มต้นของการโจมตีทางพีชคณิต และดูว่าประกาศใหม่ของพวกเขาช่วยทำลายได้อย่างไร การเข้ารหัส keeloq อย่างง่าย ในขณะที่ SHA-256 นั้นซับซ้อนกว่ามากที่จะต้องพิจารณา

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