Hash Function

Hash function гэж юу вэ?

cryptographic hash function гэдэг нь өөртөө оролтын утга (эсвэл ‘message’) аваад тогтмол хэмжээтэй тоо болон үсэгний хослол (fixed-size alphanumeric string) болох string буцаадаг функц юм. Буцааж буй string-г ‘hash value’, ‘message digest’, ‘digital fingerprint’, ‘digest’, ‘checksum’ гэж олон янзаар нэрлэдэг.

Hash Function-г password verification, data structure (DS)-д зэргээр олон янзаар хэрэглэж болдог. Жишээ нь password verification хийе гэж бодоход дээрх зурагт “abc123” гэдэг password-г Hash Function SHA-1 (Secure Hash Algorithm 1)-д оролт болгон өгөөд хариуд нь “6367c48dd193d56ea7b0baad25b19455e529f5ee” гэсэн string буюу hash value-г авсан байна. Дараа нь хүний оруулсан password-г SHA-1 аргаараа hash value-г нь аваад жинхэнэ password-ийнх нь hash value-тай тулгаж зөв эсэхийг шалгаж болно.

Энд байгаа SHA-1 гэдэг нь hash function-ийн нэг төрөл юм. Өөр олон төрлүүд байж болно.

Hashing суурь ойлголтууд

• Hash functions зөвхөн нэг чиглэлтэй байна: Бид hash value-г ашиглаад буцааж эх text-г гаргаж авах боломжгүй гэсэн үг
• Нэг hash function руу ижил оролт (text) оруулахад ижил гаралт (hash value) буцааж авдаг

Salted Hashing

Дээрх password hash жишээнээс хоёр өөр хүн ижил password-тай үед hash value нь мөн ижил байгааг анзаарсан байх. Бидний зорилго бол password-ний hash value-г өөр байлгах ёстой.

Тиймээс дээрх зурагт харуулсанаар plain text (password) дээр salt (давс) нэмж (random string) Hash Function руугаа оролт болгоод оруулах юм бол өөр өөр hash value-тай болно

Salt hashing ашиглах нь мөн brute force аргаар hash value-г ашиглаад plain text (or password) гаргаж авахад хэцүү болгодог. Ядаж л урт salt ашиглавал computational resource маш ихийг шаардана.

Brute force-р hash value-наас эх оролтыг (plain text) гаргаж авна гэдэг нь жишээлбэл бүх боломжит text-үүдийг (тодорхой урттай ч юм уу) гаргаж аваад ямар hash function ашигласныг нь мэдэж байвал (SHA-1 ч юм уу, гэхдээ энэ нь дотроо salt нтр байгаа байх л даа) тухайн auto-generated plain text-үүдээ hash function руугаа оруулаад гаралтыг нь хадгалж аваад нэг том сан үүсгэнэ гэсэн үг юм. Тэгээд түүнээсээ тодорхой plain text (жишээлбэл дээр дурьдсанаар “abc123” ч юм уу) hash value нь тогтмол (дээр дурьдсанаар бол “6367c48dd193d56ea7b0baad25b19455e529f5ee”) байдаг гэдгийг мэдэж байгаа болохоор буцаагаад plain text гаргаж авч болно гэсэн үг.

Hash Collision

Хоёр өөр оролт (plain text) оруулахад ижил утга гаргаж байвал үүнийг hash collision гэдэг.

Collision буюу давхцал үүсч байгаа үндсэн шалтгаан нь компьютерийн санах ойн болон тооцоолол хийх resource хоёрын хязгаартай (limit) байдал мөн hash function-ий өөрийнх нь сул, муу байдал юм.

Эндээс доош нь уншихгүй байсан ч болно

Жишээ нь би өөрөө нэг hash function тодорхойлоод бичсэн гэж үзье (ERKA-2 гэдэг нэртэй ч юм уу) энэ нь орж ирсэн plain text-ийн ASCII code-уудийн нийлбэрийг hash value гээд буцаадаг гэж үзье.

Оролт нь “abc” бол гаралт нь (97 + 98 +99)= 294 байна. Гэвч “cab” гэж оруулсан ч 294 хэвээр гарна. Энэ давхцлыг арилгахын тулд “ERKA-2”-г сайжруулъя. “abc” => (97 + 98 * 26¹ + 99 * 26²)=69569 болно. Энд яагаад заавал 26 гэдэг талаар жоохон бодоод үзээрэй (англи хэлний цагаан толгой 26 үсэгтэй байдаг ч билүү нээрээ). Одоо collision үүсээд байсан “cab” => (99 + 97 * 26¹ + 98 * 26²)=68869 ингээд collision маань үүссэнгүй.

Тэгвэл яг энэ аргаар зөвхөн “abc”, “cab” биш нилээн урт text (1000 урттай ч юм уу) оролтоор орж ирвэл манай hash value тоймгүй их тоо болно (26⁹⁹⁹ хэхэ). Ганц hash value-г гаргахын тулд энэ тоймгүй их тоог RAM дээр хадгалах нь оновчтой биш учраас томхон анхны тоогоор (prime number) модуль авч үлдэгдлийг нь хадгалцгаая гэсэн юм шиг байгаан.

Тэр том анхны тоог нь 10⁹+7 байсан гэж үзье. Тэгвэл бид хамгийн ихдээ л 10⁹+7 ширхэг unique hash value хадгалж чадах нь ойлгомжтой. Илүү гарсан нь давхцах нь ойлгомжтой гэсэн үг. Тэгсэн ч modular arithmetic-т 1 гэдэг тоо болон 10⁹ + 8 хоёрыг ижил тоо гэж үздэг тэ. Энэ л манай collision-ий үндсэн шалтгаан болоод байгаа юм. Үүнээс сэргийлэх аргууд байдаг. Миний санаж байгаагаар хэрвээ яг ижил hash value үүсэх юм бол тухайн hash value дээр 1-г нэмээд (ERKA-2-ийн хувьд) ч юм уу хоосон үүрэн дээр тухайн plain text-ийн hash value-г хадгалж болно. Үүндээ мэдээж (password verification ч юм уу match хийхийн тулд) зохицуулалтууд хийж өгнө.

does it make sense?, please clap