Brute force

Юу вэ?

Brute Force буюу бүрэн хайлт нь шифрлэгдсэн мэдээллийг тайлах боломжит бүх түлхүүрийг нэг бүрчлэн туршиж, зөв түлхүүрийг олох арга юм.

Энэ арга нь алгоритмын сул тал эсвэл түлхүүрийн бүтцийг урьдчилан мэдэх шаардлагагүй. Харин амжилттай хэрэгжих эсэх нь түлхүүрийн орон зайн хэмжээ (Keyspace) болон нэгж хугацаанд хэдэн түлхүүр шалгах боломжтойгоос хамаарна.

Түлхүүрийн урт нэмэгдэх тусам шалгах боломжит хувилбарын тоо экспоненциал байдлаар өсдөг. Иймээс хангалттай урт, санамсаргүй үүсгэсэн түлхүүрийг бүрэн хайлтаар олох нь бодит нөхцөлд бараг боломжгүй болдог.

Хэрхэн ажилладаг вэ?

1. Түлхүүрийн боломжит хувилбаруудыг үүсгэх: Тухайн шифрийн түлхүүрийн урт, бүтцэд тохирсон бүх боломжит түлхүүрийг тодорхойлно.
2. Түлхүүрүүдийг турших: Боломжит түлхүүр бүрийг ашиглан шифр текстийг тайлах эсвэл баталгаажуулах үйлдэл хийнэ.
3. Үр дүнг шалгах: Гарсан үр дүнг зөв эсэхийг шалгах шалгуураар үнэлнэ. Жишээлбэл, уншигдахуйц текст, файлын толгой мэдээлэл эсвэл баталгаажуулалтын код ашиглаж болно.
4. Хайлтыг хурдасгах: Олон процессор, GPU болон тусгай зориулалтын төхөөрөмж ашиглан түлхүүрүүдийг зэрэг шалгаж болно.
5. Зөв түлхүүрийг тогтоох: Шалгуурт нийцсэн түлхүүр олдвол хайлтыг зогсооно.

Түлхүүрийн урт ба хугацаа

Brute Force халдлагын үр дүн нь түлхүүрийн уртаас шууд хамаардаг. Түлхүүрийн орон зайг (2^n) гэж үзвэл n битийн түлхүүр нийт (2^n) боломжит утгатай байна.

Жишээ нь:

• Цезарийн шифр: Ердөө 25 боломжит түлхүүртэй тул бүх хувилбарыг богино хугацаанд шалгах боломжтой.
• DES: 56 битийн түлхүүртэй бөгөөд 1998 онд EFF байгууллагын бүтээсэн Deep Crack төхөөрөмж DES түлхүүрийг ойролцоогоор 56 цагт олсон.
• AES-128: (2^{128}) буюу ойролцоогоор (3.4 \times 10^{38}) боломжит түлхүүртэй. Секундэд (10^{18}) түлхүүр шалгах онолын хүчин чадалтай байсан ч бүх хувилбарыг шалгахад ойролцоогоор (10^{13}) жил шаардагдана.

Эдгээр хугацаа нь онолын тооцоолол бөгөөд бодит гүйцэтгэл нь төхөөрөмж, алгоритм болон шалгах ажиллагаанаас хамаарна.

Квант компьютерийн нөлөө

Квант компьютер дээрх Гроверын алгоритм (Grover's Algorithm) нь бүрэн хайлтын шаардлагатай үйлдлийн тоог квадрат язгуурын хэмжээнд бууруулах онолын боломжтой.

Өөрөөр хэлбэл, n битийн симметрик түлхүүрийн хайлтын нарийн төвөгшил (2^n)-ээс ойролцоогоор (2^{n/2}) болно. Иймээс AES-128-ийн квант халдлагад үзүүлэх онолын хамгаалалтын түвшнийг 64 битийнхтэй дүйцүүлэн авч үздэг.

Үүнийг харгалзан AES-256 зэрэг урт түлхүүртэй алгоритмыг квант тооцооллын ирээдүйн эрсдэлийг бууруулахад илүү тохиромжтой сонголт гэж үздэг.

Хамгаалалт

• Урт түлхүүр ашиглах: Симметрик шифрлэлтийн хувьд AES-128 болон AES-256 зэрэг хангалттай урт түлхүүртэй алгоритм сонгох.
• Санамсаргүй түлхүүр үүсгэх: Таахад хялбар үг, дараалал ашиглахгүйгээр криптографийн найдвартай санамсаргүй тоо үүсгэгч (CSPRNG) ашиглах.
• Нууц үгийг хамгаалах: Argon2id, scrypt, bcrypt зэрэг тооцооллын хувьд зориудаар өндөр өртөгтэй нууц үг хэшлэх алгоритм ашиглах.
• Нэвтрэх оролдлогыг хязгаарлах: Давтан оролдлогын тоог хязгаарлах, түр хугацаагаар түгжих болон нэмэлт баталгаажуулалт ашиглах.

Анхаарах зүйл: Brute Force нь шифрийн алгоритмыг эвдэхээс илүүтэй түлхүүрийн боломжит хувилбаруудыг бүрэн шалгах аргад тулгуурладаг. Иймээс түлхүүрийн урт, санамсаргүй байдал болон зөв хамгаалалт нь уг халдлагаас сэргийлэх үндсэн нөхцөл болдог.