On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm

Cílem tohoto článku je ukázat jiný úhel pohledu na problémdešifrování symetrických šifrovacích algoritmů. Náš odlišný přístup, vesrovnání se stávajícími metodami, spočívá ve využití síly evolučních principů,které jsou v našem kryptoanalytickém systému implementovány pomocí genetickéhoprogramování (GP), za účelem provedení known plain-text útoku (KPA). Našímočekávaným výsledkem je nalezení takového programu (tj. funkce), který modelujechování symetrického šifrovacího algoritmu DES, který pro šifrování využívá náhodnýtajný klíč. Pokud by takový program mohl existovat, pak by pomocí něj bylomožné dešifrovat další zprávy, které byly zašifrovány stejným tajným klíčem. PoužitíGP představuje základ pro tuto práci. GP je evoluční algoritmus, jehož metodikyjsou inspirované biologickou evolucí, pomocí kterých je tento algoritmus schopnývytvářet počítačové programy, které řeší odpovídající problém. Metodasymbolická regrese (SR) je využita jako aplikace GP v praxi. Metoda SR v rámcievoluce GP skládá programy/funkce z množiny terminálních a neterminálníchbloků; a tyto programy/funkce aproximují množinu vstupních párů. Evoluce GP jeřízena fitness funkcí, která vyhodnocuje výsledky odpovídajícího problém. Jakofitness funkce je pro řešení našeho problému dešifrování zvolena Hammingovavzdálenost, která určuje rozdíly mezi aktuální hodnotou a hodnotou referenční. Funkčnostnašeho GP řešení je ověřena na sadě validačních testů, které jsou složené zpolynomů různých stupňů. Řídicí struktury IF a FOR jsou ověřeny výpočtem funkcefaktoriál. V experimentální fázi je stanovena sada předpokladů: odhadnejhoršího fitness hodnoty; nalezení nejvhodnějších parametrů GP; TransformaceKPA s vyloučením počáteční a koncové permutace; evoluce nejlepšího jedince; vlivpočtu šifrovacích kol; mohutnost tréninkového sady; a výsledky modelugeneralizace. Výsledky experimentů nepotvrdily většinu stanovených předpokladů.Počet kol šifrování neovlivnilo kvalitu nejlepšího jedince, ale jeho kvalitabyla ovlivněna mohutností trénovací množiny. Vyloučení počáteční a koncové permutacenemělo žádný vliv na kvalitu výsledků v evolučním procesu. Tyto výsledkyukazují, že naše řešení pomocí GP není schopno odhalit vnitřní strukturuchování algoritmu DES. Metoda symbolická regrese se ukázala jako úspěšná přiučení pouze v rámci konvergence nejlepšího řešení, kde odhalila až na 70%tajných informací (45 bitů), nicméně neúplné řešení nemusí představovat řešeníoptimální. Složitost algoritmu DES naráží na problém škálovatelnosti GP.Algoritmus DES bere jako vstup klíč o délce 56 bitů, čímž implikuje rozsáhlýstavový prostor funkcí, ve kterých je se současnými technickými možnostminalezení optimálního modelu vysoce nepravděpodobné.