เทคนิคการค้นหาฟังก์ชันแฮชจำนวนเต็มแบบอัตโนมัติ

Hash Function Prospector

เครื่องมือนี้เป็นเครื่องมือขนาดเล็กสำหรับการค้นหาฟังก์ชันแฮชจำนวนเต็มแบบอัตโนมัติ โดยสุ่มเลือกการดำเนินการแบบย้อนกลับได้ 9 แบบเพื่อสร้างฟังก์ชันแฮชจำนวนเต็มได้หลายพันล้านตัว ฟังก์ชันที่สร้างขึ้นจะถูกคอมไพล์แบบ JIT และจะประเมินพฤติกรรม Avalanche และฟังก์ชันที่ดีที่สุดในปัจจุบันจะถูกพิมพ์ออกมาในรูปแบบไวยากรณ์ภาษา C

• คะแนน Avalanche: จำนวนบิตผลลัพธ์เฉลี่ยที่ยังคงสถานะเดิมเมื่อกลับบิตป้อนเข้าเพียงบิตเดียว ยิ่งคะแนนต่ำยิ่งดี โดยแนวคิดโดยตรงคือ 0 คะแนน; นั่นคือ เมื่อกลับบิตป้อนเข้าเดี่ยวหนึ่งบิต บิตผลลัพธ์ทั้งหมดควรถูกกลับด้วยความน่าจะเป็น 50%
• Prospector สามารถสร้างฟังก์ชันแฮชจำนวนเต็มได้ทั้งแบบ 32 บิตและ 64 บิต ตรวจสอบตัวเลือกทั้งหมดได้จากตัวช่วยใช้งาน (-h) โดย JIT compiler ทำให้รองรับเฉพาะ x86-64 แต่ฟังก์ชันที่ค้นพบสามารถใช้ได้ในทุกสภาพแวดล้อม

ฟังก์ชันแฮชที่ค้นพบ

มีฟังก์ชันแฮชที่เป็นประโยชน์อีก 2 คลาสที่ Prospector และยูทิลิตี้เสริมอื่น ๆ ที่มีอยู่ได้ค้นพบ ทั้งสองใช้โครงสร้าง xorshift-multiply-xorshift เหมือนกัน แต่อัตราจำนวนรอบต่างกัน

ฟังก์ชัน 2 รอบ

TheIronBorn ใช้การเพิ่มประสิทธิภาพแบบ combinatorial optimization เพื่อค้นหาพารามิเตอร์ที่ดีที่สุดที่ทราบสำหรับโครงสร้างนี้

• ค่าพารามิเตอร์การสับเปลี่ยน (permutation) 32 บิต 2 รอบนี้มีอคติต่ำเป็นพิเศษ และยังสามารถเอาชนะ MurmurHash3 32-bit finalizer ได้โดยส่วนต่างเพียงเล็กน้อย
• โครงสร้างฟังก์ชันแฮชนี้ถูกค้นพบโดย Prospector และปรับจูนพารามิเตอร์โดยใช้ hill climbing และ genetic algorithm

มีค่าคงที่ 2 รอบที่อคติต่ำยิ่งขึ้นอีกมาก และบางค่าดีกว่า lowbias32

ฟังก์ชัน 3 รอบ

การเพิ่มรอบ multiply-xorshift อีกหนึ่งรอบในโครงสร้างนี้ทำให้สามารถเข้าถึงขีดจำกัดอคติตามทฤษฎีได้ด้วยการเลือกพารามิเตอร์อย่างระมัดระวัง ตัวอย่างเช่น ฟังก์ชันแฮชนี้ไม่สามารถแยกแยะจาก PRF ที่สมบูรณ์แบบได้

• triple32 ไม่เพียงแต่แก้ปัญหา hash(0) = 0 แต่ยังลดอคติลงได้อีกด้วย
• มีค่าคงที่ 3 รอบที่อคติต่ำมากขึ้นอีกเช่นกัน

การวัดอคติที่แม่นยำ

โหมด -E จะประเมินอคติของฟังก์ชันแฮชที่ระบุ (-p หรือ -l) โดยปกติ Prospector ใช้ค่าประมาณเพื่อประเมินอคติของฟังก์ชันเพื่อให้เร็วขึ้น แต่เป็นแบบไม่กำหนดและมีสัญญาณรบกวนค่อนข้างสูง หากต้องการวัดอคติอย่างแม่นยำและครบถ้วนให้ใช้ตัวเลือก -e

• สามารถกำหนดฟังก์ชันที่ต้องตรวจสอบได้ด้วยการใช้ -p กับแพทเทิร์น หรือใช้ shared library ที่มีฟังก์ชัน hash() ร่วมกับ -l
• การทดสอบที่แม่นยำและครบถ้วนสำหรับฟังก์ชันแฮช 64 บิตไม่มีเนื่องจากใช้เวลานานเกินไป

การเลือกการดำเนินการแบบย้อนกลับได้

ใช้การดำเนินการต่อไปนี้:

• x = ~x;
• x ^= constant;
• x *= constant | 1; (เฉพาะค่าคงที่คี่เท่านั้น)
• x += constant;
• x ^= x >> constant;
• x ^= x << constant;
• x += x << constant;
• x -= x << constant;
• x <<<= constant; (หมุนซ้าย)
• x = bswap(x) (สลับไบต์สูงและไบต์ต่ำ)

โดยทางเทคนิคแล้ว x = ~x ถูกครอบคลุมด้วย x ^= constant; อยู่แล้ว แต่ ~x มีลักษณะเฉพาะและมีประโยชน์เป็นพิเศษมาก

แฮช 16 บิต

เนื่องจากข้อจำกัดของแฮช 16 บิตแตกต่างกัน จึงมีเครื่องมืออีกตัวสำหรับสร้างแฮชประเภทนี้ชื่อ hp16

• ต่างจาก Prospector 32 บิต/64 บิต โค้ดนี้ถูกออกแบบให้พกพาได้ และรันได้แทบทุกระบบ
• สามารถสร้างและประเมินผล S-box ขนาด 128KiB ได้
• แฮช 16 บิตอาจมีความจำเป็นมากขึ้นในเครื่องที่ไม่มีคำสั่งคูณที่เร็ว ในระหว่างการค้นหาจึงสามารถข้ามการดำเนินการบางส่วนได้ (-m, -r)

ผลลัพธ์ที่น่าสนใจหลายรายการ:

• แฮช xorshift-multiply 2 รอบ
• แฮช xorshift-multiply 3 รอบ
• แฮชที่ไม่มีการคูณ (ใช้เฉพาะ xorshift-add)

การค้นหา xorshift 3 รอบที่ดีผ่านการค้นหาแบบสั้น (hp16 -Xn3) ให้ใกล้ชิดกับ S-box ที่ดี (hp16 -S)

เมื่อทำงานกับการคำนวณ 16 บิต ต้องระวังกฎการแปลงประเภทตัวแปรจำนวนเต็มของภาษา C โปรแกรม C ที่ระบบนี้พิมพ์ออกมาจะให้ความสำคัญกับการแปลงการคำนวณ 16 บิตเป็น unsigned int ในกรณีที่จำเป็น

ความคิดเห็นของ GN⁺

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

• อย่างไรก็ตาม ความปลอดภัยของฟังก์ชันแฮชไม่สามารถรับรองได้ด้วยคุณสมบัติทางสถิติอย่างเดียว ฟังก์ชันแฮชเชิงเข้ารหัสต้องมีความทนทานต่อการโจมตีหลายชนิด เช่น PreImage Resistance, Second PreImage Resistance และ Collision Resistance จึงควรมีการวิเคราะห์ด้านเหล่านี้เพิ่มอีกด้วย

• แฮช 16 บิตน่าจะมีประโยชน์ในสภาพแวดล้อมที่จำกัด เช่น IoT หรือระบบฝังตัว เนื่องจากการที่สามารถสร้างฟังก์ชันแฮชที่ใช้เฉพาะ ADD/XOR/SHIFT ช่วยให้ใช้งานได้บน CPU ที่ไม่มีคำสั่งคูณ

• การนำเทคนิคค้นหาแบบ heuristic เช่น Hill Climbing หรือ Genetic Algorithm มาใช้กับการออกแบบฟังก์ชันแฮชเป็นแนวคิดที่สดใหม่ ขณะนี้การนำ AI เข้าสู่การออกแบบอัลกอริทึมเข้ารหัสกำลังมีความคึกคัก และวิธีเพิ่มประสิทธิภาพเชิงบวกเหล่านี้น่าจะมีบทบาทมากขึ้นในอนาคต

• อย่างไรก็ตาม แม้ Avalanche จะดีเพียงใด ก็ยังพูดไม่ถูกเลยว่า Hash Function นี้ปลอดภัยในเชิงเข้ารหัสด้วยคุณสมบัติเหล่านั้น เนื่องจากข้อจำกัดของ Hash Function ถือว่าเป็นขอบเขตที่ยอมรับได้ของโปรเจ็กต์นี้ แต่เครื่องมือดังกล่าวก็ช่วยวิเคราะห์และปรับปรุงข้อบกพร่องของฟังก์ชันแฮชเดิมได้

[GN⁺]

ความคิดเห็นบน Hacker News

• เหตุผลที่ชอบโค้ดของนักพัฒนารายนี้
  • ชอบไลบรารีอย่าง JSON ไลบรารีตัวแยกอาร์กิวเมนต์, ตัวถอดรหัส UTF-8 แบบไร้การแบ่งทาง, lock-free stack, และไลบรารี trie
  • ชอบที่ไลบรารีข้างต้นทั้งหมดถูกเผยแพร่ใต้ลิขสิทธิ์ Unlicense
• ความคิดเห็นของนักพัฒนาของ MurmurHash
  • แสดงความสนใจว่าปฏิบัติการ multiply-shift-xor ที่อยู่มานานนี้ยังคงมั่นคงได้ดี
• แชร์ความคิดเกี่ยวกับการค้นหาฟังก์ชันแฮชแบบอัตโนมัติ
  • คิดว่าน่าจะดีถ้าผนวกกับ SMHasher3 เพื่อประเมินผลลัพธ์โดยอัตโนมัติ
    • ใช้เทสต์บางส่วนเพื่อความเร็วและเพื่อให้ล้มเหลวได้อย่างรวดเร็ว
  • คิดว่าการขยายเป็นแฮช 64 บิตและ 128 บิตก็เป็นตัวเลือกที่ดีเช่นกัน (แม้จะเพิ่มพื้นที่ค้นหา)
  • สร้างโค้ด NodeJS ในไลบรารี Rain เพื่อวัด "ผลกระทบหิมะถล่ม" ของการคูณด้วยจำนวนเฉพาะ 64 บิต
• แชร์ประสบการณ์การนำโจทย์ 1brc มาทำด้วย Go
  • พยายามหาฟังก์ชัน perfect hash แบบกำหนดเองเพื่อใส่แต่ละสถานีลง bucket ของตัวเองโดยไม่เกิด collision แต่ยกเลิกเพราะมีกฎว่าห้ามปรับแต่งฟังก์ชันแฮชตามข้อมูลก่อนเริ่มโปรแกรม
  • ทำเครื่องมือทดสอบที่สุ่มเช็กค่า constant และพิมพ์ค่าดีที่สุดที่พบตามจำนวน bucket ที่ชนและจำนวน collisions
    • ด้วยอัตราเติมข้อมูลราว 40% สามารถลดเหลือ 1 bucket ที่มีค่าชนเพียง 2 ค่าเท่านั้น
    • สิ่งที่น่าสนใจคือค่าที่ใกล้เคียงกันในจำนวนตำแหน่งการเลื่อนปรากฏใน constant ที่ให้ประสิทธิภาพดีที่สุด โดยไม่ขึ้นกับ constant อื่น
• ขอคำอธิบายว่าเหตุใดโค้ดนี้ถึงดู 'เจ๋ง' และใช้ประโยชน์กับอะไร
• ตั้งข้อสงสัยว่าโค้ดนี้ทำหน้าที่อะไรแน่ๆ คือมันกำลังหาฟังก์ชันแฮชที่ดีที่สุดหรือไม่ และถ้าไม่ใช่ ทำไมฟังก์ชันแฮชที่ดีที่สุดจึงเปลี่ยนไปทุกครั้งที่รัน
• ขอข้อมูลเชิงกลไกเกี่ยวกับการค้นหาฟังก์ชันแฮชที่ดีสำหรับค่าจำนวนเต็มในช่วงที่กำหนด
  • ตัวอย่างเช่น รู้ว่าค่าจำนวนเต็มอยู่ระหว่าง 10,000 ถึง 200,000 และต้องการ hash ไปยังจำนวน bucket ที่เหมาะสมที่สุด
• มีความเห็นว่าถ้าจำกัดให้เป็นตัวดำเนินการแบบย้อนกลับได้ จะมีข้อได้เป้าด้านคณิตศาสตร์แต่ตัดตัวเลือกออกไปมาก
  • เคยคิดถึง perfect hashing โดยสมมติว่ารู้ชุดข้อมูลนำหน้า
  • โดยปกติจะใช้ constant array แต่ถ้าข้อมูล input เป็นจำนวนเต็มที่ค่อนข้างเล็กอยู่แล้ว อยากรู้ว่าย่อได้ละเอียดกว่าเดิมหรือไม่
  • จัดทำรายการ primitive operations ราว 100 ตัวแล้ว แต่รู้สึกเบื่อจึงหยุดโครงการตรงนั้น
• ระบุว่าใช้ constant เดียวกันกับการคูณทั้งสองตัวอาจลดขนาดโค้ดและเพิ่มความเร็วการคำนวณได้เล็กน้อย
• แม้ยอมรับว่าฟังก์ชันเหล่านี้ไม่เหมาะกับงานเข้ารหัส แต่ก็ถามถึงผลที่การ "bias" ที่วัดได้อาจมีต่อการวิเคราะห์คริปต์ (crypto) อย่างไร
  • แสดงความอยากทราบว่ามีใครเชี่ยวชาญด้านการเข้ารหัสแบบแตกต่าง (differential cryptanalysis) มาช่วยอธิบายได้หรือไม่
  • สงสัยว่า hash function ที่มี bias ต่ำอาจทำให้ไม่ต้องใช้รอบหรือการคำนวณมากนักเพื่อช็อตเชียร์ (break) การวิเคราะห์รหัสเข้ารหัสได้หรือไม่
  • สงสัยว่าเครื่องมือนี้จะช่วยหา hash function ทาง cryptography ที่ดีกว่าได้หรือไม่
• แนะนำโปรเจกต์ที่คล้ายกัน
  • ฟังก์ชันมีคุณภาพดีขึ้นแม้ความเร็วช้ากว่า (เพราะใช้ interpreter)
  • แต่หาไม่พบว่าดีกว่า hash function เดิมๆ ใดๆ