Hampir seperti fungsi hash portabel 64-bit tercepat dengan kualitas yang layak.
Ini adalah terjemahan dari artikel asli oleh Leonid Yuriev .
Alih-alih PenafianSaya akan menghilangkan definisi fungsi hash bersama dengan daftar terperinci dari properti dan persyaratan untuk aplikasi kriptografi mereka, dan menganggap bahwa pembaca memiliki pengetahuan minimum yang diperlukan atau akan membacanya . Perlu juga dicatat, bahwa selanjutnya saya akan berbicara tentang fungsi hash non-kriptografi (tidak cocok untuk kriptografi), kecuali dinyatakan sebaliknya.
DangkalHashing digunakan dalam banyak algoritma, dan hampir selalu diperlukan pemrosesan data yang paling efisien (cepat), bersama dengan level minimum kualitas hashing tertentu. Di sini istilah "kualitas" berarti, pertama-tama, semacam "keacakan" (stochasticity) dalam kaitannya dengan data awal. Agak jarang persyaratan tambahan diberlakukan seperti resistensi untuk generasi tabrakan yang disengaja atau ireversibilitas.
Menjadi sedikit lebih membosankanUntuk kejelasan, perlu untuk mendefinisikan konsep "kualitas" dari fungsi hash dan persyaratan lainnya dengan sedikit lebih detail:
Kualitas dasar dan efek longsoran : mengubah satu atau lebih bit yang sewenang-wenang dalam set data sumber yang berubah-ubah menyebabkan setiap bit dari hasil berubah dengan probabilitas ½.
- Irreversibilitas atau resistensi preimage pertama: ketidakmungkinan mendapatkan data asli atau bit individu dari hasil hash.
- Resistensi terhadap tumbukan orde pertama dan / atau resistensi pra-gambar kedua: kesulitan menemukan / menyesuaikan set data asli untuk mendapatkan hasil atau bagian tertentu, termasuk ketika set data awal diketahui.
- Resistensi terhadap tumbukan orde kedua: kesulitan menemukan / menyesuaikan dua set data yang berbeda yang akan memberikan hasil yang sama atau kecocokan dari bagian yang signifikan.
Menghilangkan kutipan panjang dari matematika yang mendasarinya, dapat diringkas:
- Memuaskan semua persyaratan di atas sambil memastikan kinerja tinggi adalah masalah yang cukup sulit, pemecahan yang akan memberi kita fungsi hash kriptografi yang baik. Tetapi kami belum akan melakukan ini.
- Memberikan kualitas dasar memerlukan sejumlah besar operasi ALU. Sederhananya, kualitas selalu berkompromi dengan kecepatan.
- Mendapatkan hasil berkualitas tinggi dengan lebar bit lebih besar dari lebar bit operasi ALU membutuhkan lebih dari beberapa kali lipat dalam jumlah pencampuran, dan karenanya operasi ALU dasar.
- Secara umum, membuat fungsi hash cepat melibatkan mencapai kompromi tertimbang antara kecepatan, kualitas dan bitness hasil .
Oleh karena itu, saya dapat mengatakan bahwa t1ha muncul sebagai hasil dari pencarian kompromi antara kualitas dan kecepatan, pada saat yang sama memperhitungkan kemampuan prosesor modern dan metode yang sudah ditemukan (kombinasi aritmatika-logis) dari pencampuran dan penyebaran dependensi ( efek longsoran salju).
Versi dasar t1ha adalah salah satu fungsi hash portabel tercepat untuk membangun tabel hash dan aplikasi terkait lainnya. Versi dasar t1ha difokuskan pada arsitektur little-endian 64-bit, mengambil nilai garam (biji) 64-bit dan menghasilkan hasil 64-bit, yang mencakup penguatan oleh panjang kunci dan benih. Perlu dicatat bahwa t1ha sengaja dirancang untuk mengembalikan 0 untuk data input nol (kunci ukuran nol dan nol seed).
Menjawab pertanyaan paling populerOperasi 64-bit : Mungkin perlu dicatat bahwa operasi 64-bit yang memberikan kecepatan dan kualitas tanpa mengganggu portabilitas. Bahkan, semakin lebar kapasitas digit operasi aritmatika, semakin banyak efek longsor yang mereka hasilkan dan semakin baik mereka mencampur data. Selain itu, pemrosesan data, semua hal lain dianggap sama, tentu saja lebih cepat dengan 8 byte daripada 4. Di sisi lain, operasi 64-bit sebenarnya tersedia secara native pada banyak prosesor modern, dan dapat lebih kurang memadai diterjemahkan ke dalam 32- yang sedikit. Semua opsi lain, termasuk operasi SIMD , memaksa kami untuk sangat mengorbankan portabilitas dan / atau kecepatan pada platform non-asli.
Hasil 64-bit : Untuk membangun tabel hash, dalam banyak kasus, hasil lebar bit yang lebih kecil sudah cukup. Bahkan 32 bit mungkin lebih dari cukup. Namun, ketika menggunakan operasi 64-bit, hasil 64-bit datang secara alami. Pada saat yang sama, hasil hash 64-bit yang cukup berkualitas tinggi memungkinkan Anda untuk dengan cepat melakukan perbandingan untuk non-kesetaraan, dan dengan akurasi yang baik untuk membandingkan untuk kesetaraan.
"Keajaiban" penggantian perbandingan di atas bisa tampak tidak jelas dan tidak perlu, atau dapat meningkatkan kecepatan hashing dengan urutan besarnya hanya dengan cara lokalitas data, yaitu lebih sedikit polusi cache CPU. Sederhananya, orang dapat membangun struktur tabel hash sedemikian rupa sehingga nilai hash yang dihitung berdampingan (dikemas dalam garis cache). CPU kemudian hanya akan mengambil data nyata jika nilai hash cocok. Dan dalam hal ini, 64-bit dari t1ha memungkinkan untuk mendapatkan hasil terbaik . Yang sedang berkata, 128 bit tidak akan memberikan keuntungan lagi, sementara mengambil kurang dari 64 bit selalu mungkin.
Perbandingan dengan HighwayHash : Saya memiliki perasaan campur aduk tentang proyek tidak resmi ini oleh karyawan Google .
- Di satu sisi, ia memiliki kode yang baik dan implementasi teknis yang sangat baik. Di sisi lain, HighwayHash diposisikan sebagai kuat secara kriptografi (setidaknya sama dengan SipHash ). Di dalam HighwayHash ada beberapa manipulasi yang memungkinkan kita berharap bahwa hasilnya tidak akan buruk. Namun, tidak ada bukti yang memungkinkan kami untuk mengatakannya dengan andal. Bukti "kekuatan" yang diberikan turun ke hasil tes statistik, tetapi tanpa kemampuan untuk mereproduksi mereka (pada satu titik saya bahkan membiarkan diri saya komentar yang agak berlebihan).
- HighwayHash sangat cepat hanya pada x86_64 dengan AVX2 atau SSE41. Tidakkah lebih mudah menggunakan akselerasi AES-NI atau SHA saja?
Jika semuanya berjalan dengan baik, opsi tambahan akan ditambahkan ke t1ha suite (terutama untuk bitness hasil) dan dioptimalkan untuk E2K. Dengan ini saya ingin menutup topik perbandingan dengan HighwayHash.
Kualitas
Mengevaluasi kualitas fungsi hash dalam semua aspek bisa sangat sulit. Ini dapat dilakukan baik secara analitik atau dengan menerapkan berbagai tes statistik. Sayangnya, pendekatan analitis tidak terlalu efektif untuk mengevaluasi fungsi hash dengan kompromi antara kualitas dan kecepatan. Selain itu, evaluasi analitik komparatif dari fungsi-fungsi tersebut cenderung subyektif.
Sebaliknya, uji statistik dapat memberikan perkiraan kuantitatif yang jelas. Untuk tujuan seperti itu ada paket pengujian yang terbukti, seperti SMHasher . Untuk t1ha , hasilnya sederhana - semua opsi t1ha lulus semua tes tanpa komentar. Di sisi lain, orang tidak boleh berasumsi bahwa t1ha memiliki properti lebih dari yang diperlukan untuk aplikasi target (membangun tabel hash).
Jumlah tabrakan di semua tingkatan (varian) t1ha sesuai dengan paradoks ulang tahun . Untuk merumuskannya secara ketat - probabilitas tabrakan dalam t1ha sesuai dengan probabilitas kebetulan dari nilai diskrit acak dengan bitness yang sesuai.
Probabilitas tabrakan yang serupa diamati pada semua fungsi hash berkualitas tinggi. Namun, ini hanya probabilitas, sehingga jumlah sebenarnya dari tabrakan dapat bervariasi untuk setiap set data tertentu.
Setelah artikel ini pertama kali diterbitkan, Yves Orton menemukan , bahwa t1ha1() pertama tidak selalu memenuhi kriteria longsoran yang ketat . Kelemahan ini tidak signifikan untuk aplikasi bertarget t1ha1() dan tidak terlihat dari sudut pandang praktis. Namun, kerugian ini dihilangkan pada level / varian t1ha2() berikutnya, yang pada awalnya direncanakan untuk memberikan kualitas yang sedikit lebih tinggi. Pada prosesor baru, yang menggunakan versi kompiler saat ini, t1ha2() rata-rata satu siklus lebih cepat dari t1ha1() , dan dalam kasus-kasus lainnya dapat menjadi satu siklus lebih lambat. Perlu dicatat bahwa t1ha2() juga menawarkan mode hashing stream dan hasil 128-bit.
Pembaca tentu akan menghargai analisis mendalam dan mendalam tentang kualitas dan / atau kekuatan t1ha . Namun, berdasarkan area aplikasi target t1ha , ini tampaknya berlebihan. Sederhananya, kecepatan lebih penting bagi kami, bahkan untuk tombol pendek. Oleh karena itu, pencampuran multi-putaran tidak dipertimbangkan. Versi t1ha saat ini menghemat siklus dan memberikan hasil 64-bit - praktis tidak ada gunanya untuk mengukur kompromi yang ditemukan dengan cara apa pun selain secara statistik, dan hasilnya cukup bagus.
SebenarnyaSaya hanya mengikuti rekan-rekan saya dari Google tentang cara mereka memberikan bukti statistik mereka
Tingkatan yang dicapai
Mengenai klaim sebagai " yang tercepat ". Penting untuk dicatat bahwa tidak mungkin ada fungsi hash yang berguna sekaligus tercepat di semua platform / arsitektur. Prosesor yang berbeda memiliki set instruksi berbeda yang tersedia dan menjalankan instruksi serupa dengan efisiensi yang berbeda. Jelas, fungsi " tercepat secara universal " kemungkinan besar tidak dapat dibuat. Namun, tampaknya dapat diterima untuk menggunakan istilah "itu
tercepat »untuk fungsi yang portabel dan sekaligus tercepat, setidaknya pada platform paling umum (x86_64), sementara memiliki sedikit peluang untuk kehilangan prosesor modern dengan kompiler optimalisasi yang layak.
Kode sumber proyek mencakup tes yang memeriksa kebenaran hasil dan mengukur kecepatan setiap varian yang diimplementasikan. Pada saat yang sama, pada x86, tergantung pada kemampuan prosesor (dan kompiler), varian fungsi tambahan dapat diperiksa, dan pengukuran dilakukan dalam siklus prosesor.
Selain itu, situs web proyek berisi tabel dengan hasil pengukuran kinerja melalui versi modifikasi SMHasher dari Reini Urban . Satu dapat memeriksa ulang semua angka dan / atau mendapatkan hasil pada prosesor tertentu menggunakan kompiler tertentu.
Di sini Anda dapat membandingkan t1ha dengan beberapa pesaing terdekatnya.
Hashing kunci pendek (rata-rata untuk 1,.31 byte).
Lihatlah kolom kanan "Cycles / Hash" (lebih kecil lebih baik) :
| Fungsi | MiB / Detik | Siklus / Hash |
|---|
| t1ha | 12228.80 | 35.55 |
| Fasthash64 | 5578.06 | 43.42 |
| CityHash64 | 11041.72 | 51.77 |
| xxHash64 | 11123.15 | 56.17 |
| Metrohash | 11808.92 | 46.33 |
Hashing kunci panjang (256 Kb).
Lihatlah kolom tengah "MiB / Second" (lebih besar lebih baik) :
| Fungsi | MiB / Detik | Siklus / Hash |
|---|
| t1ha | 12228.80 | 35.55 |
| Farmhash64 | 12145.36 | 60.12 |
| CityHash64 | 11041.72 | 51.77 |
| xxHash64 | 11123.15 | 56.17 |
| Spooky64 | 11820.20 | 60.39 |
Varian t1ha
Pengembangan t1ha Tujuan pertama adalah untuk mendapatkan fungsi portabel cepat yang berkualitas tinggi untuk membuat tabel hash.
Kemudian kami ingin memiliki versi tercepat dari fungsi hash yang akan memberikan hasil kualitas yang sebanding tetapi disesuaikan dengan platform target sebanyak mungkin. Misalnya, versi t1ha dasar berfungsi dengan urutan byte little-endian, yang karenanya diperlukan konversi untuk arsitektur big-endian dengan kehilangan kinerja yang tak terhindarkan. Jadi mengapa tidak menyingkirkan operasi yang tidak perlu pada platform target spesifik? Dengan cara ini, beberapa opsi ditambahkan:
- Versi sederhana untuk platform 32-bit, baik kecil maupun big-endian.
- Varian menggunakan instruksi AES-NI, tetapi tanpa AVX.
- Dua varian menggunakan petunjuk AES-NI dan AVX.
Kemudian menjadi jelas bahwa lebih banyak opsi yang dirancang untuk berbagai aplikasi akan dibutuhkan, termasuk hasil lebar bit yang berbeda, persyaratan kualitas dan daya tahan. Keragaman seperti itu membutuhkan sistematisasi yang tepat. Ini dicapai dengan mengubah skema penamaan, di mana sufiks numerik menunjukkan "level" dari fungsi:
t1ha0() - adalah opsi tercepat untuk prosesor saat ini.t1ha1() - adalah versi portabel dasar 64-bit dari t1ha.t1ha2() - adalah versi portabel 64-bit dengan sedikit lebih memperhatikan kualitas.t1ha3() - adalah versi 128-bit portabel yang cepat untuk sidik jari.- dll.
Dalam skema ini, diasumsikan bahwa t1ha0() adalah dispatcher yang mengimplementasikan pengalihan tergantung pada platform dan kemampuan prosesor saat ini. Selain itu, penggunaan sufiks "_le" dan "_be" untuk pilihan eksplisit antara varian little-endian dan big-endian dapat diperkenalkan. Jadi, di bawah papan "t1ha" sekarang ada beberapa fungsi hash, dan keluarga ini akan menumbuhkan saya di masa depan, termasuk versi yang dioptimalkan untuk "Elbrus" E2K Rusia.
Gagasan umum dari sekumpulan fungsi saat ini dan propertinya dapat dipahami dengan melihat output tes bawaan ( make check ). Perlu dicatat bahwa semua fungsi lulus semua tes SM Hasher, dan kinerja varian AES-NI sangat bervariasi tergantung pada model prosesor:
Intel(R) Core(TM) i7-6700K CPU @ 3.00GHz Build by GNU C/C++ compiler 8.2 [...] - use RDPMC_40000001 as clock source - measure granularity and overhead: 53 cycles, 0.0188679 iteration/cycle Bench for tiny keys (7 bytes): t1ha0 : 13.14 cycle/hash, 1.877 cycle/byte, 1.598 Gb/s @3GHz t1ha1_64le : 15.14 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha2_atonce : 15.50 cycle/hash, 2.163 cycle/byte, 1.387 Gb/s @3GHz t1ha1_64be : 16.78 cycle/hash, 2.397 cycle/byte, 1.251 Gb/s @3GHz xxhash32 : 17.17 cycle/hash, 2.453 cycle/byte, 1.223 Gb/s @3GHz StadtX : 17.59 cycle/hash, 2.513 cycle/byte, 1.194 Gb/s @3GHz t1ha0_32le : 18.28 cycle/hash, 2.612 cycle/byte, 1.149 Gb/s @3GHz t1ha0_32be : 20.24 cycle/hash, 2.892 cycle/byte, 1.037 Gb/s @3GHz xxhash64 : 22.17 cycle/hash, 3.167 cycle/byte, 0.947 Gb/s @3GHz t1ha2_atonce128* : 29.93 cycle/hash, 4.277 cycle/byte, 0.701 Gb/s @3GHz t1ha2_stream* : 79.81 cycle/hash, 11.402 cycle/byte, 0.263 Gb/s @3GHz HighwayHash64_avx2 : 83.75 cycle/hash, 11.964 cycle/byte, 0.251 Gb/s @3GHz HighwayHash64_sse41 : 85.25 cycle/hash, 12.179 cycle/byte, 0.246 Gb/s @3GHz t1ha2_stream128* : 99.06 cycle/hash, 14.152 cycle/byte, 0.212 Gb/s @3GHz HighwayHash64_portable: 480.75 cycle/hash, 68.679 cycle/byte, 0.044 Gb/s @3GHz HighwayHash64_pure_c : 652.58 cycle/hash, 93.226 cycle/byte, 0.032 Gb/s @3GHz Bench for large keys (16384 bytes): t1ha0 : 1185.00 cycle/hash, 0.072 cycle/byte, 41.478 Gb/s @3GHz t1ha2_atonce : 3436.00 cycle/hash, 0.210 cycle/byte, 14.305 Gb/s @3GHz t1ha2_atonce128* : 3440.00 cycle/hash, 0.210 cycle/byte, 14.288 Gb/s @3GHz t1ha1_64le : 3449.00 cycle/hash, 0.211 cycle/byte, 14.251 Gb/s @3GHz t1ha2_stream* : 3479.00 cycle/hash, 0.212 cycle/byte, 14.128 Gb/s @3GHz t1ha2_stream128* : 3508.00 cycle/hash, 0.214 cycle/byte, 14.011 Gb/s @3GHz StadtX : 3550.00 cycle/hash, 0.217 cycle/byte, 13.846 Gb/s @3GHz xxhash64 : 4121.00 cycle/hash, 0.252 cycle/byte, 11.927 Gb/s @3GHz t1ha1_64be : 4567.00 cycle/hash, 0.279 cycle/byte, 10.762 Gb/s @3GHz HighwayHash64_avx2 : 4580.00 cycle/hash, 0.280 cycle/byte, 10.732 Gb/s @3GHz HighwayHash64_sse41 : 6412.00 cycle/hash, 0.391 cycle/byte, 7.666 Gb/s @3GHz t1ha0_32le : 7191.00 cycle/hash, 0.439 cycle/byte, 6.835 Gb/s @3GHz t1ha0_32be : 7928.00 cycle/hash, 0.484 cycle/byte, 6.200 Gb/s @3GHz xxhash32 : 8197.00 cycle/hash, 0.500 cycle/byte, 5.996 Gb/s @3GHz HighwayHash64_portable: 41895.27 cycle/hash, 2.557 cycle/byte, 1.173 Gb/s @3GHz HighwayHash64_pure_c : 53296.11 cycle/hash, 3.253 cycle/byte, 0.922 Gb/s @3GHz
Sedikit tentang struktur internalUntuk mempelajari sedikit lebih detail, t1ha dibangun sesuai dengan skema Merkle-Damgård (versi "wipe-pipe") dengan penguatan dari ukuran data dan nilai seed. Di dalam loop kompresi utama, keadaan 256-bit digunakan, dengan ukuran yang sama dari blok input. Selain itu, untuk setiap operan data ada dua titik injeksi dengan penyerbukan silang. Setelah menyelesaikan siklus kompresi, keadaan 256-bit dikompresi menjadi 128 bit.
Saat melakukan tindakan di atas, operasi 64-bit, digabung menjadi mixer ARX (Add-Rotate-Xor) dan MUX / MRX (Mul-Rotate-Xor), digunakan. Adalah penting bahwa semua perhitungan ini dibangun sedemikian rupa untuk memastikan kemungkinan eksekusi paralel sebagian besar operasi dan pengemasan ketat u-ops baik ke dalam pipa dan ke dalam unit-unit eksekusi x86_64. Karena ini, kualitas yang cukup baik dicapai dengan tingkat hash yang hampir maksimum untuk kunci panjang.
Perlu dicatat bahwa loop kompresi hanya berjalan untuk blok dengan ukuran yang cukup. Jika ada lebih sedikit data, maka status 128-bit antara hanya akan terdiri dari ukuran kunci dan nilai garam.
Kemudian, sisa data yang tersisa dicampur dalam bagian-bagian dari 64 bit secara bergantian dengan bagian dari keadaan 128-bit. Akhirnya, keadaan dicampur dan secara bersamaan dikompresi menjadi hasil 64-bit. Fitur penting dari t1ha di sini adalah penggunaan mixer berdasarkan penggandaan lebar (produk 128-bit dari dua pengganda 64-bit). Hal ini memungkinkan tercampurnya kualitas yang baik dengan efek longsoran yang baik dan operasi yang lebih sedikit. Meskipun penggandaan lebar adalah operasi yang relatif mahal, lebih sedikit operasi seperti itu yang memungkinkan t1ha memproses kunci pendek dalam jumlah siklus prosesor yang rendah.
Perlu dicatat bahwa mixer berdasarkan perkalian luas dan eksklusif ATAU tidak sempurna. Meskipun t1ha lolos dari semua ujian SMHasher , penulis memahami konsekuensi dari non-injeksi . Namun demikian, kualitas yang dihasilkan tampaknya cukup rasional, dan rencana pengembangan untuk lini t1ha sudah mencerminkan niat untuk memberikan opsi kualitas yang sedikit lebih tinggi.
Anda dapat menemukan informasi lebih lanjut dan kode sumber di sini .
Terima kasih sudah membaca!