Шугаман шинжилгээ

Юу вэ?

Шугаман криптоанализ нь блок шифрийн оролт, гаралт болон түлхүүрийн битүүдийн хооронд 50%-иас ялгаатай магадлалаар биелдэг шугаман (XOR) хамаарлыг ашиглан түлхүүрийн битүүдийг статистикаар таамаглах арга юм.

Энэ аргын гол санаа нь шифрлэлтийн дотоод үйлдлүүдийг бүхэлд нь тайлахгүйгээр тэдгээрийг XOR үйлдлээр илэрхийлсэн шугаман тэгшитгэлээр ойролцоо загварчлахад оршино.

Халдагчид нээлттэй текст болон түүнд харгалзах шифр текстийн хосууд шаардлагатай байдаг тул мэдэгдэж буй нээлттэй текстийн халдлага (Known-Plaintext Attack) гэж ангилдаг.

Японы криптографч Mitsuru Matsui 1993 онд DES шифрийн эсрэг шугаман криптоанализын аргыг танилцуулсан.

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

1. Шугаман хамаарал олох: S-box бүрийн шугаман ойролцооллын хүснэгтийг (Linear Approximation Table — LAT) байгуулж, оролт болон гаралтын битүүдийн хооронд статистикийн хувьд хамгийн их хазайлттай хамаарлуудыг сонгоно.
2. Тэгшитгэл байгуулах: Сонгосон хамаарлуудыг хэд хэдэн раунд дамжуулан холбож, нээлттэй текст, шифр текст болон түлхүүрийн битүүдийг агуулсан XOR тэгшитгэл үүсгэнэ. Жишээлбэл:P[i] ⊕ C[j] ⊕ K[k] = 0Энд P[i], C[j], K[k] нь тус тус нээлттэй текст, шифр текст болон түлхүүрийн тодорхой битүүдийг илэрхийлнэ.
3. Статистик шинжилгээ хийх: Олон нээлттэй текст, шифр текстийн хос дээр тэгшитгэл хэдэн удаа биелж байгааг тоолно. Хэрэв тэгшитгэл 50%-иас мэдэгдэхүйц их эсвэл бага давтамжтай биелж байвал шифрийн дотоод бүтэцтэй холбоотой мэдээлэл агуулж байна гэж үзнэ.
4. Түлхүүрийн битийг таамаглах: Хазайлтын чиглэл болон давтамжид үндэслэн түлхүүрийн битүүдийн боломжит утгыг таамаглана. Дараа нь таамагласан түлхүүрийг бусад текстээр шалгаж баталгаажуулна.

Энд ε (epsilon) нь тэгшитгэлийн биелэх магадлал 50%-иас хэр зөрж байгааг илэрхийлэх хазайлт (bias) юм. Олон раунд дамжсан хазайлтыг тооцоолоход Piling-up lemma ашигладаг. Шаардлагатай текстийн хосын тоо нь хазайлтын хэмжээнээс хамаарах бөгөөд ойролцоогоор 1/ε²-той пропорционал байна.

Жишээ

Mitsuru Matsui 1994 онд DES шифрийн эсрэг шугаман криптоанализын бодит туршилтын үр дүнг нийтэлсэн. Түүний арга ойролцоогоор 2⁴³ мэдэгдэж буй нээлттэй текст, шифр текстийн хос ашиглан DES-ийн түлхүүрийн мэдээллийг сэргээх боломжтойг харуулсан.

Энэ нь DES-ийн түлхүүрийг бүх боломжит хувилбараар шалгах brute force аргаас онолын хувьд бага тооцоолол шаардах халдлага байсан боловч асар олон текстийн хос шаарддаг.

Хамгаалалт

• Шугаман бус чанар өндөртэй S-box ашиглах: Оролт, гаралтын битүүдийн хоорондын шугаман хамаарлын хазайлтыг багасгана.
• Раундын тоог хангалттай байлгах: Олон раунд дамжих тусам шугаман ойролцооллын хазайлтыг бага байлгах шаардлага нэмэгдэнэ.
• Шифрийн бүтцийг зөв төлөвлөх: Раунд хоорондын шугаман хамаарлыг хуримтлуулахад хүндрэлтэй бүтэц ашиглах хэрэгтэй.

AES нь Wide Trail стратегийг ашиглан шугаман болон дифференциал криптоанализын эсрэг тэсвэртэй байхаар зохион бүтээгдсэн. Тухайлбал, дөрвөн дараалсан раундын хүрээнд дор хаяж 25 идэвхтэй S-box үүсэх бүтцийн шинж чанар нь шугаман ойролцооллын хазайлтыг багасгахад тусалдаг.