Teknologi Pencarian Fungsi Hash Integer Secara Otomatis

Hash Function Prospector

Alat ini adalah utilitas kecil untuk pencarian otomatis fungsi hash integer. Alat ini menghasilkan puluhan miliar fungsi hash integer dengan memilih secara acak dari 9 operasi yang dapat dibalik. Fungsi yang dihasilkan dikompilasi JIT, dan perilaku Avalanche dievaluasi. Saat ini, fungsi terbaik dicetak dengan sintaks C.

• Skor Avalanche: jumlah bit keluaran rata-rata yang tetap tidak berubah saat satu bit input dibalik. Semakin rendah skor, semakin baik. Secara ideal skor adalah 0. Artinya, saat satu bit input dibalik, semua bit keluaran akan dibalik dengan probabilitas 50%.
• Prospector dapat menghasilkan fungsi hash integer 32-bit dan 64-bit. Lihat opsi penggunaan (-h) untuk opsi lengkapnya. Karena menggunakan JIT compiler, hanya x86-64 yang didukung, tetapi fungsi yang ditemukan dapat digunakan di mana saja.

Fungsi Hash yang Ditemukan

Terdapat dua kelas fungsi hash yang berguna yang ditemukan oleh Prospector dan utilitas bantu lainnya di sini. Keduanya menggunakan struktur xorshift-multiply-xorshift tetapi dengan jumlah putaran yang berbeda.

Fungsi 2 Putaran

TheIronBorn menggunakan optimisasi kombinatorik untuk menemukan parameter terbaik yang diketahui untuk struktur ini.

• Permutasi 2 putaran 32-bit ini memiliki bias yang sangat rendah, bahkan mengalahkan finalizer MurmurHash3 32-bit dengan selisih yang sangat kecil.
• Struktur fungsi hash ditemukan oleh Prospector, dan parameternya disetel menggunakan hill climbing serta algoritme genetika.

Masih ada lebih banyak konstanta 2 putaran dengan bias rendah, dan beberapa di antaranya lebih baik daripada lowbias32.

Fungsi 3 Putaran

Dengan menambahkan satu putaran multiply-xorshift lagi pada struktur ini, Anda dapat mencapai batas bias teoretis dengan parameter yang dipilih secara hati-hati. Sebagai contoh, fungsi hash ini tidak dapat dibedakan dari PRF yang sempurna.

• triple32 tidak hanya menangani masalah hash(0) = 0, tetapi juga menurunkan bias lebih lanjut.
• Terdapat lebih banyak konstanta 3 putaran dengan bias rendah.

Pengukuran Bias yang Akurat

Mode -E mengevaluasi bias dari suatu fungsi hash yang diberikan (-p atau -l). Secara default, Prospector menggunakan perkiraan untuk mengevaluasi bias fungsi agar lebih cepat, tetapi sifatnya tidak deterministik dan hasilnya penuh dengan noise. Gunakan opsi -e untuk mengukur bias secara akurat secara eksaustif.

• Anda dapat menentukan fungsi yang akan diperiksa dengan menggunakan pola -p atau pustaka bersama yang berisi fungsi hash() bersama opsi -l.
• Tidak ada pengujian tepat dan eksaustif untuk fungsi hash 64-bit karena terlalu lama.

Pemilihan Operasi Inversi

Operasi inversi yang digunakan adalah:

• x = ~x;
• x ^= constant;
• x *= constant | 1; (hanya konstanta ganjil)
• x += constant;
• x ^= x >> constant;
• x ^= x << constant;
• x += x << constant;
• x -= x << constant;
• x <<<= constant; (rotasi kiri)
• x = bswap(x) (menukar byte tinggi dan rendah)

Secara teknis, x = ~x sudah tercakup oleh x ^= constant. Namun, ~x unik dan sangat berguna.

Hash 16-bit

Karena batasan untuk hash 16-bit berbeda, disediakan alat terpisah bernama hp16 untuk menghasilkan hash jenis ini.

• Berbeda dengan Prospector 32-bit/64-bit, implementasi ini sepenuhnya portabel dan berjalan di hampir semua sistem.
• Dapat membuat dan mengevaluasi S-box 128KiB.
• Karena hash 16-bit kemungkinan lebih dibutuhkan di mesin tanpa instruksi perkalian cepat, beberapa operasi dapat dilewati saat pencarian (-m, -r).

Beberapa hasil yang menarik:

• Hash xorshift-multiply 2 putaran
• Hash xorshift-multiply 3 putaran
• Hash tanpa perkalian (hanya menggunakan xorshift-add)

Hash xorshift 3 putaran yang baik (pencarian singkat melalui hp16 -Xn3) mendekati S-box yang baik (hp16 -S).

Saat melakukan operasi 16-bit, perhatikan aturan promosi integer C. C program yang dicetak oleh alat ini berhati-hati untuk menaikkan operasi 16-bit menjadi unsigned int bila diperlukan.

Komentar GN⁺

• Keamanan fungsi hash memiliki peran sangat penting di kriptografi dan keamanan komputer, sehingga alat pencarian seperti ini tampaknya dapat sangat membantu penelitian. Menarik juga bahwa ia menemukan fungsi hash dengan bias rendah melalui pencarian acak.

• Namun, keamanan sebuah fungsi hash tidak dapat dijamin hanya dari sifat statistik saja. Karena fungsi hash kriptografis harus aman terhadap beragam serangan seperti PreImage Resistance, Second PreImage Resistance, dan Collision Resistance, analisis terhadap hal tersebut juga dibutuhkan.

• Fungsi hash 16-bit tampaknya berguna di lingkungan terbatas seperti IoT atau sistem tertanam. Menarik bahwa ia dapat membuat hash dengan hanya menggunakan ADD/XOR/SHIFT sehingga dapat dipakai di CPU yang tidak memiliki instruksi perkalian.

• Penerapan teknik pencarian heuristik seperti Hill Climbing atau algoritme genetika dalam desain fungsi hash juga merupakan ide yang segar. Upaya menggabungkan teknologi AI dalam perancangan algoritme kriptografi semakin marak, dan teknik optimasi seperti ini tampaknya akan memegang peran yang lebih penting ke depan.

• Namun karena keterbatasan fungsi hash, sulit menyebutnya aman secara kriptografi meskipun karakteristik Avalanche-nya baik, dan ini tampak sebagai keterbatasan proyek ini. Meski begitu, alat semacam ini tetap bisa membantu menganalisis dan menyempurnakan kelemahan fungsi hash yang sudah ada.

[GN⁺]

Komentar Hacker News

• Alasan menyukai kode pengembang ini
  • Pustaka JSON, pustaka parser opsi, decoder UTF-8 tanpa branch, lock-free stack, dan pustaka trie terasa menyenangkan
  • Saya suka bahwa pustaka-pustaka di atas semuanya dipublikasikan di bawah lisensi Unlicense
• Komentar pengembang MurmurHash
  • Menyatakan ketertarikannya bahwa operasi multiply-shift-xor telah bertahan lama
• Berbagi pemikiran tentang pencarian fungsi hash otomatis
  • Baik untuk menggabungkan dengan SMHasher3 agar hasilnya otomatis dievaluasi
    • Untuk kecepatan bisa memakai beberapa benchmark saja dan gagal lebih cepat
  • Akan baik juga untuk memperluasnya ke hash 64-bit dan 128-bit (walau ruang pencariannya lebih besar)
  • Membuat kode NodeJS untuk mengukur efek avalanche dari perkalian bilangan prima 64-bit pada Rain library
• Berbagi pengalaman mengimplementasikan masalah 1brc di Go
  • Mencoba menemukan fungsi hash perfect khusus agar setiap item masuk ke bucket-nya sendiri tanpa collision, tapi mundur karena aturan yang mencegah menyesuaikan fungsi hash dengan data sebelum program mulai
  • Membuat alat uji yang memeriksa konstanta acak dan menampilkan konstanta terbaik yang ditemukan sejauh ini berdasarkan jumlah bucket yang bertabrakan dan jumlah collision
    • Bisa menyusut menjadi 1 bucket dengan hanya 2 nilai collision pada tingkat isi sekitar 40%
    • Menarik bahwa nilai yang mirip untuk jumlah posisi perpindahan termasuk dalam konstanta performa tertinggi, terlepas dari konstanta lain
• Meminta penjelasan kenapa kode ini menarik dan untuk apa digunakan
• Mempertanyakan apa tepatnya yang dilakukan kode ini, apakah ini untuk mencari fungsi hash terbaik, dan jika tidak, mengapa setiap kali dijalankan menghasilkan fungsi hash terbaik yang berbeda
• Meminta info mekanisme untuk menemukan fungsi hash bagus untuk nilai integer dalam rentang tertentu
  • Misalnya, jika Anda mengetahui nilai integer antara 10.000 dan 200.000 dan ingin meng-hash-nya ke jumlah bucket hash yang optimal
• Menyatakan bahwa membatasi operasi yang dapat dibalik secara matematis memang bagus, tetapi mengeliminasi banyak hal
  • Saya pernah memikirkan perfect hashing untuk himpunan input yang sudah diketahui sebelumnya
  • Biasanya gunakan array konstanta, tetapi penasaran apakah bisa dipadatkan lagi saat input sudah merupakan integer kecil
  • Saya sempat menulis daftar sekitar 100 operasi dasar, tapi proyeknya dihentikan karena mulai bosan
• Pendapat bahwa memakai konstanta yang sama untuk dua perkalian bisa mengurangi ukuran kode sehingga kecepatan perhitungan sedikit meningkat
• Meskipun mengakui bahwa fungsi-fungsi ini tidak cocok untuk operasi kriptografi, mereka bertanya apa pengaruh "bias" terukur terhadap kriptanalisis
  • Bertanya apakah seseorang yang akrab dengan kriptografi diferensial bisa menjelaskan
  • Bertanya apakah hash dengan bias rendah mungkin membuat analisis kriptografi tidak efektif dengan lebih sedikit round atau komputasi
  • Bertanya apakah alat ini bisa membantu menemukan fungsi hash kriptografis yang lebih baik
• Memperkenalkan proyek serupa
  • Kualitas fungsi lebih baik walau lebih lambat (menggunakan interpreter)
  • Namun, belum menemukan yang lebih baik dibanding fungsi hash yang ada