आर्गन2: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Password-based key derivation function created in 2015}} | {{short description|Password-based key derivation function created in 2015}} | ||
'''आर्गन 2''' एक प्रमुख व्युत्पत्ति कार्य है जिसे 2015 [[पासवर्ड हैशिंग प्रतियोगिता]] के विजेता के रूप में चुना गया था।<ref>[https://password-hashing.net/ "Password Hashing Competition"]</ref><ref>{{cite arXiv |author=Jos Wetzels |date=2016-02-08 |title=Open Sesame: The Password Hashing Competition and Argon2 |class=cs.CR |eprint=1602.03097 }}</ref> यह [[लक्समबर्ग विश्वविद्यालय]] से [[ एलेक्स बिरुकोव | एलेक्स बिरुकोव]], डैनियल दीनू और [[दिमित्री खोवराटोविच]] द्वारा डिजाइन किया गया था।<ref>[https://password-hashing.net/argon2-specs.pdf Argon2: the memory-hard function for password hashing and other applications], Alex Biryukov, et al, October 1, 2015</ref> आर्गन2 का संदर्भ कार्यान्वयन [[Creative Commons CC0|क्रिएटिव कॉमन्स CC0]] लाइसेंस (यानी पब्लिक डोमेन) या अपाचे लाइसेंस 2.0 के तहत जारी किया गया है, और तीन संबंधित संस्करण प्रदान करता है: | |||
*आर्गन2d GPU [[पासवर्ड क्रैकिंग]] के प्रतिरोध को अधिकतम करता है। यह एक पासवर्ड निर्भर क्रम में मेमोरी ऐरे को एक्सेस करता है, जो टाइम-मेमोरी ट्रेड-ऑफ (टीएमटीओ) अटैक्स की संभावना को कम करता है, लेकिन संभावित साइड-चैनल अटैक का परिचय देता है। | *आर्गन2d GPU [[पासवर्ड क्रैकिंग]] के प्रतिरोध को अधिकतम करता है। यह एक पासवर्ड निर्भर क्रम में मेमोरी ऐरे को एक्सेस करता है, जो टाइम-मेमोरी ट्रेड-ऑफ (टीएमटीओ) अटैक्स की संभावना को कम करता है, लेकिन संभावित साइड-चैनल अटैक का परिचय देता है। | ||
| Line 14: | Line 14: | ||
अटैक जबकि आर्गन2d के लिए कोई सार्वजनिक क्रिप्ट विश्लेषण लागू नहीं है, आर्गन2i फ़ंक्शन पर दो प्रकाशित अटैक हैं। पहला अटैक केवल आर्गन2i के पुराने संस्करण पर लागू होता है, जबकि दूसरा नवीनतम संस्करण (1.3) तक बढ़ा दिया गया है।<ref name="blocki"></ref> | अटैक जबकि आर्गन2d के लिए कोई सार्वजनिक क्रिप्ट विश्लेषण लागू नहीं है, आर्गन2i फ़ंक्शन पर दो प्रकाशित अटैक हैं। पहला अटैक केवल आर्गन2i के पुराने संस्करण पर लागू होता है, जबकि दूसरा नवीनतम संस्करण (1.3) तक बढ़ा दिया गया है।<ref name="blocki"></ref> | ||
पहले अटैक से पता चलता है कि वांछित स्थान के एक चौथाई और पांचवे हिस्से के बीच बिना किसी समय दंड के एकल-पास आर्गन2i फ़ंक्शन की गणना करना संभव है, और केवल | पहले अटैक से पता चलता है कि वांछित स्थान के एक चौथाई और पांचवे हिस्से के बीच बिना किसी समय दंड के एकल-पास आर्गन2i फ़ंक्शन की गणना करना संभव है, और केवल {{mvar|N}}/{{mvar|e}} (≈ {{mvar|N}}/2.72) का उपयोग करके एक बहु-पास आर्गन2i की गणना करना संभव है, स्थान और बिना किसी समय दंड (पेनाल्टी) के।<ref>{{cite report |author1=Henry |author2=Corrigan-Gibbs |author3=Dan Boneh |author4=Stuart Schechter |date=2016-01-14 |title=Balloon Hashing: Provably Space-Hard Hash Functions with Data-Independent Access Patterns |url=https://eprint.iacr.org/2016/027.pdf }}</ref> आर्गन2 लेखकों के अनुसार, यह अटैक वेक्टर संस्करण 1.3 में तय किया गया था।<ref name=":0">{{Cite web|url=https://www.ietf.org/mail-archive/web/cfrg/current/msg07948.html|title=[Cfrg] Argon2 v.1.3|website=www.ietf.org|access-date=2016-10-30}}</ref> | ||
दूसरे अटैक से पता चलता है कि आर्गन2i की गणना एक एल्गोरिथ्म द्वारा की जा सकती है जिसमें जटिलता O({{mvar|n}}<sup>7/4</sup> लॉग ({{mvar|n}})) मापदंडों के सभी विकल्पों के लिए {{mvar|σ}} (अंतरिक्ष लागत), {{mvar|τ}} (समय की लागत), और थ्रेड-काउंट जैसे कि {{mvar|n}}={{mvar|σ}}∗{{mvar|τ}}.<ref>{{cite report |author1=Joël Alwen |author2=Jeremiah Blocki |date=2016-02-19 |title=कुशल रूप से डेटा-स्वतंत्र मेमोरी-हार्ड फ़ंक्शंस की गणना करना|url=https://eprint.iacr.org/2016/115.pdf }}</ref> आर्गन2 लेखकों का दावा है कि यदि आर्गन2i का उपयोग तीन या अधिक पास के साथ किया जाता है तो यह अटैक कुशल नहीं है।<ref name=":0" />हालांकि, जोएल अल्वेन और यिर्मयाह ब्लॉकी ने अटैक में सुधार किया और दिखाया कि अटैक को विफल करने के लिए, आर्गन2i v1.3 को मेमोरी पर 10 से अधिक पास की जरूरत है।<ref name="blocki">{{cite report |author1=Joël Alwen |author2=Jeremiah Blocki |date=2016-08-05 |title=Towards Practical Attacks on Argon2i and Balloon Hashing |url=https://eprint.iacr.org/2016/759.pdf }}</ref> | दूसरे अटैक से पता चलता है कि आर्गन2i की गणना एक एल्गोरिथ्म द्वारा की जा सकती है जिसमें जटिलता O({{mvar|n}}<sup>7/4</sup> लॉग ({{mvar|n}})) मापदंडों के सभी विकल्पों के लिए {{mvar|σ}} (अंतरिक्ष लागत), {{mvar|τ}} (समय की लागत), और थ्रेड-काउंट जैसे कि {{mvar|n}}={{mvar|σ}}∗{{mvar|τ}}.<ref>{{cite report |author1=Joël Alwen |author2=Jeremiah Blocki |date=2016-02-19 |title=कुशल रूप से डेटा-स्वतंत्र मेमोरी-हार्ड फ़ंक्शंस की गणना करना|url=https://eprint.iacr.org/2016/115.pdf }}</ref> आर्गन2 लेखकों का दावा है कि यदि आर्गन2i का उपयोग तीन या अधिक पास के साथ किया जाता है तो यह अटैक कुशल नहीं है।<ref name=":0" />हालांकि, जोएल अल्वेन और यिर्मयाह ब्लॉकी ने अटैक में सुधार किया और दिखाया कि अटैक को विफल करने के लिए, आर्गन2i v1.3 को मेमोरी पर 10 से अधिक पास की जरूरत है।<ref name="blocki">{{cite report |author1=Joël Alwen |author2=Jeremiah Blocki |date=2016-08-05 |title=Towards Practical Attacks on Argon2i and Balloon Hashing |url=https://eprint.iacr.org/2016/759.pdf }}</ref> | ||
== एल्गोरिथम == | == एल्गोरिथम == | ||
<span style="color:blue;">'''Function'''</span> Argon2 | |||
< | <span style="color:blue;">'''Inputs:'''</span> | ||
password ('''P'''): Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Password (or message) to be hashed</span> | |||
salt ('''S'''): Bytes (8..2<sup>32</sup>-1) <span style="color:green;">Salt (16 bytes recommended for password hashing)</span> | |||
parallelism ('''p'''): Number (1..2<sup>24</sup>-1) <span style="color:green;">Degree of parallelism (i.e. number of threads)</span> | |||
tagLength ('''T'''): Number (4..2<sup>32</sup>-1) <span style="color:green;">Desired number of returned bytes</span> | |||
memorySizeKB ('''m'''): Number (8p..2<sup>32</sup>-1) <span style="color:green;">Amount of memory (in [[Kibibyte|kibibytes]]) to use</span> | |||
iterations ('''t'''): Number (1..2<sup>32</sup>-1) <span style="color:green;">Number of iterations to perform</span> | |||
version ('''v'''): Number (0x13)<sup> </sup> <span style="color:green;">The current version is 0x13 (19 decimal)</span> | |||
key ('''K'''): Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Optional key (Errata: PDF says 0..32 bytes, RFC says 0..2<sup>32</sup> bytes)</span> | |||
associatedData ('''X'''): Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Optional arbitrary extra data</span> | |||
hashType ('''y'''): Number (0=Argon2d, 1=Argon2i, 2=Argon2id) | |||
< | <span style="color:blue;">'''Output:'''</span> | ||
tag: Bytes (tagLength)<sup> </sup> <span style="color:green;">The resulting generated bytes, tagLength bytes long</span> | |||
< | <span style="color:green;">''Generate initial 64-byte block H<sub>0</sub>.'' | ||
All the input parameters are concatenated and input as a source of additional entropy. | |||
Errata: RFC says H<sub>0</sub> is 64-bits; PDF says H<sub>0</sub> is 64-bytes. | |||
Errata: RFC says the Hash is H^, the PDF says it's ℋ (but doesn't document what ℋ is). It's actually Blake2b. | |||
Variable length items are prepended with their length as 32-bit little-endian integers.</span> | |||
buffer ← parallelism ∥ tagLength ∥ memorySizeKB ∥ iterations ∥ version ∥ hashType | |||
∥ | ∥ Length(password) ∥ Password | ||
∥ | ∥ Length(salt) ∥ salt | ||
∥ | ∥ Length(key) ∥ key | ||
∥ | ∥ Length(associatedData) ∥ associatedData | ||
H<sub>0</sub> ← Blake2b(buffer, 64) <span style="color:green;">''//default hash size of Blake2b is 64-bytes''</span> | |||
< | <span style="color:green;">Calculate number of 1 KB blocks by rounding down memorySizeKB to the nearest multiple of 4*parallelism [[Kibibyte|kibibytes]]</span> | ||
blockCount ← Floor(memorySizeKB, 4*parallelism) | |||
< | <span style="color:green;">Allocate two-dimensional array of 1 KiB blocks (parallelism rows x columnCount columns)</span> | ||
columnCount ← blockCount / parallelism; <span style="color:green;">//In the RFC, columnCount is referred to as '''q'''</span> | |||
< | <span style="color:green;">Compute the first and second block (i.e. column zero and one ) of each lane (i.e. row)</span> | ||
' | '''for''' i ← 0 '''to''' parallelism-1 '''do''' <span style="color:green;">for each row</span> | ||
B<sub>i</sub>[0] ← Hash(H<sub>0</sub> ∥ 0 ∥ i, 1024) <span style="color:green;">''//Generate a 1024-byte digest''</span> | |||
B<sub>i</sub>[1] ← Hash(H<sub>0</sub> ∥ 1 ∥ i, 1024) <span style="color:green;">''//Generate a 1024-byte digest''</span> | |||
< | <span style="color:green;">Compute remaining columns of each lane</span> | ||
' | '''for''' i ← 0 '''to''' parallelism-1 '''do''' <span style="color:green;">//for each row</span> | ||
'for' j ← 2 'to' columnCount-1 'do' <span style= color:green; >// | '''for''' j ← 2 '''to''' columnCount-1 '''do''' <span style="color:green;">//for each subsequent column</span> | ||
< | <span style="color:green;">//i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)</span> | ||
i′, j′ ← GetBlockIndexes(i, j) <span style= color:green; >//GetBlockIndexes | i′, j′ ← GetBlockIndexes(i, j) <span style="color:green;">//the GetBlockIndexes function is not defined</span> | ||
B<sub>i</sub>[j] = G(B<sub>i</sub>[j-1], B<sub>i′</sub>[j′]) <span style="color:green;">//the G hash function is not defined</span> | |||
< | <span style="color:green;">Further passes when iterations > 1</span> | ||
nIteration | '''for''' nIteration ← 2 '''to''' iterations '''do''' | ||
for i ← 0 to | '''for''' i ← 0 '''to''' parallelism-1 '''do''' <span style="color:green;">for each row</span> | ||
j ← 0 | '''for''' j ← 0 '''to''' columnCount-1 '''do''' <span style="color:green;">//for each subsequent column</span> | ||
< | <span style="color:green;">//i' and j' indexes depend if it's Argon2i, Argon2d, or Argon2id (See section 3.4)</span> | ||
i′, j′ ← GetBlockIndexes(i, j) | i′, j′ ← GetBlockIndexes(i, j) | ||
'''if''' j == 0 '''then''' | |||
B<sub>i</sub>[0] = B<sub>i</sub>[0] xor G(B<sub>i</sub>[columnCount-1], B<sub>i′</sub>[j′]) | |||
'''else''' | |||
B<sub>i</sub>[j] = B<sub>i</sub>[j] xor G(B<sub>i</sub>[j-1], B<sub>i′</sub>[j′]) | |||
< | <span style="color:green;">Compute final block '''C''' as the XOR of the last column of each row</span> | ||
C ← B<sub>0</sub>[columnCount-1] | |||
for i ← 1 to | '''for''' i ← 1 '''to''' parallelism-1 '''do''' | ||
C ← C '''xor''' B<sub>i</sub>[columnCount-1] | |||
< | <span style="color:green;">Compute output tag</span> | ||
'''return''' Hash(C, tagLength) | |||
=== चर-लंबाई हैश फ़ंक्शन === | === चर-लंबाई हैश फ़ंक्शन === | ||
Argon2 एक हैश फ़ंक्शन का उपयोग करता है जो 2 तक डाइजेस्ट उत्पन्न करने में सक्षम है<sup>32</sup> बाइट लंबा। यह हैश फ़ंक्शन आंतरिक रूप से [[ब्लेक 2]] पर बनाया गया है। | |||
<span style="color:blue;">'''Function'''</span> Hash(message, digestSize) | |||
<span style="color:blue;">'''Inputs:'''</span> | |||
< | message: Bytes (0..2<sup>32</sup>-1) <span style="color:green;">Message to be hashed</span> | ||
< | digestSize: Integer (1..2<sup>32</sup>) <span style="color:green;">Desired number of bytes to be returned</span> | ||
<span style="color:blue;">Output:</span> | |||
digest: Bytes (digestSize)<sup> </sup> <span style="color:green;">The resulting generated bytes, digestSize bytes long</span> | |||
< | |||
<span style="color:green;">'''Hash''' is a variable-length hash function, built using Blake2b, capable of generating | |||
digests up to 2<sup>32</sup> bytes.</span> | |||
< | <span style="color:green;">If the requested digestSize is 64-bytes or lower, then we use Blake2b directly</span> | ||
'''if''' (digestSize <= 64) '''then''' | |||
'''return''' Blake2b(digestSize ∥ message, digestSize) <span style="color:green;">//concatenate 32-bit little endian digestSize with the message bytes</span> | |||
< | <span style="color:green;">For desired hashes over 64-bytes (e.g. 1024 bytes for Argon2 blocks), | ||
we use Blake2b to generate twice the number of needed 64-byte blocks, | |||
and then only use 32-bytes from each block</span> | |||
< | <span style="color:green;">Calculate the number of whole blocks (knowing we're only going to use 32-bytes from each)</span> | ||
r ← Ceil(digestSize/32)-2; | |||
< | <span style="color:green;">Generate r whole blocks.</span> | ||
<span style="color:green;">Initial block is generated from message</span> | |||
V<sub>1</sub> ← Blake2b(digestSize ∥ message, 64); | |||
<span style="color:green;">Subsequent blocks are generated from previous blocks</span> | |||
'''for''' i ← 2 '''to''' r '''do''' | |||
V<sub>i</sub> ← Blake2b(V<sub>i-1</sub>, 64) | |||
<span style="color:green;">Generate the final (possibly partial) block</span> | |||
partialBytesNeeded ← digestSize – 32*r; | |||
V<sub>r+1</sub> ← Blake2b(V<sub>r</sub>, partialBytesNeeded) | |||