Otomatik Tamsayı Hash Fonksiyonu Arama Tekniği
(github.com/skeeto)Hash Function Prospector
Bu araç, otomatik tamsayı hash fonksiyonu araması için küçük bir araçtır. 9 tersinir işlem arasından rastgele seçim yapılarak milyarlarca tamsayı hash fonksiyonu üretilir. Üretilen fonksiyonlar JIT ile derlenir ve Avalanche davranışı değerlendirilir. Şu anda en iyi fonksiyon C sözdizimiyle çıktı olarak verilir.
- Avalanche puanı: Tek bir giriş bitini ters çevirdiğinizde ortalama olarak aynı kalan çıktı bit sayısıdır. Puan ne kadar düşükse o kadar iyi olur. İdeal durumda puan 0’dır. Yani tek bir giriş bitini ters çevirdiğinizde tüm çıktı bitleri %50 olasılıkla ters çevrilir.
- Prospector, 32-bit ve 64-bit tamsayı hash fonksiyonları üretebilir. Tüm seçenekler için kullanım kılavuzunu (
-h) inceleyin. JIT derleyici nedeniyle yalnızca x86-64 desteklenir, ancak bulunan fonksiyonlar her platformda kullanılabilir.
Bulunan Hash Fonksiyonları
Prospector ve burada bulunan diğer yardımcı araçlar tarafından keşfedilen iki yararlı hash fonksiyonu sınıfı vardır. İkisi de xorshift-multiply-xorshift yapısını kullanır, ancak tur sayıları farklıdır.
2 Tur Fonksiyonu
TheIronBorn, bu yapı için bilinen en iyi parametreleri bulmak adına kombinasyon optimizasyonu kullanmıştır.
- Bu 32-bit 2 tur permütasyonu özellikle düşük yanlılığa sahiptir ve ünlü MurmurHash3 32-bit finalizer’ını küçük bir farkla geçer.
- Hash fonksiyonu yapısı Prospector tarafından keşfedildi ve parametreleri, tırmanma araması (hill climbing) ile genetik algoritma kullanılarak ayarlandı.
Daha fazla düşük yanlılıklı 2 tur sabit bulunur ve bunların bir kısmı lowbias32 değerinden daha iyidir.
3 Tur Fonksiyonu
Bu yapıya bir multiply-xorshift turu daha eklendiğinde, dikkatlice seçilmiş parametrelerle teorik önyargı sınırına ulaşılabilir. Örneğin, bu hash fonksiyonu kusursuz bir PRF ile ayırt edilemeyecek kadar iyi bir davranış sergiler.
triple32, yalnızcahash(0) = 0sorununu çözmekle kalmaz, ayrıca yanlılığı da daha da düşürür.- Daha fazla düşük yanlılıklı 3 tur sabit de bulunmaktadır.
Kesin Yanlılık Ölçümü
-E modu, verilen hash fonksiyonunun (-p veya -l) yanlılığını değerlendirir. Prospector varsayılan olarak bir fonksiyonun yanlılığını hızlıca ölçmek için bir tahmin kullanır; ancak bu yaklaşım deterministik değildir ve sonuçlarda çok fazla gürültü olur. Yanlılığı tam olarak (eksiksiz) ölçmek için -e seçeneği kullanılabilir.
- Test edilecek fonksiyon,
-pile bir desen kullanılarak ya dahash()işlevini içeren paylaşılan kütüphane ve-lile tanımlanabilir. - 64-bit hash fonksiyonu için doğru ve eksiksiz test çok uzun süreceğinden mevcut değildir.
Tersinir İşlem Seçimi
Kullanılan tersinir işlemler:
x = ~x;x ^= constant;x *= constant | 1;(yalnızca tek sabitler)x += constant;x ^= x >> constant;x ^= x << constant;x += x << constant;x -= x << constant;x <<<= constant;(sola döndürme)x = bswap(x)(üst ve alt baytları değiş tokuş etme)
Teknik olarak x = ~x, x ^= constant; tarafından kapsanır. Ancak ~x özel ve özellikle kullanışlıdır.
16-bit Hash
16-bit hash için kısıtlamalar farklı olduğundan bu hashleri üretmek üzere ayrı bir araç olan hp16 bulunmaktadır.
- 32-bit/64-bit Prospector’dan farklı olarak bu uygulama tamamen taşınabilirdir ve neredeyse her sistemde çalışır.
- 128 KiB S-box üretimi ve değerlendirmesi de mümkün.
- 16-bit hash, hızlı çarpma komutu olmayan makinelerde daha faydalı olabilir; bu nedenle arama sırasında bazı işlemler atlanabilir (
-m,-r).
Bazı ilginç sonuçlar:
- 2 tur xorshift-multiply hash
- 3 tur xorshift-multiply hash
- Çarpma içermeyen hash (yalnızca xorshift-add)
İyi bir 3 tur xorshift hash’i (hp16 -Xn3 ile yapılan kısa bir arama), iyi bir S-box’a (hp16 -S) yaklaşır.
16-bit işlemler yapılırken C tamsayı yükseltme kurallarına dikkat etmek gerekir. Bu program tarafından üretilen C kodu, gerektiğinde 16-bit işlemleri unsigned int türüne yükseltmeye dikkat eder.
GN⁺ Yorumu
- Hash fonksiyonlarının güvenliği hem kriptografi hem de bilgisayar güvenliğinde çok önemli bir role sahiptir; bu nedenle bu tür bir keşif aracı araştırmalara büyük katkı sağlayacaktır. Özellikle rastgele aramayla düşük yanlılıklı hash fonksiyonları bulunması ilginç görünüyor.
- Ancak yalnızca istatistiksel özelliklere bakarak bir hash fonksiyonunun güvenli olduğu söylenemez. Kriptografik hash fonksiyonunun PreImage Resistance, Second PreImage Resistance, Collision Resistance gibi farklı saldırılara karşı güvenli olması gerekir; bu nedenle bu alanlarda da analiz yapılması gereklidir.
- 16-bit hash fonksiyonları, IoT veya gömülü sistemler gibi kısıtlı ortamlarda faydalı olabilir. Çarpma komutu olmayan CPU’larda da kullanılabilmesi için yalnızca ADD/XOR/SHIFT kullanan hash fonksiyonları üretilebilmesi etkileyici.
- Hash fonksiyonu tasarımında Hill Climbing ya da genetik algoritma gibi sezgisel keşif yöntemlerinin uygulanması da taze bir fikirdir. Kriptografik algoritma tasarımına yapay zeka entegrasyonu giderek arttıkça bu tür optimizasyon tekniklerinin gelecekte daha önemli bir role sahip olacağı düşünülebilir.
- Ancak Hash Function’ın doğası nedeniyle, Avalanche özellikleri ne kadar iyi olursa olsun kriptografik olarak güvenli olduğu söylenemez; bu projenin bir sınırlılığı olarak görülebilir. Yine de bu araçlar, mevcut hash fonksiyonlarının zayıf yönlerini analiz edip iyileştirmeye yardımcı olabilir.
1 yorum
Hacker News Yorumu
multiply-shift-xorişleminin uzun süre iyi performans vermiş olmasını ilginç buldu