Brute-force attack

[[Image:Board300.jpg|Image: 100 pixels|thumb|EFF - ийн US$250,000 - ийн үнэтэй  DES тайлагч машин, 1,800 - аад чип агуулсан, DES түлхүүрийг хэдхэн өдөрт brute-force - р тайлна.]]

**Brute-force** халдлага гэдэг нь криптографт ямарч шифрлэгдсэн мэдээллийг (мэдээлэл солилцох онолын дагуу хамгаалах төрлөөр шифрлэгдсэнээс бусад) таахад хэрэглэгддэг нууц бичээсийг тайлж унших халдалага юм. Энэ төрлийн халдлага нь шифрлэлтийн системд ямарч сул тал олдохгүй байх тохиолдолд ихэвчлэн хэрэглэгддэг. Энэ халдлагын гол санаа нь зөв нууц үгийг олтол боломжит бүх түлхүүр юмуу нууц үгийг системтэйгээр шалгах юм. Хамгийн муу тохиолдолд боломжит бүх нөхцөлийг туршиж үзэж болно. 

Нууц үг таах явцад богино хэмжээтэй нууц үгийн хувьд **brute-force** - г ашиглахад хугацаа их шаарддагүй, харин урт хэмжээтэй нууц үг таахад Dictionary attack гэх мэт илүү нарийн ажиллагаатай хугацаа бага шаардах халдлагыг ашигладаг. Орчин үеийн криптосистемд нууц үгийг таахад түлхүүрийн урт нь brute-force хийгдэх практик боломжийг тодорхойлдог. N битийн шифрлэгдсэн түлхүүрийн тайлагдах боломж хамгийн ихдээ 2*N* .

## Үндсэн зарчим 
Brute-force – ийн зарчим маш энгийн. Халдагч хохирогчийн нууц үгийн LastPass юмуу KeePass сангаас ширфлэгдсэн мэдээллийг авна. Тэд авсан мэдээлэлд өөрт хэрэгтэй байгаа мэдээлэл хадаглагдаж байгааг болон түүнийг тайлах ширфрлэлийн түлрхүүр агуулагдаж байгааг мэдэж байдаг. Ингээд шифрлэгдсэн мэдээллийг тайлахын тулд тэд боломжит бүх нууц түлхүүрээр тайлагдсан мэдээлэл гарч байгааг шалгаж үзнэ. Тэд энэ процессийг автоматжуулсан компютерийн програмаар хийдэг, ингэснээр тухайн халдлагыг хийж буй компютерийн хүчин чадал нэмэгдэхийн хэрээр секундэд хийгдэх тооцооллын хурд нэмэгдэж brute-force халдлагын явц хурдсана. 

## Веб сервер дахь Brute-force халдлага 
Сүлжээнд холбогдсон болон холбоогүй нөхцөл дэх brute-froce халдлагууд ялгаатай. Жишээ нь халдагч хохирогчийн Gmail бүртгэлруу brute-force халдлага хийхийг хүсвэл тэд боломжит бүх нууц үгийг туршиж үзнэ, гэвч Google энэ үйлдлийг даруй зогсооно. Бүртгэлтэй гишүүдийг нэвтрэх эрхээр хангадаг сервис тухайн нэвтрэхээр маш олон удаа оролдож байгаа IP хаягийг хориглож, нэвтрэх эрхийг нь хязгаарлана. Иймд веб сервисийн эсрэг хийгдэх brute-force халдлага тийм ч үр дүнтэй байдаггүй, учир нь халдлагыг зогсоолгох хүртэл хэдхэн оролдлого хийгдэх боломжтой. Хэдхэн амжилтгүй оролдлогын дараа Gmail таныг нууц үгийг автоматаар шалгаж байгаа компютер биш гэдгийг баталгаажуулах CATPCHA зурагаар шалгалт хийдэг. Хэрвээ ямар нэг аргаар оролдлогоо үргэлжлүүлвэл тэд нэвртэх оролдлогыг бүр мөсөн зогсооно.

Харин эсэргээр хэрэв халдагч хохирогчын компютерээс шифрлэгдсэн мэдээллийг хулгайлж, эсвэл веб серверийг ямар нэг аргаар буулган авч шифрлэгдсэн мэдээллийг татаж авбал халдагч өөрийн хүссэнээр хэдэнч нууц үгийг өөрийн төхөөрөмж дээрээ шалгаж үзэх боломжтой болно. Хэрэв тэд шифрлэгдсэн мэдээлэлд хандах боломжтой болвол, тэднийг богино хугацаанд их хэмжээний нууц үг шалгахыг ямар ч аргаар саатуулж чадахгүй. Хэдий хүчтэй шифрлэлт хэрэглэсэн ч, мэдээллийн аюулгүй байлгаж, хэн нэгэн тухайн мэдээлэлд хандаж чадахгүй байдлыг хангах нь тухайн мэдээлэл эзэмшигчийн хариуцлагаас давхар шалтгаална.

## Хаш 
Хүчирхэг хаш алгоритм нь brute-force халдлагыг удаашруулна. Гол төлөв хаш алгоритм нь нууц үгээс үүссэн утга диск дээр хадгалагдахаас өмнө нэмэлт матемарикийн үйлдэлийг нууц үг дээр хийдэг. Хэрэв илүү удаан хаш алгоритм хэрэглэгдсэн бол  хэдэн мянга дахин илүү математик үйлдэл хийгдэх хэрэгтэй болох ба ингэснээр brute-force халдага маш удаарширна. Гэсэн хэдий ч их үйлдэл хийгдэх шаардлагатай болох тусам тухайн систем эсвэл компютерийн ачаалал төдий чинээ ихсэнэ. Систем brute-force халдлагын эсрэг нөөцийн хэрэгллээг уян хатан тэнцвэртэй байлгах ёстой.

## Brute-force  халдлагын хурд 
Brute-force  халдлагын хурд бүхэлдээ техник хангамжын хүчин чадлаас хамаарна. Bitcoin олборлогчид Bitcoin олборлоход зориулан өөрсөддөө тусгайлан техник хангамж бүтээсэн байдаг шиг тагнуулын алба ч мөн brute-force хийх тусгай төхөөрөмжтэй. Харин энгийн хэрэглэгчидийн хувьд brute-force хийх хамгийн үр дүнтэй  төхөөрөмж бол график карт(GPU). График картын параллель боловруулалт  хийх чадамж нь brute-force – д маш олон нууц үгийг нэг дор шалгах боломж  олгодог. Халдлагын хурд өсч хэдхэн арван жилийн дотор бидний өнөөдрийн хэрэглэж буй алгоритмуудаас ч хүчирхэг алгоритмуудыг эвдэж чадах квантын компютер эсвэл үүн шиг өөр компютер бүтээгдэх магдалалтай.
 
2012 оны сүүлээр Ars Technica – ийн мэдээллснээр 25 ширхэг багц график карт ямар ч 8 ба түүнээс бага тэмдэгттэй Windows – ийн нууц үгийг 6 цагаас бага хугацаанд тайлна гэсэн байна. Microsoft – ийн ашигладаг NTLM алгоритм нь хангалттай тэсвэртэй байсангүй. Гэсэн хэдий ч энэ нь 
Microsoft - ийг ширфлэлтээ хүчирхэг болгох хүртэл аюултай байдал үүсгээгүй.

## Онолын хязгаар 
Brute-force халдлагад шаардагдах нөөц нь түлхүүрийн урт өсөх хэрээр шугаман бус, илтгэгч зэргээр өсдөг. Хэдийгээр Америк түүхэнд түлхүүрийн уртыг хязргаарлаж 56 битийн тэгш хэмт түлхүүр болгох зохицуулалт хийсэн ч тэр хязгаарлалт нь тийм ч удаан хэрэгжээгүй юм. Иймд одоогийн тэгш хэмт алгоритмууд ихэвчлэн тооцооллын хувьд хүчирхэг 128 - 256 битийн түлхүүрүүдийг ашигладаг. 

Brute-force халдлагын эсрэг 128 битийн тэгш хэмт түлхүүр нь тооцооллын хувьд аюулгүй гэх физик нотолгоо байдаг. Ландауэрийн хязгаар (Landauer limit) гэгддэг энэ нотолгоо нь тооцоолол дахь нэг битийн арчигдахад шаардагдах энергийн хамгийн бага хязгаар нь *kT · ln 2* гэсэн санааг агуулдаг. *T* нь тооцоолох төхөөрөмжийн температур(Кэлвин), *k* нь Болцманы тогтмол, *натурал логарифм 2* нь ойролцоогоор 0.693. Ямарч мөнхийн тооцоолох төхөөрөмж үүнээс бага энерги ашиглах боломжгүй. Иймээс 128 битийн тэгш хэмт түлхүүрт боломжит утгуудыг энгийнээр шалгаж үзэхийн тулд (жинхэнэ тооцоолох аргаар шалгахыг тооцохгүйгээр) онолын хувьд 2*128*-1 битийг энгийн процессорт шалгана. Хэрвээ тооцооллыг тасалгааны температурт (~300 К) болсон гэж үзвэл Вон Нэйман - Ландауэрийн хязгаарын тооцооллоор ~10*18* жоул буюу нэг жилд 30 гигават цахилгаан хэрэглэх энерги шаардагдана. Энэ нь 30 · 10*9* W · 365 · 24 · 3600 s = 9.46 · 10*17* J эсвэл 262.7 TWh (дэлхийн нийт энерги үйлдвэрлэлийн 1/100 - с их) - тэй тэнцэнэ. Жинхэнэ тооцоолох арга буюу зөв хариу байгаа эсэхийг мэдэхийн тулд түлхүүр бүрийг  шалгаж үзвэл үүнээс хэд дахин илүү энерги хэрэглэнэ. Түүнчлэн энд түлхүүрийн бүх боломжит утгыг шалгах циклд шаардагдах энергийг тооцсоноос бит тус бүрийг шалгахад зарцуулах бодит хугацааг тооцоогүй, энэ нь ямагт 0 - ээс их байдаг. 

[[Image:ATI Radeon HD 5770 Graphics Card-oblique view.jpg|Image: 100 pixels|thumb|left|Орчин үеийн GPU - нууд нь техник хангамжид суурилсан давталтад ажиллагаат нууц үгийн халдлага хийхэд тохиромжтой]]Гэсэн хэдий ч рэгистэрийн утгууд уламжлалт асуух болон арилгах үйлдлээр өөрчлөгдөж ингэснээр [энтропи](https://en.wikipedia.org/wiki/Entropy_(computing)) кодлол үүсгэдэг гэж дүгнэлтээр таамаглаж байгаа. Үүнээс үзэхэд тооцооллын техник хангамжууд энэ онолын саадтай толхиолдохгүй байхаар загварчлагдаж болох ч ингэж зохион бүтээгдсэн нэг ч компютер байхгүй. Засгийн газрын ASICs Solution  буюу өөрөөр “custom hardware attack” - с үйлдвэрлэгдэх боломжтойгоор уламжлагдан хөгжиж буй хоёр технологи  тодорхой шифрлэлтийн brute-force халдлага хийх боломжтой гэдгээ харуулж чадсан. Нэг нь одоогийн график боловсруулалтын цөм буюу GPU технологи, нөгөө нь “field-programmable gate array” (FPGA) технологи. GPU түүний өргөн хүрээг хамарсан байдал болон гүйцэтгэлийн өртөгийн ашигтай байдал нь давуу талтай, харин FPGA - ийн хувьд криптографийн үйлдэл бүр дээрх энэргийн үр ашигтай байдал нь давуу тал юм. Энэ хоёр технологи хоёул brute-force халдлагад паралел боловсруулалтын давуу талыг ашигладаг.  Зуу зуун цөмтэй GPU, мянга мянган цөмтэй FPGA - тэй байх нөхцөлд энэ нь  нууц үг тайлахад уламжлалт процесороос хэд дахин илүү тохирмжтой юм. Өнөөдрийн FPGA технологийн энергийн үр ашигтай байдлыг криптографын шинжилгээний олон тайлангууд дээр батлан харуулсан.  Жишээлбэл COPACOBANA алгоритм дээр FPGA кластер компютер нь ердийн PC - тэй ижил хэмжээний цахилгаан (600 W) зарцуулж байгаа ч 2500 PC - тэй ижил хэмжээтэй гүйцэтгэл үзүүлж байна. Олон фирмүүд техник хангамж суурьт FPGA криптографик шинжилгээний шийдэлд FPGA PCI Express картаас FPGA компютер хүртэлх төхөөрөмжүүдээр хангаж байна. WPA болон WPA2 нууцлалууд нь уламжлалт CPU болон FPGA - ийн харьцуулалтаар ажилын ачааллыг багасга brute-force халдлагаар амжилттай тайлагдсан.

AES нь 256 бит түлхүүр ашигаладаг. 256 битийн тэгш хэмт түлхүүрийг brute-force халдлагаар эвдэх нь  128 битийн түлхүүрийг тооцоолхоос 2*128* - р их тооцооллын эрчим хүч шаардана. Хэрвээ секүндэд 10*18* AES түлхүүрийг шалгах чадалтай 50 супер компютер (хэрвээ ийм төхөөрөмж байдаг бол) - тэй бол онолын хувьд 256 бит түлхүүрийн бүх утгыг шалгаж үзэхэд 3 · 10*51* жил зарцуулна. 

Brute-force халдлагын гол утга санаа нь ямар нэг алгоритм түүний оролцоогүй санаандгүй тоо үүсгэгчээр үүсгэгдсэн бүрэн төгс түлхүүрийн сантай байх юм.  Жишээлбэл brute-force халдлагаар эвдэгдэх ямарч боломжгүй гэж үзэж байсан системүүд нь хуурмаг санамсаргүй тоо үүсгэгчийн дутагдалтай талаас болж бодож байснаас хамаагүй бага түлхүүрийн сантайгаас шалтгаалж эвдэгдэх тохиолдол гардаг. Үүнд  Netscape - ийн SSL - боловсруулалт (1995 онд Ian Goldberg болон David Wagner - р эвдэгдсэн),  OpenSSL - ийн Debian/[Ubuntu](https://en.wikipedia.org/wiki/Ubuntu_(operating_system)) - т зориүлсан хувилбарын сул тал 2008 онд олдсон. Үүнтэй ижил сул тал дээр хийгдсэн энтропи нь Enigma - ийн код эвдэгдэхэд хүргэсэн.

## Тайлагдашгүй кодууд 
Математик шинж чанараасаа шалтгаалж зарим төрлийн нууцлалуудыг brute-force - р тайлагдах боломжгүй байдаг. Үүний нэг жишээ нь one-time pad криптограф. Ил бичвэрийн бит бүрийг туйлын санамсаргүй түлхүүрийн битийн дарааллуудаар ижилсүүлдэг. 140 тэмдэгттэй one-time pad - аар нууцлагдсан бичвэрийг brute-force - р тайлахад эцэст нь зөв хариултыг оролцуулсан боломжит 140 тэмдэгт мөр олдох болно, гэвч эдгээрээс аль нь яг зөв бэ гэдгийг мэдэх боломжгүй. Энэ төрлийн системийг эвдэх үйл явц Venona төсөлд хэрэгжиж байсан.

## Урвуу brute-force халдлага 
Урвуу brute-force халдлага гэдэг нь халдагч ихэвчлэн нэг нууц үгийг олон тооны нууцлагдсан файлд шалгаж үздэг. Энэ үйл явц хэд хэдэн нууц үгээр давтагдаж болно. Ийм аргаар халдагч яг тухайлсан хэрэглэгчийг байгаа болгодоггүй. Нийтлэг хэрэглэгддэг нууц үг ашигалхгүй байж урвуу brute-force халдлага тохиолдох эрсдэлийг бууруулж болно. 

## Сөрөг арга хэмжээ 
Өөрийн мэдээллийг brute-force халдлагаас бүрэн төгс хамгаалах ямарч арга байхгүй. Комптютерийн техник хангамжийн хөгжил ямар түвшинд хүрэх, мөн өнөөдрийн хэрэглэгдэж байгаа алгоритмуудын сул талууд ирээдүйд илэрч тайлагдах боломжтой болохыг хэн ч хэлэх боломжгүй. Онлайн бус горимд халдагч нууцлагдсан материал хаана байгаа газарт хандаж, хөндлөнгийн оролцоо эсвэл баригдах аюулгүйгээр чөлөөт цагаараа түлхүүрийн хослолуудаа шалгаж үзэж болдог. Гэвч онлайн халдлагын үед өгөдглийн сан болон удирдлагын администраторууд нууц үг турших оролдлогын тоог хязгаарлах, дараалласан хандалтын хооронд хүлээлгэ үүсгэх, шалгах асуултыг чангатгах (CAPTCHA хариулт шаардах, утасруу баталгаажуулах код явуулах гэх мэт), эсвэл олон удаагийн амжилтгүй нэвтрэх оролдлогын дараа бүртгэлийг түгжих гэх мэтээр халдлагын эсрэг арга хэмжээ авдаг. Вэбсайтын администраторууд сайт дахь ямарч бүртгэлд нэг IP - с тогтоосон тооноос олон удаагийн нэвтрэх оролдлого  ирсэн тохиолдолд хамгаалах арга хэмжээ авдаг.

## Brute-force attack хийдэг програм хангамжууд 
*Aircrack-ng
*[Cain and Abel](https://en.wikipedia.org/wiki/Cain_and_Abel_(software))
*[Crack](https://en.wikipedia.org/wiki/Crack_(password_software))
*[DaveGrohl](https://en.wikipedia.org/wiki/DaveGrohl_(software))
*Hash Code cracker
*Hashcat
*John the Ripper
*L0phtCrack
*Ophcrack
*RainbowCrack

## Мөн үзэх 
* 
* 
* 
* 
* 
* 
* 
*  and 
* 
* 

## Гадаад холбоос 
*Basic idea on How Password Bruteforce Tool is Created
*RSA-sponsored DES-III cracking contest
*How We Cracked the Code Book Ciphers – Essay by the winning team of the challenge in 
*Why not use larger cipher keys?

Ангилал:Алгоритм
Ангилал:Тоглоомын онол
Ангилал:Мэдээллийн технологийн аюулгүй байдал
Ангилал:Криптоанализ