[Cryptography] एक्सओआर हैश को गठबंधन करने का डिफ़ॉल्ट तरीका क्यों है?


Answers

हैरिंग के दौरान उपयोग करने के लिए xor एक खतरनाक डिफ़ॉल्ट फ़ंक्शन है। यह और से या बेहतर है, लेकिन यह ज्यादा नहीं कहता है।

xor सममित है, इसलिए तत्वों का क्रम खो गया है। तो "bad" हैश हैश को "dab" रूप में जोड़ देगा।

xor शून्य के समान मानों को मानचित्र करता है, और आपको शून्य पर "सामान्य" मान मैपिंग से बचना चाहिए:

तो (a,a) 0 पर मैप हो जाता है, और (b,b) को 0 तक मैप किया जाता है। चूंकि ऐसे जोड़े यादृच्छिकता से अधिक आम हैं, तो आप शून्य से कई टकरावों को समाप्त कर सकते हैं।

इन दो समस्याओं के साथ, xor एक हैश combiner होने के समाप्त होता है जो सतह पर आधा सभ्य दिखता है, लेकिन आगे निरीक्षण के बाद नहीं।

आधुनिक हार्डवेयर पर, आमतौर पर जितना तेज़ xor के रूप में जोड़ते हैं (यह संभवतः इसे खींचने के लिए अधिक शक्ति का उपयोग करता है, स्वीकार्य रूप से)। जोड़ना सच्चाई तालिका प्रश्न में थोड़ा सा xor के समान है, लेकिन जब दोनों मान 1 हैं तो यह अगले बिट पर थोड़ा सा भेजता है। इससे कम जानकारी मिटा दी जाती है।

तो hash(a) + hash(b) उसमें बेहतर है यदि a==b , परिणाम इसके बजाय hash(a)<<1 बजाय hash(a)<<1

यह सममित रहता है। हम इस समरूपता को मामूली लागत के लिए तोड़ सकते हैं:

hash(a)<<1 + hash(a) + hash(b)

उर्फ hash(a)*3 + hash(b) । ( hash(a) गणना करना hash(a) बार और भंडारण की सलाह दी जाती है यदि आप शिफ्ट समाधान का उपयोग करते हैं)। 3 बजाए कोई अजीब स्थिरता एक size_t (या के-बिट हस्ताक्षरित स्थिरांक) को अपने आप में जोड़ देगा, क्योंकि बिना हस्ताक्षरित स्थिरांक पर मानचित्र कुछ के लिए गणित मॉड्यूलो 2^k , और कोई विषम स्थिरता 2^k अपेक्षाकृत प्रमुख है।

यहां तक ​​कि एक प्रशंसक संस्करण के लिए, हम boost::hash_combine जांच कर सकते हैं, जो प्रभावी रूप से है:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

यहां हम seed कुछ स्थानांतरित संस्करणों को एक स्थिर के साथ जोड़ते हैं (जो मूल रूप से यादृच्छिक 0 एस और 1 एस है - विशेष रूप से यह 32 बिट निश्चित बिंदु अंश के रूप में सुनहरा अनुपात के विपरीत है) कुछ अतिरिक्त और एक xor के साथ। यह समरूपता को तोड़ता है, और कुछ "शोर" पेश करता है यदि आने वाले शेड मूल्य खराब होते हैं (यानी, प्रत्येक घटक की 0 हैश की कल्पना करें - उपरोक्त इसे अच्छी तरह से संभालता है, प्रत्येक गठबंधन के बाद 1 और 0 एस की धुंध उत्पन्न करता है। मेरा बस एक आउटपुट करता है 0 )।

उन लोगों के लिए जो सी / सी ++ से परिचित नहीं हैं, एक size_t एक हस्ताक्षरित पूर्णांक मान है जो स्मृति में किसी ऑब्जेक्ट के आकार का वर्णन करने के लिए काफी बड़ा है। 64 बिट सिस्टम पर, यह आमतौर पर 64 बिट हस्ताक्षरित पूर्णांक होता है। 32 बिट सिस्टम पर, एक 32 बिट हस्ताक्षरित पूर्णांक।

Question

मान लें कि आपके पास दो हैंश H(A) और H(B) और आप उन्हें गठबंधन करना चाहते हैं। मैंने पढ़ा है कि दो हैंश को गठबंधन करने का एक अच्छा तरीका XOR है, उदाहरण के लिए XOR( H(A), H(B) )

मैंने पाया है कि सबसे अच्छा स्पष्टीकरण इन हैश फ़ंक्शन दिशानिर्देशों पर संक्षेप में छुआ है:

मोटे तौर पर यादृच्छिक वितरण परिणामों के साथ दो नंबरों को एक्सओर करना, अभी भी लगभग किसी भी संख्या में यादृच्छिक वितरण * के साथ, लेकिन जो अब दो मानों पर निर्भर करता है।
...
* दो संख्याओं के प्रत्येक बिट को गठबंधन करने के लिए, 0 0 आउटपुट होता है यदि दो बिट बराबर होते हैं, अन्यथा 1. दूसरे शब्दों में, 50% संयोजनों में, 1 आउटपुट होगा। तो यदि दो इनपुट बिट्स में 0 या 1 होने का लगभग 50-50 मौका होता है, तो आउटपुट बिट भी होगा।

क्या आप अंतर्ज्ञान और / या गणित के बारे में बता सकते हैं कि XOR को हैश फ़ंक्शंस (OR या AND आदि के बजाय) के संयोजन के लिए डिफ़ॉल्ट ऑपरेशन क्यों होना चाहिए?




बाएं 2 कॉलम को कवर करें और आउटपुट का उपयोग कर इनपुट का उपयोग करने का प्रयास करें।

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

जब आपने 1-बिट देखा तो आपको यह पता होना चाहिए था कि दोनों इनपुट 1 थे।

अब एक्सओआर के लिए ऐसा ही करें

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

एक्सओआर इनपुट के बारे में कुछ भी नहीं देता है।




यदि आप एक पक्षपातपूर्ण इनपुट के साथ एक यादृच्छिक इनपुट XOR , आउटपुट यादृच्छिक है। AND या OR लिए भी यह सच नहीं है। उदाहरण:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

जैसा कि @ ग्रेग हेगिल का उल्लेख है, भले ही दोनों इनपुट यादृच्छिक हैं, एंड्रॉइड या OR का उपयोग करके पक्षपातपूर्ण आउटपुट होगा।

XOR उपयोग कुछ और जटिल पर करने का कारण यह है कि, अच्छी तरह से, कोई ज़रूरत नहीं है: XOR पूरी तरह से काम करता है, और यह चमकदार रूप से बेवकूफ है।




एक्सर हैश को गठबंधन करने का "डिफ़ॉल्ट" तरीका हो सकता है लेकिन ग्रेग हेगिल का जवाब यह भी दिखाता है कि इसका नुकसान क्यों है: दो समान हैश मानों का xor शून्य है। वास्तविक जीवन में, समान हैश एक अपेक्षा की तुलना में अधिक आम हैं। फिर आप पाएंगे कि इन (इतने कम नहीं) कोने के मामलों में, परिणामस्वरूप संयुक्त हैंश हमेशा एक ही (शून्य) होते हैं। हैश टकराव बहुत अधिक होगा, आप अपेक्षा से अधिक बार।

एक उत्तीर्ण उदाहरण में, आप अपने द्वारा प्रबंधित विभिन्न वेबसाइटों के उपयोगकर्ताओं के हैंश किए गए पासवर्ड जोड़ सकते हैं। दुर्भाग्यवश, बड़ी संख्या में उपयोगकर्ता अपने पासवर्ड का पुन: उपयोग करते हैं, और परिणामस्वरूप हैश का एक आश्चर्यजनक अनुपात शून्य है!