Дифференциал шинжилгээ

Юу вэ?

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

Ихэнхдээ XOR үйлдлээр тодорхойлсон оролтын ялгааг ашиглаж, тухайн ялгаа шифрийн раундуудаар дамжин гаралтын ямар ялгаа үүсгэхийг магадлалаар тооцдог.

Энэ арга нь халдагч өөрийн сонгосон нээлттэй текстүүдийг шифрлүүлэх боломжтой сонгосон нээлттэй текстийн халдлага (Chosen-Plaintext Attack)-ын нэг хэлбэрээр хэрэгждэг.

Дифференциал криптоанализыг Eli Biham, Adi Shamir нар 1990 онд олон нийтэд танилцуулсан. Гэхдээ IBM-ийн баг DES алгоритмыг боловсруулах явцдаа энэ төрлийн халдлагыг мэдэж байсан бөгөөд S-box-уудыг уг халдлагад тэсвэртэй байхаар сонгосон байсныг Don Coppersmith 1994 онд дэлгэрүүлэн тайлбарласан.

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

1. Оролтын ялгааг сонгох: Хоорондоо тодорхой XOR ялгаатай хоёр нээлттэй текст сонгоно. Жишээлбэл, ΔP = P ⊕ P′.
2. Шифрлэж үр дүнг цуглуулах: Сонгосон текстүүдийг ижил түлхүүрээр шифрлүүлж, гаралтын ялгааг ΔC = C ⊕ C′ хэлбэрээр тооцно.
3. Ялгааны тархалтыг шинжлэх: S-box бүрийн ялгааны тархалтын хүснэгт (Difference Distribution Table — DDT)-ийг ашиглан тодорхой оролтын ялгаа гаралтын ямар ялгаа үүсгэх магадлалтайг тооцно.
4. Ялгааны замыг тодорхойлох: Шифрийн олон раунд дамжихдаа өндөр магадлалтай хадгалагдах ялгааны дарааллыг буюу Differential Characteristic-ийг тодорхойлно.
5. Түлхүүрийн хэсгийг таамаглах: Сүүлийн раундын түлхүүрийн боломжит хэсгүүдийг шалгаж, ажиглагдсан гаралтын ялгаа тооцоолсон загвартай хэр нийцэж байгааг статистикаар үнэлнэ.

Жишээ

DES алгоритм нь дифференциал криптоанализын түүхэн чухал жишээ юм.

Biham, Shamir нар DES-ийн 16 раундтай хувилбарт чиглэсэн дифференциал криптоанализын аргыг боловсруулж, ойролцоогоор (2^{47}) сонгосон нээлттэй текст ашиглан түлхүүрийг олох боломжтойг харуулсан.

Энэ нь DES-ийн 56 битийн түлхүүрийг бүрэн хайх Brute Force аргаас онолын хувьд илүү үр ашигтай байж болохыг харуулсан. Гэхдээ ийм халдлагыг хэрэгжүүлэхэд маш олон сонгосон текст болон статистик боловсруулалт шаардлагатай.

Хамгаалалт

• S-box-ийн найдвартай байдал: Ялгааны жигд байдал (Differential Uniformity) багатай, оролтын ялгаанаас гаралтын тодорхой ялгаа үүсэх магадлал бага S-box ашиглах.
• Раундын тоог хангалттай байлгах: Ялгааны замаар дамжих магадлалыг олон раундын турш бууруулах.
• Шифрийн бүтцийг зөв сонгох: Дифференциал криптоанализ болон бусад статистик халдлагад тэсвэртэй алгоритмын загвар ашиглах.

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

Анхаарах зүйл: Дифференциал криптоанализ нь бүх шифрт ижил үр дүнтэй биш. Шифрийн бүтэц, раундын тоо, S-box-ийн шинж чанар болон халдагчийн сонгосон текстэд хандах боломж зэргээс хамааран үр дүн нь өөр өөр байдаг.