स्वचालित पूर्णांक हैश फ़ंक्शन खोज तकनीक
(github.com/skeeto)Hash Function Prospector
यह टूल पूर्णांक हैश फ़ंक्शन खोज को ऑटोमेट करने के लिए बनाया गया एक छोटा utility है। यह 9 रिवर्सिबल ऑपरेशनों में से यादृच्छिक रूप से चुनकर अरबों integer हैश फ़ंक्शन जेनरेट करता है। जेनरेट किए गए फ़ंक्शन JIT compile होकर चलते हैं और उनका Avalanche व्यवहार evaluate होता है। वर्तमान में सबसे अच्छा फ़ंक्शन C syntax में output होता है।
- Avalanche score: किसी एक input बिट को पलटने पर औसतन output में कितने बिट अपनी स्थिति में स्थिर रहते हैं। score जितना कम होता है, उतना बेहतर। आदर्श स्थिति में score 0 होना चाहिए। यानी, एक input bit बदलने पर सभी output बिट 50% संभावना से पलटते हैं।
- Prospector 32-bit और 64-bit दोनों integer हैश फ़ंक्शन बना सकता है। पूरी सूची के विकल्पों के लिए usage (
-h) देखें। JIT compiler की वजह से केवल x86-64 supported है, लेकिन खोजे गए फ़ंक्शन कहीं भी इस्तेमाल किए जा सकते हैं।
खोजे गए हैश फंक्शन
Prospector और इसमें मौजूद अन्य helper utilities द्वारा दो उपयोगी classes के हैश फंक्शन खोजे गए हैं। दोनों xorshift-multiply-xorshift structure का उपयोग करते हैं, बस rounds अलग हैं।
2-राउंड फंक्शन
TheIronBorn ने इस structure के लिए best-known parameters खोजने हेतु combinatorial optimization का उपयोग किया।
- यह 32-bit 2-राउंड permutation विशेष रूप से कम bias रखता है और प्रसिद्ध MurmurHash3 32-bit finalizer को भी छोटी margin से पीछे छोड़ देता है।
- यह हैश फंक्शन structure Prospector द्वारा खोजा गया था, और इसके parameters hill climbing और genetic algorithm से tune किए गए हैं।
और भी कई अधिक low-bias 2-राउंड constants उपलब्ध हैं, जिनमें से कुछ lowbias32 से बेहतर हैं।
3-राउंड फंक्शन
इस structure में multiply-xorshift का एक अतिरिक्त round जोड़ने पर carefully चुने गए parameters के साथ theoretical bias limit तक पहुँचा जा सकता है। उदाहरण के लिए, यह hash function एक ideal PRF से distinguish नहीं किया जा सकता।
triple32केवलhash(0) = 0issue को fix नहीं करता, बल्कि bias को और भी कम करता है।- और भी कई low-bias 3-राउंड constants मौजूद हैं।
सटीक bias मापन
-E mode किसी दिए हुए हैश फंक्शन (-p या -l) का bias मापता है। डिफ़ॉल्ट रूप से Prospector, फ़ंक्शन का bias तेज़ी से estimate करने के लिए अनुमान का उपयोग करता है, लेकिन यह non-deterministic होता है और परिणामों में काफी noise आ सकता है। सटीक bias को exhaustive तरीके से मापने के लिए -e option उपयोग करें।
-pऔर pattern के साथ याhash()नाम वाले function वाली shared library और-lके साथ, टेस्ट करने के लिए function define किया जा सकता है।- 64-bit हैश फंक्शन के लिए पूर्ण और exhaustive टेस्ट उपलब्ध नहीं है क्योंकि इसमें बहुत अधिक समय लगता है।
रिवर्सिबल ऑपरेशन्स का चयन
निम्नलिखित reversible ops उपयोग होते हैं:
x = ~x;x ^= constant;x *= constant | 1;(केवल odd constant)x += constant;x ^= x >> constant;x ^= x << constant;x += x << constant;x -= x << constant;x <<<= constant;(left rotate)x = bswap(x)(high byte और low byte swap)
तकनीकी रूप से x = ~x को x ^= constant से cover किया जा सकता है। हालांकि ~x अनूठा (distinct) है और खास तौर पर उपयोगी भी।
16-bit हैश
16-bit hashes के लिए अलग constraints होने के कारण इन्हें खोजने के लिए अलग tool hp16 उपलब्ध है।
- 32-bit/64-bit Prospector की तुलना में यह implementation पूरी तरह portable है और लगभग हर सिस्टम पर रन हो सकता है।
- 128KiB S-box बनाने और evaluate करने की सुविधा भी है।
- 16-bit hashes शायद उन machines पर ज़्यादा काम के होंगे जहाँ fast multiplication instruction नहीं है, इसलिए खोज के दौरान कुछ ऑपरेशन छोड़ सकते हैं (
-m,-r)।
कुछ दिलचस्प परिणाम:
- 2-राउंड xorshift-multiply hash
- 3-राउंड xorshift-multiply hash
- बिना multiplication वाला hash (सिर्फ़ xorshift-add का उपयोग)
अच्छा 3-राउंड xorshift hash (hp16 -Xn3 के साथ छोटा search) एक अच्छे S-box (hp16 -S) के करीब आता है।
16-bit ऑपरेशन करते समय C integer promotion rules पर ध्यान देना ज़रूरी है। इस प्रोग्राम में output होने वाला C code आवश्यक होने पर 16-bit ऑपरेशन को unsigned int में promote करने का ध्यान रखता है।
GN⁺ की राय
-
हैश फंक्शन की सुरक्षा cryptography और computer security में बेहद अहम है, इसलिए ऐसा खोज tool शोध के लिए निश्चित रूप से मददगार है। खासकर random खोज के ज़रिये low-bias हैश फंक्शन खोज निकालना बहुत दिलचस्प है।
-
लेकिन केवल statistical properties के आधार पर किसी hash function की सुरक्षा सुनिश्चित नहीं मानी जा सकती। cryptographic hash function को PreImage Resistance, Second PreImage Resistance, Collision Resistance जैसी कई attack vectors के खिलाफ safe होना चाहिए, इसलिए उसका अलग से analysis भी ज़रूरी है।
-
16-bit हैश फंक्शन IoT या embedded systems जैसी constrained environment में काम के हो सकते हैं। यह विशेष रूप से उल्लेखनीय है कि CPU बिना multiplication instruction के भी ADD/XOR/SHIFT का उपयोग करके hash फंक्शन बनाया जा सकता है।
-
Hash function design में hill climbing या genetic algorithm जैसी heuristic खोज तकनीकों का उपयोग करना भी एक ताज़ा idea है। crypto algorithm design में AI technology जोड़ने के प्रयास तेज़ी से बढ़ रहे हैं, और ये optimization तकनीकें आगे और अधिक महत्वपूर्ण भूमिका निभा सकती हैं।
-
हालांकि Hash Function की सीमाओं के कारण Avalanche गुण कितना भी अच्छा हो, इसे cryptographically safe कहना कठिन है; यह इस project की सीमा प्रतीत होती है। फिर भी ऐसे tools के माध्यम से existing hash फंक्शनों की समस्याओं का analysis करके सुधार में मदद मिल सकती है।
1 टिप्पणियां
Hacker News टिप्पणी
multiply-shift-xorऑपरेशन का इतने लंबे समय तक बिना टूटे चलना जारी रहना रोचक बताया