Evoluce pomáhá při hledání chyb v šifrovacích programech

Ochrana dat je v digitálním světě jednou z největších priorit. Jednou z možností jak citlivé informace při komunikaci chránit jsou algoritmy, které data před odesláním zašifrují a pak znovu dešifrují. Šifrovací algoritmy přetaví data do série zdánlivě vypadající jako série náhodných čísel, neumí to ale dokonale. I dobré algoritmy mají nedostatky, které mohou využít třeba hackeři.

Kryptografických algoritmů se používají stovky. Jejich vytvoření je ale velmi náročné a od roku 2000 se konaly jen dvě skutečně celosvětové soutěže na výběr nového algoritmu – Advanced Encryption Standard (AES) a Secure Hash Algorithm (SHA-3).

I když vytvoření šifrovacího algoritmu zabere několik let, generování náhodných čísel (za pomoci počítače) potřebných pro aplikaci těchto algoritmů není bez chyb. A ty se zatím hledají ručně. „Za pomoci různých nástrojů nalézají analytici v navržených algoritmech nedostatky, které opraví. My jsme před několika lety začali pracovat na tom, jak jim tento proces ještě ulehčit,“ uvedl Vašek Matyáš z Fakulty informatiky MU.

Základní možnosti testování šifrovacích programů jsou dvojí. V prvním případě je možné kontrolovat rozdíly ve výstupech v závislosti na změnách na vstupu, přičemž musí platit pravidlo takzvaného lavinového efektu. To říká, že když na vstupu provedu jakoukoliv změnu, musí být pravděpodobnost změny výstupu u každého bitu, tedy jednotky informace (což je v binárním kódu 1 nebo 0), přesně poloviční. Druhou cestou je v podstatě statistická analýza výstupu, která by měla ukázat, že je v něm například přibližně stejný počet 1 a 0 a neopakují se v něm opakovat žádné vzory.

„Snažíme se najít způsob jak kontrolu dělat automatizovaně. Při nalezení takzvaného rozlišovače, tedy nedostatku, který ukazuje na chybu v kryptografické funkci, by ale naše řešení mělo zároveň nasměrovat analytiky do té části algoritmu, kde chyba vzniká,“ přiblížil cíl výzkumu Matyáš.

K takovému výsledku ale ještě informatiky čeká dlouhá cesta. „V oblasti testování algoritmů pro generování náhodných čísel jsme se zatím dostali na úroveň ostatních skupin ve světě, které tuto oblast zkoumají. Srovnáváme výstupy nepříliš povedených kryptografických programů s výstupy z kvantového generátoru náhodných čísel a hledáme rozlišovače,“ řekl Matyáš. Využívají k tomu Evropskou gridovou infrastrukturu, tedy síť vzájemně propojených počítačů s vysokým výkonem, protože takové úkoly jsou výpočetně nesmírně náročné.

Informatici upravují testování šifrovacích algoritmů i za pomoci genetického programování. „Používá se v situacích, kdy nejste schopni otestovat všechna možná řešení problému, protože je jich příliš mnoho. Vyberete tedy jen některá možná řešení problému, která aplikujete v tomto případě na danou kryptografickou funkci. Pokud má toto řešení při hledání rozlišovačů úspěch, povolíme v něm určité rozmezí mutací, tedy změny v algoritmech, a testujeme je znovu. Zkoušíme také úspěšnější řešení křížit a testujeme jejich potomky,“ popsal princip genetického programování Matyáš.

Podle něj se ukazuje, že v pro řešení některých problémů je to jedna z nejúčinnějších cest. I když genetické programování nedokáže vždycky najít optimální řešení, tak se mu hodně blíží a přitom je časově a výpočetně podstatně méně náročné. „S využitím těchto metod tak budeme moci nalézt nedostatky v nových šifrovacích algoritmech a navíc poukázat na pravděpodobné místo jejich vzniku podstatně rychleji a levněji,“ zdůraznil informatik.

Masarykova univerzita | Masaryk university