Detail publikace
On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm
Homoliak Ivan, Ing., Ph.D. (UITS FIT VUT)
Hanáček Petr, doc. Dr. Ing. (UITS FIT VUT)
symbolická regrese, genetické programování, kryptoanalýza, DES
Cílem tohoto článku je ukázat jiný úhel pohledu na problém dešifrování symetrických šifrovacích algoritmů. Náš odlišný přístup, ve srovná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ého programování (GP), za účelem provedení known plain-text útoku (KPA). Naším očekávaným výsledkem je nalezení takového programu (tj. funkce), který modeluje chová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 bylo mož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ž metodiky jsou inspirované biologickou evolucí, pomocí kterých je tento algoritmus schopný vytvářet počítačové programy, které řeší odpovídající problém. Metoda symbolická regrese (SR) je využita jako aplikace GP v praxi. Metoda SR v rámci evoluce GP skládá programy/funkce z množiny terminálních a neterminálních bloků; 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. Jako fitness funkce je pro řešení našeho problému dešifrování zvolena Hammingova vzdálenost, která určuje rozdíly mezi aktuální hodnotou a hodnotou referenční. Funkčnost našeho GP řešení je ověřena na sadě validačních testů, které jsou složené z polynomů různých stupňů. Řídicí struktury IF a FOR jsou ověřeny výpočtem funkce faktoriál. V experimentální fázi je stanovena sada předpokladů: odhad nejhoršího fitness hodnoty; nalezení nejvhodnějších parametrů GP; Transformace KPA s vyloučením počáteční a koncové permutace; evoluce nejlepšího jedince; vliv počtu šifrovacích kol; mohutnost tréninkového sady; a výsledky modelu generalizace. Výsledky experimentů nepotvrdily většinu stanovených předpokladů. Počet kol šifrování neovlivnilo kvalitu nejlepšího jedince, ale jeho kvalita byla ovlivněna mohutností trénovací množiny. Vyloučení počáteční a koncové permutace nemělo žádný vliv na kvalitu výsledků v evolučním procesu. Tyto výsledky ukazují, že naše řešení pomocí GP není schopno odhalit vnitřní strukturu chování algoritmu DES. Metoda symbolická regrese se ukázala jako úspěšná při uč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žnostmi nalezení optimálního modelu vysoce nepravděpodobné.
@INPROCEEDINGS{FITPUB11144,
author = "Tom\'{a}\v{s} Smetka and Ivan Homoliak and Petr Han\'{a}\v{c}ek",
title = "On the Application of Symbolic Regression and Genetic Programming for Cryptanalysis of Symmetric Encryption Algorithm",
pages = "305--312",
booktitle = "Proceedings of 2016 IEEE International Carnahan Conference on Security Technology",
year = 2016,
location = "Orlando, Fl, US",
publisher = "Institute of Electrical and Electronics Engineers",
ISBN = "978-1-5090-1072-1",
doi = "10.1109/CCST.2016.7815720",
language = "english",
url = "https://www.fit.vut.cz/research/publication/11144"
}