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

Юу вэ?

Шугаман криптоанализ нь нээлттэй текст, шифр текст, түлхүүрийн битүүдийн хооронд ½-оос ялгаатай магадлалтай биелэх шугаман (XOR) хамаарлыг олж, түлхүүрийн битүүдийг статистикаар сэргээдэг. Халдагч зөвхөн нээлттэй ба шифр текстийн хосуудыг мэдэхэд хангалттай тул мэдэгдэж буй нээлттэй текстийн (known-plaintext) халдлага юм.

Mitsuru Matsui 1993 онд DES-ийн эсрэг анх танилцуулсан.

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

1. S-box бүрийн шугаман ойролцооллын хүснэгтийг (LAT) гаргаж, хамгийн их хазайлттай тэгшитгэлүүдийг сонгоно.
2. Раундуудыг холбож P[i] ⊕ C[j] ⊕ K[k] = 0 хэлбэрийн, ½ + ε магадлалтай биелэх тэгшитгэл үүсгэнэ. Энд ε нь хазайлт (bias) бөгөөд раундуудын хазайлтыг piling-up lemma-гаар нийлүүлнэ.
3. Олон хос текст дээр тэгшитгэл хэдэн удаа биелэхийг тоолно.
4. Хазайлтын чиглэлээс түлхүүрийн битийн утгыг тогтооно. Шаардлагатай хосын тоо ойролцоогоор 1/ε² байдаг.

Жишээ

Matsui 1994 онд DES-ийг 2⁴³ мэдэгдэж буй хосоор бодит туршилтаар эвдэж, энэ нь DES-ийн эсрэг олон нийтэд туршигдсан анхны brute force-оос хурдан халдлага болсон.

Хамгаалалт

• Шугаман бус чанар (nonlinearity) өндөртэй S-box ашиглах.
• Хангалттай олон раунд хийх.
• AES-ийн wide trail стратеги шугаман характеристикийн хазайлтыг ч мөн адил маш бага болгодог.